Structure and Interpretation of Computer Programs 1986 Video Notes
MIT 6.001 (SICP)

These are numbers like 3, 17.4, or 5. Other primitives are discussed later in the course.

4
17.4
5

4
17.4
5

Lisp’s numerical primitives can be combined with “operations” such as addition, written in prefix notation.

(+ 3 17.4 5)

25.4

Other basic operations are provided by Lisp, such as multiplication and division. Of course, combinations can be combined recursively:

(+ 3 (* 5 6) 8 2)

43

This should show you the tree structure inherent in all of Lisp:

In Lisp, () is the application of an operation or function in prefix notation.

Abstraction can simply be done by naming things. Giving complicated things a name prevents us from having to understand how the thing the name refers to works, and instead lets us “abstractly” use the name for our purposes.

(define a (* 5 5))
a
(* a a)
(define b (+ a (* 5 a)))
b
(+ a (/ b 5))

25
625
150
55

Now, it’s often more useful to abstract away imperative how-to knowledge. Consider:

(define (square x)
  (* x x))

(square 10)

100

This defines square as a function taking a single argument x, and returning (* x x). Note that this way of writing a define is actually “syntactic sugar” for:

(define square
  (lambda (x)
    (* x x)))

(square 25)

625

lambda (x) means “make a procedure that takes argument x”. The second argument to lambda is the actual procedure body. The define names this anonymous procedure square.

Just like we can use combinations recursively, so we can abstractions. Consider:

(define (average x y)
  (/ (+ x y) 2))

(define (mean-square x y)
  (average (square x)
           (square y)))

(mean-square 2 3)

13/2

Note the indentation: since Lisp is parenthesis heavy, we use indentation. Good editors like Emacs should do this automatically.

• Numbers (evaluate to “themselves”)
• Symbols (represent some procedure)
• Combinations
• λ-expressions (used to build procedures)
• Definitions (used to name symbols)

• Conditionals

  We will focus our use of the substitution rule on the first three. The last three are called “special forms”, and we’ll worry about them later.

Consider:

(define (sum-of-squares x y)
  (+ (square x) (square y)))

(sum-of-squares 3 4)

25

Let’s try to apply the substitution rule to our application,

(sum-of-squares 3 4)
(+ (square 3) (square 4))
(+ (square 3) (* 4 4))
(+ (square 3) 16)
(+ (* 3 3) 16)
(+ 9 16)
25

Peano arithmetic defines addition as:

(define (pa+ x y)
  (if (= x 0)
      y
      (pa+ (dec x) (inc y))))

(pa+ 3 4)

7

Assume that inc and dec are primitives available that increment and decrement the argument respectively. How is the procedure pa+ working? Let’s apply the substitution rule.

(pa+ 3 4)
(if (= 3 0)
    4
    (pa+ (dec 3) (inc 4)))
(pa+ 2 5)
...
(pa+ 1 6)
...
(pa+ 0 7)
7

We’re skipping some steps, but the idea is that x keeps giving one “unit” to y until it reaches zero. Then the sum is y. Written with steps skipped:

(pa+ 3 4)
(pa+ 2 5)
(pa+ 1 6)
(pa+ 0 7)
7

Consider:

(define (pb+ x y)
  (if (= x 0)
      y
      (inc (pb+ (dec x) y))))

This is also a Peano adder: but it’s implemented slightly differently syntax-wise, a few characters here and there. Let’s use the substitution rule to see how it works.

(pb+ 3 4)
(inc (pb+ 2 4))
(inc (inc (pb+ 1 4)))
(inc (inc (inc (pb+ 0 4))))
(inc (inc ((inc 4))))
(inc (inc 5))
(inc 6)
7

See that it does work:

(pb+ 3 4)

7

Now, consider how these two, pa+ and pb+, are different. While the procedures do the same thing, the processes are wildly different. Let’s discuss their time and space complexity. It should be obvious to you that the time complexity is the vertical axis in the substitution rule application, since the interpreter “executes” these instructions line by line. More lines means more time.

In the case of pa+, the number of lines increases by 1 if you increase input x by 1. Thus, the time complexity is \(O(x)\). Similarly, in the case of pb+, the number of lines increases by 2 (once in the expansion, once in the contraction) when you increase x by 1. Thus, it is also \(O(x)\).

Now, the horizontal axis shows us how much space is being used. In the case of pa+, the space used is a constant. Thus, \(O(1)\). On the other hand, see that pb+ first expands then contracts. The length of the maximum expansion increases by 1 if we increase \(x\) by 1, since there’s one more increment to do. Thus, \(O(x)\).

Now, we call a process like pa+ linear iterative and a process like pb+ linear recursive.

Note that the process pa+ being iterative has nothing to do with the implementation/definition of the procedure, which is recursive. Iteration refers to the constant space requirement.

Recall that the algorithm itself relies on writing a function

\[f\colon y\mapsto \frac{y+\frac{x}{y}}{2}\]

Note that this works because \(f(\sqrt{x}) = \sqrt{x}\):

\[f(\sqrt{x})=\frac{\sqrt{x}+\frac{x}{\sqrt{x}}}{2} = \frac{2\sqrt{x}}{2} = \sqrt{x}\]

See that this is actually an algorithm for finding a fixed point of a function \(f\), which is defined as finding the point where \(f(z)=z\). This algorithm is merely an instance of a function \(f\) whose fixed point happens to be the square root.

For some functions, the fixed point can be found by iterating it.

This is the top-level abstraction we’ll write a function for. First, let’s see how we’d write a square-root function by wishful thinking:

(define (sqrt x)
  (fixed-point
   (lambda (y) (average (/ x y)
                        y))
   1))

Now writing fixed-point:

(define (fixed-point f start)
  (define (close-enough-p x y)
    (< (abs (- x y))
       0.00001))
  (define (iter old new)
    (if (close-enough-p old new)
        new
        (iter new (f new))))
  (iter start (f start)))

Let’s try it out!

