COS 371: Programming Languages
Spring 2022
proj6: Apply
Due: Wednesday, 04/27 at 22:00
1. Goals
To support applying functions created withlambda
expressions; to support the define
special form.
2. Introduction
You have an evaluator with the ability to handleif
, let
, and quote
special forms.
We now extend its capabilities to handle define
and lambda
special forms.
In particular, we will be able to apply functions created with lambda
.
In the next checkpoint, we will be able to apply built-in functions.
3. Tasks
-
Extend your collection with at least 4 pairs of test files to test the functionality specified in this checkpoint.
(More is better!)
As before, each pair of files should be named
test.eval.input.XX
andtest.eval.output.XX
, whereXX
is a test number. - Add
VOID_TYPE
andCLOSURE_TYPE
tovalue.h
. -
Your
eval
function must additionally handle the following Scheme features:define
,define
-bound variables,lambda
, and combinations. -
Implement an
apply
function ininterpreter.c
that handles applyinglambda
expressions. -
Modify your
Makefile
to compile your new interpreter code, if necessary. When I'm in your directory and I execute the commandmake interpreter
, I should get an executable file calledinterpreter
in that directory.
4. Specification
Support the correct evaluation of various types of Scheme expressions.(define var expr)
.Bind
var
to the value ofexpr
in the top-level frame. (You may assume that alldefine
expressions occur at the top level and affect the top-level environment; otherwise, the behaviour is unspecified. See explanation below.)The return value of a
define
expression is unspecified in the R5RS standard. I ask that you return aVOID_TYPE
value. Moreover, modify your interpreter so it does not printVOID_TYPE
values. (This is consistent with DrRacket not displaying any results upon a successfuldefine
.)Make sure
define
-bound variables resolve correctly.(lambda (x1 x2 ... xk) body)
.The value of this expression is a procedure object called a closure, which is a
Value
ofCLOSURE_TYPE
, consisting of all the data needed to apply this procedure later. Specifically, in theValue
union, add astruct Closure
consisting of (pointers to)- a list of formal parameter names;
- the function body; and
- the frame in which the
lambda
expression was evaluated.
- Combinations:
(e1 ... en)
, wheree1
is not a special form.First, recursively evaluate e1 through en (in some unspecified order). Then, apply the value of
e1
to the remaining values by calling anapply
function with the following prototype:Value *apply(Value *function, Value *args);
In the next checkpoint, you will extend
apply
to handle primitive functions such as+
andcons
. For now,apply
should handle the case offunction
being aCLOSURE_TYPE
, as follows:- construct a new frame whose parent frame is the frame stored in the closure;
- add bindings to the new frame, mapping each formal parameter (found in the closure)
to the corresponding actual parameter (found in
args
); - evaluate the function body (found in the closure) in the new frame; and
- return this result (to
eval
).
When you are done, you should be able to handle a test like this one:
(define not (lambda (bool) (if bool #f #t))) (define tofu (lambda (cond conseq alt) (let ((nconseq (not conseq)) (nalt (not alt))) (if cond nconseq nalt)))) (tofu 23 #f #t)
5. Unspecified behaviour
In R5RS, the behaviour of some code is unspecified. What this means is that a correct implementation of R5RS can do whatever it wants, short of crashing, when encountering such code.
For example, it is mentioned above that we assume define
expressions only occur at the top level,
and that a define
expression anywhere else has unspecified behaviour.
In other words, if a define
expression occurs at wrong places,
you can choose to do anything you want, including ignoring the define
expression, exiting gracefully, printing an ASCII art of a tofu, etc.
The one thing your program shouldn't do, however, is crash.
That's the only thing we'll be testing for unspecified behaviour.
In particular, for this checkpoint, we will test your code by purposefully placing define
in wrong places.
The only thing we'll check for in those cases is that your interpreter doesn't crash.
This principle also applies for all other unspecified behaviour in subsequent checkpoints: do whatever you want, just don't crash. (As repeatedly mentioned in previous checkpoints, your interpreter should never crash when given correct or incorrect input.)
6. Possible extensions
- Support multiple expressions in the body of
lambda
as inlet
. - Support the syntactic sugar for binding variables to procedures that Dybvig and I eschew.
- Support internal definitions at the beginning (only) of the body of a
lambda
,let
,let*
, orletrec
expression.
7. Submission
Your code should have no memory leaks or memory errors when run on any input (correct or incorrect) using Valgrind. We will be checking this during grading, so you should test your code via Valgrind yourself.
Follow the submission instructions from the previous checkpoint;
tag your commit with proj6
and push the tag to GitHub.
This assignment was originally created by David Liben-Nowell and has since been updated by Dave Musicant, Laura Effinger-Dean, and Jed Yang.
Start early, have fun, and discuss questions on Moodle.