Scheme Interpreter

• scheme.zip

Introduction

Important submission note: For full credit,

• Submit with Phase 1 complete by Tuesday 11/18 (worth 1 pt).
• Submit with Phase 1 and Phase 2 complete by Thursday 11/20 (worth 1 pt).
• Submit with all phases complete by Tuesday 11/25.

Try to attempt the problems and run their ok tests in order, as some later problems will depend on earlier problems in their implementation.

The entire project can be completed with a partner.

You can get 1 EC point by submitting the entire project by Monday 11/24.

In this project, you will use Python to implement an interpreter for a subset of the Scheme language. The subset of the language used in this project is described in the functional programming section of Composing Programs, as well as this language specification and built-in procedure reference.

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.

Download starter files

You can download all of the project code as a zip archive.

Files you will edit:

• scheme_eval_apply.py: the recursive evaluator for Scheme expressions
• scheme_forms.py: Python functions for evaluating special forms in Scheme (such as define, lambda, and, cond, etc.)
• scheme_classes.py: Python classes that describe Scheme expressions
• questions.scm: Scheme procedures for you to implement

The rest of the files in the project:

• link.py: defines the Link class, nil, and map_link
• scheme.py: the interpreter read-eval-print loop or REPL (the user interface to the interpreter)
• scheme_builtins.py: built-in Scheme procedures
• scheme_reader.py: the reader (parser) for Scheme expressions
• scheme_tokens.py: the tokenizer for Scheme input
• scheme_utils.py: functions for inspecting Scheme expressions
• buffer.py: a utility class for the scheme reader
• ucb.py: utility functions for use in 61A projects
• tests.scm: a collection of test cases written in Scheme
• ok: the autograder
• tests: a directory of tests used by ok
• mytests.rst: a file where you can add your own tests

Logistics

The project is worth 30 points. 28 points are for correctness, 1 point for submitting Phase 1 by the first checkpoint date, and 1 point for submitting Phases 1 & 2 by the second checkpoint date.

You can get 1 EC point for submitting the entire project by Monday 11/24.

You will turn in the following files:

• scheme_eval_apply.py
• scheme_forms.py
• scheme_classes.py
• questions.scm

You do not need to modify or turn in any other files to complete the project. To submit the project, submit the required files to the appropriate Pensieve assignment.

You may not use artificial intelligence tools to help you with this project or reference solutions found on the internet.

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 or edit any files not listed above. 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. However, you should not be testing too often, to allow yourself time to think through 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.

If you want to test your code interactively, you can run

 python3 ok -q [question number] -i 

You can also use the debugging print feature in OK by prefixing your print statements with "DEBUG:". For example, if you wanted to inspect the value of a variable x, you could write:

 print(f"DEBUG: x is {x}") 

Interpreter details

Scheme features

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

scm> 2
2
scm> (+ 2 3)
5
scm> ((lambda (x) (* x x)) 5)
25

The starter code provided for the Scheme interpreter is enough to successfully evaluate the first expression above, a number. However, more complicated operations such as the second example (a call to a built-in procedure) and the third (a computation of 5 squared) will not work yet.

Load. You can load a file by passing in a symbol for the file name. For example, to load tests.scm, evaluate the following call expression.