(sqrt #i2)

1.4142135623746899

A fair question when seeing the function \[f_1\colon y\mapsto \frac{y+\frac{x}{y}}{2}\] is why another function \[f\colon y\mapsto \frac{x}{y}\] wouldn’t work in its place. This question is best answered by trying to find its fixed point by iteration. Let’s try to find it for \(x=2\), starting at \(y=1\). Then,

\[f(1) = \frac{2}{1} = 2\] \[f(2) = \frac{2}{2} = 1\] \[f(1) = \frac{2}{1} = 2\] \[f(2) = \frac{2}{2} = 1\] \[~\dots\]

It seems that instead of converging, this function is oscillating between two values. We know that it’s easy to fix this: we have to damp these oscillations. The most natural way to do this is to take the average of successive values \(y\) and \(f(y)\). A sqrt function that uses average damping would be:

(define (sqrt x)
  (fixed-point
   (avg-damp (lambda (y) (/ x y)))
   1))

The avg-damp function takes in a procedure, creates an average damping procedure, and returns it. Or, in Lisp:

(define avg-damp
  (lambda (f)
    (lambda (x) (average (f x) x))))

It is worth discussing how avg-damp works. It is defined as a procedure which takes the argument of a function f. It then returns an anonymous procedure which takes an argument x, and computes the average of \(f(x)\) and \(x\). This is finally the highest level of abstraction we can reach for the sqrt algorithm — finding the fixed point of a damped oscillating function.

Using the sqrt function,

(sqrt #i2)

1.4142135623746899

We don’t know, however, how to represent this data in a Lisp procedure. Let’s use our powerful “wishful thinking” strategy. Assume that we have the following procedures available to us:

• A constructor (make-rat n d) which makes a fraction with numerator n and denominator d.
• Two selectors:
  • (numer x) which takes in a fraction x and returns its numerator.

  • (denom x) which takes in a fraction x and returns its denominator.

    Then, our procedures are easy to write:

    (define (+rat x y)
      (make-rat
       (+ (* (numer x) (denom y))
          (* (numer y) (denom x)))
       (* (denom x) (denom y))))
    
    (define (*rat x y)
      (make-rat
       (* (numer x) (numer y))
       (* (denom x) (denom y))))
    

    Why do we need this data object abstraction anyway? We could very well define +rat to take in four numbers, two numerators and two denominators. But to return, we can’t return both numerator and denominator. We now have to define two summation functions, one for the numerator and one for the denominator, and somehow keep track of the fact that one of these numbers is the numerator and the other the denominator. Furthermore, when applying more complex operations like:

    (*rat (+rat x y)
          (+rat s t))
    

    The data abstraction helps. If it weren’t there, we’d have to maintain some temporary registers to store the numerator and denominator values of the +rat operations into, then pass them to *rat.

    Worse than confusing the program, such a design philosophy would confuse us, the programmers.

The glue we use to stick two numbers together is provided by three Lisp primitives:

• A constructor cons, which generates an ordered pair.
• Two selectors:
  • car, which selects the first element of the pair, and

  • cdr, which selects the second element of the pair.

    In use,

    (define x (cons 1 2))
    (car x)
    (cdr x)
    

    1
    2
    

    We can now write the procedures that we’d deferred writing earlier:

    (define (make-rat x y)
      (cons x y))
    
    (define (numer x)
      (car x))
    
    (define (denom x)
      (cdr x))
    

    
    
    (define x (make-rat 1 2))
    (define y (make-rat 1 4))
    (define z (+rat x y))
    (numer z)
    (denom z)
    

    6
    8
    

    Agh. We forgot to reduce results to the simplest form. We can easily include this in the make-rat procedure:¹

    (define (make-rat x y)
      (let ((g (gcd x y)))
        (cons (/ x g)
              (/ y g))))
    
    (define (numer x)
      (car x))
    
    (define (denom x)
      (cdr x))
    

    Note that we could shift the gcd bit to functions numer and denom, which would display the simplest form at access time rather than creation time. Deciding between the two is a matter of system efficiency: a system which displays often should use creation time simplification, while a system which creates many fractions should use access time simplification. We now need a GCD function:

    (define (gcd a b)
      (if (= b 0)
          a
          (gcd b (remainder a b))))
    

    We can now use +rat in exactly the same way, since the interface is the same. This is the advantage of abstraction.

    
    
    (define x (make-rat 1 2))
    (define y (make-rat 1 4))
    (define z (+rat x y))
    (numer z)
    (denom z)
    

    3
    4
    

    Excellent: we now have a working system. The data abstraction model can be visualised as follows:

    +rat, *rat …
    make-rat, numer, denom
    gcd
    Pairs

    At each layer of abstraction, we merely care about the usage of the lower layers and not their implementation or underlying representation.

Say we wanted to write a procedure scale-list which multiplies every element in the list by a certain value. That is, when scale list is called on one-to-four with value 10, it returns (10 20 30 40). Here’s one possible (recursive) implementation:

(define (scale-list l scale)
  (if (null? l)
      nil
      (cons (* scale (car l))
            (scale-list (cdr l) scale))))

(scale-list one-to-four 10)

(10 20 30 40)

null? is a predicate which tells us whether the given input is the empty list. This will be the case at the end of the list. Of course, this is actually a general method for processing all values of a list and returning another list, so we write a higher-order procedure which applies a procedure to all elements of a list and returns the result as a list, called map.

(define (map p l)
  (if (null? l)
      nil
      (cons (p (car l))
            (map p (cdr l)))))

Now defining scale-list in terms of map:

(define (scale-list l s)
  (map (lambda (x) (* x s))
       l))

(scale-list one-to-four 20)

(20 40 60 80)

We can now square lists:

(map square one-to-four)

(1 4 9 16)

Similar to map, we define a higher-order procedure for-each, which, instead of cons-ing a list and returning it, simply applies to procedure to each element of the list.

(define (for-each proc l)
  (cond ((null? l) done)
        (else
         (proc (car l))
         (for-each proc (cdr l)))))

This language has only one primitive: “picture”, which is a figure scaled to fit a frame.

• Rotate, which rotates a picture and returns it.
• Flip, which flips the picture across an axis and returns it.
• Beside, which takes two pictures and a scale, then puts the two next to each other, returning a picture.

• Above, like beside, but above.

  See that the closure property (that an operation on pictures returns a picture)⁴ allows us to combine these operations/means of combination to build complex pictures with ease.

  Let’s now implement this part of the language.

See that the picture language is now embedded in Lisp. We can write recursive procedures to modify a picture:

(define (right-push pict n a)
  (if (= n 0)
      pict
      (beside pict
              (right-push pict (dec n) a)
              a)))

We can even write a higher order procedure for “pushing”:

(define (push comb)
  (lambda (pict n a)
    ((repeated
      (lambda (p)
        (comb pict p a))
      n)
     pict)))

(define right-push (push beside))

There’s a lot to learn from this example:

• We’re embedding a language inside Lisp. All of Lisp’s power is available to this small language now: including recursion.
• There’s no difference between a procedure and data: we’re passing pictures around exactly like data, even though it’s actually a procedure.
• We’ve created a layered system of abstractions on top of Lisp, which allows each layer to have all of Lisp’s expressive power. This is contrasted to a designing such a system bottom-up as a tree, which would mean that:
  • Each node does a very specific purpose and is limited in complexity because a new feature has to be built ground-up at the node.
  • Making a change is near impossible, since there’s no higher order procedural abstraction. Making a change that affects more than one node is a nightmare.

One very simple way to represent expressions is to use Lisp’s way: expressions that form trees. Consider:

\[ax^{2} \mapsto \mathtt{(*~a~(*~x~x))}\] \[bx+c \mapsto \mathtt{( \mathtt{+} ~(*~b~x)~c)}\]

This has the advantage that representing such expression is just a list. Moreover, finding out the operation is merely the car of the list, and the operands are the cdr. This effectively eliminates our need for parsing algebraic expressions.

Let’s start defining our procedures.

(define (constant? expr var)
  (and (atom? expr)
       (not (eq? expr var))))

(define (same-var? expr var)
  (and (atom? expr)
       (eq? expr var)))

(define (sum? expr)
  (and (not (atom? expr))
       (eq? (car expr) '+)))

(define (product? expr)
  (and (not (atom? expr))
       (eq? (car expr) '*)))

We see a new form here: '+ and '*. This is called “quoting”. Why do we need to do this? Consider:

“Say your name!”
“Susanne.”
“Say ‘your name’!”
“Your name.”

To differentiate the cases where we mean literally say “your name” and the case where we actually ask what “your name” is, we use quotation marks in English. Similarly, quoting a symbol in Lisp tells the interpreter to check literally for (car expr) to be the symbol + and not the procedure +.

Quotation is actually quite a complicated thing. Following the principle of substituting equals for equals, consider:

“Chicago” has seven letters.
Chicago is the biggest city in Illinois.
“The biggest city in Illinois” has seven letters.

The first two statements are true, and quotation marks are used correctly in the first to show that we’re talking about Chicago the word and not Chicago the city. However, the third statement is wrong entirely (although it is the result of changing equals for equals), because the phrase “The biggest city in Illinois” does not have seven letters. That is, we cannot substitute equals for equals in referentially opaque contexts.

Note that the ' symbol breaks the neat pattern of Lisp where all expressions are delimited by (). To resolve this, we introduce the special form (quote +), which does the exactly same thing as '+.

Now defining the constructors:

(define (make-sum a1 a2)
  (list '+ a1 a2))

(define (make-product m1 m2)
  (list '* m1 m2))

Finally, we must define the selectors:

(define a1 cadr)
(define a2 caddr)

(define m1 cadr)
(define m2 caddr)

cadr is the car of the cdr and caddr is the car of the cdr of the cdr. These are forms provided for convenience while programming, since list processing a big part of Lisp.⁵

Let’s try it out:

(deriv '(+ (* a (* x x)) (+ (* b x) c)) 'x)
(deriv '(+ (* a (* x x)) (+ (* b x) c)) 'a)
(deriv '(+ (* a (* x x)) (+ (* b x) c)) 'b)
(deriv '(+ (* a (* x x)) (+ (* b x) c)) 'c)

(+ (+ (* a (+ (* x 1) (* 1 x))) (* 0 (* x x))) (+ (+ (* b 1) (* 0 x)) 0))
(+ (+ (* a (+ (* x 0) (* 0 x))) (* 1 (* x x))) (+ (+ (* b 0) (* 0 x)) 0))
(+ (+ (* a (+ (* x 0) (* 0 x))) (* 0 (* x x))) (+ (+ (* b 0) (* 1 x)) 0))
(+ (+ (* a (+ (* x 0) (* 0 x))) (* 0 (* x x))) (+ (+ (* b 0) (* 0 x)) 1))

Note the recursive nature of deriv: the process creates results with the same shape even when we differentiate with respect to some other variable. This is because the recursion only ends when an expression is decomposed to either same-var? or constant?.

However, these results are ugly, and we know why — there’s no simplification. Technically, it’s correct:

Note that we’ve faced this same problem before with fractions, and recall that the solution was to change the constructors so that they’d simplify while creating the lists. Consider:

(define (make-sum a1 a2)
  (cond ((and (number? a1)
              (number? a2))
         (+ a1 a2))
        ((and (number? a1)
              (= a1 0))
         a2)
        ((and (number? a2)
              (= a2 0))
         a1)
        (else
         (list '+ a1 a2))))

(define (make-product m1 m2)
  (cond ((and (number? m1)
              (number? m2))
         (* m1 m2))
        ((and (number? m1)
              (= m1 0))
         0)
        ((and (number? m2)
              (= m2 0))
         0)
        ((and (number? m1)
              (= m1 1))
         m2)
        ((and (number? m2)
              (= m2 1))
         m1)
        (else
         (list '+ m1 m2))))

Now trying deriv:

(deriv '(+ (* a (* x x)) (+ (* b x) c)) 'x)
(deriv '(+ (* a (* x x)) (+ (* b x) c)) 'a)
(deriv '(+ (* a (* x x)) (+ (* b x) c)) 'b)
(deriv '(+ (* a (* x x)) (+ (* b x) c)) 'c)

(+ (+ a (+ x x)) b)
(* x x)
x
1

Excellent, these are much better. Note, of course, that we could simplify the first one further, but, in general, algebraic simplification is a painful problem, since the definition of simplest form varies with application. However, this is good enough.

The idea of the LHS language is to provide a framework where certain constructs can be matched and possibly named. These names will then be passed to the skeleton instantiator.⁶

The RHS language provides a skeleton wherein values provided by the LHS language can be substituted.

Abstractly, the job of the matcher is to do a tree traversal and comparison. Consider the rule LHS: (+ (* (? x) (? y)) (? y)), and an expression to match: (+ (* 3 x) x) (say). Then, the trees are:

Clearly, these expressions should be matched in the tree traversal. Don’t confuse the (? x) in the rule LHS with the symbol x in the expression: for the rule, it’s just a matching variable, but the x in the expression goes into the dictionary.

Let’s now write our first implementation of match:

(define (match pat expr dict)
  (cond ((eq? dict 'failed) 'failed)
        ; ... some other cases
        ((atom? expr) 'failed)
        (else
         (match (cdr pat)
           (cdr expr)
           (match (car pat)
             (car expr)
             dict)))))

Before we write the entire procedure, let’s observe how the general case (else) works, because that’s the bit which does the tree traversal. It calls match on the car of the pattern and expression. If they match, we return a dictionary, which is then used to match the cdr of the original expression. Why does this do tree traversal? Well, it’s basically a depth first search on a tree. Consider what happens when match is called on the car. After being called for the caar and caaar…it’ll eventually be called for the cadr and the caddr and so on. That’s precisely what a depth first search is. It’ll keep going deeper and deeper until it fails, which is when it takes one step back and goes deeper into another branch.

Now, it is important to define the non-general cases, especially the ones that terminate match. The most important of these is when the expression passed is atomic, since that means we’re at the leaf of the expression tree. Another possible failure is the insertion into the dictionary failing. How is this possible? Consider:

Just before match reaches the last leaf (boxed), our dictionary will look something like the following:

However, when it tries to insert y: q, the dictionary will failed to do so, because y already has value x, and thus the rule does not match.

Finally, we implement as more cases in the cond other things we may need to match, according to the rule language (8.1).

(define (match pattern expression dict)
  (cond ((eq? dict 'failed) 'failed)

        ((atom? pattern)
         (if (atom? expression)
             (if (eq? pattern expression)
                 dict
                 'failed)
             'failed))

        ((arbitrary-constant? pattern)
         (if (constant? expression)
             (extend-dict pattern expression dict)
             'failed))

        ((arbitrary-variable? pattern)
         (if (variable? expression)
             (extend-dict pattern expression dict)
             'failed))

        ((arbitrary-expression? pattern)
         (extend-dict pattern expression dict))

        ((atom? expression) 'failed)

        (else
         (match (cdr pattern)
           (cdr expression)
           (match (car pattern)
             (car expression)
             dict)))))

We add one case wherein both the pattern to be matched and the expression are atomic and the same, (the case foo in 8.1), in which we simply return the dictionary, since the pattern matches. The other new cases are self-explanatory: they are merely matching (?c), (?v), and (?).

Recall that instantiate must take accept the input of a skeleton and a dictionary, traverse the skeleton tree, and replace rule variables for expression values according to the dictionary. That is, given the tree:

And the dictionary (x: 3, y: 4), it should produce the tree:

This is a fairly simple procedure to write:

(define (instantiate skeleton dict)
  (cond ((atom? skeleton) skeleton)
        ((skeleton-evaluation? skeleton)
         (evaluate (evaluation-expression skeleton)
                   dict))
        (else (cons (instantiate (car skeleton) dict)
                    (instantiate (cdr skeleton) dict)))))

The general case is our usual tree recursion: it first instantiates the car, then cons’ that with the instantiated cdr. The depth-first search ends if the leaf is atomic, as usual.

The interesting bit is what we do when we want to evaluate a skeleton of the (:) form (predicate skeleton-evaluation?). In this case, we call a procedure evaluate, to which we pass the expression to be evaluated (the cadr, really, since we don’t need the :).

Now, evaluate works in a special way we’ll see later, so take on faith that the following evaluate function does its job of instantiation the way we want it to:

(define (evaluation-expression evaluation) (cadr evaluation))

(define (evaluate form dict)
  (if (atom? form)
      (lookup form dict)
      (apply (eval (lookup (car form) dict)
                   user-initial-environment)
             (map (lambda (v) (lookup v dict))
                  (cdr form)))))

The GIGO (garbage in, garbage out)⁷ simplifier is implemented by stringing together the matcher, the instantiator, and the list of rules we are given as an input. We write it in lexically scoped style, because the procedures within it are merely helpers.

(define (simplifier the-rules)
  (define (simplify-expression expression)
    (try-rules
     (if (compound? expression)
         (map simplify-expression expression)
         expression)))
  (define (try-rules expression)
    (define (scan rules)
      (if (null? rules)
          expression
          (let ((dict (match (pattern (car rules))
                        expression
                        (make-empty-dict))))
            (if (eq? dict 'failed)
                (scan (cdr rules))
                (simplify-expression (instantiate
                                         (skeleton (car rules))
                                         dict))))))
    (scan the-rules))
  simplify-expression)

Okay, there’s a fair amount to break down here.

• simplify-expression tries all the rules on every node in the given expression tree. It does this using our (by now) standard depth first tree recursion. In this case, the leaf is an atomic expression. The general case is when the expression is compound, in which case we try to simplify the car. If this doesn’t work, we try the cdr, recursively. This fulfils our objective of trying all rules on all nodes. Note that instead of doing the recursion explicitly, we use map. This doesn’t make a difference, it is merely somewhat easier to write.
• try-rules accepts an expression as an input, and scans the input list of rules, applying each in turn using scan.
• scan takes the pattern of the first rule in the list and tries to match it to the expression. If it succeeds, we instantiate the skeleton of this rule with the values from the dictionary. On the other hand, if the match failed, we simply try the rest of the rules (cdr).
• Finally, simplifier returns the simplify-expression procedure, which can apply the-rules to any input expression. Note that this is what the desired behaviour is (8.2).

The actual dictionary implementation isn’t of much interest to us, since it has much more to do with Lisp primitives we’ll study later than our program.

(define (make-empty-dict) '())

(define (extend-dict pat dat dictionary)
  (let ((vname (variable-name pat)))
    (let ((v (assq vname dictionary)))
      (cond ((not v)
             (cons (list vname dat) dictionary))
            ((eq? (cadr v) dat) dictionary)
            (else 'failed)))))

(define (lookup var dictionary)
  (let ((v (assq var dictionary)))
    (if (null? v)
        var
        (cadr v))))

Finally, we must implement the predicates we’ve used throughout. These are simple to implement and self-explanatory:

(define (compound? exp) (pair? exp))
(define (constant? exp) (number? exp))
(define (variable? exp) (atom? exp))
(define (pattern rule) (car rule))
(define (skeleton rule) (cadr rule))

(define (arbitrary-constant? pat)
  (if (pair? pat) (eq? (car pat) '?c) false))

(define (arbitrary-expression? pat)
  (if (pair? pat) (eq? (car pat) '?) false))

(define (arbitrary-variable? pat)
  (if (pair? pat) (eq? (car pat) '?v) false))

(define (variable-name pat) (cadr pat))

(define (skeleton-evaluation? pat)
  (if (pair? pat) (eq? (car pat) ':) false))

Consider the rule set:

(define algebra-rules
  '(
    ( ((? op) (?c c1) (?c c2))                (: (op c1 c2))                )
    ( ((? op) (?  e ) (?c c ))                ((: op) (: c) (: e))          )
    ( (+ 0 (? e))                             (: e)                         )
    ( (* 1 (? e))                             (: e)                         )
    ( (* 0 (? e))                             0                             )
    ( (* (?c c1) (* (?c c2) (? e )))          (* (: (* c1 c2)) (: e))       )
    ( (* (?  e1) (* (?c c ) (? e2)))          (* (: c ) (* (: e1) (: e2)))  )
    ( (* (* (? e1) (? e2)) (? e3))            (* (: e1) (* (: e2) (: e3)))  )
    ( (+ (?c c1) (+ (?c c2) (? e )))          (+ (: (+ c1 c2)) (: e))       )
    ( (+ (?  e1) (+ (?c c ) (? e2)))          (+ (: c ) (+ (: e1) (: e2)))  )
    ( (+ (+ (? e1) (? e2)) (? e3))            (+ (: e1) (+ (: e2) (: e3)))  )
    ( (+ (* (?c c1) (? e)) (* (?c c2) (? e))) (* (: (+ c1 c2)) (: e))       )
    ( (* (? e1) (+ (? e2) (? e3)))            (+ (* (: e1) (: e2)))         )
    ))

(define dsimp
  (simplifier deriv-rules))

(define algsimp
  (simplifier algebra-rules))

(define (derivative x)
  (algsimp (dsimp x)))

(derivative '(dd (* x x) x))
(derivative '(dd (+ (+ x (* x 5)) (* x x)) x))

(+ x x)
(+ 6 (+ x x))

We now have a complete pattern matching and replacement language at our disposal, and we’ve tested it out on the rules of differentiation and algebraic simplification.

Complex numbers are represented in the complex plane as:

It should be clear that for a complex number \(z=|z|e^{i\theta}=x+iy\): \[|z|=\sqrt{x^{2}+y^{2}}\] \[\theta = \arctan{\frac{y}{x}}\] \[x=|z|\cos{\theta}\] \[y=|z|\sin{\theta}\]

Let us say we want to add, subtract, multiply, and divide complex numbers. The most natural way to add is using rectangular form:

\[\Re{(z_1+z_2)} = \Re{(z_1)} + \Re{(z_2)}\] \[\Im{(z_1+z_2)} = \Im{(z_1)} + \Im{(z_2)}\]

However, the most natural way to multiply is using polar form:

\[|z_1z_2|=|z_1||z_2|\] \[\theta{(z_1z_2)} = \theta{(z_1)}+\theta{(z_2)}\]

Let’s implement the four basic arithmetic operations. As in the case of rational numbers, we assume the availability of the constructors and selectors:

(make-rect x y)
(make-pol magnitude theta)
(real z)
(img z)
(mag z)
(ang z)

Then,

(define (+c z1 z2)
  (make-rect
   (+ (real z1) (real z2))
   (+ (img z1) (img z2))))

(define (-c z1 z2)
  (make-rect
   (- (real z1) (real z2))
   (- (img z1) (img z2))))

(define (*c z1 z2)
  (make-pol
   (* (mag z1) (mag z2))
   (+ (ang z1) (ang z2))))

(define (/c z1 z2)
  (make-pol
   (/ (mag z1) (mag z2))
   (- (ang z1) (ang z2))))

George loves the rectangular form of complex numbers. He therefore implements the constructors and selectors in the following way:

(define (make-rect x y)
  (cons x y))

(define (real z)
  (car z))

(define (img z)
  (cdr z))

(define (make-pol r a)
  (cons
   (* r (cos a))
   (* r (sin a))))

(define (mag z)
  (sqrt (+ (square (car z))
           (square (cdr z)))))

(define (ang z)
  (atan (cdr z) (car z)))

Martha, on the other hand, much prefers the polar representation. She implements the constructors and selectors as:

(define (make-pol r a)
  (cons r a))

(define (mag z)
  (car z))

(define (ang z)
  (cdr z))

(define (real z)
  (* (car z)
     (cos (cdr z))))

(define (img z)
  (* (car z)
     (sin (cdr z))))

(define (make-rect x y)
  (cons
   (sqrt (square x) (square y))
   (atan y x)))

Naturally, George’s representation is better if we want to use +c a lot, while Martha’s is better if we want to use *c a lot. Often, it’s impossible to choose between two equally good representations. The solution is to use generic selectors and constructors. Diagrammatically:

One of our chief problems is that when we have a pair that’s a complex number, we have no way of knowing whether it’s rectangular or polar. By attaching this pair to a “type label”, we can easily tell by reading the label which type it is, and accordingly call George’s or Martha’s procedures. Consider:

(define (attach-type type contents)
  (cons type contents))

(define (type datum)
  (car datum))

(define (contents datum)
  (cdr datum))

Now, George redefines his procedures as:

(define (make-rect x y)
  (attach-type 'rectangular (cons x y)))

(define (real-rectangular z)
  (car z))

(define (img-rectangular z)
  (cdr z))

(define (mag-rectangular z)
  (sqrt (+ (square (car z))
           (square (cdr z)))))

(define (ang-rectangular z)
  (atan (cdr z) (car z)))

Note that he changes his procedure names so that they don’t conflict with the generic make-rect, real, and so on. The major change is that he rectangular complex numbers. Moreover, there’s no need for George to have a make-pol, since that functionality is already provided by Martha, who implements her procedures as:

(define (make-pol r a)
  (attach-type 'polar (cons r a)))

(define (mag-polar z)
  (car z))

(define (ang-polar z)
  (cdr z))

(define (real-polar z)
  (* (car z)
     (cos (cdr z))))

(define (img-polar z)
  (* (car z)
     (sin (cdr z))))

Now, we can implement the generic procedures as:

(define (real z)
  (cond ((rectangular? z)
         (real-rectangular (contents z)))
        ((polar? z)
         (real-polar (contents z)))))

(define (img z)
  (cond ((rectangular? z)
         (img-rectangular (contents z)))
        ((polar? z)
         (img-polar (contents z)))))

(define (mag z)
  (cond ((rectangular? z)
         (mag-rectangular (contents z)))
        ((polar? z)
         (mag-polar (contents z)))))

(define (ang z)
  (cond ((rectangular? z)
         (ang-rectangular (contents z)))
        ((polar? z)
         (ang-polar (contents z)))))

We call procedures written this way “managers”, since they decide whom to dispatch the data object to for processing. The predicates are simple label-checkers:

(define (rectangular? z)
  (eq? 'rectangular (type z)))

(define (polar? z)
  (eq? 'polar (type z)))

(define a (make-rect 2 3))
(define b (make-pol 5 (tan (/ 3 4))))

(define result (+c a b))
(real result)
(img result)

(car a)
(car b)
(car result)
(cadr result)
(cddr result)

4.98276733430013
7.012866684732013
rectangular
polar
rectangular
4.98276733430013
7.012866684732013

Note that complex numbers are now a pair of a label and a pair.

There are two major issues with this way of engineering the complex number system (“dispatch on type”):

• George and Martha having to change their procedure names to prevent namespace violation. This issue, however, can be fixed by methods explored in later lectures.

• A larger issue is that when an additional representation is added (say, Harry’s), the manager’s cond has to be changed. This isn’t ideal, since it’s a set of centralized procedures which all of George, Martha, and Harry have to be able to edit. This centralization and causes a bottleneck, and is annoying, especially because all the manager does, really, is a conditional dispatch — it’s a bureaucrat.

  Our next efforts will be directed at eliminating the manager procedures.

(put 'rectangular 'real real-rectangular)
(put 'rectangular 'img img-rectangular)
(put 'rectangular 'mag mag-rectangular)
(put 'rectangular 'ang ang-rectangular)

Note carefully that the value inserted into the table cell is actually a lambda, it’s not a symbol. This means that the table literally contains within it the procedures, not their names. Technically, George could have given the third argument of put as a λ directly instead of first defining it. This is desirable, since George can safely debug and change his procedures, and only “commit” them when he puts them in the table. Moreover, it greatly simplifies lookups: to apply a procedure, one must only grab the correct cell of the table.

Similarly:

(put 'polar 'real real-polar)
(put 'polar 'img img-polar)
(put 'polar 'mag mag-polar)
(put 'polar 'ang ang-polar)

Now, if Harry wants to add his procedures, he doesn’t have to do anything except put them in the table.

The procedures hanging around in the table isn’t enough: when +c calls (say) real, it needs to get these values from the table. This is done by:

(define (operate op object)
  (let ((proc (get (type object) op)))
    (if (not (null? proc))
        (proc (contents object))
        (error "Operation undefined."))))

It is now simple to define the generic operators:

(define (real obj)
  (operate 'real obj))

(define (img obj)
  (operate 'img obj))

(define (mag obj)
  (operate 'mag obj))

(define (ang obj)
  (operate 'ang obj))

The usage is the same as last time, since the difference is in the implementation:

(define a (make-rect 2 3))
(define b (make-pol 5 (tan (/ 3 4))))

(define result (+c a b))
(real result)
(img result)

(car a)
(car b)
(car result)
(cadr result)
(cddr result)

4.98276733430013
7.012866684732013
rectangular
polar
rectangular
4.98276733430013
7.012866684732013

Note that an alternative to keeping the operations in a lookup table is to include the operations with the data object. This allows the data object to carry independently all the information required to work with it. This style of programming is called “message passing”.

We can see by the substitution rule how this system is working:

(real z)
(operate 'real z)
((get 'polar 'real) (contents z))
(real-polar (contents z))

Let us now embed our complex number system “package” in a more complex arithmetic system which, diagrammatically, looks like the following:

Our goal is to embed our complex number, rational number, and standard Lisp number code into a single system. This will also be done with tags and a lookup table, with data being tagged as complex, rational, or number. The top-level operations add, sub, mul, and div are defined in terms of an operate which is binary rather than unary. Later, we expand this system by adding a way to add polynomials.

The rational number procedures in this system are implemented thus:

(define (make-rat n d)
  (attach-type 'rational (cons n d)))

(put 'rational 'add +rat)
(put 'rational 'mul *rat)

The definitions of +rat and *rat are the same as last time:

(define (+rat x y)
  (make-rat
   (+ (* (numer x) (denom y))
      (* (numer y) (denom x)))
   (* (denom x) (denom y))))

(define (*rat x y)
  (make-rat
   (* (numer x) (numer y))
   (* (denom x) (denom y))))

Similarly, we can implement constructors and put procedures for complex numbers and standard Lisp numbers in this system:

(define (make-complex z)
  (attach-type 'complex z))

(define (+complex z1 z2)
  (make-complex (+c z1 z2)))

(define (-complex z1 z2)
  (make-complex (-c z1 z2)))

(define (*complex z1 z2)
  (make-complex (*c z1 z2)))

(define (/complex z1 z2)
  (make-complex (/c z1 z2)))

(put 'complex 'add +complex)
(put 'complex 'sub -complex)
(put 'complex 'mul *complex)
(put 'complex 'div /complex)

Note that we define additional procedures +complex, -complex, and so on to add the complex tag to results of operating on complex numbers. Moving to standard numbers:

(define (make-number n)
  (attach-type 'number n))

(define (+number x y)
  (make-number (+ x y)))

(define (-number x y)
  (make-number (- x y)))

(define (*number x y)
  (make-number (* x y)))

(define (/number x y)
  (make-number (/ x y)))

(put 'number 'add +number)
(put 'number 'sub -number)
(put 'number 'mul *number)
(put 'number 'div /number)

Finally, we must implement add, sub, mul, and div themselves:

(define (add x y)
  (operate-2 'add x y))

(define (sub x y)
  (operate-2 'sub x y))

(define (mul x y)
  (operate-2 'mul x y))

(define (div x y)
  (operate-2 'div x y))

Finally, we implement the binary operate, operate-2:

(define (operate-2 op arg1 arg2)
  (if (eq? (type arg1) (type arg2))
      (let ((proc (get (type arg1) op)))
        (if (not (null? proc))
            (proc (contents arg1)
                  (contents arg2))
            (error "Operation undefined.")))
      (error "Argument type mismatch.")))

We’re now ready to test this system:

(define p (make-complex (make-pol 1 2)))
(define q (make-complex (make-pol 3 4)))
(mul q p)

(define r (make-rat 2 4))
(define s (make-rat 1 4))
(add r s)

(sub (make-number 65) (make-number 3))

(complex polar 3 . 6)
(rational 12 . 16)
(number . 62)

See from the output the structure: labels followed by actual value of the datum.

To do arithmetic on polynomials, we must first figure out how to represent them. Consider the polynomial:

\[x^{15} + 2x^7 + 5\]

One simple way to represent a polynomial is a list of coefficients, with the rightmost coefficient being the constant term, the second last being the linear term, followed by quadratic, and so on. However, for “sparse” polynomials like the one in the example, this will result in a list with a lot of zeros. We therefore choose a slightly different representation: a list of pairs. The car of the pair is the order, and the cdr is the coefficient. Thus, the polynomial in the example is represented as ((15 1) (7 2) (0 5)). We call this the “term list” of the polynomial. In our final representation, we’ll cons this with the last bit of missing information: the variable the polynomial is in.

Thus, to construct a polynomial:

(define (make-poly var term-list)
  (attach-type 'polynomial (cons var term-list)))

(define (var poly) (car poly))
(define (term-list poly) (cdr poly))

Now, implementing +poly:

(define (+poly p1 p2)
  (if (eq? (var p1) (var p2))
      (make-poly
       (var p1)
       (+term (term-list p1)
              (term-list p2)))
      (error "Polynomials not in same variable.")))

(put 'polynomial 'add +poly)

Of course, this just pushed the real work onto +term, which is defined as:

(define (+term L1 L2)
  (cond ((empty-termlist? L1) L2)
        ((empty-termlist? L2) L1)
        (else
         (let ((t1 (first-term L1))
               (t2 (first-term L2)))
           (cond ((> (order t1) (order t2))
                  (adjoin-term
                   t1
                   (+term (rest-terms L1) L2)))
                 ((< (order t1) (order t2))
                  (adjoin-term
                   t2
                   (+term L1 (rest-terms L2))))
                 (else
                  (adjoin-term
                   (make-term (order t1)
                              (add (coeff t1)
                                   (coeff t2)))
                   (+term (rest-terms L1) (rest-terms L2)))))))))

Clearly, we need to implement some predicates, constructors, and selectors for term’s and term-list’s:

(define (empty-termlist? tl)
  (null? tl))

(define (first-term tl)
  (car tl))

(define (rest-terms tl)
  (cdr tl))

(define (adjoin-term term tl)
  (cons term tl))

(define (make-term o c)
  (cons o c))

(define (order t)
  (car t))

(define (coeff t)
  (cdr t))

Usage is obvious:

(define p1-tl
  (list
   (cons 15 (make-number 1))
   (cons 7 (make-number 2))
   (cons 0 (make-number 5))))
(define poly1 (make-poly 'x p1-tl))

(define p2-tl
  (list
   (cons 25 (make-number 1))
   (cons 15 (make-number 8))
   (cons 9 (make-number 4))
   (cons 7 (make-number 4))
   (cons 0 (make-number 15))))
(define poly2 (make-poly 'x p2-tl))

(add poly1 poly2)

(polynomial x (25 number . 1) (15 number . 9)
              (9 number . 4) (7 number . 6) (0 number . 20))

Although somewhat hard to read, this is just the polynomial:

\[x^{25} + 9x^{15} + 4x^9 + 6x^7 + 20\]

which is the correct result of summing the polynomials:

\[(x^{15}+2x^7+5) + (x^{25} + 8x^{15} + 4x^9 + 4x^7 + 15)\]

It’s easy to miss one very crucial point in the implementation of procedure +term: that when we actually add the coefficients of two same-order terms, we use the generic operator add. Or, instead of doing this:

(+ (coeff t1)
   (coeff t2))

we do:

(add (coeff t1)
     (coeff t2))

What this does is that it lets our polynomial have any coefficients supported by the overall system. We therefore, “for free”, have rational and complex coefficients. Therefore, expressions like the following are fully supported:

\[\frac{3}{2}x^{2} + \frac{17}{7}\] \[(3+2i)x^5+(4+7i)\]

This works by calling add on the coefficients, which knows how to add fractions and complex numbers.

(define p1-tl
  (list
   (cons 15 (make-rat 1 2))
   (cons 7 (make-rat 2 17))
   (cons 0 (make-rat 5 4))))
(define poly1 (make-poly 'x p1-tl))

(define p2-tl
  (list
   (cons 25 (make-rat 1 3))
   (cons 15 (make-rat 8 7))
   (cons 9 (make-rat 4 13))
   (cons 7 (make-rat 14 7))
   (cons 0 (make-rat 15 1))))
(define poly2 (make-poly 'x p2-tl))

(add poly1 poly2)

(polynomial x (25 rational 1 . 3) (15 rational 23 . 14)
              (9 rational 4 . 13) (7 rational 252 . 119) (0 rational 65 . 4))

Even cooler is the fact that we have support for polynomials with polynomial coefficients, such as:

\[(x^2+1)y^2 + (x^3-2x)y + (x^4-7)\]

This is because add also knows, recursively, how to add polynomials. We can, theoretically, nest this as far as we want to, having polynomials whose coefficients are polynomials whose coefficients are polynomials whose…

Note that we could rewrite +rat to use add instead of +, and we’d be able to support expressions such as

\[\frac{3x+7}{x^2+1}\]

This exposes a powerful technique: once we have the basic implementation of any operation, say matrix addition, in the form:

\[\begin{bmatrix} a & b\\ c & d \end{bmatrix} + \begin{bmatrix} p & q\\ r & s \end{bmatrix} = \begin{bmatrix} a+p & b+q\\ c+r & d+s \end{bmatrix} \]

If we use generic operators, it doesn’t matter what \(a\), \(b\), and the other operands are: they can be any type the generic operators support, including matrices.

Functional programs encode mathematical truth in a procedure. For instance,

(define (fact n)
  (cond ((= n 1) 1)
        (else (* n (fact (dec n))))))

(fact 4)

24

This is almost precisely the mathematical definition of a factorial in Lisp: \[f(n) = \begin{cases} 1& n=1\\ n\times f(n-1) & n>1\end{cases}\]

Moreover, such a function can be fully understood by substituting recursively:

(fact 4)
(* 4 (fact 3))
(* 4 (* 3 (fact 2)))
(* 4 (* 3 (* 2 (fact 1))))
(* 4 (* 3 (* 2 1)))
(* 4 (* 3 2))
(* 4 6)
24

Furthermore, we can differentiate between procedures with different processes. Consider our Peano adders:

(define (pa+ x y)
  (if (= x 0)
      y
      (pa+ (dec x) (inc y))))

and

(define (pb+ x y)
  (if (= x 0)
      y
      (inc (pb+ (dec x) y))))

Imperative programming involves writing statements which change the overall state of the program. Lisp does this using assignment statements called set!. set! is called by giving it two arguments. The second is a value, and the first is the variable to assign it to. Or:

(set! <var> <value>)

Consider what this assignment does. It creates an instant in time. Before this instant, <var> had no value, or some other value. After this set!, <var> has value <value>, which means that the set! changed something in the program state. Before the set! the state was (say) A, and after, it was a different state, (say) B. This is entirely different from any of our previous programs, all of which used functional programming style.

It should be obvious that procedures which use assignment are not bijective, that is, for the same input, they may have different outputs. Consider:

(define count 1)

(define (demo x)
  (set! count (inc count))
  (+ x count))

(demo 3)
(demo 3)
(demo 3)

5
6
7

demo does not compute any mathematical function. Instead, the successive values of count are set! and remembered somewhere in the environment each time demo is called.

Clearly, assignment introduces difficulties. Even our previous substitution model is now insufficient, since it is a static phenomenon which cannot account for changing values in the environment. Symbols now can refer to some place where the values of variables are stored. While this certainly makes our job harder, assignment is worth the trouble, as we’ll see later.

Here’s an iterative implementation of a functional factorial procedure:

(define (fact n)
  (define (iter m i)
    (cond ((> i n) m)
          (else
           (iter (* i m) (inc i)))))
  (iter 1 1))

(fact 4)

24

And an iterative implementation of an imperative-style factorial procedure:

(define (fact n)
  (let ((i 1) (m 1))
    (define (loop)
      (cond ((> i n) m)
            (else
             (set! m (* i m))
             (set! i (inc i))
             (loop))))
    (loop)))

(fact 4)

24

Note the difference between the two. The first passes successive values of i and m as parameters into the next call of iter. However, in the imperative style, the very values of i and m are changed to their new values, and the procedure simply called again without any arguments.

Note also that swapping the set! statements:

(set! i (inc i))
(set! m (* i m))

Will mess up the execution of the program, since m depends on i having the correct value at the time it’s reassigned to (* i m). The time instance creation inherent in assignment creates these time-based dependencies, which are worth being aware of.

We say that a variable v is “bound in an expression” E if the meaning of E is unchanged by the uniform replacement of v with a variable w (not occurring in E) for every occurrence of v in E.

Bound variables exist naturally in mathematics. Consider the expressions: \[\forall x\exists y P(x,y)\] \[\int_0^1 \frac{\mathrm{d}x}{1+x^2}\]

have no difference in meaning when \(x\) is substituted: \[\forall w\exists y P(w,y)\] \[\int_0^1 \frac{\mathrm{d}w}{1+w^2}\]

This is because, in both cases, \(x\) is a bound variable. Now,

A quantifier is a symbol which binds a variable.

Thus, in these cases, \(\forall\), \(\exists\), and \(\int\) were the quantifiers of bound variable \(x\). Similarly, consider a Lisp expression:

(lambda (y) ((lambda (x) (* x y)) 3))

Here, x and y are bound variables, and the λ are quantifiers for them. This can be illustrated by swapping out the variables and having no change in meaning:

(lambda (v) ((lambda (w) (* w v)) 3))

However, it is not necessary that all variables be bound. Consider the Lisp expression:

(lambda (x) (* x y))

x is bound, with quantifier λ. However, y is not bound (it is a free variable). This is because the definition of y does not come from the formal parameter list of a λ-expression or any other known location within the expression. Instead, it comes from somewhere outside. We cannot replace y with another variable v, since we don’t know what value y may have. Formally,

We say that a variable v is “free in an expression” E if the meaning of E is changed by the uniform replacement of v with a variable w (not occurring in E) for every occurrence of v in E.

In fact, in the expression:

(lambda (y) ((lambda (x) (* x y)) 3))

The symbol * is a free variable, since the expression’s meaning will change if we replace it with the symbol +.

Formally,

If x is a bound variable in E, then there is a λ-expression where it is bound. We call the list of formal parameters of this λ-expression the “bound variable list” and we say that the λ-expression “binds” the variable defined in the bound variable list. Moreover, those parts of the expression where a variable has a value defined by the λ-expression which binds it is called the “scope” of the variable.

Or, for example: \[\mathtt{(\lambda~(y)~\underbrace{\mathtt{((\lambda~(x)~\overbrace{\mathtt{(*~x~y)}}^{\mathrm{Scope~of~}\mathtt{x}})~3)}}_{\mathrm{Scope~of~}\mathtt{y}})}\]

./images/frames.pdf

An environment is made up of a linked chain of frames. Shown in the figure are three frames, I, II, and III. Now, each of A, B, C, and D are different environments, which view the frames in different ways.

Environments can be considered as different “vantage points” of the frame chain. From A, we see the values of the frame II and the frames behind II, in this case I. Therefore, we get the values of x, y, and z. However, there are two possible values of x. In this case, we say that the value of x in frame II “shadows” the value of x in all previous frames, and we consider that value to be the correct one. Note that this is actually making the choice to use the innermost scope’s variables over ones in outer scopes. Other environments are similarly analyzed. Note that C and D are the same environment.

A procedure objects consists of:

1. A pointer to the procedure object.
2. A pointer to the environment the procedure will execute in.

3. The actual body (code) of the procedure.

   Diagrammatically:

   ./images/frameobj.pdf

1. A procedure object is applied to a set of arguments by constructing a frame binding the formal parameters of the procedure to the actual arguments of the call, then evaluating the body of the procedure in the context of the new environment thus constructed. The new frame has as its enclosing environment the environment part of the procedure being applied.

   For example, for a procedure P, evaluated at (P 3 4), the actual arguments to P are “appended” to the environment P is called in. The procedure object itself has three pointers:

   • The first is to the procedure itself, P.
   • The second points to the extended environment.
   • The third point points to the actual λ.

   Diagrammatically:

   ./images/rule1.pdf

2. A λ-expression is evaluated relative to a given environment as follows: a new procedure object is formed, the combining the code of the λ-expression with a pointer to the environment of evaluation.

   This rule is self-explanatory.

   Our most important take-away is that an environment is a linked chain of frames, going all the way back to the first (global) frame. We now have a new working model, which works with assignment, as we’ll soon see.

Let’s play around with assignment in the environment model. Consider the following procedure:

(define make-counter
  (lambda (n)
    (lambda ()
      (set! n (inc n))
      n)))

What does the environment look like once we define make-counter? Something like this:

./images/make-counter.pdf

Let us now use make-counter to define two counters, each of which start at different values of n:

(define C1 (make-counter 0))
(define C2 (make-counter 10))

The environment now looks like:

./images/c1c2.pdf

See that there is no possible confusion between which n C1 uses and which n C2 uses. Moreover, neither C1 nor C2 would care about a globally defined n, or any n in a higher level frame, since it’d get shadowed by their own n’s.

We can now see how the following would work:

(C1)
(C2)
(C1)
(C2)

1
11
2
12

The first call to (C1) sees that n is zero in its environment, and sets n to 0+1=1, and returns 1. The first call to (C2) sees that its n is 10, sets it to 11, and returns 11. The second call to (C1) sees that its n is 1, then sets and returns 2. The final call to (C2) sees that its n is 11, which is then sets to 12 and returned.

We have some questions to answer about sameness and change of objects. Consider that in the previous example, C1’s n and C2’s n are both called n, and yet refer to different objects. However, C1 refers to only one object, C1. How then, can we tell if an identifier refers to an object? This issue is almost philosophical: if the only way know of an object is its identifier, what is an object anyway?

We avoid these issues in Lisp’s environment model by defining action, change, and identity as follows:

Action \(A\) has an effect on object \(X\) (\(A\) changes \(X\)) if property \(P\) true of \(X\) before \(A\) is false of \(X\) after \(A\).

and

\(X\) and \(Y\) are the same object if any action which changes \(X\) changes \(Y\).

The (Lisp) world is thus made up of many individual objects, all with some local state.

Cesàro’s theorem tells us that:

\[P(\mathrm{gcd}(a,b)=1) = \frac{6}{\pi^{2}}\]

Of course, we can estimate probabilities using the Monte Carlo method (do lots of tests, and divide the number of successful tests by the total number of tests conducted). Using assignment, the program looks like:

(define (estimate-pi n)
  (sqrt (/ 6 (monte-carlo n cesaro))))

(define (cesaro)
  (= (gcd (random 4294967087) (random 4294967087)) 1))

(define (monte-carlo trials experiment)
  (define (iter remaining passed)
    (cond ((= remaining 0)
           (/ passed trials))
          ((experiment)
           (iter (dec remaining)
                 (inc passed)))
          (else
           (iter (dec remaining)
                 passed))))
  (iter trials 0))

(estimate-pi 10000000)

3.141330429791511

Note that we use Racket’s built in random to generate a random number. However, if we had to implement a PRNG on our own, it’d look something like: