8 ms·
The Y Combinator (no, not that one) – A Crash Course on Lambda Calculus
- vqc 12y agoOne of my favorite programming videos: Jim Weirich on the Y Combinator https://www.youtube.com/watch?v=FITJMJjASUs https://www.youtube.com/watch?v=FITJMJjASUs
- bsaul 12y agoThanks for letting me discover the work of that man. Its approach to learning about something by actually doing it really shines in the video you linked.
- jparishy 12y agoIf anyone hasn't seen this I highly recommend it, if not just because Weirich was a great guy and was very entertaining. RIP.
- vhost- 12y agoThanks for this. I just learned a lot!
- prawks 12y agoGreat video, I was hoping it would be linked here. Jim's is not only an informative talk but an inspirational ability to teach.
- socksy 12y agoIf 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).
- yzzxy 12y agoI actually complained about this on twitter a while ago, and pg said he didn't believe me - recommending "y combinator lambda" as a search string. But more specific things like "y combinator golang" require you to block HN and a few other sites to get meaningful results.
- kazinator 12y agoY Combinator in TXR's embedded Lisp dialect: @(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]))
- deleted 12y ago[deleted]
- anatoly 12y agoHas the Y combinator been useful to anything? Has it been used in any software in a role other than pedagogic? 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.
- jng 12y agoHey. You're completely missing it. The Y combinator shows that full general computation, including recursion and iteration, derives automatically and inevitably from just basic rewrite rules. Obviously it is too raw to be used directly. But if you design/implement any system with rewrite rules, you have provided indefinite power for recursions, and you have opened the Pandora box of undecidable-termination. This means that decidable computation can only occur without rewriting, which is incredibly restricted. Food for thought.
- eru 12y agoExactly! Look at eg primitive recursion for an interesting subset of computation that does not suffer from undecidability. Most programmers are familiar with regular expressions, too. There are another interesting subset.
- fexl 12y agoI do use it directly. For example in Fexl I define the append function for lists as: \append=(@\append\x\y x y \h\t [h; append t y]) Where '@' is the Y-combinator. Note that there's no direct self-reference with the symbol "append" there. I could define it equivalently as: \append=(@\loop\x\y x y \h\t [h; loop t y])
- anatoly 12y agoWhy? Is it unreasonably difficult for you to implement recursion via direct self-reference in your language? Or do you just not want to because the Y combinator is there and it's cool?
- SeoxyS 12y agoI once tried an insane thing: building the Y-Combinator in C, and wrote a blog post about it. http://kswizz.com/post/50429268286/fibonacci-the-y-combinator-in-c http://kswizz.com/post/50429268286/fibonacci-the-y-combinato... It was a fun thought exercise. Not something I'd use in production code.
- tromp 12y agoMy page on lambda diagrams at http://www.cwi.nl/~tromp/cl/diagrams.html http://www.cwi.nl/~tromp/cl/diagrams.html has a nice picture of the Y-combinator at the top, and this note at the bottom: The diagram in the title, produced by the postscript code below, is a slightly deformed alternative Y diagram made to look like a Y. %!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
- agumonkey 12y agoSince SICP and Lambda papers I have a fascination for the relationship with discrete math, computing devices and their topology. This doesn't help.
- derengel 12y agoFrom The Little Schemer - http://www.ccs.neu.edu/home/matthias/BTLS/sample.pdf http://www.ccs.neu.edu/home/matthias/BTLS/sample.pdf That chapter made me grok the Y Combinator.
- agumonkey 12y agoStill wishing more people read that book. It is not overrated.
- JimmyM 12y agoI love Racket, and thus Schemes of many kinds, but that chapter is really difficult for me to read compared to more academic or technical approaches - and I am really not an academic or technical person! I find the use of some sort of Socratique dialogue to be deeply confusing, distracting and frustrating. Creepy, SCP-foundation or Welcome-to-Nightvale-like asides such as "We did not expect you to know this." only add to my confusion. It makes simple concepts like recursion look like some sort of House of Leaves nightmare world.
- im3w1l 12y agotl;dr A fixed point p for a function f, is a value so that f(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. The y-combinator (aka fixed-point-combinator) is a function, that for a function f, finds a fixed point for f. 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.
- tel 12y agoAlso, and a big also, the Y-combinator exists in (untyped) lambda calculus---e.g. all you need is abstraction and application. This came as a shock to Church when he invented it as he wanted to use LC as a language for mathematical logic and fixed point combinators spell out doom for logical purposes. He thus invented the simply typed lambda calculus to banish such constructions.
- deleted 12y ago[deleted]
- drdeca 12y agoThere appears to by a typo in one of the lines. The line 6 * (if 3 == 0 then 1 else 1 * (YF)(1–1)) 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. My guess was that this was copied from the first version, and they just forgot to change one of the threes to a 1. (that is, unless I misunderstood something, which is of course possible) I think the line should be 6 * (if 1 == 0 then 1 else 1 * (YF)(1–1))
- ayanonagon 12y agoNice catch, thank you. I've fixed it now. :)
- cousin_it 12y agoIt still amazes me that you can define the Y combinator in Haskell directly: y f = f (y f) And in ML, only slightly less directly: let rec y f x = f (y f) x
- wlevine 12y agoNice 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. 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. 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. 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.
- deleted 12y ago[deleted]
- chriswarbo 12y agoThere are only two bits of syntax for lambda calculus: 'application', written "a b", and 'abstraction', which I'll write as "\a. b" (since "\" is easier to type than lambda). The words "abstraction" and "function" are pretty-much interchangable, although we might use "abstraction" to specifically refer to a "new" function definition, like this: \x. x As opposed to a "calculated" function, like the result of an application: a b Regarding precedence, application is "left-associative", meaning that a b c is the same as (a b) c Abstractions 'capture' everything after the ".", so \a. b c \d. \e. f is the same as \a. (b c \d. (\e. f)) You need to use parentheses to go the other way, eg. a (b c) (\x. x) y In the case of the Y combinator, there is only one "f" variable but it gets used twice. There are two "x" variables, one per abstraction, although those abstractions just-so-happen to look the same. In other words, we could replace one of the "x" abstractions with "\y. f (y y)" (known as an "alpha conversion") but we can't rename one of the "f"s without renaming all three occurences. Regarding your last point, the only semantic values in lambda calculus are functions, so "t" can't be anything else. However, we just saw that there are two syntactic forms which "t" can take. If "t" is an abstraction, we can simplify our expression immediately via the beta-reduction rule ('applying t to s'). If "t" is an application, like "t1 t2", then we can try simplifying that to get either an abstraction (which we can apply to "s") or another application, which we can try simplifying, and so on. It's possible (due to the Halting Problem) that we keep getting applications no matter how much we try to simplify, in which case we've hit an infinite loop while trying to calculate "t", and hence we can never reach the point where we can apply it to "s".
- supsep 12y agoI remember taking this in University, lambda scared the hell out of me.