[2/3/99]

===============================================================================

* The third section group is at MW 730-820pm, Phillips 407.
  The first section has officially moved to Upson 205.

===============================================================================

* Evaluation example from last section:

  --------------------
    (define (fact n)
      (if (zero? n)
        1
        (* n (fact (- n 1)))))
   
    (fact 6)
  --------------------

  Note that we still get the lambda expression although its not a literal part
  of the definition.

  --------------------
    ((lambda (n) (if (zero? n) 1 (* n (fact (- n 1))))) 6)
    (if (zero? 6) 1 (* 6 (fact (- 6 1))))
    (if #f 1 (* 6 (fact (- 6 1))))
    (* 6 (fact (- 6 1)))
    (* 6 (fact 5))
    (* 6 ((lambda (n) (if (zero? n) 1 (* n (fact (- n 1))))) 5))
    (* 6 (if (zero? 5) 1 (* 5 (fact (- 5 1)))))
    (* 6 (if #f 1 (* 5 (fact (- 5 1)))))
    (* 6 (* 5 (fact (- 5 1))))
    (* 6 (* 5 (fact 4)))
    (* 6 (* 5 ((lambda (n) (if (zero? n) 1 (* n (fact (- n 1))))) 4)))
    (* 6 (* 5 (if (zero? 4) 1 (* 4 (fact (- 4 1))))))
    (* 6 (* 5 (if #f 1 (* 4 (fact (- 4 1))))))
    (* 6 (* 5 (* 4 (fact 3))))
    ...
    (* 6 (* 5 (* 4 (* 3 (fact 2)))))
    ...
    (* 6 (* 5 (* 4 (* 3 (* 2 (fact 1))))))
    ...
    (* 6 (* 5 (* 4 (* 3 (* 2 (* 1 (fact 0)))))))
    ...
  --------------------

  Note that in the following we mustn't evaluate the else part of the if or we
  will enter an infinite loop.

  --------------------
    (* 6 (* 5 (* 4 (* 3 (* 2 (* 1 (if (zero? 0) 1 (* 0 (fact (- 0 1))))))))))
    (* 6 (* 5 (* 4 (* 3 (* 2 (* 1 (if #t 1 (* 0 (fact (- 0 1))))))))))
    (* 6 (* 5 (* 4 (* 3 (* 2 (* 1 1))))))
    (* 6 (* 5 (* 4 (* 3 (* 2 1)))))
    (* 6 (* 5 (* 4 (* 3 2))))
    (* 6 (* 5 (* 4 6)))
    (* 6 (* 5 24))
    (* 6 120)
    720
  --------------------

===============================================================================

* Note: it is crucial that we treat an if statement in a special way - we
  evaluate the condition first, then if it comes out true, we never try to
  evaluate the else part!  (just try to define a function that will work like
  if and see what happens).
  A simpler example where this requirement is obvious:

  --------------------
    (if (zero? x) 0 (/ y x))
  --------------------

===============================================================================

* Another note: observe how the expression that we hold (which is equivalent to
  stuff we keep on the stack while running) keeps growing.  This is since in
  every call we must "remember" the value of n, compute the factorial for n-1
  and only then get the final result.

===============================================================================

* A similar function that behaves in the same way is a function that sum the
  elements from 0 to n:

  --------------------
    (define (n-sum n)
      (if (zero? n)
        0
        (+ n (n-sum (- n 1)))))
  --------------------

===============================================================================

* In fact, these two functions are so similar, that we should be able to
  generalize them to a single function - and in fact we can - using higher
  order functions (in lectures to come).  For now, just try throwing ideas
  about how to do this.  Especially identify people that are stuck in the
  C/Pascal way - doing something like:

  --------------------
    (define (fact/n-sum n mul?)
      (if (zero? n)
        (if mul? 1 0)
        (if mul?
          (* n (fact/n-sum (- n 1)))
          (+ n (fact/n-sum (- n 1))))))

    (define (fact n) (fact/n-sum n #t))
    (define (n-sum n) (fact/n-sum n #f))
  --------------------

  We will return to this example and see how it can be done *much* more
  elegantly.  (Think about what you could do if you could pass functions as
  values for variables.)

===============================================================================

* Another interesting thing to play with: look at the definition of this
  function:

  --------------------
    (define (fact0 n a)
      (if (zero? n)
        a
        (fact0 (- n 1) (* n a))))

    (define (fact n) (fact0 n 1))
  --------------------

  If we try to evaluate this we get (again, simpler example on the board or a
  slide):

  --------------------
    (fact 3)
    ((lambda (n) (fact0 n 1)) 3)
    (fact0 3 1)
    ((lambda (n a) (if (zero? n) a (fact0 (- n 1) (* n a)))) 3 1)
    (if (zero? 3) 1 (fact0 (- 3 1) (* 3 1)))
    (if #f 1 (fact0 (- 3 1) (* 3 1)))
    (fact0 (- 3 1) (* 3 1))
    (fact0 2 3)
    ((lambda (n a) (if (zero? n) a (fact0 (- n 1) (* n a)))) 2 3)
    (if (zero? 2) 3 (fact0 (- 2 1) (* 2 3)))
    (if #f 3 (fact0 (- 2 1) (* 2 3)))
    (fact0 (- 2 1) (* 2 3))
    (fact0 1 6)
    ((lambda (n a) (if (zero? n) a (fact0 (- n 1) (* n a)))) 1 6)
    (if (zero? 1) 6 (fact0 (- 1 1) (* 1 6)))
    (if #f 6 (fact0 (- 1 1) (* 1 6)))
    (fact0 (- 1 1) (* 1 6))
    (fact0 0 6)
    ((lambda (n a) (if (zero? n) a (fact0 (- n 1) (* n a)))) 0 6)
    (if (zero? 0) 6 (fact0 (- 0 1) (* 0 6)))
    (if #t 6 (fact0 (- 0 1) (* 0 6)))
    6
  --------------------

===============================================================================

* The new thing here - the size of the expression does not grow!  Try to do the
  same trick to the n-sum function (or the generalized fact/n-sum).

===============================================================================