@@ -0,0 +1,224 @@
; Stumbling towards Y
;
; The applicative-order Y combinator is a function that allows one
; to create a recursive function without using define.
; This may seem strange. Usually a recursive function has to call
; itself, and thus relies on itself having been defined.
;
; Regardless, here we will stumble towards the implementation of the
; Y combinator (in Scheme).
;
; This was largely influenced by material in "The Little Schemer".
; http://www.ccs.neu.edu/home/matthias/BTLS/
;
; I wrote this because I needed the excersise of arriving at Y on my
; own terms.
;
; Mark Bolusmjak, 2009
; Disclaimer: This document and code are without warrenty.
; Let's start with the Factorial function as our example.
(define fact
(lambda (n )
(cond
((= 0 n) 1 )
(else (* n (fact (- n 1 )))))))
; Since we can't use define, let's strip that off.
; For the recursive call, let's just put in a placeholder
; to see how things look. We'll call the placeholder "myself".
(lambda (n )
(cond
((= 0 n) 1 )
(else (* n (myself (- n 1 ))))))
; Ok, we need a way for the function to call itself via "myself".
; How will we get a handle on that if we can't use define?
; Maybe something can pass it in for us. Let's hope so and
; keep going.
(lambda (myself )
(lambda (n )
(cond
((= 0 n) 1 )
(else (* n (myself (- n 1 )))))))
; That looks a lot like our original define-ed factorial function.
; Let's replace "myself" with fact and take a look (below).
;
; From the outside, it looks like something that makes the factorial
; function.
; Strangely, this function that creates the factorial function,
; relies on the function "fact" to be supplied to itself.
; Where will that come from?
; Doesn't that bring us back to square one?
(lambda (fact )
(lambda (n )
(cond
((= 0 n) 1 )
(else (* n (fact (- n 1 )))))))
; Well, here we have a function that builds the factorial function.
; That seems nearly as useful as a factorial function. Maybe we
; could pass that to itself and call on it when we need it.
;
; First we need to pass that whole (lambda (fact) ... ) to itself.
; It's pretty easy to pass a function to itself if we have it
; defined.
; e.g. (f f)
; What about an anonymous function?
; No problem, just write a helper function that takes any function
; and applies it to itself.
(lambda (f ) (f f))
; Ok, let's throw that in and take a look.
; We'll pass (lambda (fact) ... ) to itself via this helper.
((lambda (f ) (f f))
(lambda (fact )
(lambda (n )
(cond
((= 0 n) 1 )
(else (* n (fact (- n 1 ))))))))
; What happens if we try this out?
(((lambda (f ) (f f))
(lambda (fact )
(lambda (n )
(cond
((= 0 n) 1 )
(else (* n (fact (- n 1 )))))))) 0 )
; Hey it works for 0, but not for anything else.
; What's going on?
;
; With 0, (= 0 n) is true, and we get 1 back.
;
; If we try any other number we get a complaint that * is expecting a
; numbervas it's 2nd argument, but is getting a procedure. Huh?
; We got a bit ahead of ourselves.
; Recall, fact is not the factorial funtion anymore. It now *builds*
; the factorial function. We can't just pass it a number.
; As the fact builder function, it expects a function as an argument
; before it returns the actual function we want.
;
; This may be getting strange, but let's try to make a useful
; function out of fact by calling (fact fact). At least (fact fact)
; will work for the next step into our recursive function.
((lambda (f ) (f f))
(lambda (fact )
(lambda (n )
(cond
((= 0 n) 1 )
(else (* n ((fact fact) (- n 1 ))))))))
; Hmm ... recursion works by "always working for the next step",
; which we seem to have just covered. So could it work for all the
; "next steps"?
; Let's try to call that with a value other than 0.
(((lambda (f ) (f f))
(lambda (fact )
(lambda (n )
(cond
((= 0 n) 1 )
(else (* n ((fact fact) (- n 1 )))))))) 5 )
; Wow! That actually worked.
; Take a breather and think about this for a second. We just
; implemented a recursive function without using define.
; Pretty cool, but it's kind of messy.
;
; We have something that kind of looks like our original factorial
; definition in there. Let's try to refactor that out and see what
; we're left with.
;
; Our original fact function didn't have anything looking like a
; (fact fact) in it, so let's try to fix that first.
;
; As the next step, we'll pull out the (fact fact) and give it a
; name.
; What should we call it?
; fact is kind of like factorial builder at this point, so
; (fact fact) is more like the factorial function.
; Hmm ... let's just call (fact fact) fact2, see how things look and
; go from there.
;
; We're going to be clever and instead of simply passing (fact fact)
; in as fact2, we're going to wrap it up as a closure to prevent
; (fact fact) from getting evaluated before it gets passed in. Cool?
; We'll pass in (lambda (x) ((fact fact) x)) instead.
((lambda (f ) (f f))
(lambda (fact )
((lambda (fact2 )
(lambda (n )
(cond
((= 0 n) 1 )
(else (* n (fact2 (- n 1 )))))))(lambda (x ) ((fact fact) x)))))
; If we try this out, we see it still works.
(((lambda (f ) (f f))
(lambda (fact )
((lambda (fact2 )
(lambda (n )
(cond
((= 0 n) 1 )
(else (* n (fact2 (- n 1 )))))))(lambda (x ) ((fact fact) x))))) 12 )
; Taking a closer look, we see that (lambda (fact2) ... ) looks
; exactly like our original (lambda (fact) ... ).
; Let's simply rename fact to y, and fact2 to fact to make this
; clear.
((lambda (f ) (f f))
(lambda (y )
((lambda (fact )
(lambda (n )
(cond
((= 0 n) 1 )
(else (* n (fact (- n 1 )))))))(lambda (x ) ((y y) x)))))
; Let's pull out (lambda (fact) ... ) and pass it in as a parameter
; r (for recursive function).
((lambda (r )
((lambda (f ) (f f))
(lambda (y )
(r (lambda (x ) ((y y) x))))))
(lambda (fact )
(lambda (n )
(cond
((= 0 n) 1 )
(else (* n (fact (- n 1 ))))))))
; Still works! Try it.
(((lambda (r )
((lambda (f ) (f f))
(lambda (y )
(r (lambda (x ) ((y y) x))))))
(lambda (fact )
(lambda (n )
(cond
((= 0 n) 1 )
(else (* n (fact (- n 1 )))))))) 4 )
; Now we've isolated the scaffolding we've built to allow the
; creation of a recursive function without define.
;
; Finally, we've lived long enough without define, and that thing we
; built seems pretty useful.
; Let's use define and call it Y.
(define Y
(lambda (r )
((lambda (f ) (f f))
(lambda (y )
(r (lambda (x ) ((y y) x)))))))
; That's it. We've built the applicative-order Y combinator.
; Try it with another recursive function. Here it is with the
; Fibonacci number generator, taking a value of 8 as a parameter.
((Y
(lambda (fib )
(lambda (n )
(cond
((< n 2 ) n)
(else (+ (fib (- n 1 )) (fib (- n 2 )))))))) 8 )
z5h created this gist