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.
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).
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.)
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.
(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.
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.