scm> (load 'tests)

Symbols. In the dialect of Scheme we use in CS 61A, a symbol (or 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 differ only in the capitalization of letters. They are internally represented and printed in lower case:

scm> 'Hello
hello

Running the interpreter

To start an interactive Scheme interpreter session, type:

python3 scheme.py

To exit the Scheme interpreter, press Ctrl-d on Mac/Linux (or Ctrl-z Enter on Windows) or evaluate the built-in exit procedure (after completing problem 3 where calling built-in Scheme procedures is implemented):

scm> (exit)

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 scheme.py:

python3 scheme.py tests.scm

The tests.scm file contains a long list of sample Scheme expressions and their expected values. Many of these examples are from Chapters 1 and 2 of Structure and Interpretation of Computer Programs, the textbook from which Composing Programs is adapted.

Phase 1: The Evaluator

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

In Phase 1, you will develop the following features of the interpreter:

• Symbol definition and lookup
• Expression evaluation
• Calling built-in procedures (such as +, exit, equal?, etc.; see the built-in procedure reference for the full list)

Here's a tour of the starter code.

In scheme_eval_apply.py:

• scheme_eval evaluates a Scheme expression expr in an environment env. This function is nearly complete but is missing the logic for call expressions.
• Consider this if-statement block in scheme_eval:

  if scheme_symbolp(first) and first in scheme_forms.SPECIAL_FORMS:
      return scheme_forms.SPECIAL_FORMS[first](rest, env)

Notice that when evaluating a special form, scheme_eval redirects evaluation to an appropriate do_?_form function found in scheme_forms.py. Some examples of special forms are and, or, cond, if (note that these are not Built-In Procedures). We will work on implementing do_?_form functions in a future part.

• scheme_apply applies a procedure to some arguments.

In scheme_classes.py:

• The Frame class represents frames, and each frame also represents an environment starting with that frame.
• The LambdaProcedure class represents user-defined procedures.

IMPORTANT NOTE: Since all non-atomic Scheme expressions (i.e., call expressions, special forms, definitions) are Scheme lists (and therefore linked lists), we use the Link class to represent them. For example, the expression (+ 1 2) will be represented in our interpreter as Link('+', Link(1, Link(2, nil))). More complicated expressions can be represented with nested Links. For example, the expression(+ 1 (* 2 3)) will be represented as Link('+', Link(1, Link(Link('*', Link(2, Link(3, nil))), nil))).

Use Ok to test your understanding:

python3 ok -q eval_apply -u
Copy
✂️

Problem 1 (1 pt)

Implement the define and lookup methods of the Frame class in scheme_classes.py.

Each Frame object has the following instance attributes:

• bindings is a dictionary representing the bindings in the frame instance. Each item associates a Scheme symbol (represented as a Python string) to a Scheme value.
• parent is the parent Frame instance (parent environment frame). The parent of the Global Frame is None.

To complete these methods:

1. define takes a symbol (represented by a Python string) and a value. It binds the symbol to the value in the Frame instance using bindings.

2. lookup takes a symbol and returns the value bound to that symbol in the first frame of the environment where it is found. The environment for a Frame instance consists of that frame, its parent frame, and all its ancestor frames, including the Global Frame. When looking up a symbol:

   • If the symbol is bound in the current frame, return its value.
   • If the symbol is not bound in the current frame and the frame has a parent frame, continue looking up the symbol in the parent frame.
   • Keep checking all parent frames until either the symbol is found or there are no more parent frames.
   • If the symbol is never found in any frame, raise a SchemeError.

Before writing any code, unlock the tests to verify your understanding of the question:

python3 ok -q 01 -u
Copy
✂️

Once you are done unlocking, begin implementing your solution. You can check your correctness with:

python3 ok -q 01
Copy
✂️

After you complete this problem, start your Scheme interpreter (with python3 scheme.py) and you should now be able to look up built-in procedure names:

scm> +
#[+]
scm> odd?
#[odd?]

However, your Scheme interpreter will still not be able to call these procedures until you complete the next problem.

Remember, at this point, you can only exit the interpreter by pressing Ctrl-d on Max/Linux (or Ctrl-z Enter on Windows).

Problem 2 (2 pt)

To be able to call built-in procedures, such as +, you need to complete the BuiltinProcedure case within the scheme_apply function in scheme_eval_apply.py. Built-in procedures are applied by calling a corresponding Python function that implements the procedure.

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

A BuiltinProcedure has two instance attributes:

• py_func: the Python function that implements the built-in Scheme procedure.
• need_env: a Boolean that indicates whether or not this built-in procedure will need the current environment to be passed in as the last argument. The environment is required, for instance, to implement the built-in eval procedure.

scheme_apply takes the procedure object, a linked list of argument values args, and the current environment env. The args argument is a Scheme list, represented as a Link object or nil, containing the values passed to the procedure. For example, if the Scheme built-in procedure we are trying to use is + and we pass in args as Link(1, Link(2, nil)) to scheme_apply, we would be making the call (+ 1 2).

Your implementation should do the following:

• Convert the Scheme list to a Python list of arguments. Hint: args is a Link, which has .first and .rest attributes.
• If procedure.need_env is True, then add the current environment env to the end of this list.
• Return the result of calling procedure.py_func on all of those arguments. Since you don't know the exact number of arguments, use *args notation: f(1, 2, 3) is equivalent to f(*[1, 2, 3]). Do this part within the try statement provided, after the line that says try:.

We have already implemented the following behavior for you:

• If calling the function results in a TypeError exception being raised, then the wrong number of arguments were passed. The try statement handles this exception and raises a SchemeError with the message 'incorrect number of arguments'.

Before writing any code, unlock the tests to verify your understanding of the question:

python3 ok -q 02 -u
Copy
✂️

Once you are done unlocking, begin implementing your solution. You can check your correctness with:

python3 ok -q 02
Copy
✂️

👩🏽‍💻👨🏿‍💻 Pair programming? Remember to alternate between driver and navigator roles. The driver controls the keyboard; the navigator watches, asks questions, and suggests ideas.

Problem 3 (2 pt)

The scheme_eval function (in scheme_eval_apply.py) evaluates a Scheme expression in an environment. The provided code already looks up symbols in the current environment, returns self-evaluating expressions (such as numbers), and evaluates special forms.

Implement the missing part of scheme_eval, which evaluates a call expression. To evaluate a call expression:

1. Evaluate the operator (which should evaluate to a Procedure instance – see scheme_classes.py for Procedure definitions).
2. Evaluate all of the operands and collect the results (the argument values) in a Scheme list.
3. Return the result of calling scheme_apply on this Procedure, these argument values, and the current environment.

You'll have to recursively call scheme_eval in the first two steps. Here are some other functions/methods you should use:

• The map_link function returns a new Scheme list constructed by applying a one-argument Python function to every item in a Scheme list.
• The scheme_apply function applies a Scheme procedure to arguments represented as a Scheme list (a Link instance or nil).

Important: do not mutate the passed-in expr. That would change a program as it's being evaluated, creating strange and incorrect effects.

Before writing any code, unlock the tests to verify your understanding of the question:

python3 ok -q 03 -u
Copy
✂️

Once you are done unlocking, begin implementing your solution. You can check your correctness with:

python3 ok -q 03
Copy
✂️

Some of the unlocking tests call a primitive (built-in) procedure called print-then-return. This procedure doesn't exist in Scheme, but was added to this project just to test this question. print-then-return takes two arguments. It prints out its first argument and returns the second. If you're interested, you can find this function at the bottom of scheme_builtins.py

Your interpreter should now be able to evaluate built-in procedure calls, giving you the functionality of the Calculator language and more. Run python3 scheme.py, and you can now add and multiply!

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

Problem 4 (2 pt)

The define special form (spec) in Scheme can be used either to assign the value of a given expression to a symbol or to create a procedure and bind it to a symbol:

scm> (define a (+ 2 3))  ; Binds the symbol a to the value of expression (+ 2 3)
a
scm> (define (foo x) x)  ; Creates a procedure and binds it to the symbol foo
foo

Notice that the type of the first operand can tell us what is being defined:

• If it is a symbol, e.g. a, then the expression is defining a symbol.
• If it is a Scheme list, e.g. (foo x), then the expression is creating a procedure.

The do_define_form function in scheme_forms.py evaluates (define ...) expressions. There are two missing parts in this function; one for when the first operand is a symbol, and the other for when it is a Scheme list (i.e. Link). For this problem, implement just the first part, which evaluates the second operand to obtain a value and binds the first operand, a symbol, to that value. Then, do_define_form returns the symbol that was bound.

Hint: The define method of a Frame instance creates a binding in that frame.

Before writing any code, unlock the tests to verify your understanding of the question:

python3 ok -q 04 -u
Copy
✂️

Once you are done unlocking, begin implementing your solution. You can check your correctness with:

python3 ok -q 04
Copy
✂️

You should now be able to assign values to symbols and evaluate those symbols.

scm> (define x 15)
x
scm> (define y (* 2 x))
y
scm> y
30

The following ok test determines whether the operator of a call expression is evaluated multiple times. The operator should be evaluated only a single time before raising an error (because x is not bound to a procedure).

(define x 0)
; expect x
((define x (+ x 1)) 2)
; expect SchemeError
x
; expect 1

If the operator is evaluated twice, then x will be bound to 2 instead of 1 at the end, causing the test to fail. Therefore, if your code fails this test, you'll want to make sure you only evaluate the operator of a call expression once in scheme_eval.

Problem 5 (1 pt)

In Scheme, you can quote expressions in two ways: with the quote special form (spec) or with the symbol '. The reader converts '... into (quote ...), so that your interpreter only needs to evaluate the (quote ...) syntax. The quote special form returns its operand expression without evaluating it:

scm> (quote hello)
hello
scm> '(cons 1 2)  ; Equivalent to (quote (cons 1 2))
(cons 1 2)

Implement the do_quote_form function in scheme_forms.py so that it simply returns the unevaluated operand of the (quote ...) expression.

Before writing any code, unlock the tests to verify your understanding of the question:

python3 ok -q 05 -u
Copy
✂️

Once you are done unlocking, begin implementing your solution. You can check your correctness with:

python3 ok -q 05
Copy
✂️

After completing this function, you should be able to evaluate quoted expressions. Try out some of the following in your interpreter!

scm> (quote a)
a
scm> (quote (1 2))
(1 2)
scm> (quote (1 (2 three (4 5))))
(1 (2 three (4 5)))
scm> (car (quote (a b)))
a
scm> 'hello
hello
scm> '(1 2)
(1 2)
scm> '(1 (2 three (4 5)))
(1 (2 three (4 5)))
scm> (car '(a b))
a
scm> (eval (cons 'car '('(1 2))))
1
scm> (eval (define tau 6.28))
6.28
scm> (eval 'tau)
6.28
scm> tau
6.28

Submit your Phase 1 checkpoint

Check to make sure that you completed all the problems in Phase 1:

python3 ok --score

Then, submit scheme_eval_apply.py, scheme_forms.py, scheme_classes.py, and questions.scm to the Scheme Checkpoint 1 assignment on Pensieve before the first checkpoint deadline.

When you run ok commands, you'll still see that some tests are locked because you haven't completed the whole project yet. You'll get full credit for the checkpoint if you complete all the problems up to this point.

Phase 2: Procedures

In Phase 2, you will add the ability to create and call user-defined procedures. You will add the following features to the interpreter:

• Lambda procedures, using the (lambda ...) special form
• Named procedures, using the (define (...) ...) special form
• Dynamically scoped mu procedures, using the (mu ...) special form.

Problem 6 (1 pt)

Change the eval_all function in scheme_eval_apply.py (which is called from do_begin_form in scheme_forms.py) to complete the implementation of the begin special form (spec).

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.

To complete the implementation of begin, eval_all will take in expressions (a Scheme list of expressions) and env (a Frame representing the current environment), evaluate all the expressions in expressions, and return the value of the last expression in expressions.

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

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

Before writing any code, unlock the tests to verify your understanding of the question:

python3 ok -q 06 -u
Copy
✂️

Once you are done unlocking, begin implementing your solution. You can check your correctness with:

python3 ok -q 06
Copy
✂️

👩🏽‍💻👨🏿‍💻 Pair programming? This would be a good time to switch roles. Switching roles makes sure that you both benefit from the learning experience of being in each role.

User-Defined Procedures

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

• formals: a Scheme list containing the formal parameter names for the arguments of the lambda procedure.
• body: a nested Scheme list of expressions representing the body of the procedure.
• env: the environment in which the procedure was defined.

For example, in (lambda (x y) (+ x y)), formals is Link('x', Link('y', nil)). body is Link(Link('+', Link('x', Link('y', nil))), nil), which is a nested Scheme list where the first element (body.first) is the expression (+ x y) represented as Link('+', Link('x', Link('y', nil))). body is nested to allow for complex expressions and nested function calls.

Problem 7 (2 pt)

Implement the do_lambda_form function (spec) in scheme_forms.py, which creates and returns a LambdaProcedure instance.

In Scheme, the body of a procedure can contain multiple expressions, but must include at least one. The body attribute of a LambdaProcedure instance is a nested Scheme list of these expressions, and the formals attribute is a Link. Like a begin special form, evaluating the body of a procedure executes all expressions in order. A procedure returns the value of its last body expression.

Before writing any code, unlock the tests to verify your understanding of the question:

python3 ok -q 07 -u
Copy
✂️

Once you are done unlocking, begin implementing your solution. You can check your correctness with:

python3 ok -q 07
Copy
✂️

While you cannot call a user-defined procedure yet, you can visually verify that you have created the procedure correctly by evaluating a lambda expression in your interpreter.

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

Problem 8 (2 pt)

Implement the make_child_frame method of the Frame class (in scheme_classes.py), which will be used to create new frames when calling user-defined procedures. This method takes in two arguments: formals, which is a Scheme list of symbols (ex: Link('x', Link('y', nil))), and vals, which is a Scheme list of values (ex: Link(3, Link(5, nil))). It should return a new child frame with the formal parameters bound to the values.

To do this:

• If the number of argument values does not match with the number of formal parameters, raise a SchemeError.
• Create a new Frame instance that is the child of this frame (called self).
• Bind each formal parameter to its corresponding value in the newly created frame. The first symbol in formals should be bound to the first value in vals, and so on. Remember that formals and vals are Links.
• Return the new frame.

Hint: The define method of a Frame instance creates a binding in that frame.

Before writing any code, unlock the tests to verify your understanding of the question:

python3 ok -q 08 -u
Copy
✂️

Once you are done unlocking, begin implementing your solution. You can check your correctness with:

python3 ok -q 08
Copy
✂️

Problem 9 (2 pt)

Implement the LambdaProcedure case in the scheme_apply function in scheme_eval_apply.py. This elif block is executed when the procedure being applied is a LambdaProcedure instance.

First create a new Frame instance and bind the procedure's formal parameters to the argument values by calling the make_child_frame method on the appropriate parent frame.

Then, within this new frame, evaluate each of the expressions of the body of the procedure using eval_all.

Hint: Your new frame should be a child of the frame in which the lambda was defined. The env provided as an argument to scheme_apply is instead the frame in which the procedure was called.

See User-Defined Procedures to remind yourself of the attributes of LambdaProcedure.

Before writing any code, unlock the tests to verify your understanding of the question:

python3 ok -q 09 -u
Copy
✂️

Once you are done unlocking, begin implementing your solution. You can check your correctness with:

python3 ok -q 09
Copy
✂️

Problem 10 (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)))
f

However, we'd like to be able to use the shorthand form of defining named procedures, which is what we've been doing in homeworks and labs:

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

Modify the do_define_form function in scheme_forms.py so that it correctly handles define (...) ...) expressions (spec).

Make sure that it can handle multi-expression bodies. For example,

scm> (define (g y) (print y) (+ y 1))
g
scm> (g 3)
3
4

There are (at least) two ways to solve this problem. One is to construct an expression (define _ (lambda ...)) and call do_define_form on it (omitting the define). The second is to implement it directly:

• Using the given variables signature and expressions, find the defined function's name (symbol), formals, and body.
• Create a LambdaProcedure instance using the formals and body. (You could call do_lambda_form to do this.)
• Bind the symbol to this new LambdaProcedure instance.
• Return the symbol that was bound.

Doctest Walkthrough: Consider the doctest do_define_form(read_line("((f x) (+ x 2))"), env). This is the Python call that will evaluate (define (f x) (+ x 2)) in Scheme. read_line is a utility function that takes in "((f x) (+ x 2))" and returns its Link representation. Therefore, that Link representation is passed into do_define_form as its expressions parameter.

Hint for Way 2: How can we utilize the Scheme list representation of ((f x) (+ x 2)) (the structure for (define (f x) (* x 2))) to have the same functionality as (define f (lambda (x) (+ x 2))), which we know our Scheme interpreter (and thus our Python code) can already handle? Try writing out the Scheme list representation yourself and consider what components you would need to extract from it in order to be able to replicate the functionality of (define f (lambda (x) (+ x 2))) in Python within do_define_form.

Before writing any code, unlock the tests to verify your understanding of the question:

python3 ok -q 10 -u
Copy
✂️

Once you are done unlocking, begin implementing your solution. You can check your correctness with:

python3 ok -q 10
Copy
✂️

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

• Creating procedures using lambda expressions,
• Defining named procedures using define expressions, and
• Calling user-defined procedures.

Submit your Phase 1 & 2 checkpoint

Check to make sure that you completed all the problems in Phase 1 and 2:

python3 ok --score

Then, submit scheme_eval_apply.py, scheme_forms.py, scheme_classes.py, and questions.scm to the Scheme Checkpoint 2 assignment on Pensieve before the checkpoint deadline.

When you run ok commands, you'll still see that some tests are locked because you haven't completed the whole project yet. You'll get full credit for the checkpoint if you complete all the problems up to this point.

Phase 3: Mu and Logical Forms

Problem 11 (1 pt)

All of the Scheme procedures we've seen so far use lexical scoping: the parent of the new call frame is the environment in which the procedure was defined. Another type of scoping, which is not standard in Scheme but appears in other variants of Lisp, is called dynamic scoping: the parent of the new call frame is the environment in which the call expression was evaluated. With dynamic scoping, calling the same procedure with the same arguments from different parts of your code can create different behavior (due to different parent frames).

The mu special form (spec; invented for this project) evaluates to a dynamically scoped procedure.

scm> (define f (mu () (* a b)))
f
scm> (define g (lambda () (define a 4) (define b 5) (f)))
g
scm> (g)
20

Above, the procedure f does not have a or b as arguments; however, because f gets called within the procedure g, it has access to the a and b defined in g's frame.

Your job:

• Implement do_mu_form in scheme_forms.py to evaluate the mu special form. A mu expression evaluates to a MuProcedure. The MuProcedure class (defined in scheme_classes.py) has been provided for you.
• In addition to implementing do_mu_form, complete the MuProcedure case within the scheme_apply function (in scheme_eval_apply.py) so that when a mu procedure is called, its body is evaluated in the correct environment. When a MuProcedure is called, the parent of the new call frame is the environment in which that call expression was evaluated. As a result, a MuProcedure does not need to store an environment as an instance attribute. Your code here should be VERY similar to what you did for question 9.

Before writing any code, unlock the tests to verify your understanding of the question:

python3 ok -q 11 -u
Copy
✂️

Once you are done unlocking, begin implementing your solution. You can check your correctness with:

python3 ok -q 11
Copy
✂️

This rest of the section will be completed in scheme_forms.py.

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 #f is a false value. All other values (including 0 and nil) are true values. You can test whether a value is a true or false value using the provided Python functions is_scheme_true and is_scheme_false, defined in scheme_utils.py.

Scheme traditionally uses #f to indicate the false Boolean value. In our interpreter, that is equivalent to false or False. Similarly, true, True, and #t are all equivalent. However, when unlocking tests, use #t and #f.

To get you started, we've provided an implementation of the if special form in the do_if_form function.

Problem 12 (2 pt)

Implement do_and_form and do_or_form so that and and or expressions (spec) 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 is a false value, return that value. Otherwise, return the value of the last sub-expression. If there are no sub-expressions in an and expression, it evaluates to #t.

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

In your code here, you should represent Scheme's #t as Python's True and Scheme's #f as Python's False.

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

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

Important: Use the provided Python functions is_scheme_true and is_scheme_false from scheme_utils.py to test boolean values.

Before writing any code, unlock the tests to verify your understanding of the question:

python3 ok -q 12 -u
Copy
✂️

Once you are done unlocking, begin implementing your solution. You can check your correctness with:

python3 ok -q 12
Copy
✂️

Additional Scheme Tests (1 pt)

Your final task in Part III of this project is to make sure that your scheme interpreter passes the additional suite of tests we have provided.

To run these tests (worth 1 point), run the command:

python3 ok -q tests.scm

If you have passed all of the required cases, you should see 1/1 points received for tests.scm when you run python3 ok --score. If you are failing tests due to output from print statements you've added in your code for debugging, make sure to remove those as well for the tests to pass.

Congratulations! Your Scheme interpreter implementation is now complete!

Phase 4: 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 the questions.scm file, which will complete the implementation of the game of Schémémon.

See the built-in procedure reference for descriptions of the behavior of all built-in Scheme procedures.

To help you write Scheme, you can use the online Scheme interpreter or run python3 editor to open a window in your browser and use a web-based Scheme editor created by former student Rahul Arya. If a browser window doesn't open automatically, navigate to localhost:31415.

Make sure to run python3 ok in a separate tab or window so that the editor keeps running.

👩🏽‍💻👨🏿‍💻 Pair programming? Remember to alternate between driver and navigator roles. The driver controls the keyboard; the navigator watches, asks questions, and suggests ideas.

If you want to use cond for Problems 13, 14, or 15, you must implement Problem EC1 for your tests to run.

Problem 13 (1 pt)

Implement the (enumerate s) procedure, which takes in a list of values s 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. Set the first index to 0.

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

Use Ok to test your code:

python3 ok -q 13
Copy
✂️

Problem 14 (3 pt)

A dictionary list is a Scheme list of pairs ((key value) (key value) ... (key value)) where each key is a unique symbol.

Implement (get dict key), a scheme procedure that takes a dictionary list dict and a value key that appears as the first element in some pair within dict. The get procedure returns the value paired with key. If key is not the first value in a pair within dict, return #f.

Then, implement (set dict key value), a scheme procedure that takes a dictionary list dict and key and value values. If key is a key in dict, then it returns a new dictionary-list that is the same length as dict but has value as the value paired with key. If key is not a key in dict, then it returns a dictionary list with all of the key-value pairs in dict as well as a new pair at the end containing (key value). Assume that no key appears more than once in dict.

scm> (define dict-list '((a 1) (b 2) (c 3)))
dict-list
scm> (get dict-list 'b)
2
scm> (get dict-list 'e)
#f
scm> (set dict-list 'b 4)
((a 1) (b 4) (c 3))
scm> (set dict-list 'x 0)
((a 1) (b 2) (c 3) (x 0))

Use Ok to test your code:

python3 ok -q 14
Copy
✂️

Problem 15 (3 pt)

In Schémémon, before taking an action, you have the option to solve a Scheme programming problem. Correctly answering the problem will double the damage you deal during your turn and prevent you from missing! The programming problems all consist of a description followed by a define form with a blank. For example,

Implement factorial(), which takes an integer "n" and outputs the value of "n"!.

(define (factorial n)
    (if (= n 0)
        1
        (* n _____)
    )
)

Implement solution-code, a scheme procedure that takes in a Scheme list problem that contains a Scheme expression with a blank, as well as a Scheme expression solution. It returns the result of replacing the five-underscore blank _____ with the solution. If there are multiple blanks, they should each be replaced by the same solution expression.

scm> (define add-problem '(define (add x y) _____))
add-problem
scm> (define add-sol '(+ x y))
add-sol
scm> (solution-code add-problem add-sol)
(define (add x y) (+ x y))

Use Ok to test your code:

python3 ok -q 15
Copy
✂️

Play Schémémon

Once you complete your Scheme interpreter and implement solution-code, you can run Schémémon on your own computer with python3 schememon.py. It will use your interpreter to check whether double-damage Scheme problems are answered correctly.

Conclusion

Congratulations, you have reached the end of your last CS 61A project! You have just implemented an interpreter for an entire language! If you enjoyed this project and want to extend it further, you may be interested in looking at more advanced features, like let* and letrec, unquote splicing, error tracing, and continuations.

Project Submission

Run ok on all problems to make sure all tests are unlocked and pass:

python3 ok

You can also check your score on each part of the project:

python3 ok --score

Once you are satisfied, submit scheme_eval_apply.py, scheme_forms.py, scheme_classes.py, and questions.scm to the Scheme assignment on Pensieve before the Tuesday 11/25 deadline. Only one partner needs to submit and then add the other partner to the submission.

Extra Challenge

During Office Hours and Project Parties, the staff will prioritize helping students with required questions. We will not be offering help with this question unless the queue is empty.

Problem EC 1 (0 pts)

Fill in the missing parts of do_cond_form so that it correctly implements cond (spec), returning the value of the first result sub-expression corresponding to a true predicate, or the value of the result sub-expression corresponding to else.

Some special cases:

• When the true predicate does not have a corresponding result sub-expression, return the predicate value.
• When a result sub-expression of a cond case has multiple expressions, evaluate them all and return the value of the last expression. (Hint: Use eval_all.)

Your implementation should match the following examples and the additional tests in tests.scm.

scm> (cond ((= 4 3) 'nope)
           ((= 4 4) 'hi)
           (else 'wait))
hi
scm> (cond ((= 4 3) 'wat)
           ((= 4 4))
           (else 'hm))
#t
scm> (cond ((= 4 4) 'here (+ 40 2))
           (else 'wat 0))
42

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. If there is only an else, return the value of its result sub-expression. If it doesn't have one, return #t.

scm> (cond (False 1) (False 2))
scm> (cond (else))
#t

Use Ok to unlock and test your code:

python3 ok -q EC1 -u
python3 ok -q EC1
Copy
✂️

Problem EC 2 (0 pts)

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

scm> (define x 5)
x
scm> (define y 'bye)
y
scm> (let ((x 42)
           (y (* x 10)))  ; this 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 in scheme_forms.py, which returns a child frame of env that binds the symbol in each element of bindings to the value of its corresponding expression. The bindings Scheme list contains pairs that each contain a symbol and a corresponding expression.

You may find the following functions and methods useful:

• validate_form: this function can be used to validate the structure of each binding. It takes in a Scheme list expr of expressions and a min and max length. If expr is not a list with length between min and max inclusive, it raises an error. If no max is passed in, the default is infinity.
• validate_formals: this function validates that its argument is a Scheme list of symbols for which each symbol is distinct.

Hint: When building new linked lists iteratively, it may be easier to build it from right to left (or end to start).

Remember to refer to the spec if you don't understand any of the test cases!

Use Ok to unlock and test your code:

python3 ok -q EC2 -u
python3 ok -q EC2
Copy
✂️

In the next challenge, you will implement tail-call optimization, an essential feature of the Scheme language. Watch this playlist to learn about tail calls.

We will implement tail-call optimization in Scheme by using a technique called "trampolining" to tail-call optimize our scheme_eval function in Python.

First, let's begin with why optimizing the scheme_eval function will optimize the Scheme interpreter.

(define (foo n)
    (if (= n 0)
        0
        (foo (- n 1))))

(define (foo n)
    (if (= n 0)
        0
        (foo (- n 1))))

(define (f x)
    (define y (g x))
    (* x y))

(define (g x)
   (* 6 x))

(f 7)

>>> my_thunk1 = lambda: sqrt(16384) + 22
>>> my_thunk2 = lambda: some_costly_operation(1000)

>>> my_thunk1()
150.0
>>> my_thunk2()
# result of evaluating some_costly_operation(1000)

>>> my_nested_thunk = lambda: lambda: lambda: 4 * (2 + 3)
>>> thunk2 = my_nested_thunk()
>>> thunk3 = thunk2()
>>> result = thunk3()
>>> result
20

def trampoline(value):
    while callable(value): # While value is still a thunk
        value = value()
    return value

def tail_factorial(n, so_far=1):
    if n == 0:
        return so_far
    return tail_factorial(n - 1, so_far * n)

def thunk_factorial(n, so_far=1):
    def thunk():
        if n == 0:
            return so_far
        return thunk_factorial(n - 1, so_far * n)
    return thunk

def factorial(n):
    value = thunk_factorial(n)
    while callable(value): # While value is still a thunk
        value = value()
    return value

Problem EC 3 (0 pts)

Preface: This question is challenging and requires you to modify multiple areas in the interpreter without specifying where. We recommend taking the time to thoroughly understand all the concepts and develop a clear strategy before beginning to code.

Important: While working, continuously ensure that the code you write for this question does not cause other parts of the project to fail. If you find yourself losing track of your edits, it might be a good idea to save a copy of your original code for reference.

Complete the function optimize_tail_calls in scheme_eval_apply.py. It returns an alternative to scheme_eval that is tail-call optimized in Python. That is, it will allow an unbounded number of active tail calls to scheme_eval in constant space. It has a third argument tail that indicates whether the call to scheme_eval is a tail call or not.

The Unevaluated class represents an expression that needs to be evaluated in a specific environment. When optimized_eval receives a non-atomic expression in a tail context, it returns an instance of Unevaluated. Otherwise, optimized_eval should keep calling unoptimized_scheme_eval on the current expr and env until the result is a final value, rather than an Unevaluated instance.

After you are done implementing optimize_tail_calls, uncomment the following line in scheme_eval_apply.py to reassign the original scheme_eval to the optimized implementation:

scheme_eval = optimize_tail_calls(scheme_eval)

Finally, identify which calls to scheme_eval in your interpreter are tail calls. Modify those scheme_eval tail calls to pass in True as the third argument (the tail parameter) whenever applicable.

Note: A successful implementation will require changes to several other functions, including some functions that we provided for you.

Hints:

A call to scheme_eval is a tail call if it is the last thing to be done in a function before it returns.

Even within a function, not every call to scheme_eval will benefit from tail-call optimization. Consider which specific calls will benefit and pass True for the tail argument accordingly.

Use Ok to test your code:

python3 ok -q EC3
Copy
✂️