3 — Abstract Syntax, Compilation

Due Tuesday, 28 January, 6am

One purpose of this assignment is to understand three basic ideas of compilation: static distance calculation, its use in interpretation, and memory allocation during program execution.

Another purpose is to drive home the idea of abstract syntax and separation of information parsing from data processing.

Delivery Deliver your solutions in a folder called 3 in your github repo with the following organization:

Programming Task 1 Modify your interpreter from 2 — Static Distance, Simple Interpretation so that it determines the value of VExprs transformed into static-distance form. The interpreter must pre-allocate all necessary memory before the interpretation proper starts. If you chose a language that prohibits mutation, use the state monad instead find an alternative solution. The interpreter uses this pre-allocated memory imperatively to represent the current environment for each sub-expression in an imperative manner.

You will need to modify your JSON parser to accept VExpr programs that may contain JSON arrays of the form [Natural, Natural] in places where Vars occur. The two numbers are interpreted as in 2 — Static Distance, Simple Interpretation; recall that the count starts at 0.

Natural is a natural number.

Programming Task 2 Design ast, which is a parser that maps S-expression syntax for our language of variable expressions to the intermediate representation you developed for 2 — Static Distance, Simple Interpretation.

The Rosetta Code repository has readers for S-expressions for a large variety of programming languages. If you have chosen a language that is not listed and if you can’t find an S-expression reader for it, see me.

Testing Task Write the test harnesses xast and xinterpreter for your ast and interpreter programs, respectively.

Create three two tests for xast and xinterpreter each. Place them in ASTTests/ and ITests/, respectively. A test consists of two files: N-in.json and N-out.json for N in {1, 2}. An input file in ASTests/ contains a single SVExpr; an input file in ITests contains a single VExpr as extended in the programming task above. An output file for xast is the corresponding VExpr, meaning you may reuse the unparse program from 2 — Static Distance, Simple Interpretation.

Recall JSON: Simplicity and Complexity.