Required Problems

Today we will build PyCombinator, our own basic Python interpreter. By the end of this lab, you will be able to use a bunch of primitives such as add, mul, and sub, and even more excitingly, we will be able to create and call lambda functions -- all through your own homemade interpreter!

You will implement some of the key parts that will allow us to evaluate the following commands and more:

> add(3, 4)
7
> mul(4, 5)
20
> sub(2, 3)
-1
> (lambda: 4)()
4
> (lambda x, y: add(y, x))(3, 5)
8
> (lambda x: lambda y: mul(x, y))(3)(4)
12
> (lambda f: f(0))(lambda x: pow(2, x))
1

You can find the Read-Eval-Print Loop code for our interpreter in repl.py. Here is an overview of each of the REPL components:

  • Read: The function read in reader.py calls the following two functions to parse user input.
    • The lexer is the function tokenize in reader.py which splits the user input string into tokens.
    • The parser is the function read_expr in reader.py which parses the tokens and turns expressions into instances of subclasses of the class Expr in expr.py, e.g. CallExpr.
  • Eval: Expressions (represented as Expr objects) are evaluated to obtain values (represented as Value objects, also in expr.py).
    • Eval: Each type of expression has its own eval method which is called to evaluate it.
    • Apply: Call expressions are evaluated by calling the operator's apply method on the arguments. For lambda procedures, apply calls eval to evaluate the body of the function.
  • Print: The __str__ representation of the obtained value is printed.

In this lab, you will only be implementing the Eval and Apply steps in expr.py.

You can start the PyCombinator interpreter by running the following command:

python repl.py

Try entering a literal (e.g. 4) or a lambda expression, (e.g. lambda x, y: add(x, y)) to see what they evaluate to.

You can also try entering some names. You can see the entire list of names that we can use in PyCombinator at the bottom of expr.py. Note that our set of primitives doesn't include the operators +, -, *, / -- these are replaced by add, sub, etc.

Right now, any names (e.g. add) and call expressions (e.g. add(2, 3)) will output None. It's your job to implement Name.eval and CallExpr.eval so that we can look up names and call functions in our interpreter!

You don't have to understand how the read component of our interpreter is implemented, but if you want a better idea of how user input is read and transformed into Python code, you can use the --read flag when running the interpreter:

python repl.py --read
> add
Name('add')
> 3
Literal(3)
> lambda x: mul(x, x)
LambdaExpr(['x'], CallExpr(Name('mul'), [Name('x'), Name('x')]))
> add(2, 3)
CallExpr(Name('add'), [Literal(2), Literal(3)])

To exit the interpreter, type Ctrl-C or Ctrl-D.