Project Proposal: broil ( a lisp in bril)

[mercure67]

What will you do?

We'll implement a lisp targeting Bril, and try to run some programs with it.

How will you do it?
We found some links. First, https://bernsteinbear.com/assets/img/kelsey-ssa-cps.pdf, which suggests an algorithm for converting from continuation passing style (a simplification of functional languages) to SSA. There's also surely an algorithm for converting from Lisp / functional to CPS. Then, we can use our existing infrastructure for manipulating the resulting SSA. We'll probably use an off-the-shelf parser, like Pest, for simplicity.

Otherwise, we might scope our Lisp out / get implementation details based on https://www.buildyourownlisp.com/contents (a project to implement a lisp in C), as presumably one of these toy starter-project type implementations is reasonably narrow in scope to start with. The book also suggests some extensions, which is convenient!

How will you empirically measure success?
We'll see if a select few Lisp programs work as a start, and then perhaps find some more complicated examples from the internet or elsewhere to continue. Something else that could be interesting is comparing / re-implementing some of the benchmarks in our Lisp and comparing the generated code against the imperative version.

Team members:
@pedropontesgarcia

[sampsyo]

Sounds fun! You'll certainly learn about some of the compiler techniques that are endemic in functional languages that we don't really cover in 6120.

I will need a little more detail here before I can fully approve your project. Namely:

• Exactly which dialect of Lisp? Surely you will need to target a subset of the language—what subset? (Which constructs will you support, and which will you not?)
• Relatedly, what about types? Many Lisps are untyped; Bril is typed. Will you start with a typed Lisp, or will you use the dynamic type extension? (I can't think of any other practical option.)
• Also relatedly, what will you use for the "reference implementation" to compare against? I would really like you to do differential testing with some other, non-Bril implementation.
• Can you also measure performance, especially if you have a reference implementation?
• Where exactly will you get those test programs? Basically, I am asking you to do this work now, at the proposal phase, instead of during the project: "find some more complicated examples from the internet or elsewhere to continue." This hopefully easy (just a matter of googling around) and will significantly de-risk the project because you will know what it will take to test your implementation.

I also think it would be great if you could do a little homework at this phase to nail down the pipeline of compiler passes you'll implement. I think you're saying something like this:

1. new lexer/parser, using Pest
2. ordinary Lisp to CPS-form Lisp
3. CPS-form Lisp to a new SSA IR you design?
4. that SSA IR to SSA-form Bril

Is that right? I think it would be a real good idea to flesh out the "???" step in here (i.e., step 2) a bit farther before you get started. If this were the lambda-calculus, this would "just" be the standard CPS transform, but two things seem more complicated this project: (1) supporting any "advanced" constructs (see my above request for a specific list of which language features you will support), and (2) closure conversion. The latter is required because I assume you will want to support first-class functions (?), and Bril only has first-order functions.

To nail that down, maybe you want to read a little bit about compiling with continuations?

[pedropontesgarcia]

Thank you for the feedback! We have some answers and some related follow-up questions. Right now, our current line of thinking is to design and implement a small Lisp or ML-inspired functional programming language with explicit static types and no type inference. We are considering evaluating the correctness and performance of our implementation by curating a benchmarking suite of very common algorithms, perhaps inspired by the Bril benchmarks, and comparing their performance to the same algorithms implemented directly in Bril (to measure the overhead of our compilation pipeline) and potentially in a known compiled functional programming language. Here are the features we would like to support:

• Types: int, char, bool, pair, unit
• Structures: scoped bindings, function definitions and application, recursion, conditionals
• Operators: standard arithmetic for ints and logic for bools, comparison for ints, bools and unit, p.left and p.right access for pairs
• Standard functions: print char
• Other potential extensions: closures, sum types, type inference, syntactic sugar

Our proposed compile pipeline:

1. New lexer / parser using pest
2. Source-to-source CPS transformation
3. (optional) Spply source-to-source syntactic sugar / etc.
4. CPS to Bril SSA
5. Bril compilation / optimisation passes with our existing infrastructure

Our questions are:

• Does this seem reasonable?
• If we were picking between SML syntax or Scheme syntax, which one might be more desirable/get less "in the way"? (Helen will expand on this)

[mercure67]

expanding on above --- if you really want us to implement something with a reference implementation, do you think it'd be easier to try to implement standard ml or scheme? Pedro brought up implementing something ML-like as being potentially easier due to its strong typing, pointing to a prior ML-subset interpreter project in CS3110 as an additional choice for what langugae to support.

also, which is easier to 'remove parts of' and still have a decently robust language? like, we'd probably not support macros in scheme; but how 'big of a deal' is that? can we remove more of lisp versus sml?

[sampsyo]

A reference implementation seems pretty important for testing this kind of compiler… but I guess, if you really want to invent a new language from scratch, you could write that reference implementation yourself? That is, write an interpreter for your Lisp and do differential testing between that interpreter and the compiler Bril code.

Anyway, about your actual question:

do you think it'd be easier to try to implement standard ml or scheme?

That's a good question, and I admit I don't exactly know! If you like Scheme but want static types, Typed Racket could be an interesting starting point too. But yeah, Standard ML doesn't have a terribly complicated grammar so hopefully wouldn't be that hard to parse (famous last words) and would be a natural fit for a typed language with higher-order functions.

like, we'd probably not support macros in scheme; but how 'big of a deal' is that? can we remove more of lisp versus sml?

Right, good point, supporting macros would be a huge drag. One exotic option would be to hook into an existing Scheme system and grab the program after macro expansion and compile that. That seems a little bit wild but could be fun if you're into it!

If I think about what you'd want to do in SML, you'd probably want to skip support for ADTs and pattern matching (they just seem somewhat beside the point) and parametric polymorphism (ditto) and just focus on a few primitive types and first-class functions. You could also avoid implementing type inference, if you like, and require everything to come with type annotations. That would make for a pretty minimal but compile-able SML, and then you could put a few of those extensions into stretch goals?

[sampsyo]

Oops; I for got to answer this question:

Does this seem reasonable?

Yes! Thanks for detailing the plan; this sound excellent.

[mercure67]

okay, thanks! it seems like we're tending towards the SML side.

have we 'passed' this assignment?

[sampsyo]

Yes, you're all set!