In class, we've seen how to implement interpreters for eager languages with first-class functions. We saw two different implementation strategies: by substitution and by delayed substitution (henceforth, environments). We've explored and will explore delayed substitution in some depth.

When we were still implementing a first-order language, we saw that the semantic difference between the lazy and eager languages led to implementation differences. You should naturally be intrigued by whether this is true for a language with first-class functions also.

This homework will quell your curiosity. In this assignment, you must implement an interpreter with environments (and no subst function or equivalent) for a statically-scoped language with first-class functions that employs a lazy application semantics. If that sounds like a mouthful, and it does, here's the relevant difference from what we're doing in class: make application lazy, not eager.

Your version of Rip must contain the following language constructs:

• numbers
• addition
• let
• variables
• proc
• application

You may get rid of let using a transforming pre-processor if you wish.

For this assignment, you will have to abandon your macho/macha programming ways. First, you must program in Scheme. Second, we will grade you on the quality of your data definitions, contracts, purpose statements, adherence to the data definition, and test cases, in addition to the quality and correctness of the actual functions. You do not need to provide templates, though you are certainly welcome to use them and, if you include them, we will rejoice. (Just a little bit.)

Interface

You must provide at least one procedure, run. (We will not assume the names of any other procedures, nor will we invoke them.) We will provide run a quoted Rip program. The procedure must compute the result of evaluating the Rip program (if any). For example,

> (run '{+ 1 2})
3
> (run '{let {f {proc {x} x}} {f 4}})
4

If you don't understand this use of quote, ask the TAs.