6.001                                                    Recitation #7
                                                         A.R. Meyer
                           NOTES FOR FRI, 9/19


EXAMPLE 1: Substitution Model evaluation

     (define (fact n)
       (if (= n 1)
	   1
	   (* n (fact (- n 1)))))

is sugar for

(define fact (lambda (n) (if (= n 1) 1 (* n (fact (- n 1)))))

Now evaluate:

     (fact                                             3)

             ;substitute the value of FACT in for FACT:
     ((lambda (n) (if (= n 1) 1 (* n (fact (- n 1))))) 3)

             ;to apply the lambda expression, substitute
             ;3 for N in its body:
     (if (= 3 1) 1 (* 3 (fact (- 3 1))))

             ;substitute the value for the primitive application (+ 3 1):
     (if #f 1 (* 3 (fact (- 3 1))))

             ;use the rewrite rule for IF:
     (* 3 (fact (- 3 1)))

             ;substitute the value of FACT in for FACT:
     (* 3 ((lambda (n) (if (= n 1) 1 (* n (fact (- n 1))))) 2))

             ;and so on:
     (* 3 (if (= 2 1) 1 (* 2 (fact (- 2 1)))))
     (* 3 (if #f 1 (* 2 (fact (- 2 1)))))
     (* 3 (* 2 (fact (- 2 1))))
     (* 3 (* 2 ((lambda (n) (if (= n 1) 1 (* n (fact (- n 1))))) 1)))
     (* 3 (* 2 (if (= 1 1) 1 (* 1 (fact (- 1 1))))))
     (* 3 (* 2 (if #t 1 (* 1 (fact (- 1 1))))))
     (* 3 (* 2 1))
     (* 3 2)
     6


EXAMPLE 2: HIGHER-ORDER PROCEDURES

A procedure MAKE-PAIR is called a "pairing procedure" if it satisfies the

PAIRING CONTRACT: There are procedures FIRST and SECOND such that
                 (first (make-pair <val0> <val1>)) ==> <val0>
and
                 (second (make-pair <val0> <val1>)) ==> <val1>
for all scheme values <val0>, <val1>.


For example, the following definitions will do the job:

(define (make-pair v0 v1)
  (lambda (which)
    (if (zero? which) v0 v1)))

(define (first a-pair) (a-pair 0))

(define (second a-pair) (a-pair 1))


To see how these definitions work, let's use the Substitution Model
to verify that (make-pair 7 9) evaluates to 7.

(first (make-pair                                                 7 9))

             ;substitute the value of MAKE-PAIR in for MAKE-PAIR:
(first ((lambda (v0 v1)(lambda (which) (if (zero? which) v0 v1))) 7 9))

             ;to apply the lambda expression, substitute 7 and 9
             ;for v0 and v1 in its body:
(first                 (lambda (which) (if (zero? which) 7 9))        )
                       .                                     .
                       .                                     .
                       \                                    /
                        ----this lambda expr IS the pair----

             ;substitute the value of FIRST in for FIRST:
((lambda (a-pair) (a-pair 0)) (lambda (which) (if (zero? which) 7 9)))

             ;to apply the lefthand lambda expression, substitute
             ;the righthand lambda expression for A-PAIR in the body 
             ;of the lefthand lambda expression:
((lambda (which) (if (zero? which) 7 9)) 0)

             ;to apply the lambda expression, substitute 0 for WHICH:
(if (zero? 0) 7 9)

             ;substitute the value for the primitive application (zero? 0):
(if #t 7 9)

             ;use the rewrite rule for IF:
7

      -------THE FOLLOWING WAS DISTRIBUTED BUT NOT DISCUSSED:-------

EXAMPLE 3: Scoping and Renaming Rules:

DEFINE, LAMBDA, and LET are "binding constructs" in Scheme.  Variables
which are "bound" by the same occurrence of binding construct can always
be renamed to "fresh" names, that is, names which do not appear within the
scope of the binding construct.  Scheme evaluation rules guarantee that
such fresh renaming will have no detectable effect on the 
evaluation of Scheme expressions.

To show which variables are "bound" where
in the following example, we rename them as variables with numerical suffixes:

ORIGINAL:

(define (sqrt x)
  (define (good-enough? guess x)
    (< (abs (- (square guess) x)) 0.001))
  (define (improve guess x)
    (average guess (/ x guess)))
  (define (sqrt-iter guess x)
    (if (good-enough? guess x)
        guess
        (sqrt-iter (improve guess x) x)))
  (sqrt-iter 1.0 x))

RENAMED:

(define (sqrt x1)
  (define (good-enough?1 guess1 x2)
    (< (abs (- (square guess1) x2)) 0.001))
  (define (improve1 guess2 x3)
    (average guess2 (/ x3 guess2)))
  (define (sqrt-iter1 guess3 x4)
    (if (good-enough?1 guess3 x4)
        guess3
        (sqrt-iter1 (improve1 guess3 x4) x4)))
  (sqrt-iter1 1.0 x1))

IMPORTANT POINT: note that the occurrence of GOOD-ENOUGH? within the body
of the definition of SQRT-ITER counts as within the scope of the
definition of GOOD-ENOUGH 5 lines above: the scope of each DEFINE at the
beginning of a body includes the bodies of all the other DEFINE's at the
beginning of the body.  We could also have renamed SQRT, but we didn't
bother to since it occurs only once.  We CAN'T rename AVERAGE, since it is
not bound in the expression above -- it occurs as a "free" or "global"
variable.

EXAMPLE 4:  ((lambda (x) (* x (+ x y))) (* x y))

The X in parens following LAMBDA is a "binding occurrence" and the next
two X's are bound to it.  The fourth X is a free occurrence.  Both Y's are
free occurrences.  We can rename the bound X's:


 ((lambda (x1) (* x1 (+ x1 y))) (* x y))



IN CLASS EXERCISE:

Do enough fresh renaming in the following expression to ensure that there
is at most one binding of each variable name.  Also, make sure that no 
variable has both bound and free occurences.


(let ((m (lambda (n)
           (let ((n-times-2 (* n 2)))
             (lambda (i j) (- n-times-2 (+ i j)))))))
  (define (max2d m n)
    (define (max1d m n)
      (define (iter max-so-far k)
        (if (zero? k)
            max-so-far
            (iter
             (max max-so-far (m k))
             (- k 1))))
      (iter 0 n))
    (if (zero? n)
        0
        (max (max1d (lambda (i) (m n i)) (- n 1))
             (max1d (lambda (j) (m j n)) n)
             (max2d m (- n 1)))))
  (max2d (m 4) n))