What is a y-combinator? (2008)(stackoverflow.com)
stackoverflow.com
What is a y-combinator? (2008)
http://stackoverflow.com/questions/93526/what-is-a-y-combinator
6 comments
I have no idea what I am reading, where do you learn this sort of things? computer science? math? or else... how long would it take for someone to understand this topics?
Our professor in first semester (computer science) briefly touched lambda calculus in a lecture, but of course back then all you see is a bunch of strange things with no idea what it actually is. What's needed to understand is probably a little background in functional programming and a little interest in the topic to dig deeper.
I once came across a nice example that gradually transformed a normal Ruby program into such a monstrosity, while explaining everything along the way: http://codon.com/programming-with-nothing
Side note: I roughly understand some principles of all that but in no way good enough to actually write code that way. Specifically I still cannot come up with a Y combinator definition (and right now work time limits my opportunity of reading the article completely).
I once came across a nice example that gradually transformed a normal Ruby program into such a monstrosity, while explaining everything along the way: http://codon.com/programming-with-nothing
Side note: I roughly understand some principles of all that but in no way good enough to actually write code that way. Specifically I still cannot come up with a Y combinator definition (and right now work time limits my opportunity of reading the article completely).
LC is a really really really simple language. One of the simplest languages that is Turing Complete.
It has 3 syntactic forms that build its AST: lambda functions (that bring variables into scope), applications (of functions to arguments), and variable access.
It has 1 reduction rule (Whenever there's an application of a lambda, the whole thing is replaced by the lambda's body with references to the lambda's variable substituted by the application's argument.
3 syntactic forms + 1 reduction rule: That's it!
How can you do anything with it? Using "Church encodings" of various things.
Enumerating all of them is going to take a lot of text! So I'll just give you a taste. First, we can encode "multiple argument functions" on top of our single-argument lambdas by simply nesting lambdas:
Our function of two arguments can return the second argument too:
It has 3 syntactic forms that build its AST: lambda functions (that bring variables into scope), applications (of functions to arguments), and variable access.
It has 1 reduction rule (Whenever there's an application of a lambda, the whole thing is replaced by the lambda's body with references to the lambda's variable substituted by the application's argument.
3 syntactic forms + 1 reduction rule: That's it!
How can you do anything with it? Using "Church encodings" of various things.
Enumerating all of them is going to take a lot of text! So I'll just give you a taste. First, we can encode "multiple argument functions" on top of our single-argument lambdas by simply nesting lambdas:
λx. λy. x
Our function of two arguments can return the second argument too:
λx. λy. y
True = λt. λf. t
False = λt. λf. f
and = λb1. λb2. λt. λf. b1 (b2 t f) f
or = λb1. λb2. λt. λf. b1 t (b2 t f)
The lambda calculus is sort of at the intersection of math and computer science, and it's actually very simple. The mess above is a bit of a parlor trick. It is a composition of lots of very simple parts to make a complex whole. What is interesting about it (IMO) is that the whole actually turns out to be a lot less complex than you might at first suspect, and once you've put it together, it actually works the way theory says it does.
If you want to learn about it just Google for 'lambda calculus'. You'll find a zillion tutorials on the web.
If you want to learn about it just Google for 'lambda calculus'. You'll find a zillion tutorials on the web.
It's just lisp(-y, an s-expression language). You can learn the language in under 10 minutes. After that, understanding the y-combinator is just sitting down and deconstructing that code for an hour or two.
Basically it looks so complicated because it lacks as much structure as a language can possibly lack while still being turing complete. This makes it easy to map to lambda-calculus, something mathematicians use for reasoning about programming.
edit: am I wrong?
Basically it looks so complicated because it lacks as much structure as a language can possibly lack while still being turing complete. This makes it easy to map to lambda-calculus, something mathematicians use for reasoning about programming.
edit: am I wrong?
You're wrong about LC being (necessarily) Lisp-y. Church's original notation for the lambda calculus was not based on S-expressions. (Those were invented 30+ years later by John McCarthy.) I only used s-expression notation for the factorial example to drive home the point that you can actually run this code.
Ah, I did not mean to imply that LC is Lisp-y. I just meant that the notation you used is valid lisp (as far as I can tell) and can therefore be read, learned about, executed and deconstructed rather easily.
I was downvoted a few times, but I actually think the line "it's just lisp" is a better response to the commenters question than any of the other comments that attempt to explain what LC is. Why explain an algorithmic construct to someone in mathematical notation, if there's an executable notation that's easier on the eyes (at least for a programmer)?
I was downvoted a few times, but I actually think the line "it's just lisp" is a better response to the commenters question than any of the other comments that attempt to explain what LC is. Why explain an algorithmic construct to someone in mathematical notation, if there's an executable notation that's easier on the eyes (at least for a programmer)?
I certainly used Lisp notation, but if you think it's "just Lisp" then you're kind of missing the point. It's not just "just Lisp", it's "just lambda". There is nothing else in there, no primitives, no numbers, no CAR, CDR, CONS, COND or QUOTE. And, to drive home the point that the Y combinator is in there, no DEFUN, LABELS or LETREC. (Well, OK, there's an IF in there, but even that could be gotten rid of with a lazy lambda.)
I recommend you Good Math by Mark C. Chu-Carroll; it's a fantastic book for programmers who don't know higher math and it explains well how Lambda Calculus works. You can also find useful explanations about logic programming, turing completeness, etc.
You can take it as an introductory book in Computer Science and read the books mentioned by the author to deepen your knowledge.
(λ (x) E) is `(function (x) E)` or `function (x) { E; }` or `\x -> E` or `lambda x: E` or `proc { |x| E }`.
Everything else comes out of the incredibly clever realization that functions are capable of encoding everything you need in order to program.
Everything else comes out of the incredibly clever realization that functions are capable of encoding everything you need in order to program.
Yeah so I'm going to stick to frontend development..
This is a reddit type comment, but I upvoted anyway.I look at what was posted and I thought to myself that I'm just glad other people know what it is, and I really have no interest in learning it.
I mean I would love to learn this kind of stuff, just have no idea where to begin. I'm a total novice at math.
If you are curious about the topic, I strongly recommend watching these videos:
Y Not- Adventures in Functional Programming by Jim Weirich http://www.youtube.com/watch?v=FITJMJjASUs
Programming with Nothing by Tom Stuart http://www.youtube.com/watch?v=VUhlNx_-wYk
Y Not- Adventures in Functional Programming by Jim Weirich http://www.youtube.com/watch?v=FITJMJjASUs
Programming with Nothing by Tom Stuart http://www.youtube.com/watch?v=VUhlNx_-wYk
Here's a CoffeeScript fixed-point combinator I wrote some time ago:
edit: also, a question - a comment on stackoverflow says that fixed-point combinators are used to prove the turing-completeness of lambda calculus. Can't it be proved with something simpler, such as that?
y = ((y)->y y) (y) -> (f) -> (n) -> (f (y y) f) n
edit: also, a question - a comment on stackoverflow says that fixed-point combinators are used to prove the turing-completeness of lambda calculus. Can't it be proved with something simpler, such as that?
y = (f) -> (n) -> (f f) n
fact = y (f) -> (n) -> if n is 0 then 1 else n * (f f) n-1You don't need turing completeness to implement the factorial function, hence it is not a proof of turing completeness.
[deleted]
I recommend the explanations found here: http://pl.barzilay.org/lec10.txt
can't talk about fixed point combinators without mentioning my old favourite:
Yk = (L L L L L L L L L L L L L L L L L L L L L L L L L L)
where:
L = λabcdefghijklmnopqstuvwxyzr. (r (t h i s i s a f i x e d p o i n t c o m b i n a t o r))
(see http://en.wikipedia.org/wiki/Fixed-point_combinator#Other_fi...)
Yk = (L L L L L L L L L L L L L L L L L L L L L L L L L L)
where:
L = λabcdefghijklmnopqstuvwxyzr. (r (t h i s i s a f i x e d p o i n t c o m b i n a t o r))
(see http://en.wikipedia.org/wiki/Fixed-point_combinator#Other_fi...)
Okay, now explain how it works.
You can actually run this code with an appropriate definition of λ:
Writing the code for λ is left as an exercise :-)