Project 2: Extending the Interpreter

Assigned 11 Oct, due 1 Nov

Extended to 8 Nov

because I didn't finish grading project 1 until 1 Nov

Continuing to crib shamelessly from CS 173 at Brown University...

For every function you write, you must include a contract and a well-chosen set of test cases.

For this assignment, switch languages in Racket to "Use Language Declared in Source", and replace the #lang racket with #lang plai.

If you didn't finish all of Project 1, please do. We'll need to build on that for this assignment.


  1. Chapter 4 of the PLAI textbook introduces functions as external to the language. This is sorta like having a library of predefined functions, but not letting programmers write their own. (For example, in DrRacket's Beginning Student Language, the Interactions pane can call lots of functions, but can't define new ones.) Combine Dr. K's code in Chapter 4 with your own from Project 1 to add external functions to your language.

    This will require defining a new "function definition" type; changing the internal-form type by adding a "function-call" variant (Dr. K. calls it "app"); changing the parser to recognize function calls; and changing the interpreter to handle them. The most substantial change is to the interpreter, which will now take in an extra argument: a list of known function definitions (Dr. K. uses the example
    (FunDef 'double 'x (add (id 'x) (id 'x)))

    Test your expanded language by writing functions such as double, square, negate, etc.

    Call this language F1MBWAE.


  2. Add a conditional construct ifpos to the language. It should take three expressions as arguments: if the first is positive, it evaluates and returns the second, while if the first is negative or zero, it evaluates and returns the third. For example,

    {with {{x 3}} {ifpos x 5 6}}
    should return 5 because x is positive.

    Note that the un-taken branch shouldn't be evaluated at all, so for example

    {with {{x 2}} {ifpos x 5 {/ x 0}}}
    should not produce a division-by-zero error.

    Note: This will require changing the internal representation to include an additional variant (in addition to numbers, identifiers, binary operators, and "with"-expressions). You'll then need to modify the parser to recognize these things correctly, and modify the interpreter to compute the right answers.

    Test your expanded language by defining some functions that use conditionals, such as "not", "abs", "equal-0", and "factorial". (Remember that we don't have a separate boolean type; we're treating positive numbers as true, and non-positive numbers as false.)

    Call this language CF1MBWAE.

  3. Deferring substitution

  4. Chapter 5 of the PLAI book introduces an alternative way to interpret "with" constructs: rather than immediately substituting for all free occurrences of the variable in the body expression, simply build up a list of variable substitutions to be performed, and don't actually do them until you encounter those variables in the course of evaluation.

    The sample code in PLAI uses a data structure called a DefrdSub, which is either an "mtSub" or a structure containing a symbol, a value to replace it with, and another DefrdSub. I'm not sure why Dr. K chose to do it that way -- I would have used an ordinary list of (symbol, value) pairs -- but you're welcome to use whichever approach makes more sense to you.

    In any case, modify your program from above (with external functions, conditionals, etc.) to use deferred substitution rather than immediate substitution. The input language should be exactly the same as before, and every expression in the input language should produce the same result as it did before. However, the interpreter will need an additional parameter: an "environment", or DefrdSub, to represent what variables need to be substituted with what values.

    Call this language DCF1MBWAE.

  5. Multi-parameter functions

  6. Modify your program from above to handle multiple-parameter functions. (You may assume that each function takes a fixed number of parameters -- for example, f(x,y,z) takes in exactly three parameters, and should produce an error message if anybody calls it on two or four. Five is right out.) This will require changing several data type definitions, the parser, and the interpreter.

    Test your expanded language by defining some functions with multiple arguments, such as "or", "and", "equal", "greater", "max".

    Call this language MPDCF1MBWAE.

What to Turn In

Turn in four Racket source files: f1mbwae.rkt, cf1mbwae.rkt, dcf1mbwae.rkt, and mpdcf1mbwae.rkt, containing the source code for the four stages of the assignment. If you don't get them all working, turn in as much as you've got, with an explanation of where you got stuck and what you've tried. If you have real trouble with one of the language features, but can do the next one, go ahead and do what you can: for example, if you didn't get deferred substitution, but got multiple-parameter functions working, turn in mpcf1mbwae.rkt.

Last modified:
Stephen Bloch /