Interpreter, Define / Lambda
Table of Contents
For this portion of the project, you’ll implement both define
and lambda
. When done, your interpreter will run functions that you create yourself, in Scheme!
This is an interpreter project team assignment, which means that if you are working on a team with someone else, you and your partner should do your best to even the workload between you. Strict pair programming is not required, but you should make sure that both team members are contributing to the project. I do recommend that you try to do pair programming if it is convenient to do so.
1 Get started
Hopefully, you’ve got the hang of it by now as to how these projects start. Feel free to go back again to the tokenizer assignment if you want detailed instructions on how to clone the repository to Repl.it. Here is the new GitHub Classroom link that you’ll need to create the repository on GitHub. Once you have created your repository, its name will have lambda
as a prefix.
2 Functionality
For this phase of the project, you must support the correct evaluation of the following types of Scheme expressions:
2.1 (define var expr)
Scheme actually has a number of different variations on define
; you only need
to implement the first one. Unlike let, define does not create a new environment
frame; rather, it modifies the current environment frame. You will therefore
need to have a “top” or “global” frame which contains bindings of variables
created using define
. You can put bindings for primitive functions in this
top-level frame too; you’ll read more about that later.
You should not print anything after a define statement. You should go about this
by having define
return a special Value
with type VOID_TYPE
, and only
print the result of an expression if it is not VOID_TYPE
. There’s probably
other ways of doing this too. Add a VOID_TYPE
to value.h.
Scheme is able to detect when define is used in the wrong place — don’t worry
about this if you don’t want to. You can just modify the current frame. We will
not test for correct or incorrect behavior if define
is used anywhere but at
the top-level. That said, you can add as optional extensions error checking as
appropriate.
2.2 (lambda params body)
You will need to implement closures. Specifically, for purposes of this project
a closure is just another type of value, containing everything needed to execute
a user-defined function: (1) a list of formal parameter names; (2) a pointer to
the function body; (3) a pointer to the environment frame in which the function
was created. Use a CLOSURE_TYPE
within value.h
. Here’s a snippet of my Value
definition:
typedef enum {INT_TYPE, ..., VOID_TYPE, CLOSURE_TYPE, ...} valueType; struct Value { valueType type; union { int i; ... struct Closure { struct Value *paramNames; struct Value *functionCode; struct Frame *frame; } cl; } }
2.3 Function application: (e1 ... en)
You should recursively evaluate e1
through en
and then apply the value of
e1
to the remaining values. The section below on function application has more
details.
As usual, your program should never crash or segfault on bad input; just print “Evaluation error” and exit gracefully. You can supplement with more detailed error information if you wish.
Once you’ve finished these components, your interpreter should be able to evaluate user-defined functions, even those which are recursive. Here’s one non-recursive example for you to try:
$ cat test-in-01.scm (define not (lambda (bool) (if bool #f #t))) (define testit (lambda (cond conseq alt) (let ((nconseq (not conseq)) (nalt (not alt))) (if cond nconseq nalt)))) (testit #t #f #t) (testit #f #f #t) $ ./interpreter < test-in-01.scm #t #f
3 Function application
In addition to eval
as described above, you will need to implement function
application. To do this, create a function called apply
:
Value *apply(Value *function, Value *args);
You should call this function once you’ve evaluated the function and the
arguments. Here, function
is a user-defined function (i.e. a
closure). You should take the following steps in order to execute the function:
- Construct a new frame whose parent frame is the environment 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) with the new frame as its
environment, and return the result of the call to
eval
.
Here’s my new eval
skeleton, modified to support function application:
Value *eval(Value *tree, Frame *frame) { switch (tree->type) { case INT_TYPE: ... break; case ......: ... break; case SYMBOL_TYPE: return lookUpSymbol(tree, frame); break; case CONS_TYPE: Value *first = car(expr); Value *args = cdr(expr); // Sanity and error checking on first... if (!strcmp(first->s,"if")) { result = evalIf(args, frame); } // .. other special forms here... else { // If not a special form, evaluate the first, evaluate the args, then // apply the first to the args. Value *evaledOperator = eval(first, frame); Value *evaledArgs = evalEach(args, frame); return apply(evaledOperator,evaledArgs); } break; .... } .... }
If a function is evaluated but not applied, you should just output <#procedure>
. Here is an example:
$ cat test-in-02.scm (lambda (x) x) $ ./interpreter < test-in-02.scm #<procedure>
4 Capstone work
Work in this section is 100% optional, and doesn’t contribute towards your grade. Nonetheless, if you’re looking for an extra challenge, these are fun additional exercises to try.
- Implement the third version of define shown in Dybvig, which is the one that lets you use
define
alone as shorthand for bothdefine
andlambda
:
(define (myfunction x y z) (+ x y z))
The above works, but is really shorthand for
(define myfunction (lambda (x y z) (+ x y z)))
- Implement a variation of lambda that takes a single parameter, not in parentheses, that gets bound to a list of parameters. This is described in this section of Dybvig, in the second bullet describing how formals works. Here’s an example:
$ cat test-in-02.scm (define tryit (lambda x x)) (tryit 1 2 3) $ ./interpreter < test-in-02.scm (1 2 3)
5 Your repository and your files
Your repository will follow the same structure that it has for the previous assignments. There should be no changes at all in the files that I provide; you’ll then need to add in the files from your previous version, and/or switch over to using my binaries. But note that the binaries I provide only go through part 4 of the project; I am not providing a working if/let interpreter. (The project gets too intermingled at this point for me to be able to supply complete partial work.)
Building and testing your code will work precisely the same as on the previous assignment.
6 What to submit
Make sure that you have added files if necessary, then push to GitHub. (You can leave out your compiled executables as well as the .o
object files if you wish.)
Make sure to label your submission as usual via an appropriate commit message, and make sure your tests have run on GitHub.
Have fun interpreting!
This assignment was originally created by David Liben-Nowell and has since been updated by Dave Musicant, Jed Yang, and Laura Effinger-Dean.