CSE 130, Summer 2009

Programming Languages: Principles and Paradigms

Programming Assignment 3

The purpose of this assignment is to deepen your understanding by continuing to extend your interpreter. It is to be completed individually according to the course collaboration policy.

You can work on this assignment using DrScheme or MzScheme on ACS machines or on your own machine. Wherever you work, you first have to install the PLAI language. Once installed, it will work in both DrScheme and MzScheme, and you will find documentation for the PLAI language by selecting "Help Desk" from the Help menu in DrScheme, and then following the link labeled Programming Languages: Application and Interpretation under the heading "Languages".

Tasks

Beginning with your interpreter for the WAE language, you will extend it with the features described below. The resulting language will be called CFCFWAE, for "conditionals, first-class functions, with, and arithmetic expressions." Accordingly you'll rename your WAE datatype to CFCFWAE and your calc function to interp (as with the languages enriched with functions in PLAI).

Deferred Substitution

Implement deferred substitution as described in Chapter 5.

• Use the DefrdSub type to represent environments and the lookup function to retrieve values bound to identifiers. As in Chapter 5, values in the environment are numbers initially, just as expressions evaluate to numbers. This will change later when function (closure) values are introduced.
• Don't add the FunDef type or the app variant introduced in Chapter 4 of PLAI; it's best not to modify your existing WAE type at all initially.
• Rename your calc function to interp. Note (in the file provided) interp is a case-lambda that takes one or two parameters. The first parameter is an expression to evaluate; the optional second parameter is an environment in which to evaluate it. When no second parameter is present, an empty environment is used by default.
• Since deferred substitution should not change the semantics of the language, make sure your existing tests continue to pass.
• When you're finished implementing deferred substitution, no remnant of the old subst function should appear in your code.

Arithmetic Conditional

Create a construct called if0 interpreted as follows:

1. Its first argument, the test expression is evaluated;
2. if the value of the test expression is 0, then the second argument, the then expression, is evaluated, and the entire if0 expression takes that value;
3. otherwise the third argument, the else expression, is evaluated, and the entire if0 expression takes that value.

If the test expression does not evaluate to a number, your interpreter should signal an error. Note also that if the then expression is evaluated, the else expression is not evaluated, and vice-versa; evaluating both is an error even if the correct value is returned.

First-Class Functions

Implement functions and function applications as in the FAE language in Chapter 6. This will involve producing CFCFWAE-Values instead of plain numbers when evaluating CFCFWAE expressions.

• In the aSub variant of the DefrdSub type, you'll need to change the value field to hold a CFCFWAE-Value instead of a number.
• You'll need to to update the way binop and if0 are interpreted so they expect numV values as parameters and use numV-n to extract the numbers from them.

Aside: Once you have added these features, you will be able to do useful recursion in CFCFWAE by passing a function to itself in a parameter! But with only a single parameter per function, it's a bit ugly.

Functions with Multiple Parameters

Finally, permit functions to accept multiple parameters. (This is very similar to implementing parallel bindings in with.)

Aside: Multiple parameters are in some sense syntactic sugar, since we can always use currying instead to take one paramater at a time. However, this sugar is pretty sweet. In the test file you will see an example that recursively computes a factorial, and it's even reasonably easy to read!

<CFCFWAE> ::= <num>
            | {<binop> <CFCFWAE> <CFCFWAE>}
            | {with {<binding> ...} <CFCFWAE>}
            | <id>
            | {if0 <CFCFWAE> <CFCFWAE> <CFCFWAE>}
            | {fun {<id> ...} <CFCFWAE>}
            | {<CFCFWAE> <CFCFWAE> ...}

<binop> ::= + | - | * | /

<binding> ::= {<id> <CFCFWAE>}