Part 1: The Evaluator

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

  • Symbol evaluation
  • Calling built-in procedures
  • Definitions

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

First, read the relevant code. In the "Eval/Apply" section of scheme_eval_apply.py:

  • scheme_eval evaluates a Scheme expression in the given environment. This function is nearly complete but is missing the logic for call expressions.
  • When evaluating a special form, scheme_eval redirects evaluation to an appropriate do_?_form function found in scheme_forms.py.
  • scheme_apply applies a procedure to some arguments. This function has cases for the various types of procedures (builtin procedures, user-defined procedures, and so forth) that you will implement.

In the "Environments and Procedures" section of scheme_classes.py:

  • The Frame class implements an environment frame.
  • The LambdaProcedure class (in the Procedures section) represents user-defined procedures.

These are all of the essential components of the interpreter. scheme_forms.py defines special forms, scheme_builtins.py defines the various functions built into the standard library, and scheme.py defines input/output behavior.

Use Ok to test your understanding:

$ python ok -q eval_apply -u