{{ message }}

Instantly share code, notes, and snippets.

# z5h/Y_combinator.ss

Created Nov 19, 2009
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 ; 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

### everton commented Dec 30, 2021 • edited

@makble your version without X don't work with the examples. It leads to infinite recursion.

to join this conversation on GitHub. Already have an account? Sign in to comment