This lab is designed to help you go deeper into program transformations, and how we can analyze the AST of a program and perform different transformations on it, either for performance or for end-user ease-of-use.
For this lab, you should again have Julia 1.0 installed, the same as for the rudimentary interpreter. You will need both the Lexer and Error modules, and you will need your code from the Extended Interpreter.
For this lab, you will expand the interpreter that you have already built, and add in a new “analysis” function that performs three different flavors of syntactic de-sugaring.
The primary deliverable for this lab is a new Julia module. Your module should export parse
, calc
and analyze
functions, and two return types, NumVal
and ClosureVal
.
Your module should be able to do everything that your simple interpreter could do and everything that your extended interpreter can do. However, you will use program analysis to both eliminate With
nodes, and to add two new simple features.
The CI4.jl
module is available in the Content section in Learning Suite.
Please name your module TransInt.
For this lab, you will implement an analyze
function similar to what we covered in class. The analyze
function accepts as input an AST, rewrites it, and returns a new AST.
There are three rewrites you must implement:
with
nodes to be multi-argument lambda
nodes.+
operation that is implemented with only binary +
operations.and
operation that is implemented with only if0
operations.Each is discussed in more detail in the following sections.
Note that we do not expect you to nor want you to implement short-circuiting of if0 nodes or pre-calculation of arithmetic expressions. Only do the syntactic de-sugaring as described here.
The grammar for our new language is the following:
<AE> ::= number | (+ <AE> <AE> <AE>*) # at least two parameters, possibly infinity. note extra star! | (- <AE> <AE>) | (* <AE> <AE>) | (/ <AE> <AE>) | (mod <AE> <AE>) | (collatz <AE>) | (- <AE>) | id | (if0 <AE> <AE> <AE>) | (with ( (id <AE>)* ) <AE>) | (lambda (id*) <AE>) | (and <AE> <AE> <AE>*) # new operation 'and' | (<AE> <AE>*)
Here we discuss the three new features you must support in our language.
Part 1: Multi-site with
→ multi-site lambda
In class we showed how to implement with
expressions using lambda
expressions, but only for with
and lambda
expressions that involve one parameter. For the first part of the lab, you must rewrite the AST of a program to eliminate all with
nodes, even with multiple parameters, and replace them with equivalent function creation / function calls.
Remember from class that
(with (x 5) (+ x 1))
becomes
((lambda x (+ x 1)) 5)
Your code should make a similar transformation for multiple-identifier with
expressions to applying multiple-parameter lambda
expressions. For example,
(with ((x 5) (y 6)) (+ x y))
becomes
((lambda (x y) (+ x y)) 5 6)
No changes to the grammar are necessary to support this change, and therefore, no changes to your parser from the Extended Interpreter are necessary to implement this under-the-hood syntactic rewrite. The transformation should happen in the analyze
function.
Part 2: Addition operation with arbitrary number of parameters
For the second feature, you must implement a more flexible +
operator.
Specifically, instead of only two operands, the new +
operator should support an arbitrary number of operands, as long as there are more than two.
However, this will be syntactic sugar – you should implement this using your existing binary operations.
So, we would essentially rewrite this:
(+ a b c d)
into this:
(+ a (+ b (+ c d)))
Note that this involves a change to the grammar, and therefore you will need to change your parser! You may need to change the definition of the plus node – it can no longer by implemented as a BinOp. The analyze
function should eventually convert it to a sequence of BinOp operations only, and your calc
function should handle this without change.
Part 3: A simple and
operator
For the final part of this lab you will implement a simple short-circuited and
operation in terms of if0
calls. The semantics of the and
node is that it should return 1 iff all subexpressions evaluate to nonzero, and return 0 otherwise. Or in other words, it should return 0 if any subexpression evaluates to zero.
As an example, we will transform this:
(and (+ 4 0) (- 3 3) (* 4 3))
into this:
(if0 (+ 4 0) 0 (if0 (- 3 3) 0 (if0 (* 4 3) 0 1)))
Note that this is a new construct in our grammar, so you will need to create a new AST node type (call it And
) and parse it appropriately. However, because it is being implemented in terms of if0
calls, you will not need to modify your calc
function to support it. The transformation from the And
node to the if0
nodes should happen in the analyze
function.