Due by 11:59pm on Friday, November 8.
By the end of this lab, you should have submitted the lab with
python3 ok --submit. You may submit more than once before the
deadline; only the final submission will be graded.
Check that you have successfully submitted your code on
Consult this section if you need a refresher on the material for this lab. It's okay to skip directly to the questions and refer back here should you get stuck.
An interpreter is a program that allows you to interact with the computer in a certain language. It understands the expressions that you type in through that language, and performs the corresponding actions in some way, usually using an underlying language.
In Project 4, you will use Python to implement an interpreter for Scheme. The Python interpreter that you've been using all semester is written (mostly) in the C programming language. The computer itself uses hardware to interpret machine code (a series of ones and zeros that represent basic operations like adding numbers, loading information from memory, etc).
When we talk about an interpreter, there are two languages at work:
- The language being interpreted/implemented. In this lab, you will implement the PyCombinator language.
- The underlying implementation language. In this lab, you will use Python to implement the PyCombinator language.
Note that the underlying language need not be different from the implemented language. In fact, in this lab we are going to implement a smaller version of Python (PyCombinator) using Python! This idea is called Metacircular Evaluation.
Many interpreters use a Read-Eval-Print Loop (REPL). This loop waits for user input, and then processes it in three steps:
Read: The interpreter takes the user input (a string) and passes it through a lexer and parser.
- The lexer turns the user input string into atomic pieces (tokens) that are like "words" of the implemented language.
- The parser takes the tokens and organizes them into data structures that the underlying language can understand.
Eval: Mutual recursion between eval and apply evaluate the expression to obtain a value.
- Eval takes an expression and evaluates it according to the rules of the
language. Evaluating a call expression involves calling
applyto apply an evaluated operator to its evaluated operands.
- Apply takes an evaluated operator, i.e., a function, and applies it to
the call expression's arguments. Apply may call
evalto do more work in the body of the function, so
applyare mutually recursive.
- Eval takes an expression and evaluates it according to the rules of the language. Evaluating a call expression involves calling
- Print: Display the result of evaluating the user input.
Here's how all the pieces fit together:
+-------------------------------- Loop -----------+ | | | +-------+ +--------+ +-------+ +-------+ | Input ---+->| Lexer |-->| Parser |-->| Eval |-->| Print |-+--> Output | +-------+ +--------+ +-------+ +-------+ | | ^ | | | | v | ^ +-------+ v | | Apply | | | REPL +-------+ | +-------------------------------------------------+