CSC 270
Project 3
Assigned Nov 2, due Dec 8

This assignment is to be done in Racket (#lang plai). You are encouraged to do this in teams of two, both students working together on all parts of the assignment; if you do this, turn in one homework with both names on it.

As always, every function must have a contract and test cases, and I expect that you've tested every function before turning it in to me. Any user errors you can catch in the parser should be caught there, rather than waiting for run-time (the interpreter), such as calling a built-in binary operator on the wrong number of arguments, or a with with the wrong syntax, or referring to an undefined variable, or calling a "user-defined" function that isn't defined.

  1. First-class Functions (warm-up)

    Modify your WAE or BWAE program from Project 1 so it implements first-class functions as described in Chapter 6 of PLAI. There will be two new types of expression: an (anonymous) function definition, analogous to "lambda" in Scheme, and a function call. Here's an example of the concrete syntax:

    {{fun {y} {* y y}} 5}
    In this example, we've created an anonymous function which squares things, and we've called that function on the argument 5.

    It should also be possible to store functions in variables, e.g.

    {with {{sqr {fun {x} {* x x}}}} {+ {sqr 3} {sqr 4}}}
    would define a sqr function, apply it to 3 and 4, and return the sum of the results.

    For this part of the assignment, functions will only take exactly one parameter, and the interp function (what used to be named calc) should work by substitution (not deferred). The PLAI book does most of the work for you; you'll mostly just need to write test cases and the parser.

    Call this language FWAE or FBWAE (depending on which language you started with).

  2. Adding features from Project 2

    In Project 2, you've already implemented conditionals (ifpos), deferred substitution, and multi-parameter functions. Add these features to the language with first-class functions, in whatever order you like (with the goal of getting all three working, of course).

    As pointed out in Chapter 6, combining deferred substitution with first-class functions requires introducing something called a "function closure", which wraps up a function together with the values of variables that were in effect at the time the function was defined. Thus for example

    {with {f {with {x 5} {fun {y} {+ x y}}}} {with {x 7} {f 3}}}
    should evaluate to 8, not 10, because f is actually defined as a function closure combining {fun {y} {+ x y}} with the fact that x=5.

    A variable can now hold data of two different types: a number or a function closure, and an expression can evaluate to either of those two things. You may at this point want to separate the run-time types "number" and "function closure" from the abstract syntax variants "num" and "fun" -- or, if you prefer, you can merge them together, and have the parser build function closures with empty variable lists.

    It doesn't make sense to multiply two function closures, or multiply a number by a function closure, and it doesn't make sense to "call" a number on arguments. It also doesn't make sense to call a function closure of 3 parameters on only 1 argument. Any of these things should be flagged as errors. Some such errors may be detectable by the parser, but in general you'll have to check for them at run-time (i.e. in interp).

    One error that can (and should!) be caught by the parser is a function definition with the same parameter name appearing more than once, just as a multi-branched with shouldn't be allowed to bind more than one variable of the same name.

    Since we now have an easy way to define functions within the language, we no longer need interp to take in a list of function definitions; it can just take in an expression and an environment.

    Call this language MPDCFMBWAE, or something to indicate which features you've actually implemented.

    Answer the discussion questions 6.2.1, 6.2.2, 6.2.3.

    (Another side effect of defining named functions in the language, using with and fun and function closures, is that recursion becomes trickier. Our current semantics for with tell us to evaluate the bound-value before defining the new variable, so

    {with {x 5} {with {x {+ x 2}} x}}
    returns 7 rather than returning 5 or going into an infinite loop or something. However, this means that the definition
    {with {fact {fun {n} {ifpos n {* n {fact {- n 1}}} 1}}} {fact 4}}
    fails because fact isn't defined yet when we build the function closure. We'll see ways around this in chapters 9-10, next semester.)

  3. Eliminating with

    Do exercise 6.3.1, writing a preprocessor that takes an FWAE expression containing with's and produces an equivalent expression that doesn't contain any with's. (If you've got multi-parameter functions working, it should be easy to transform multi-branched withs. If not, just deal with single-branched withs.) Note: This means that any programming language that has lambda doesn't need local variables.

    Write this as a function named something like eliminate-with, and add it to the MPDCFMBWAE file from the previous stage.

    Answer the discussion questions 6.4.1, 6.4.2.

What to Turn In

For each phase of the assignment, turn in the Racket source code for your abstract-syntax definition, parser, interpreter, and any helper functions they need. Each function must have a contract and test cases (using test).

As mentioned above, eliminate-with is just a function (and perhaps some helper functions) which can be added to the source file for the last, most inclusive language you've got.

Last modified:
Stephen Bloch /