6.001 Recitation #7

                      5-minute-problem #6b (UNUSED):
               Using Self-application instead of Recursion
                       (suggested by Amerasinghe, 9/24)


It is theoretically possible to eliminate all recursive definitions from
Scheme because they can be simulated by applying a procedure to itself in
an unusual way.  We'll illustrate the idea with the factorial procedure.

(define (fact-def-helper g)
  (lambda (n)
    (if (zero? n)
        1
        (* n ((g g) (- n 1))))))

(define factorial (fact-def-helper fact-def-helper))

To understand how this works, let <G> be a lambda-expression.  Using the
substitution model, the value of
                          (fact-def-helper <G>)
is
                          (lambda (n)
                              (if (zero? n)
                                  1
                                  (* n ((<G> <G>) (- n 1)))))

Now let <F> be the lambda-expression for the value of FACT-DEF-HELPER.
Then by the substitution model:
   (fact-def-helper fact-def-helper)
evaluates to 
   (<F> <F>)
which evaluates to the value
   (lambda (n)
     (if (zero? n)
         1
         (* n ((<F> <F>) (- n 1)))))

So the combination (<F> <F>) evaluates to the lambda-expression which is
the value of recursively defined FACTORIAL, except that (<F> <F>) appears
where the variable FACTORIAL would ordinarily appear.

Illustrate how this construction works by carrying out a careful
substitution model calculation for the value of
                              (factorial 2)