Money Tree

Eval calls apply,
which just calls eval again!
When does it all end?


In this project, you will develop an interpreter for a subset of the Scheme language. As you proceed, think about the issues that arise in the design of a programming language; many quirks of languages are byproducts of implementation decisions in interpreters and compilers. The subset of the language used in this project is described in the functional programming section of Composing Programs.

You will also implement some small programs in Scheme. Scheme is a simple but powerful functional language. You should find that much of what you have learned about Python transfers cleanly to Scheme as well as to other programming languages. To learn more about Scheme, you can read Structure and Interpretation of Computer Programs online for free. Examples from Chapters 1 and 2 are included as test cases for this project. Language features from Chapters 3, 4, and 5 are not part of this project, but of course you are welcome to extend your interpreter to implement more of the language. Since we only include a subset of the language, your interpreter will not exactly match the behavior of other interpreters such as STk.

The project concludes with an open-ended graphics contest that challenges you to produce recursive images in only a few lines of Scheme. As an example, the picture above abstractly depicts all the ways of making change for $0.50 using U.S. currency. All flowers appear at the end of a branch with length 50. Small angles in a branch indicate an additional coin, while large angles indicate a new currency denomination. In the contest, you too will have the chance to unleash your inner recursive artist.

This project includes several files, but all of your changes will be made to the first four:,, questions.scm, and tests.scm. You can download all of the project code as a zip archive, which contains the following files:

  • the Scheme evaluator
  • the Scheme syntactic analyzer
  • questions.scm: a collection of functions written in Scheme
  • tests.scm: a collection of test cases written in Scheme
  • a tokenizer for Scheme
  • primitive Scheme procedures
  • a buffer implementation
  • utility functions for 61A
  • ok: the autograder
  • tests: a directory of tests used by ok

You'll work in a team of two people, Partner A and Partner B. In each part, you will do some of the work separately and some together with your partner. For example, if a problem is marked 5A, then it is a solo problem for Partner A. Both partners should read, think about, and understand the solution to all questions. Feel free to help each other on the solo questions. If you choose to work on the whole project alone, you must complete all questions yourself.

In Parts I and II, you will develop the interpreter in several stages:

  • Reading Scheme expressions
  • Symbol evaluation
  • Calling built-in procedures
  • Definitions
  • Lambda expressions and procedure definition
  • Calling user-defined procedures
  • Evaluation of special forms

In Part III, you will implement Scheme procedures.


This is a 2 week project. You may work with one other partner. You should not share your code with students who are not your partner or copy from anyone else's solutions.

In the end, you will submit one project for both partners. The project is worth 30 points. 28 points are assigned for correctness, and 2 points for the overall composition of your program.

You will turn in the following files:

  • questions.scm
  • tests.scm

You do not need to modify or turn in any other files to complete the project. To submit the project, run the following command:

python3 ok --submit

You will be able to view your submissions on the OK dashboard.

For the functions that we ask you to complete, there may be some initial code that we provide. If you would rather not use that code, feel free to delete it and start from scratch. You may also add new function definitions as you see fit.

However, please do not modify any other functions. Doing so may result in your code failing our autograder tests. Also, please do not change any function signatures (names, argument order, or number of arguments).


Throughout this project, you should be testing the correctness of your code. It is good practice to test often, so that it is easy to isolate any problems.

We have provided an autograder called ok to help you with testing your code and tracking your progress. The first time you run the autograder, you will be asked to log in with your OK account using your web browser. Please do so. Each time you run ok, it will back up your work and progress on our servers.

The primary purpose of ok is to test your implementations, but there is a catch. At first, the test cases are locked. To unlock tests, run the following command from your terminal:

python3 ok -u

This command will start an interactive prompt that looks like:

Assignment: A Scheme Interpreter
OK, version ...

Unlocking tests

At each "? ", type what you would expect the output to be.
Type exit() to quit

Question 0 > Suite 1 > Case 1
(cases remaining: 1)

>>> Code here

At the ?, you can type what you expect the output to be. If you are correct, then this test case will be available the next time you run the autograder.

The idea is to understand conceptually what your program should do first, before you start writing any code.

Once you have unlocked some tests and written some code, you can check the correctness of your program using the tests that you have unlocked:

