6.001/Recitation 25
Rob Speer
< 6.001
[edit]
The Y combinator
Y = (λ(f) ((λ(h) (λ(x) ((f (h h)) x)))
((λ(h) (λ(x) ((f (h h)) x))))
(Y F) = (F (Y F))
That's all there is to it, but I suppose you'll want more explanation.
See the lecture slides at https://sicp-s1.mit.edu/spring06/lessons/Lesson27/lec27.pdf - I'll be working through those.
[edit]
The V combinator
(λ(x) ((λ(h) λ(x) (h h)) (λ(h) λ(x) (h h))))
No matter what you pass to V, it always returns V. It's a useless sort of recursion... unless you're programming in Unlambda.
[edit]
OMG WTF ``SKK
We still have time? Excellent. Let's work this into Unlambda.
In Unlambda, I means "true" and V means "false". How do you use them?
According to the Unlambda page:
(((ifthenelse b) x) y) evaluates x if b, and y if not b.
(ifthenelse b) = (call/cc (lambda (q) ((k (k i)) ((b q) k))))
(If you care, after you remove the lambdas, you get ``s`kc``s`k`s`k`k`ki``ss`k`kk.)
The big question: WTF does this do?
