Homework #2: Let* AE
Out: Friday, January 20th, Due: Friday, January 27th, 4:30pm

Administrative

The language for this homework is:

#lang plait

As a reminder, solutions without complete test coverage will be penalized by 20%, and solutions which fail the submission checks will be penalized by a up to 50% for a total 60% penalty (0.8*0.5 = 0.4).

Introduction

The homework is an extension of the LAE language from lectures. You will add a lets form that can bind any number of identifiers and allow bindings to refer to previous bindings within the same lets. You can get the general idea by looking at documentation for the plait form let*.

Begin by downloading the template file to serve as the basis of your work.

You will notice the type LAE has been renamed to L*AE, and a new Let* variant has been added. The parser has been updated for you. Note that the the new surface syntax is called lets rather than let* to avoid confusion with the plait builtin.

The semantics of lets should mimic those of plait’s let*. You are given a list of bindings, and each one applies to successive named expressions in the list as well as the bound body. Here are a few example tests of lets forms

(test (run `{lets {{x 5}
                    {y {- x 3}}} {+ y y}})  4)
(test (run `{lets {{x 5}
                    {y x}} y}) 5)
(test (run `{lets {{x 5}
                    {x x}} x}) 5)

A typical way to define let* (and hence lets) is recursively, as follows

{lets {} body} = body
{lets {{id val} bindings ...} body} = {let1 {id val} {lets {bindings ...} body}}

The use of ... here is analogous to the way it is used in s-exp-match?. As an example, we can transform the example {lets {{x 5} {y {- x 3}}} {+ y y}} from above into

{let1 {x 5}
      {let1 {y {- x 3}} {+ y y}}}

Update the substitution function

Use the given recursive definition to extend subst function to handle Let* abstract syntax. There are at least two ways to do this: either fully transform to nested let1 forms, or just apply one step of transformation and recursively call subst on that. In either case you will call L*AE constructors to synthesize some abstract syntax.
Add tests for subst. Your tests should ensure complete coverage for subst, and you should explain how they relate to your design.

Update the evaluator

Add a case for Let* to eval.
Add tests to ensure complete coverage for eval. Make you sure you test lets well, and explain those tests.

Finally