This assignment is to be done in PLT Scheme. 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 referring to an undefined variable or calling a user-defined function that isn't actually defined at all.
Modify your program from Homework 2 so it implements first-class functions as described in Chapter 6 of PLAI. There will be one new type of expression: an (anonymous) function definition, analogous to "lambda" in Scheme. Here's an example of its concrete syntax:
{fun {a b c} {- {* a a} {+ {* b b} {* c c}}}}
Your program should allow functions with any natural number of parameters:
0, 1, 2, 3, ....
So for example, the expression
{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.
The PLAI book suggests an abstract syntax for this; you'll need to modify that abstract syntax to handle multi-parameter functions.
As in Homework 2, your interpreter should use deferred substitution (aka "environments").
As pointed out in Chapter 6, this requires introducing the notion of
a "function closure", a function together with the variable values
that were in effect at the time the function was defined. In the above
example, the name sqr should be bound to a function closure
with no bindings, parameter name x, and body {* x x}.
Here's another example:
{with {{delta 5}} {with {{f {fun {x} {+ x delta}}} {f 3}}}
This time, the name f should be bound to a function closure
with the binding delta=5, parameter name x,
and body {+ x delta}.
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.
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 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.
Answer the discussion questions 6.2.1, 6.2.2, 6.2.3.
withDo 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.
Note: This means that any programming language that has
lambda doesn't need local variables.
Answer the discussion questions 6.4.1, 6.4.2.
Modify your program so it does lazy evaluation. This affects
how interp handles with-expressions and
function calls: in eager evaluation, the arguments to a
function call or the initial values of variables in a
with-expression are evaluated before being
substituted, whereas in lazy evaluation they're not evaluated
until the parameter or local variable is actually used in a computation.
For example, consider
{with {{f {fun {x y} {* x x}}}} {f {+ 1 2} {/ 3 0}}}
An eager evaluator will crash with a division-by-zero error.
A lazy evaluator will return 9; it never bothers dividing 3 by 0
because the y parameter to f is never used.
Hint: Lazy evaluation may require extending the notion of "function closures" to "expression closures" as well. Recall that a function closure encapsulates a parameter list, a function body, and an environment. An expression closure, similarly, encapsulates an expression and an environment. Why do you need this? (Give an example.)
Lazy evaluation allows you to do some really neat stuff, as we'll learn in Chapter 7.
For the First-class Functions exercise, turn in the
Scheme 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 or check-expect).
For the Eliminating with exercise, turn in the
Scheme source code for a function that takes in an FWAE expression
and produces an equivalent expression without any with's.
For the Lazy Evaluation exercise, turn in the Scheme
source code for your abstract-syntax definition, parser, interpreter,
and any helper functions they need. Some of these will be identical
to the eager version, above, but turn in all the lazy stuff as a
self-contained package so it's easier for me to test.