public
Last active

  • Download Gist
Y_combinator.ss
Scheme
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 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)

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

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.