python3 ok

Most of the time, you will want to focus on a particular question. Use the -q option as directed in the problems below.

If you are trying to debug a test failure, you can launch an interactive session after the test is run with:

python3 ok -q 05 -i

This will run the tests and launch an interactive session if a test does not pass.

Assignment: Project 1: Hog
OK, version ....

Running tests

Question ... > Suite ... > Case ...

>>> the_test()
"expected value"

# Error: expected
#     "expected value"
# but got
#     None

# Interactive console. Type exit() to quit

The tests folder is used to store autograder tests, so make sure not to modify it. You may lose all your unlocking progress if you do. If you need to get a fresh copy, you can download the zip archive and copy it over, but you will need to start unlocking from scratch.

Details of Scheme

Read-Eval-Print. The interpreter reads Scheme expressions, evaluates them, and displays the results.

scm> 2
scm> (+ 2 3)
scm> (((lambda (f) (lambda (x) (f f x)))
       (lambda (f k) (if (zero? k) 1 (* k (f f (- k 1)))))) 5)

The starter code for your Scheme interpreter in can successfully evaluate the first expression above, since it consists of a single number. The second (a primitive call) and the third (a computation of 5 factorial) will not work just yet.

Load. Our load procedure differs from standard Scheme in that we use a symbol for the file name. For example, to load tests.scm, evaluate the following call expression.

