{{ message }}

Instantly share code, notes, and snippets.

# z5h/Y_combinator.ss

Created Nov 19, 2009
 ; 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)

### makble commented Apr 9, 2014

 More general form. x is unnecessary. ```(define Y (lambda (r) ((lambda (f) (f f)) (lambda (y) (r (y y))))))``` Equals `λr.(λy.(r (y y)) λy.(r (y y)))` Better naming ```Y = λf.(λs.(f (s s)) λs.(f (s s))) Y f = f ( Y f )``` f is the function need to recursive s means self application