Interpreters
- The scheme interpreter represents expressions as Pairs.
- For the operands, we must evaluate each of the values individually. This is because we may have compound expressions, where operands themselves may be expressions,
- Within an interpreter, we have an
evaland anapplyeval: evaluates values and expressionsapply: Applies operands to an operator
- Both eval and apply may call each other. Eval requires a working environment, Apply needs to create an environment.
Eval
- Base cases:
- Primitive values (numbers)
- Look up values in the environment bound to symbols
- Recursive calls:
- Eval(operator, operands) of call expressions
- Apply(procedure, arguments)
- Eval(sub-expressions) of special forms
Apply
- Base cases:
- Built-in primitive procedures
- Recursive calls:
- Eval(body) of user-defined procedures
Steps of an interpreter
- Tokenization/Parsing: Converts text ito Python representation of Scheme expressions:
- Numbers are represented as numbers
- Symbols are represented as strings
- Lists are represented as instances of the Pair class
- Evaluation: Converts scheme expressions to values while executing side effects.
- Ex: Return the symbol of a define expression
1
2
3
4
5
6
7
def symbol(exp):
assert exp.first == 'define' and exp.rest is not nil and exp.rest.rest is not nil
signature = exp.rest.first
if scheme_symboolp(signature):
return signature
else:
return signature.first
Scehem Evaluation
- The
scheme+evalfunction chooses behavior based on expression form:- Symbols are looked up in the current environment
- Self-evaluating expressions are returned as values
- All other legal expressions are represented as Scheme lists, called combinations
Lambda Expressions
- Lambda expressions evaluate to user-defined procedures
(lambda (formal parameters) (<body>))
- It is represented in Python through a
LambdaProcedureclass.
1
2
3
4
5
class LambdaProcedure:
def __init__(self, formals, body, env):
self.formals = formals # A scheme list of symbols
self.body = body # A scheme list of expressions
self.env = env # A frame instance
Frames and Environments
- A frame represents an environment by having a parent frame
- Frames are Python intsnace with methods
lookupanddefine
1
2
3
4
5
6
7
8
9
g = Frame(None)
f = Frame(g)
g.define('y', 3)
g.define('z', 5)
f.define('x', 2)
f.define('z', 4)
g.lookup('y') # 3
f.lookup('x') # 2
f.lookup('z') # 4