Discussion 10: Interpreters
Switch to Pensieve:
- Everyone: Go to pensieve.co, log in with your @berkeley.edu email, and enter your group number (which was in the email that assigned you to this lab).
Once you're on Pensieve, you don't need to return to this page; Pensieve has all the same content (but more features). If for some reason Penseive doesn't work, return to this page and continue with the discussion.
Getting Started
To get help from a TA, If you do not have an in-person TA, you can reach your TA using this Zoom link.
If there are fewer than 3 people in your group, feel free to merge your group with another group in the room.
Everybody say your name, and then figure out who is planning to travel outside of the Bay Area the soonest. Feel free to discuss your travel plans.
Representing Lists
A Scheme call expression is a Scheme list that is represented using a Pair
instance in Python.
For example, the call expression (+ (* 3 4) 5) is represented as:
Pair('+', Pair(Pair('*', Pair(3, Pair(4, nil))), Pair(5, nil)))
The Pair class and nil object are defined in pair.py of the Scheme project.
class Pair:
"A Scheme list is a Pair in which rest is a Pair or nil."
def __init__(self, first, rest):
self.first = first
self.rest = rest
... # There are also __str__, __repr__, and map methods, omitted here.Q1: Representing Expressions
Write the Scheme expression in Scheme syntax represented by each Pair below.
Try drawing the linked list diagram too. The first one is done for you.
Pair('+', Pair(Pair('*', Pair(3, Pair(4, nil))), Pair(5, nil)))>>> Pair('+', Pair(1, Pair(Pair('*', Pair(2, Pair(3, nil))), nil)))
>>> Pair('and', Pair(Pair('<', Pair(1, Pair(0, nil))), Pair(Pair('/', Pair(1, Pair(0, nil))), nil)))
Answer 1: (+ (* 3 4) 5)
Answer 2: (+ 1 (* 2 3))
Answer 3: (and (< 1 0) (/ 1 0))
Discussion Time: What does (and (< 1 0) (/ 1 0)) evaluate to? Discuss among
your group until you all agree.
#f
Evaluation
To evaluate the expression (+ (* 3 4) 5) using the Project 4 interpreter,
scheme_eval is called on the following expressions (in this order):
(+ (* 3 4) 5)+(* 3 4)*345
Discussion time: Describe to each other why * is evaluated and what it
evaluates to.
The * is evaluated because it is the operator sub-expression of (* 3 4),
which is an operand sub-expression of (+ (* 3 4) 5).
By default, * evaluates to a procedure that multiplies its arguments together.
But * could be redefined at any time, and so the symbol * must be evaluated
each time it is used in order to look up its current value.
scm> (* 2 3) ; Now it multiplies
6
scm> (define * +)
*
scm> (* 2 3) ; Now it adds
5An if expression is also a Scheme list represented using a Pair instance.
For example, (if (< x 0) (- x) x) is represented as:
Pair('if', Pair(Pair('<', Pair('x', Pair(0, nil))), Pair(Pair('-', Pair('x', nil)), Pair('x', nil))))
To evaluate this expression in an environment in which x is bound to 2 (and
< and - have their default values), scheme_eval is called on the following
expressions (in this order):
(if (< x 0) (- x) x)(< x 0)<x0x
Presentation time: Come up with a short explanation of why neither if nor
- are evaluated even though they both appear in (if (< x 0) (- x) x). Once
your group agrees on an answer (or wants help), pick someone who hasn't presented to the course staff recently to share your group's answer with your TA (in person or on Zoom).
The symbol if is not evaluated because it is the start of a special form, not
part of a call expression. The symbols that introduce special forms (and,
if, lambda, etc.) are never evaluated.
The symbol - is not evaluated, nor is the whole sub-expression (- x) that it
appears in, because (< x 0) evaluates to #f. If you're still not certain
why some parts are evaluated and some aren't, ask the course staff.
Q2: Evaluation
(Note: Some past exams have had a question in exactly this format.)
Which of the following are evaluated when scheme_eval is called on
(if (< x 0) (- x) (if (= x -2) 100 y)) in an environment in which x is bound to -2?
(Assume <, -, and = have their default values.)
if<=xy0-2100-()
With x bound to -2, (< x 0) evaluates to #t, and so (- x) will be
evaluated, but (if (= x 1) 100 x) will not. The operator and operands of a
call expression are evaluated for every call expression that is evaluated.
(< x 0) and (- x) are both call expressions.
Q3: Print Evaluated Expressions
Define print_evals, which takes a Scheme expression expr that contains only
numbers, +, *, and parentheses. It prints all of the expressions that are
evaluated during the evaluation of expr. They are printed in the order that
they are passed to scheme_eval.
Note: Calling print on a Pair instance will print the Scheme expression it represents.
>>> print(Pair('+', Pair(Pair('*', Pair(3, Pair(4, nil))), Pair(5, nil))))
(+ (* 3 4) 5) def print_evals(expr):
"""Print the expressions that are evaluated while evaluating expr.
expr: a Scheme expression containing only (, ), +, *, and numbers.
>>> nested_expr = Pair('+', Pair(Pair('*', Pair(3, Pair(4, nil))), Pair(5, nil)))
>>> print_evals(nested_expr)
(+ (* 3 4) 5)
+
(* 3 4)
*
3
4
5
>>> print_evals(Pair('*', Pair(6, Pair(7, Pair(nested_expr, Pair(8, nil))))))
(* 6 7 (+ (* 3 4) 5) 8)
*
6
7
(+ (* 3 4) 5)
+
(* 3 4)
*
3
4
5
8
"""
if not isinstance(expr, Pair):
print(expr)
else:
print(expr)
while expr is not nil:
print_evals(expr.first)
expr = expr.rest
If expr is not a pair, then it is a number or '+' or '*'. In all of these
cases, the expr should be printed to indicate that it would be evaluated.
If expr is a pair, then it is a call expression. Print it. Then, the operator
and operands are evaluated. These are the elements in the list expr. So,
iterate through expr (using either a while statement or expr.map(...)) and
call print_evals on each element.
Document the Occasion
Please all fill out the attendance form (one submission per person per week).