| Code: | pa3.ss |
| Tests: | pa3-tests.ss |
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".
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).
Create a construct called if0 interpreted as follows:
0,
then the second argument, the then expression, is evaluated,
and the entire if0 expression takes that value;
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.
Implement functions and function applications as in the FWAE language in the book. Permit binding identifiers to function values as well as numbers, and permit function applications using identifiers bound to functions.
Aside: Once you have added these first two 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.
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!
Here is a BNF grammar for the CFCFWAE language:
<CFCFWAE> ::= <num>
| {<binop> <CFCFWAE> <CFCFWAE>}
| {with {<binding> ...} <CFCFWAE>}
| <id>
| {if0 <CFCFWAE> <CFCFWAE> <CFCFWAE>}
| {fun {<id> ...} <CFCFWAE>}
| {<CFCFWAE> <CFCFWAE> ...}
<binop> ::= + | - | * | /
<binding> ::= {<id> <CFCFWAE>}
The ellipsis (...) means
the previous non-terminal is present zero or more times.
The last rule above for expanding a CFCFWAE to
a non-empty list of CFCFWAEs represents a function application.
Your parser will need to detect illegal syntax.
The tests include an example of each error your parser must detect,
and the message it should pass to Scheme's error function.
You may earn bonus points by implementing deferred substitution as shown in PLAI.
As with previous assignments, you will need to think carefully about where your code might fail and add your own test cases to the test file. Your submission will be tested against a more comprehensive suite of tests than we gave you and we may also assess the quality of your tests.