Class 34 - Finishing the Interpreter

Red Belt Test

The first opportunity to take the Red Belt test will be Monday, 25 April. The test will be take-home with limited resources (details will be explained on the exam). Passing the red belt level ensures at least an A- in the course.

To be eligible to take the Red Belt test, you need to complete Project 5 and Project 6 (turn in by class Friday to have a chance to be eligible on Monday).

The Red Belt level includes everything in the class through Monday, 25 April. This includes:

• Everything that was covered by the Blue Belt test.
• Classes, Objects, and Types (covered by Project 5 and in classes)
• Interpreters (Chapter 11 and Project 6 and classes)
• Modeling Computation (Turing Machines, Finite State Machines)
• Computability (Chapter 12 and Friday and Monday’s Classes)

Slides

Church-Turing Thesis

All mechanical computers are equally powerful (except for practical limits like memory size, time, display, energy, etc.).

How should we define power of a computing machine?

A Turing Machine (with the right program) can simulate any mechanical computer.
A Turing Machine (with the right program) can simulate a Python interpreter.
A Python interpreter (with the right program) can simulate a Turing Machine.
A Charme interpreter (with the right program) can simulate a Turing Machine.
A Charme interpreter (with the right program) can simulate a Python interpreter.
A Charme interpreter (with the right program) can simulate any mechanical computer.

What do we need to do to prove Charme is as powerful as Python?

Apply and Eval

To apply a constructed procedure:

1. Construct a new environment, whose parent is the environment of the applied procedure.

2. For each procedure parameter, create a place in the frame of the new environment with the name of the parameter. Evaluate each operand expression in the environment of the application and initialize the value in each place to the value of the corresponding operand expression.

3. Evaluate the body of the procedure in the newly created environment. The resulting value is the value of the application.

class Procedure:
    def __init__(self, params, body, env):
        self._params = params
        self._body = body
        self._env = env
    ...

def evalLambda(expr,env):
    assert isLambda(expr)
    if len(expr) != 3: evalError ('Bad lambda expression: ...')
    return Procedure(expr[1], expr[2], env)

def evalApplication(expr, env):
    subexprvals = [meval(sexpr, env) for sexpr in expr]
    return mapply(________________, ________________)

def mapply(proc, operands):
    if (isPrimitiveProcedure(proc)):
        return proc(operands)
    elif isinstance(proc, Procedure):
        params = proc.getParams()
        newenv = Environment(proc.getEnvironment())
        if len(params) != len(operands):
            evalError ('Parameter length mismatch: ...')
        for i in range(0, len(params)):
            newenv.addVariable(params[i], ___________)
        return meval(______________, newenv)        
    # error case