Problem 3 (200pts): scheme_eval

The scheme_eval function (in scheme_eval_apply.py) evaluates a Scheme expression (represented as a Pair) in a given environment. The provided code already looks up names 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 an instance of Procedure)
  2. Evaluate all of the operands
  3. Apply the procedure on the evaluated operands by calling scheme_apply, then return the result

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

  • The map method of Pair returns a new Scheme list constructed by applying a one-argument function to every item in a Scheme list.
  • The scheme_apply function applies a Scheme procedure to arguments represented as a Scheme list (a Pair instance).

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

Use Ok to unlock and test your code:

python ok -q 03 -u
python ok -q 03

Some of these 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.

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

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