4 A4: Term Rewrites and Unifying Program State
Due: April 21, 2025
You’ve just joined NebulaSoft, a quirky mid-size company with a custom programming language that was once the darling of internal tools. Two years ago, the language’s sole creator and self-proclaimed “rockstar engineer” left in a blaze of startup glory, taking with them all knowledge of the language’s internals, documentation, and most of the unit tests.
Since then, the language has been running on life support. People still use it—begrudgingly—for legacy systems. Over time, users have filed more and more feature requests, but no one has dared touch the interpreter codebase... until now.
Users desperately want the expressive power of conditional branching using cond. The language only supports single-argument functions (because the rockstar thought multi-arg was “bloated”), so you will have to implement a rewriter that transforms multi-arg functions into a chain of single-arg functions. You knowledge from Programs as Data Structures will be useful here.
Under the hood, the interpreter uses a two-pronged model: a local environment for variable bindings and a global store for mutable values. Right now, it’s the programmer’s responsibility to remember when something needs to be allocated in the store versus when it can live in the environment. It’s confusing, error-prone, and unergonomic. You’re going to fix that too.
You’ll modify the interpreter so that all bindings—whether local or global—are handled uniformly via automatic store allocation. The environment will map names to addresses, and the store will map addresses to values. No more manual juggling of scopes and storage! Your knowledge from Environments and Program State will be relevant here.
4.1 Rewrite cond to a sequence of if
In A2: Primitives and Conditionals, you added cond which enabled you to write a sequence of conditionals and evaluate them sequentially. To do it, you added a case for cond and added relevant semantics to the interpreter. The goal of this task is to rewrite cond statement to nested if expressions so that it can run in the original interpreter. For example:
can be written as
More generally,
(cond [e-p1 e-a1] [e-p2 e-a2] [e-p3 e-a3] ... [else e-an])
can be written as
(if e-p1 e-a1 (if e-p2 e-a2 (if e-p3 e-a3 ... e-an)))
The benefit of rewriting expressive syntax to a simpler term automatically enables us to keep our interpreter simple, reducing the chances of bugs. To do this you must:
Write a function cond->if in rewriter.rkt. It takes an expression as an input and produces the rewritten expression with cond replaced by if.
Add tests in rewriter.rkt to check if you handle rewrites correctly in all kinds of expressions.
4.2 Currify Functions
In functional programming, currying is a technique of translating a function that takes multiple arguments (added in A3: Let Bindings and Functions) into a series of functions that each take a single argument. This transformation enables more flexible function composition and partial application. Haskell is a language that supports partial application. For example, if we have a function adder that adds 2 numbers:
A currified version of the same code will look like:
A big advantage of a language that allows currying is to enable partial application:
The function adder2 is built using adder, but takes one argument and always adds 2 to it. One can create such partially applied functions and can apply it on rest of the arguments later in the program. The goal of this task is to rewrite lambdas and their applications to the currified version. For example:
will be transformed to:
In general,
is converted to:
Similarly, function applications are also transformed as:
(e-1 e-2 e-3 ... e-n)
to
(((e-1 e-2) e-3) ... e-n)
Doing such a rewrite will allow our language to support partial application without making any changes to the interpreter.
Write a function currify in rewriter.rkt. It takes an expression as an input and produces the rewritten currified expression.
Add tests in rewriter.rkt to check if you handle rewrites correctly in all kinds of expressions.
4.3 Unifying Program State
As a programmer in our language, one needs to make a decision of when a local binding is appropriate vs. when storing something in the state is appropriate. This is similar to thinking of putting values on the stack or heap. We would like to simplify this and store everything in the program state. With this change new and deref will go away from our language.
So programs like:
(let ((x (new 5))) (seq (set x (add1 (deref x))) (+ 3 (deref x))))
can be written as:
(let ((x 5)) (seq (set x (add1 x)) (+ 3 x)))
Or the factorial function can be written as:
(let ((fact #f)) (seq (set fact (λ (n) (if (zero? n) 1 (* n (fact (- n 1)))))) (fact 5)))
In general:
Whenever a local variable is bound, it is allocated and stored in the global state, the binding has the location of the value; and
Whenever a variable is used, the location is dereferenced and accessed from the state.
To do this you must:
Update interp.rkt to remove cases for new and deref, and update the semantics for let to be like new and for variable uses to be like deref.
Add tests to check if your changes behave correctly throughout the language.
4.4 Testing
You should test your code by writing test cases and adding them to relevant files. The starter code is available in hw4.zip on Canvas. Use the command raco test [filename] to test your code. Alternatively, pressing “Run” in Dr. Racket will also run your test cases.
For grading, your submitted interpreter will be tested on multiple programs drawn from this language. Writing your own test cases will give you confidence that your interpreter can handle previously unseen programs.
4.5 Submitting
You should submit on Gradescope. You should submit two files: interp.rkt and rewriter.rkt for grading, so make sure all your work is contained there! You may add any function you need to these files, but do not rename the file or the interp, cond->if, and currify function.