scm> (load 'tests)

Symbols. Various dialects of Scheme are more or less permissive about identifiers (which serve as symbols). For example, the language of the current Scheme reference manual excludes "1+" as a possible symbol, but MIT/GNU Scheme allows it (probably because it is a traditional symbol for the successor function in other Lisp dialects). Likewise, in MIT/GNU Scheme, identifiers are not case-sensitive; the reference manual says otherwise.

Our rule is that

An identifier is a sequence of letters (a-z and A-Z), digits, and characters in !$%&*/:<=>?@^_~-+. that do not form a valid integer or floating-point numeral. Our version of Scheme is case-insensitive: two identifiers are considered identical if they match except possibly in the capitalization of letters. They are internally represented and printed in lower case:

scm> 'Hello

Turtle Graphics. In addition to standard Scheme procedures, we include procedure calls to the Python turtle package. This will come in handy in Part IV, for the contest.

You can read the turtle module documentation online.

Note: The turtle Python module may not be installed by default on your personal computer. However, the turtle module is installed on the instructional machines. So, if you wish to create turtle graphics for this project (i.e. for the contest), then you'll either need to setup turtle on your personal computer or use university computers.


Testing. The tests.scm file contains a long list of sample Scheme expressions and their expected values.

(+ 1 2)
; expect 3
(/ 1 0)
; expect Error

You can compare the output of your interpreter to the expected output by running:

python3 ok -q tests.scm

For the example above, your scheme interpreter will evaluate (+ 1 2) using your code in, then output a test failure if 3 is not returned as the value. The second example tests for an error (but not the specific error message.

Only a small subset of tests are designated to run by default because tests.scm contains an (exit) call near the beginning, which halts testing. As you complete more of the project, you should move or remove this call. However, your interpreter doesn't know how to exit until Problems 3 and 4 are completed; all tests will run until then.

Important: As you proceed in the project, add new tests to the top of tests.scm to verify the behavior of your implementation. Your composition score for this project will depend on whether or not you have tested your implementation in ways that are different from the ok tests.

Exceptions. As you develop your Scheme interpreter, you may find that Python raises various uncaught exceptions when evaluating Scheme expressions. As a result, your Scheme interpreter will halt. Some of these may be the results of bugs in your program, and some may be useful indications of errors in user programs. The former should be fixed (of course!) and the latter should be handled, usually by raising a SchemeError. All SchemeError exceptions are handled and printed as error messages by the read_eval_print_loop function in Ideally, there should never be unhandled Python exceptions for any input to your interpreter.

Running Your Scheme Interpreter

To run your Scheme interpreter in an interactive session, type:


You can use your Scheme interpreter to evaluate the expressions in an input file by passing the file name as a command-line argument to

python3 tests.scm

Currently, your Scheme interpreter can handle a few simple expressions, such as:

scm> 1
scm> 42
scm> true

To exit the Scheme interpreter, press Ctrl-d or evaluate the exit procedure (after completing problems 3 and 4):

scm> (exit)

Part I: The Reader

The first part of this project deals with reading and parsing user input. All changes in this part should be made in

The function scheme_read in parses a Buffer (see instance that returns valid Scheme tokens when its current and pop methods are invoked. Unlike a Python list, the pop method of a buffer removes and returns its first element, rather than its last. The scheme_read function returns the next full Scheme expression in the src buffer, using this representation:

Scheme Data Type Our Internal Representation
Numbers Python's built-in int and float values
Symbols Python's built-in string values
Booleans (#t, #f) Python's built-in True, False values
Pairs Instances of the Pair class, defined in
nil The nil object, defined in

Problem 1 (1 pt)

Complete the scheme_read function in by adding support for quotation. This function selects behavior based on the type of the next token:

  • If the next token in src is the string "nil", return the nil object. (provided)
  • If the next token is not a delimiter, then it is self-evaluating. Return it. (provided)
  • If the current token is a single quote (apostrophe), such as the first character of 'bagel, then return a quote special form such as (quote bagel). (you implement)
  • If the current token is a left parenthesis "(", return the result of read_tail. (provided)

Some examples of how to handle the quote form:

  • (quote bagel) is converted to Pair('quote', Pair('bagel', nil))
  • 'bagel is equivalent to (quote bagel), so it is also converted to Pair('quote', Pair('bagel', nil))

Test your understanding and implementation before moving on:

python3 ok -q 01 -u
python3 ok -q 01

Problem 2 (2 pt)

Complete the read_tail function in by adding support for dotted lists. An ordinary list denotes a linked sequence of Pairs in which the second attribute of the final pair is nil. A dotted list in Scheme is one in which there is a dot before the last item of the list; it denotes a sequence in which the second attribute of the final pair is the item after the dot, which may be any Scheme value:

(1 2 . 3) should be converted to Pair(1, Pair(2, 3))

One can in fact write a standard (or "proper") list as a dotted list as well:

(1 . (2 . (3 . nil))) and (1 2 . (3 . nil)) should both be converted to Pair(1, Pair(2, Pair(3, nil)))

The read_tail function expects to read the rest of a list or dotted list, assuming the open parenthesis of that list has already been popped by scheme_read. A dotted list must have exactly one item after the dot; anything else is a syntax error.

Consider the case of calling scheme_read on input "(1 2 . 3)". The read_tail function will be called on the suffix "1 2 . 3)", which is

  • The pair consisting of the Scheme value 1 and the value of the tail "2 . 3)", which is
  • The pair consisting of the Scheme value 2 and the Scheme value 3.

Thus, read_tail would return Pair(1, Pair(2, 3)).

Hint: In order to verify that only one element follows a dot, after encountering a '.', read one additional expression and then check to see that a closing parenthesis follows.

To complete this question, you will need to interact with the parameter src, which is a Buffer object (defined in There are two main ways to interact with src:

  • src.pop(): returns the first token in src and also removes the token from src.

    For example, if src currently contains the tokens [4, '.', 3, ')'], then src.pop() will return 4, and src will be left with ['.', 3, ')'].

  • src.current(): returns the first token in src, but does not remove the token from src.

    For example, if src currently contains the tokens [4, '.', 3, ')'], then src.current() will return 4; src remains the same.

Test your understanding and implementation before moving on:

python3 ok -q 02 -u
python3 ok -q 02

You should also test your parser in the following way:

  • run the doctests for (python3 -m doctest
  • test interactively by running python3 Every time you type in a value into the prompt, both the str and repr values of the parsed expression are printed. You can try the following inputs:

    read> 42
    str : 42
    repr: 42
    read> '(1 2 3)
    str : (quote (1 2 3))
    repr: Pair('quote', Pair(Pair(1, Pair(2, Pair(3, nil))), nil))
    read> nil
    str : ()
    repr: nil
    read> '()
    str : (quote ())
    repr: Pair('quote', Pair(nil, nil))
    read> (1 (2 3) (4 (5)))
    str : (1 (2 3) (4 (5)))
    repr: Pair(1, Pair(Pair(2, Pair(3, nil)), Pair(Pair(4, Pair(Pair(5, nil), nil)), nil)))
    read> (1 (9 8) . 7)
    str : (1 (9 8) . 7)
    repr: Pair(1, Pair(Pair(9, Pair(8, nil)), 7))
    read> (hi there . (cs . (student)))
    str : (hi there cs student)
    repr: Pair('hi', Pair('there', Pair('cs', Pair('student', nil))))

Part II: The Evaluator

All changes in this part should be made in For each question, also add a few tests to the top of tests.scm to verify the behavior of your implementation.

In the implementation given to you, the evaluator can only evaluate self-evaluating expressions: numbers, booleans, and nil.

Read the first two sections of, called Eval/Apply and Environments.

  • The scheme_eval and scheme_apply functions are complete, but most of the functions or methods they use are not yet implemented.
  • The .apply and .eval_call methods in subtypes of Procedure and the make_call_frame function assist in applying built-in and user-define procedures.
  • The Frame class implements an environment frame.
  • The LambdaProcedure class represents user-defined procedures.

These are all of the essential components of the interpreter; the rest of defines special forms and input/output behavior.

Test your understanding of how these components fit together by unlocking the tests for eval_apply.

python3 ok -q eval_apply -u

Some Core Functionality

Problem 3 (1 pt)

Implement the lookup method of the Frame class. It takes a symbol (represented by a Python string) and returns the value bound to that name in the first Frame of the environment in which that name is found. A Frame represents an environment via two instance attributes:

  • bindings is a dictionary that maps Scheme symbol keys (represented as Python strings) to Scheme values.
  • parent is the parent Frame instance. The parent of the Global Frame is None.

Your lookup implementation should:

  • Return the value of the symbol in self.bindings if it exists.
  • Otherwise, lookup that symbol in the parent if the parent exists.
  • Otherwise, raise a SchemeError. (provided)

Test your understanding and implementation before moving on:

python3 ok -q 03 -u
python3 ok -q 03

After you complete this problem, you can open your Scheme interpreter (with python3 You should be able to look up built-in procedure names:

scm> +
scm> odd?
scm> display

However, your Scheme interpreter will still not be able to apply these procedures. Let's fix that.

Problem 4 (2 pt)

Implement the apply method in the class PrimitiveProcedure, which is called by scheme_apply. Primitive procedures are applied by calling a corresponding Python function that implements the procedure. Instances of class PrimitiveProcedure, defined in, represent the values of Scheme primitive procedures. A PrimitiveProcedure has two instance attributes:

  • fn is the Python function that implements the primitive Scheme procedure.
  • use_env is a boolean flag that indicates whether or not this primitive procedure will expect the current environment to be passed in as the last argument. The environment is required, for instance, to implement the primitive eval procedure.

To see a list of all Scheme primitive procedures used in the project, look in the file. Any function decorated with @primitive will be added to the globally-defined PRIMITIVES list.

The apply method of PrimitiveProcedure takes a Scheme list of argument values, and the current environment. Your implementation should:

  • Convert the Scheme list to a Python list of arguments. (provided)
  • If self.use_env is True, then add the current environment env as the last argument to this Python list.
  • Call self.fn on all of those arguments (Hint: use *args notation).
  • If calling the function results in a TypeError exception being thrown, which indicates that the wrong number of parameters were passed, intercept the exception and raise an appropriate SchemeError in its place.

Test your understanding and implementation before moving on:

python3 ok -q 04 -u
python3 ok -q 04

Your interpreter should now be able to evaluate primitive procedure calls, giving you the functionality of the Calculator language and more.

scm> (+ 1 2)
scm> (* 3 4 (- 5 2) 1)
scm> (odd? 31)

Problem 5A (1 pt)

There are two missing parts in the do_define_form function, which handles the (defineĀ ...) special forms. Implement just the first part, which binds names to values but does not create new procedures. do_define_form should return the name after performing the binding.

scm> (define tau (* 2 3.1415926))

Test your understanding and implementation before moving on:

python3 ok -q 05A -u
python3 ok -q 05A

You should now be able to give names to values and evaluate the resulting symbols.

scm> (define x 15)
scm> (define y (* 2 x))
scm> y
scm> (+ y (* y 2) 1)
scm> (define x 20)
scm> x
scm> (eval (define tau 6.28))

Problem 6B (1 pt)

Implement the do_quote_form function, which evaluates the quote special form.

Test your understanding and implementation before moving on:

python3 ok -q 06B -u
python3 ok -q 06B

You should now be able to evaluate quoted expressions.

scm> 'hello
scm> '(1 . 2)
(1 . 2)
scm> '(1 (2 three . (4 . 5)))
(1 (2 three 4 . 5))
scm> (car '(a b))
scm> (eval (cons 'car '('(1 2))))

At this point in the project, your Scheme interpreter should support the following features:

  • Evaluate atoms, which include numbers, booleans, nil, and symbols,
  • Evaluate the quote special form,
  • Evaluate lists,
  • Define symbols, and
  • Call primitive procedures, for example evaluating (+ (- 4 2) 5).

User-Defined Procedures

User-defined procedures are represented as instances of the LambdaProcedure class. A LambdaProcedure instance has three instance attributes:

  • formals is a Scheme list of the formal parameters (symbols) that name the arguments of the procedure.
  • body is a single Scheme expression; the body of the procedure.
  • env is the environment in which the procedure was defined.

Problem 7 (2 pt)

Implement the eval_all function (which is called from do_begin_form), to complete the implementation of the begin special form. A begin expression is evaluated by evaluating all sub-expressions in order. The value of the begin expression is the value of the final sub-expression.

scm> (begin (+ 2 3) (+ 5 6))
scm> (define x (begin (display 3) (newline) (+ 2 3)))
scm> (+ x 3)
scm> (begin (print 3) '(+ 2 3))
(+ 2 3)

If eval_all is passed an empty list of expressions (nil), then it should return the Python value None, which represents an undefined Scheme value.

Test your understanding and implementation before moving on:

python3 ok -q 07 -u
python3 ok -q 07

Problem 8 (1 pt)

Implement the do_lambda_form method, which creates LambdaProcedure instances by evaluating lambda expressions. While you cannot call a user-defined procedure yet, you can verify that you have created the procedure correctly by evaluating a lambda expression:

scm> (lambda (x y) (+ x y))
(lambda (x y) (+ x y))

In Scheme, it is legal to place more than one expression in the body of a procedure (there must be at least one expression). The body attribute of a LambdaProcedure instance is a Scheme list of body expressions.

Test your implementation before moving on:

python3 ok -q 08

Problem 9A (2 pt)

Currently, your Scheme interpreter is able to bind symbols to user-defined procedures in the following manner:

scm> (define f (lambda (x) (* x 2)))

However, we'd like to be able to use the shorthand form of defining named procedures:

scm> (define (f x) (* x 2))

Modify the do_define_form function so that it correctly handles the shorthand procedure definition form above. Make sure that it can handle multi-expression bodies.

Test your understanding and implementation before moving on:

python3 ok -q 09A -u
python3 ok -q 09A

You should now find that defined procedures evaluate to lambda procedures.

scm> (define (square x) (* x x))
scm> square
(lambda (x) (* x x))

Problem 10 (2 pt)

Implement the make_child_frame method of the Frame class, which:

  • Creates a new Frame instance, the parent of which is self. (provided)
  • If the number of inputted argument values does not match with the number of formal parameters, raises a SchemeError.
  • Binds formal parameters to their corresponding argument values in the newly created frame.

Test your understanding and implementation before moving on:

python3 ok -q 10 -u
python3 ok -q 10

Problem 11B (2 pt)

Implement the check_formals function to raise an error whenever the Scheme list of formal parameters passed to it is invalid. Raise a SchemeError if the list of formals is not a well-formed list of symbols or if any symbol is repeated.

Hint: The scheme_symbolp function in returns whether a value is a Scheme symbol.

Test your implementation before moving on:

python3 ok -q 11B

Problem 12 (2 pt)

Implement the make_call_frame method in LambdaProcedure, which is needed by the apply method defined in UserDefinedProcedure. It should create a new Frame instance using the make_child_frame method of the appropriate parent frame, binding formal parameters to argument values.

Test your understanding and implementation before moving on:

python3 ok -q 12 -u
python3 ok -q 12

At this point in the project, your Scheme interpreter should support the following features:

  • Create procedures using lambda expressions,
  • Define named procedures using define expressions, and
  • Call user-defined procedures.

Now is an excellent time to revisit the tests in tests.scm and ensure that you pass the tests that involve definition (Sections 1.1.2 and 1.1.4). You should also add additional tests of your own at the top of tests.scm to verify that your interpreter is behaving as you expect.

Special Forms

Logical special forms include if, and, or, and cond. These expressions are special because not all of their sub-expressions may be evaluated.

In Scheme, only False is a false value. All other values are true values. You can test whether a value is a true value or a false value using the provided Python functions scheme_true and scheme_false, defined in (Scheme traditionally uses #f to indicate a false value, which is equivalent to false or False. Similarly, true, True, and #t are all equivalent.)

Problem 13 (1 pt)

Implement do_if_form so that if expressions are evaluated correctly. This function should evaluate either the second (consequent) or third (alternative) expression of the if expression, depending on whether the value of the first (predicate) expression is true.

scm> (if (= 4 2) 'a 'b)
scm> (if (= 4 4) (* 1 2) (+ 3 4))

It is legal to pass in just two expressions to the if special form. In this case, you should return the second expression if the first expression evaluates to a true value. Otherwise, return the Python value None, which represents an undefined value and is not printed by the interpreter.

scm> (if (= 4 2) 'a)

Test your understanding and implementation before moving on:

python3 ok -q 13 -u
python3 ok -q 13

Problem 14B (2 pt)

Implement do_and_form and do_or_form so that and and or expressions are evaluated correctly.

The logical forms and and or are short-circuiting. For and, your interpreter should evaluate each sub-expression from left to right, and if any of these evaluates to a false value, then False is returned. Otherwise, it should return the value of the last sub-expression. If there are no sub-expressions in an and expression, it evaluates to True.

scm> (and)
scm> (and 4 5 6)  ; all operands are true values
scm> (and 4 5 (+ 3 3))
scm> (and True False 42 (/ 1 0))  ; short-circuiting behavior of and

For or, evaluate each sub-expression from left to right. If any sub-expression evaluates to a true value, return that value. Otherwise, return False. If there are no sub-expressions in an or expression, it evaluates to False.

scm> (or)
scm> (or 5 2 1)  ; 5 is a true value
scm> (or False (- 1 1) 1)  ; 0 is a true value in Scheme
scm> (or 4 True (/ 1 0))  ; short-circuiting behavior of or

Test your understanding and implementation before moving on:

python3 ok -q 14B -u
python3 ok -q 14B

Problem 15A (2 pt)

Implement do_cond_form so that it returns the value of the first result sub-expression corresponding to a true predicate, or the sub-expression corresponding to else. Your implementation should match the following examples and the additional tests in tests.scm.

scm> (cond ((= 4 3) 'nope)
           ((= 4 4) 'hi)
           (else 'wait))
scm> (cond ((= 4 3) 'wat)
           ((= 4 4))       ; When the true predicate appears alone, return its vale
           (else 'hm))
scm> (cond ((= 4 4) 'here (+ 40 2))  ; When there are multiple expressions,
                                     ; evaluate all and return value of the last
           (else 'wat 0))

Hint: For the last example, where the body of a cond case has multiple expressions, use eval_all.

The value of a cond is undefined if there are no true predicates and no else. In such a case, do_cond_form should return None.

scm> (cond (False 1) (False 2))

Test your understanding and implementation before moving on:

python3 ok -q 15A -u
python3 ok -q 15A

Problem 16 (2 pt)

The let special form binds symbols to values locally, giving them their initial values. For example:

scm> (define x 5)
scm> (define y 'bye)
scm> (let ((x 42)
           (y (* x 10)))  ; x refers to the global value of x, not 42
       (list x y))
(42 50)
scm> (list x y)
(5 bye)

Implement make_let_frame, which returns a child frame of env that binds the symbol in each element of bindings to the value of the corresponding expression.

You may find the following functions and methods useful:

  • check_form: this function can be used to check the structure of each binding.
  • make_child_frame: this method (which you implemented in Problem 10) takes two Pairs of formal paremeters and values, and creates a new frame with all the formals bound to the corresponding values.

Test your understanding and implementation before moving on:

python3 ok -q 16 -u
python3 ok -q 16

Problem 17 (2 pt)

Implement do_mu_form to evaluate the mu special form, a non-standard Scheme expression type. A mu expression is similar to a lambda expression, but evaluates to a MuProcedure instance that is dynamically scoped. The MuProcedure class has been provided for you.

Additionally, update the body of MuProcedure so that when a call on such a procedure is executed, it is dynamically scoped. Calling a LambdaProcedure uses lexical scoping: the parent of the new call frame is the environment in which the procedure was defined. Calling a MuProcedure created by a mu expression uses dynamic scoping: the parent of the new call frame is the environment in which the call expression was evaluated. As a result, a MuProcedure does not need to store an environment as an instance attribute. It can refer to names in the environment from which it was called.

scm> (define f (mu (x) (+ x y)))
scm> (define g (lambda (x y) (f (+ x x))))
scm> (g 3 7)

Looking at LambdaProcedure should give you a clue about what needs to be done to MuProcedure to complete it. Test your understanding and implementation before moving on:

python3 ok -q 17 -u
python3 ok -q 17

Congratulations! Your Scheme interpreter implementation is now complete!

You should have been adding tests to the top of tests.scm as you did each problem. The tests that you have written tests will be evaluated as part of your composition score for the project.

To run your tests, run the command:

  python3 ok -q tests.scm

Make sure to remove all of the (exit) commands, so that all the tests are run!

Part III: Write Some Scheme

Not only is your Scheme interpreter itself a tree-recursive program, but it is flexible enough to evaluate other recursive programs. Implement the following procedures in Scheme in the questions.scm file.

All changes in this part should be made in questions.scm.

Problem 18 (1 pt)

Implement the enumerate procedure, which takes in a list of values and returns a list of two-element lists, where the first element is the index of the value, and the second element is the value itself.

scm> (enumerate '(3 4 5 6))
((0 3) (1 4) (2 5) (3 6))
scm> (enumerate '())

Test your implementation before moving on:

python3 ok -q 18

Problem 19 (2 pt)

Implement the list-change procedure, which lists all of the ways to make change for a positive integer total amount of money, using a list of currency denominations, which is sorted in descending order. The resulting list of ways of making change should also be returned in descending order.

To make change for 10 with the denominations (25, 10, 5, 1), we get the possibliites:

5, 5
5, 1, 1, 1, 1, 1
1, 1, 1, 1, 1, 1, 1, 1, 1, 1

To make change for 5 with the denominations (4, 3, 2, 1), we get the possibilities:

4, 1
3, 2
3, 1, 1
2, 2, 1
2, 1, 1, 1
1, 1, 1, 1, 1

You may find that implementing a helper function, cons-all, will be useful for this problem. cons-all takes in an element, first and a list of lists, rests, and adds first to the beginning of each list in rests:

scm> (cons-all 1 '((2 3) (2 4) (3 5)))
((1 2 3) (1 2 4) (1 3 5))

Test your implementation before moving on:

python3 ok -q 19

Problem 20 (2 pt)

In Scheme, source code is data. Every non-primitive expression is a list, and we can write procedures that manipulate other programs just as we write procedures that manipulate lists.

Re-writing programs can be useful: we can write an interpreter that only handles a small core of the language, and then write a procedure analyze that converts other special forms into the core language before a program is passed to the interpreter.

For example, the let special form is equivalent to a call expression that begins with a lambda expression. Both create a new frame extending the current environment and evaluate a body within that new environment.

(let ((x 42) (y 16)) (+ x y))
;; Is equivalent to:
((lambda (x y) (+ x y)) 42 16)

We can use this rule to rewrite all let special forms into lambda expressions. We prevent evaluation of a program by quoting it, and then pass it to analyze:

scm> (analyze '(let ((a 1) (b 2)) (+ a b)))
((lambda (a b) (+ a b)) 1 2)
scm> (analyze '(let ((a 1)) (let ((b a)) b)))
((lambda (a) ((lambda (b) b) a)) 1)

In order to handle all programs, analyze must be aware of Scheme syntax. Since Scheme expressions are recursively nested, analyze must also be recursive. In fact, the structure of analyze looks like that of scheme_eval:

(define (analyze expr)
  (cond ((atom?   expr) <Analyze atom>)
        ((quoted? expr) <Analyze quoted>)
        ((lambda? expr) <Analyze lambda>)
        ((define? expr) <Analyze define>)
        ((let?    expr) <Analyze let>)
        (else           <Analyze other>)))

Implement the analyze procedure, which takes in an expression and converts all of the let special forms in the expression into their equivalent lambda expressions.

Hint: You may want to implement map and zip at the top of questions.scm.

scm> (zip '((1 2) (3 4) (5 6)))
((1 3 5) (2 4 6))
scm> (zip '((1 2)))
((1) (2))
scm> (zip '())
(() ())

Test your understanding and implementation before moving on:

python3 ok -q 20 -u
python3 ok -q 20

Note: We used let while defining analyze. What if we want to run analyze on an interpreter that does not recognize let? We can pass analyze to itself to compile itself into an equivalent program that does not use let:

;; The analyze procedure
(define (analyze expr)

;; A list representing the analyze procedure
(define analyze-code
  '(define (analyze expr)

;; An analyze procedure that does not use 'let'
(define analyze-without-let
  (analyze analyze-code))

Problem 21 (0 pt; optional)

Implement the hax procedure, which draws the following recursive illustration when passed two arguments, a side length d and recursive depth k. The example below is drawn from (hax 200 4).


To see how this illustration is constructed, consider this annotated version that gives the relative lengths of lines of the component shapes in the figure.


Part IV: Extra Credit

Extra Credit Problem 22 (2 pt)

Complete the function scheme_optimized_eval in This alternative to scheme_eval is properly tail recursive. That is, the interpreter will allow an unbounded number of active tail calls in constant space.

The Evaluate class represents an expression that needs to be evaluated in an environment. When scheme_optimized_eval receives an expression in a tail context, then it returns an Evaluate instance. Otherwise, it repeatedly evaluates expressions within the body of a while statement, updating result in each iteration.

A successful implementation will require changes to several other functions. All tail calls should call scheme_eval with True as a third argument, indicating a tail call.

Once you finish, uncomment the following line in to use your implementation:

scheme_eval = scheme_optimized_eval

Test your understanding and implementation before moving on:

python3 ok -q EC -u
python3 ok -q EC


Congratulations! You have finished the final project for 61A! Assuming your tests are good and you've passed them all, consider yourself a proper computer scientist!

Now, get some sleep. You've earned it!

Recursive Art Contest

We've added a number of primitive drawing procedures that are collectively called "turtle graphics". The turtle represents the state of the drawing module, which has a position, an orientation, a pen state (up or down), and a pen color. The tscheme__x_ functions in are the implementations of these procedures, and show their parameters with a brief description of each.

The Python documentation of the turtle module contains more detail.

Contest: Create a visualization of an iterative or recursive process of your choosing, using turtle graphics. Your implementation must be written entirely in Scheme using the interpreter you have built. However, you may add primitive procedures to interface with Python's turtle or math modules. Other than that all computation must be done in Scheme. If you do add new primitives, then make sure to submit in addition to contest.scm.

Prizes, as well as 3 extra credit points, will be awarded for the winning entry in each of the following categories:

  • Featherweight: Fewer than 256 Scheme tokens
  • Heavyweight: Fewer than 2048 Scheme tokens

You can check the number of tokens in a Scheme file called contest.scm by running the command

python3 contest.scm

Entries (code and images) will be posted online, and winners will be selected by popular vote as part of a future homework. The voting instructions will read:

Please vote for your favorite entry in this semester's 61A Recursion Exposition contest. The winner should exemplify the principles of elegance, beauty, and abstraction that are prized in the Berkeley computer science curriculum. As an academic community, we should strive to recognize and reward merit and achievement (translation: please don't just vote for your friends).

To improve your chance of success, you are welcome to include a title and descriptive haiku in the comments of your entry, which will be included in the voting.

Entries that do not construct an image iteratively or recursively may be disqualified. Please don't just draw a preexisting image, even if the drawing function is iterative or recursive. If you're unsure, just ask.

Submission instructions will be posted closer to the deadline.

Extra Challenge

We have implemented a significant subset of Scheme in this project, but our interpreter can be extended with more features by following the extension instructions.