## Jupyter at Bryn Mawr College

Public notebooks: /services/public/dblank / CS245 Programming Languages / 2016-Fall / Notebooks

# 1. Summary of Lab03¶

If you save your notebook as a program (menu -> File -> Download as -> Python (.py)) then you can edit that file, removing everything but the final functions.

Then you can

from lab04 import *

Loaded lab04!


Just a quick review of the state of Lab03:

## 1.1 Lab03, Exercise 5:¶

In [2]:
scalc("(- 5 3)")

Out[2]:
2
In [3]:
scalc("(/ 6 3)")

Out[3]:
2.0

## 1.2 Lab03, Exercise 6:¶

In [4]:
scalc("(quote 42)")

Out[4]:
42
In [8]:
scalc("(quote (1 2 3))")

Out[8]:
[1, [2, [3, '()']]]

## 1.3 Lab03, Exercise 7¶

In [12]:
scalc("#t")

Out[12]:
1
In [7]:
scalc("(+ #t #f)")

Out[7]:
1

## 1.4 Lab03, Exercise 8¶

In [13]:
scalc("""(if 1 1 2)""")

Out[13]:
1
In [14]:
scalc("""(if #f 1 2)""")

Out[14]:
2
In [15]:
scalc("""(if #t 1 (/ 2 0))""")

Out[15]:
1

# 2. Sidebar: Readable Scheme Lists in Python¶

sexp (structured expressions) composed of cons cells represented in Python are hard to read!

In [11]:
sexp([1, 2, 3])

Out[11]:
[1, [2, [3, '()']]]
In [12]:
cons(1, cons(2, cons(3, "()")))

Out[12]:
[1, [2, [3, '()']]]
In [13]:
cons(1, cons( cons(2, 4), cons(3, "()")))

Out[13]:
[1, [[2, 4], [3, '()']]]

One solution is to subclass list, and override the __repr__ method:

In [16]:
class SchemeList(list):
def __repr__(self):
retval = ""
current = self
while isinstance(current, list):
if retval:
retval += " "
retval += str(car(current))
current = cdr(current)
if current != "()": # proper list
if retval:
retval += " "
retval += ". %s" % current
return "(%s)" % retval

In [18]:
SchemeList(sexp([1, 2, 3]))

Out[18]:
(1 2 3)
In [17]:
SchemeList([1, [SchemeList([2, 4]), [3, "()"]]])

Out[17]:
(1 (2 . 4) 3)

then you only need use this method when you make a cons cell:

In [19]:
def cons(a, b):
return SchemeList([a, b])


And voila!

In [20]:
from lab05 import *

In [21]:
scalc("(quote (1 2 3))")

Out[21]:
(1 2 3)

Compared to [1, [2, [3, '()']]] the Scheme-like repr of (1 2 3) looks quite nice! But remember that (1 2 3) really means [1, [2, [3, '()']]].

# 3. Moving Function Definitions to an Environment¶

Currently, we have:

def evaluator_apply(op, operands):
if op == "print":
Print(operands)
elif op == "+":
else:
raise Exception("unknown apply operator: %s" % op)


What we would like to do is add all of those definitions of functions to an environment. Then a language can add to them, remove them, and change them. Then op can just be an actual Python function:

def evaluator_apply(op, operands):
return op(operands)


To do this, we need to have an "environment" where the symbols (such as "print" and "+") can be associated with their actual functions. We will define an environment (or env for short) as a list of frames where a frame is a list of symbol-function pairs, such as:

In [19]:
top_level_env = [
# a frame:
[
["print", Print],
],
]


A frame is a list of bindings. We say that "+" is bound the the add_prim function. add_prim is the value bound to the symbol "+".

def lookup(symbol, env):
"""
Lookup a symbol in an environment
"""
if ...:
return ...
else:
raise Exception("no such variable: %s" % symbol)

In [20]:
lookup("print", top_level_env)

Out[20]:
<function lab05.Print>
In [21]:
temp_function = lookup("print", top_level_env)
temp_function(sexp([1, 2, 3]))

1
2
3

def evaluator(expr, env):
if car(expr) == "lit-exp":
elif car(expr) == "var-exp": ## NOW: look it up
else:
raise Exception("invalid ast: %s" % expr)

