One of my favorite programming videos: Jim Weirich on the Y Combinator <a href="https://www.youtube.com/watch?v=FITJMJjASUs" rel="nofollow">https://www.youtube.com/watch?v=FITJMJjASUs</a>
Nice article, definitely piqued my interest in the lambda calculus, but there were a few points that were confusing for me as my first glimpse at the lambda calculus.<p>The first confusing point was the lack of definition of the order of operations. I first stumbled at the line (λy.(λx. x) y) a b . Is this supposed to be (λy.(λx. x) y) (a b) or ((λy.(λx. x) y) a) b . In this case both give the same answer, but it's not obvious that associativity holds in general.<p>It gets worse with the Y combinator: λf. (λx. f (x x))(λx. f (x x)) . Is this (λf. (λx. f (x x)))(λx. f (x x)) or λf. ((λx. f (x x))(λx. f (x x))) . Peeking ahead, it seems to be the latter, which makes more sense (otherwise the letter f would be pressed into service in two different contexts), but it's totally ambiguous from the rules that have been presented in the article.<p>The other point of confusion was regarding rule #3 (If t and s are both valid λ-terms, then t s is a valid λ-term.) The article tells is a certain manipulation we can do if t is a "function" (i.e. something that begins with a λ, I don't know the technical name for this), but doesn't say what to do if t is not a "function". As far as I can tell the answer is: do nothing, there is no simplification in this case. It would be nice if this was said explicitly.
My page on lambda diagrams at
<a href="http://www.cwi.nl/~tromp/cl/diagrams.html" rel="nofollow">http://www.cwi.nl/~tromp/cl/diagrams.html</a>
has a nice picture of the Y-combinator at the top,
and this note at the bottom:<p>The diagram in the title, produced by the postscript code below, is a slightly deformed alternative Y diagram made to look like a Y.<p><pre><code> %!PS-Adobe-2.0 EPSF-2.0
%%BoundingBox:0 0 118 110
/m{moveto}def/l{lineto}def/c{concat 6 m 0 6 l 7 8 m 0 8 l l l 3 6 l 2 6 m 7 6 l
3 4 m 6 4 l 6 6 l stroke}def 3 0 0 0 1[-8 4 0 8 60 9]c 3 2 0 2 2[-1 1 0 1 0 0]c</code></pre>
tl;dr<p>A fixed point p for a function f, is a value so that f(p)=p.<p>A semi-recursive function f is a like a recursive function, except that instead of invoking itself, it invokes some other function provided as an argument to f.<p>The y-combinator (aka fixed-point-combinator) is a function, that for a function f, finds a fixed point for f.<p>We can turn a semi-recursive function f into the corresponding recursive function g, by finding a fix point for f, which we can do using the y-combinator.
I once tried an insane thing: building the Y-Combinator in C, and wrote a blog post about it. <a href="http://kswizz.com/post/50429268286/fibonacci-the-y-combinator-in-c" rel="nofollow">http://kswizz.com/post/50429268286/fibonacci-the-y-combinato...</a><p>It was a fun thought exercise. Not something I'd use in production code.
From The Little Schemer - <a href="http://www.ccs.neu.edu/home/matthias/BTLS/sample.pdf" rel="nofollow">http://www.ccs.neu.edu/home/matthias/BTLS/sample.pdf</a><p>That chapter made me grok the Y Combinator.
If there's one thing that the prolific rise of the Y Combinator accelerator has done, it's made the combinator much harder to google for. (Though ofc Fixed-point combinator would still work).
Has the Y combinator been useful to anything? Has it been used in any software in a role other than pedagogic?<p>It's a beautiful way to make a recursive call without binding the function to an identifier, but has it actually proven useful? It would seem that languages that allow that make it easy to use the Y combinator also typically make it easy to use named recursion with a permanent or a temporary name.
Y Combinator in TXR's embedded Lisp dialect:<p><pre><code> @(do
;; The Y combinator:
(defun y (f)
[(op @1 @1)
(op f (op [@@1 @@1]))])
;; The Y-combinator-based factorial:
(defun fac (f)
(do if (zerop @1)
1
(* @1 [f (- @1 1)])))
;; Test: 4! -> 24
(pprinl [[y fac] 4]))</code></pre>
There appears to by a typo in one of the lines.<p>The line<p>6 * (if 3 == 0 then 1 else 1 * (YF)(1–1))<p>The previous line is
6 * (λx.(if x == 0 then 1 else x * (YF)(x–1)) 1)
When replacing the x s with 1s, it replaces one of the x s with 1, but replaces the first one with 3.<p>My guess was that this was copied from the first version, and they just forgot to change one of the threes to a 1.<p>(that is, unless I misunderstood something, which is of course possible)<p>I think the line should be<p>6 * (if 1 == 0 then 1 else 1 * (YF)(1–1))
It still amazes me that you can define the Y combinator in Haskell directly:<p><pre><code> y f = f (y f)
</code></pre>
And in ML, only slightly less directly:<p><pre><code> let rec y f x = f (y f) x</code></pre>