SICP 4.1.5 and 4.1.6
2024-07-17 Wed

Data as Programs

One operational view of the meaning of a program: a program is a description of an abstract machine (Cf. the lecture).
Example: factorial.
The evaluator can be thought of as a special machine that takes as input a description of a machine and emulates the machine whose description it takes.
The evaluator could, for example, take factorial and be able to compute factorials.
The evaluator can, therefore, be seen as a universal machine.
``This is striking'' (386)
``Another striking aspect of the evaluator is that it acts as a bridge between the data objects that are manipulated by our programming language and the programming language itself''. (386)
``That the user's program are the evaluator's data need not be a source of confusion.'' (386)

Exercise 4.15

Exercise:

Given a one-argument procedure p and an object a, p is said to "halt" on a if evaluating the expression (p a) returns a value (as opposed to terminating with an error message or running forever). Show that it is impossible to write a procedure halts? that correctly determines whether p halts on a for any procedure p and object a. Use the following reasoning: If you had such a procedure halts?, you could implement the following program:

(define (run-forever) (run-forever))

(define (try p)
  (if (halts? p p)
      (run-forever)
      'halted))

Now consider evaluating the expression (try try) and show that any possible outcome (either halting or running forever) violates the intended behavior of halts?.¹

Answer:

Suppose that applying try to try halts. If so, then, when calling (try try), we will call (run-forever) and, indeed, run forever.

Suppose that applying try to try does not halt. If so, then, when calling (try try), we would return halted.

So, this is the way I would put it: we have got a paradox. On the one hand, if (try try) halts, then it doesn't halt. On the other hand, if (try try) does not halt, then it halts.

Internal Definitions

Environment model of evaluation & metacircular evaluator: definition are executed ``in sequence, extending the environment frame one definition at a time.''
``This is particularly convenient for interactive program development…''
``However, if we think carefully about the internal definitions used to implement block structure […] we will find that name-by-name extension of the environment may not be the best way to define local variables.''

Example:

(define (f x)
  (define (even? n)
    (if (= n 0)
        true
        (odd? (- n 1))))
  (define (odd? n)
    (if (= n 0)
        false
        (even? (- n 1))))
  <REST OF BODY OF `F'>)

``the only satisfactory interpretation of the two define's is to regard them as if the name even? and odd? were being added to the environment simultaneously.''
``More generally, in block structure, the scope of a local name is the entire procedure body in which the define is evaluated.''
``…our interpreter will evaluate calls to f correctly, but for an "accidental" reason…''
There is ``a simple way to treat definitions so that internally defined names have truly simultaneous scope''…
The procedure
```
(lambda <VARS>
  (define u <E1>)
  (define v <E2>)
  <E3>)
```
can be transformed into
```
(lambda <VARS>
  (let ((u '*unassigned*)
        (v '*unassigned*))
    (set! u <E1>)
    (set! v <E2>)
    <E3>))
```
``where `*unassigned*' is a special symbol that causes looking up a variable to signal an error if an attempt is made to use the value of the not-yet-assigned variable.''

Exercise 4.16

Exercise:

In this exercise we implement the method just described for interpreting internal definitions. We assume that the evaluator supports let (See Exercise 4.6).

a. Change lookup-variable-value (Section 4.1.3) to signal an error if the value it finds is the symbol *unassigned*.

b. Write a procedure scan-out-defines that takes a procedure body and returns an equivalent one that has no internal definitions, by making the transformation described above.

c. Install scan-out-defines in the interpreter, either in make-procedure or in procedure-body (section 4-1-3). Which place is better? Why?

Answer:

(define (lookup-variable-value var env)
  (define (env-loop env)
    (define (scan vars vals)
      (cond ((null? vars)
             (env-loop (enclosing-environment env)))
            ((eq? var (car vars))
             (if (eq? (car vals) '*unassigned*)
                 (error "not-yet-assigned variable" var)
                 (car vals)))
            (else (scan (cdr vars) (cdr vals)))))
    (if (eq? env the-empty-environment)
        (error "Unbound variable" var)
        (let ((frame (first-frame env)))
          (scan (frame-variables frame)
                (frame-values frame)))))
  (env-loop env))

(define (filter pred seq)
  (cond ((null? seq)
         nil)
        ((pred (car seq))
         (cons (car seq)
               (filter pred (cdr seq))))
        (else (filter pred (cdr seq)))))

(define (append l1 l2)
  (if (null? l1)
      l2
      (cons (car l1) (append (cdr l1) l2))))

;; example of a procedure body
(define body-example
  '((define even?
      (lambda (n)
        (if (= n 0)
            true
            (odd? (- n 1)))))
    (define odd?
      (lambda (n)
        (if (= n 0)
            false
            (even? (- n 1)))))
    (message "hello world")
    (progn (* 3 3)
           (message "foobar"))
    (define another-var
      (* 3 2))))

;; return a list with:
;; car   (1st el): body without definitions
;; cadr  (2nd el): a list of the variables
;; caddr (3rd el): a list of the values for the variables
(define (gp-build-lists body body-no-defs vars vals)
  (cond ((null? body)
         (list body-no-defs vars vals)) ;; we finished scanning, return results
        ((eq? (caar body) 'define)
         (gp-build-lists (cdr body) ;; filter definition out
                         body-no-defs ;; nothing to be addedd to new-body (we
                         ;; want the define to be gone)
                         (cons (cadar body) vars) ;; add var
                         (cons (caddar body) vals))) ;; add val
        (else (gp-build-lists (cdr body)
                              (append body-no-defs (list (car body)))
                              vars
                              vals))))

;; map vars to lists whose car is the var and show cadr is the symbol
;; '*unassigned*
(define (build-unassigned-vars vars)
  ;; we could use map, but I'm doing it manually
  (if (null? vars)
      nil
      (cons (list (car vars) '*unassigned*) (build-unassigned-vars (cdr vars)))))

;; maps vars to lists whose car is the var and whose cadr is the
;; associated val
(define (build-sets vars vals)
  ;; we could use map, but I'm doing it manually
  (if (null? vars)
      nil
      (cons (list 'set! (car vars) (car vals))
            (build-sets (cdr vars) (cdr vals)))))

(define (scan-out-defines body)
  (let ((lists (gp-build-lists body nil nil nil)))
    (let ((body-no-defs (car lists))
          (vars (cadr lists))
          (vals (caddr lists)))
      (append (append
               (cons 'let (list (build-unassigned-vars vars)))
               (build-sets vars vals))
              body-no-defs))))

;; example:
(scan-out-defines body-example)
;; =>
;; (let ((another-var *unassigned*) (odd? *unassigned*) (even? *unassigned*))
;; (set! another-var (* 3 2))
;; (set! odd? (lambda (n) (if (= n 0) false (even? (- n 1)))))
;; (set! even? (lambda (n) (if (= n 0) true (odd? (- n 1)))))
;; (message "hello world")
;; (progn (* 3 3) (message "foobar")))

c:

Make-procedure is used in eval to construct procedures. Procedure-body is used in apply to select the bodies of procedures.

I think it would be better to install scan-out-defines in make-procedure, rather than in procedure-body, because we would avoid calling scan-out-defines more than once for the same procedure (scan-out-defines would be called for each application).
```
(define (make-procedure parameters body env)
  (list 'procedure parameters (scan-out-defines body) env))
```

Exercise 4.17

Exercise:

Draw diagrams of the environment in effect when evaluating the expression <e3> in the procedure in the text, comparing how this will be structured when definitions are interpreted sequentially with how it will be structured if definitions are scanned out as described. Why is there an extra frame in the transformed program? Explain why this difference in environment structure can never make a difference in the behavior of a correct program. Design a way to make the interpreter implement the "simultaneous" scope rule for internal definitions without constructing the extra frame.

Answer:

The following is the environment structure when definition are interpreted sequentially; <e3> is evaluated in E1.

 global env
      |
      V
+-------------+
| ...         |
|             |
+-------------+
       ^    ^        E1
       |    |         |
       |    |         V
 +---+-+-+  |    +-------------+
 | . | . |  +----+  u: e1      |
 +-+-+---+       |  v: e2      |
   |             +-------------+
   |
   V
 params: vars
 body: (define u <E1>)
       (define v <E2>)
       <E3>

The following is the environment structure when definition are scanned out; <e3> is evaluated in E2.

   global env
      |
      V
+-------------+
| ...         |
|             |
+-------------+
       ^    ^                 E1
       |    |                  |
       |    |                  V
 +---+-+-+  |             +-------------+
 | . | . |  +-------------+ vars        |
 +-+-+---+                |             |
   |                      +-------------+          E2
   |                                  ^             |
   V                                  |             V
 params: vars                         |  +-------------+
 body: (let ((u '*unassigned*)        +--+ u: e1       |
            (v '*unassigned*))           | v: e2       |
         (set! u <E1>)                   +-------------+
         (set! v <E2>)
         <E3>)

In the second structure there is an extra frame because a let is equivalent to the application of a lambda, and the application of a lambda involves the creation of a new frame.

As long as <e3> is evaluated after u is set to e1 and v to e2 there won't be any difference between the behaviuor in the two environments, because there is no difference with respect to the values of the bindings in the environment.

Simultaneous scope without an extra frame could be achieved by transforming the body of the lambda so that all its internal definitions come before all the rest (cf. the ``accidental reason'', Authors mention, because calls to the example procedure f work).

Exercise 4.19

Exercise:

Ben Bitdiddle, Alyssa P. Hacker, and Eva Lu Ator are arguing about the desired result of evaluating the expression
(let ((a 1))
  (define (f x)
    (define b (+ a x))
    (define a 5)
    (+ a b))
  (f 10))
Ben asserts that the result should be obtained using the sequential rule for define: b is defined to be 11, then a is defined to be 5, so the result is 16. Alyssa objects that mutual recursion requires the simultaneous scope rule for internal procedure definitions, and that it is unreasonable to treat procedure names differently from other names. Thus, she argues for the mechanism implemented Exercise 4.16. This would lead to a being unassigned at the time that the value for b is to be computed. Hence, in Alyssa's view the procedure should produce an error. Eva has a third opinion. She says that if the definitions of a and b are truly meant to be simultaneous, then the value 5 for a should be used in evaluating b. Hence, in Eva's view a should be 5, b should be 15, and the result should be 20. Which (if any) of these viewpoints do you support? Can you devise a way to implement internal definitions so that they behave as Eva prefers?

Answer:

Both Ben's approach and Alyssa's approach seem okay to me. As far as I can see, a serious obstacle for Eva's approach is represented by what we might call ``interdependent definitions''. For example, what would we be supposed to do if the definitions of b and a were the following?

(define b (+ a x))
(define a (b + 5))

I cannot see a way to follow Eva's approach, given the possibility of this kind of situations, can I?

(

Authors say that MIT Scheme generates an error. Javascript raises an error too, when evaluating equivalent code:

((a) => {
  function f(x) {
    let b = a + x;
    let a = 5;
    return a + b;
  }
  f(10);
})(1)
/*
  Uncaught ReferenceError: Cannot access 'a' before initialization
  at f (REPL11:4:15)
  at REPL11:9:5
*/

)

Exercise 4.20

Exercise:

Because internal definitions look sequential but are actually simultaneous, some people prefer to avoid them entirely, and use the special form letrec instead. Letrec looks like let, so it is not surprising that the variables it binds are bound simultaneously and have the same scope as each other. The sample procedure f above can be written without internal definitions, but with exactly the same meaning, as
(define (f x)
  (letrec ((even?
            (lambda (n)
              (if (= n 0)
                  true
                  (odd? (- n 1)))))
           (odd?
            (lambda (n)
              (if (= n 0)
                  false
                  (even? (- n 1))))))
    <rest of body of f>))
Letrec expressions, which have the form
(letrec ((<var_1> <exp_1>) ... (<var_n> <exp_n>))
  <body>)
are a variation on let in which the expressions <exp_k> that provide the initial values for the variables <var_k> are evaluated in an environment that includes all the letrec bindings. This permits recursion in the bindings, such as the mutual recursion of even? and odd? in the example above, or the evaluation of 10 factorial with
(letrec ((fact
          (lambda (n)
            (if (= n 1)
                1
                (* n (fact (- n 1)))))))
  (fact 10))
a. Implement letrec as a derived expression, by transforming a letrec expression into a let expression as shown in the text above or in Exercise 4.18. That is, the letrec variables should be created with a let and then be assigned their values with set!.

b. Louis Reasoner is confused by all this fuss about internal definitions. The way he sees it, if you don't like to use define inside a procedure, you can just use let. Illustrate what is loose about his reasoning by drawing an environment diagram that shows the environment in which the <rest of body of f> is evaluated during evaluation of the expression (f 5), with f defined as in this exercise. Draw an environment diagram for the same evaluation, but with let in place of letrec in the definition of f.

Answer:

(define (append l1 l2)
  (if (null? l1)
      l2
      (cons (car l1) (append (cdr l1) l2))))

(define example-letrec
  '(letrec ((even?
             (lambda (n)
               (if (= n 0)
                   true
                   (odd? (- n 1)))))
            (odd?
             (lambda (n)
               (if (= n 0)
                   false
                   (even? (- n 1))))))
     (message "ciao")
     (message "hola")))

(define (letrec-body exp)
  (cddr exp))

(define (letrec-bindings exp)
  (cadr exp))

(define (letrec-vars bindings)
  (if (null? bindings)
      nil
      (cons (caar bindings) (letrec-vars (cdr bindings)))))

(define (letrec-vals bindings)
  (if (null? bindings)
      nil
      (cons (cadar bindings) (letrec-vals (cdr bindings)))))

(define (letrec-build-unassigned-vars vars)
  (if (null? vars)
      nil
      (cons (list (car vars) '*unassigned*) (letrec-build-unassigned-vars (cdr vars)))))

(define (letrec-build-sets vars vals)
  (if (null? vars)
      nil
      (cons (list 'set! (car vars) (car vals))
            (letrec-build-sets (cdr vars) (cdr vals)))))

(define (letrec-to-let exp)
  (append
   (cons 'let (list (letrec-build-unassigned-vars (letrec-vars (letrec-bindings exp)))))
   (append (letrec-build-sets (letrec-vars (letrec-bindings exp))
                              (letrec-vals (letrec-bindings exp)))
           (letrec-body exp))))

(letrec-to-let example-letrec)
;; =>
;; (let ((even? *unassigned*) (odd? *unassigned*))
;;   (set! even? (lambda (n) (if (= n 0) true (odd? (- n 1)))))
;;   (set! odd? (lambda (n) (if (= n 0) false (even? (- n 1)))))
;;   (message "ciao")
;;   (message "hola"))

I had a bit of trouble doing part b of the exercise. But, after looking on the web for what people have said and asking for help…, the following should be the correct drawings. The key thing to notice, assuming this is correct, is that, when using let (which is just a lambda; see p. 64), the expressions whose evaluation gives the values of the let bindings are not evaluated in the context of the new frame created by the let, but they are evaluated in the context of the frame to which the new frame created by the let points to (that is, its ``enclosing environment''). In a sense, we can say, they are evaluated while the new frame is in the process of being created.

When using letrec, <rest of body of f> is evaluated in the following E2 frame:

      E0
  +-------------------+
  |f:--+              |
  |    |              |
  |    |              |
  +----+--------------+
       |   ^    ^
       |   |    |
       V   |    |                 E1
+---+---+  |    |   +--+------+---------+
| | |  -+--+    +---+x: 5               |
+-+-+---+           +-------------------+
  |                          ^
  V                          |
 ...                         |
                             |    E2
                     +-------+------------+
                     | even?:-------------+---------------+
                     |                    |               |
                     |                    |<-----------   |
                     | odd?:---+          |            \  |
                     +---------+----------+             \ V
                               |     ^             +---+-\-+
                               |     |             | | |   +
                               |     |             +-+-+---+
                               V     |               |
                          +---+---+  |               |
                          | | |  -+--+               V
                          +-+-+---+                 ...
                            |
                            |
                            V
                           ...

When using let, <rest of body of f> is evaluated in the following E2 frame:

    E0
  +-------------------+
  |f:--+              |
  |    |              |
  |    |              |
  +----+--------------+
       |   ^    ^
       |   |    |
       V   |    |                 E1
+---+---+  |    |   +--+------+---------+ <----------------------------+
| | |  -+--+    +---+x: 5               | <---------------------+      |
+-+-+---+           +-------------------+                       |      |
  |                          ^                                  |      |
  V                          |                                  |      |
 ...                         |                                  |      |
                             |    E2                            |      |
                     +-------+------------+                     |      |
                     | even?:-------------+---------------+     |      |
                     |                    |               |     |      |
                     |                    |               |     |      |
                     | odd?:---+          |               |     |      |
                     +---------+----------+               V     |      |
                               |                   +---+---+    |      |
                               |                   | | |  -+----+      |
                               |                   +-+-+---+           |
                               V                     |                 |
                          +---+---+                  |                 |
                          | | |   +---------+        V                 |
                          +-+-+---+         |       ...                |
                            |               |                          |
                            |               |                          |
                            V               |                          |
                           ...              |                          |
                                            |                          |
                                            +--------------------------+

Exercise 4.21

Exercise:

Amazingly, Louis's intuition in Exercise 4.20 is correct. It is indeed possible to specify recursive procedures without using letrec (or even define), although the method for accomplishing this is much more subtle than Louis imagined. The following expression computes 10 factorial by applying a recursive factorial procedure².
((lambda (n)
   ((lambda (fact)
      (fact fact n))
    (lambda (ft k)
      (if (= k 1)
          1
          (* k (ft ft (- k 1)))))))
 10)
a. Check (by evaluating the expression) that this really does compute factorials. Devise an analogous expression for computing Fibonacci numbers.

b. Consider the following procedure, which includes mutually recursive internal definitions:
(define (f x)
  (define (even? n)
    (if (= n 0)
        true
        (odd? (- n 1))))
  (define (odd? n)
    (if (= n 0)
        false
        (even? (- n 1))))
  (even? x))
Fill in the missing expressions to complete an alternative definition of f, which uses neither internal definitions nor letrec:
(define (f x)
  ((lambda (even? odd?)
     (even? even? odd? x))
   (lambda (ev? od? n)
     (if (= n 0) true (od? <??> <??> <??>)))
   (lambda (ev? od? n)
     (if (= n 0) false (ev? <??> <??> <??>)))))

Answer:

((lambda (n)
   ((lambda (fib)
      (fib fib n))
    (lambda (ft k)
      (cond ((= k 0)
             0)
            ((= k 1)
             1)
            (else (+ (ft ft (- k 1))
                     (ft ft (- k 2))))))))
 12) ;; => 144

(define (f x)
  ((lambda (even? odd?)
     (even? even? odd? x))
   (lambda (ev? od? n)
     (if (= n 0) true (od? ev? od? (- n 1))))
   (lambda (ev? od? n)
     (if (= n 0) false (ev? ev? od? (- n 1))))))

Footnotes:

Although we stipulated that `halts?' is given a procedure object, notice that this reasoning still applies even if `halts?' can gain access to the procedure's text and its environment. This is Turing's celebrated "Halting Theorem", which gave the first clear example of a "non-computable" problem, i.e., a well-posed task that cannot be carried out as a computational procedure.

This example illustrates a programming trick for formulating recursive procedures without using define. The most general trick of this sort is the Y "operator", which can be used to give a "pure λ-calculus" implementation of recursion. (See Stoy 1977 for details on the λ calculus, and Gabriel 1988 for an exposition of the Y operator in Scheme.)

SICP 4.1.5 and 4.1.6 2024-07-17 Wed

Data as Programs

Exercise 4.15

Internal Definitions

Exercise 4.16

Exercise 4.17

Exercise 4.19

Exercise 4.20

Exercise 4.21

Footnotes:

SICP 4.1.5 and 4.1.6
2024-07-17 Wed