In [22]:
evaluator(scalc_parse("+"), top_level_env)

Out[22]:
<function lab05.add_prim>
In [23]:
scalc("(+ 5 4)")

Out[23]:
9
In [24]:
top_level_env = [
# a frame:
[
["print", Print],
["pi", math.pi],
],
]

In [25]:
def scalc(string):
return evaluator(scalc_parse(string), top_level_env)

In [27]:
scalc("pi")

Out[27]:
3.141592653589793
In [28]:
scalc("(+ pi pi)")

Out[28]:
6.283185307179586

# 4. Defining your own Functions¶

2. Parse of a lambda is a procedure
3. Evaluation of a procedure is a closure

A procedure (proc-exp) is:

• a list of symbols (the parameters)
• the body of the lambda

A closure is:

• a list of symbols (the parameters)
• the body of the lambda
• the environment at the time that the procedure was evaluated
In [28]:
scalc_parse("(lambda (i) i)")

Out[28]:
(proc-exp (i) (var-exp i))
In [29]:
scalc("(lambda (i) i)")

Out[29]:
(closure-exp (i) (var-exp i) [[['print', <function Print at 0x7f7424099620>], ['+', <function add_prim at 0x7f7424099730>], ['pi', 3.141592653589793]]])

But now we have two types of functions to apply:

• closures

We must change evaluator_apply such that an op (operator) can be a closure.

When we get a closure, we must unpack the components:

• symbols (the parameters)
• body (code to evaluate)
• the env in the closure

Then to evaluate the body of the lambda, we extend the environment to include the symbols bound to the operands.

In [30]:
def evaluator_apply(op, operands, env):
if isinstance(op, list) and car(op) == "closure-exp":
return evaluator(body,
extend_env(make_frame(symbols, operands),
closure_env))
else: # a Python function
return op(operands)

In [31]:
make_frame(sexp(["a", "b", "c"]), sexp([1, 2, 3]))

Out[31]:
[['a', 1], ['b', 2], ['c', 3]]
In [32]:
extend_env(make_frame(sexp(["a", "b", "c"]), sexp([1, 2, 3])), top_level_env)

Out[32]:
[[['a', 1], ['b', 2], ['c', 3]],
[['print', <function lab05.Print>],
['pi', 3.141592653589793]]]
In [33]:
scalc("((lambda (i) i) 42)")

Out[33]:
42

For the next section, I had to also add eq_prim and bind that to "=" in the environment.

In [34]:
from lab05 import *

In [35]:
scalc("(= 42 43)")

Out[35]:
0

# 5. Recursion in a language that doesn't support recursion¶

SCalc doesn't support a function calling itself. Why not?

• we don't have define
• we don't have assignment

Try to write factorial:

In [ ]:
scalc("""
((lambda (n)
(if (= n 1)
1
(* n (??? (- n 1)))))
5)
""")


What should ??? actually be? It should be the function that we are defining. But we don't have a way of referring to it.

But we could think of passing in something to act as ???:

In [ ]:
scalc("""
((lambda (n ???)
(if (= n 1)
1
(* n (??? (- n 1) ???))))
5
???
""")


Hey, we could make a copy of the function and pass it in! We can change the ??? in the lambda to be f and we have a complete, real function:

(lambda (n f)
(if (= n 1)
1
(* n (f (- n 1) f))))


Then we make a copy of that, and pass it in as f:

In [41]:
scalc("""
((lambda (n f)
(if (= n 1)
1
(* n (f (- n 1) f))))
5
(lambda (n f)
(if (= n 1)
1
(* n (f (- n 1) f))))
)
""")

Out[41]:
120

Whoa. We can do recursion in our language, even though it doesn't directly support recursion. This was a trick discovered in lambda calculus. In fact, you can "factor out the recursion" in the above to discover what is called the Y-combinator:

In [43]:
scalc("""

(((lambda (m)
((lambda (f) (m (lambda (a) ((f f) a))))
(lambda (f) (m (lambda (a) ((f f) a))))))

(lambda (factorial)
(lambda (n)
(if (= n 1)
1
(* n (factorial (- n 1)))))))
5)

""")

Out[43]:
120

Very cool!