; Let's jettison the baggage of representing numbers as Church numerals
; etc. and focus on recursion in native Scheme, using native data types,
; for simplicity.
(define fact-functional
(lambda (fact)
(lambda (n)
(if (= n 0)
1
(* n (fact (- n 1)))) ) ) )
; We know (from the Paradigms course) that a slightly modified
; functional can be called on itself to give "true" fact...
(define fact-functional-twin
(lambda (fact)
(lambda (n)
(if (zero? n)
1
(* n ( (fact fact) (- n 1) ))) ) ) )
; ]=> ( ( (lambda (m) (m m)) fact-functional-twin ) 6 )
; will do the right thing. And in fact, by definition,
; ]=> ( (fact-functional ( (lambda (m) (m m)) fact-functional-twin ) ) 6 )
; should do the same.
; We can actually implement the twin using fact-functional:
(define fact-functional-twin-2
(lambda (fact)
(fact-functional (fact fact))))
; ]=> ( (fact-functional-twin-2 fact-functional-twin-2) 6 )
; Oops! This won't work with an applicative order interpreter,
; because (fact fact) will land us in a hole before fact-functional
; can take over. But we already know how to fix this with an (inverse)
; eta transformation.
(define fact-functional-twin-3
(lambda (fact)
(fact-functional (lambda (a) ( (fact fact) a ) ) )))
; ]=> ( (fact-functional-twin-3 fact-functional-twin-3) 7 )
; feels much better.
; We should be able to generalize the transformation of
; fact-functional to fact-functional-twin-3 and its self-application
; to any recursive function.
(define (make-recursive functional)
( (lambda (m) (m m)) ; implements self-application
(lambda (func)
(functional (lambda (eta-var) ( (func func) eta-var )) ) ) ) )
; Finally, we should be able to say
; ]=> ( (make-recursive fact-functional) 7 )
; Let's use make-recursive to create another recursive function.
(define length-functional
(lambda (length)
(lambda (lst)
(if (null? lst) 0
(1+ (length (cdr lst))) ) ) ) )
; ]=> ( (make-recursive length-functional) '(may the power be with you) )
; behaves exactly as expected.
; Thus, make-recursive is a powerful routine which takes a functional
; as input and finds the fixpoint of the functional. It is also
; called the applicative order Y-combinator.
; Compiling (rec I E) to a lambda expression has now been solved.
; Simply eval to ( make-recursive (lambda I eval[E]) ).
;
; Exercise: Once you get comfortable with ASTs, try this out.