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 == "+":
        return car(operands) + cadr(operands)
    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],
        ["+", add_prim],
    ],
]

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":
        return cadr(expr)
    elif car(expr) == "var-exp": ## NOW: look it up
        return lookup(cadr(expr), env)
    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],
        ["+", add_prim],
        ["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

  1. Add lambda to parser
  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:

  • primitives (like add_prim)
  • 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":
        symbols = cadr(op)
        body = caddr(op)
        closure_env = cadddr(op)
        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>],
  ['+', <function lab05.add_prim>],
  ['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!