4 ms·

What is a y-combinator? (2008)

deleted 13y ago
[deleted]
nadaviv 13y ago
Here's a CoffeeScript fixed-point combinator I wrote some time ago: y = ((y)->y y) (y) -> (f) -> (n) -> (f (y y) f) n Its a little different than the common implementation of y combinator, but looks cooler imo :) 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-1
- reycharles 13y ago
  You don't need turing completeness to implement the factorial function, hence it is not a proof of turing completeness.
lisper 13y ago
This is what the factorial function looks like in (almost) pure lambda calculus: ((λ (f) ((λ (g) (g g)) (λ (h) (λ (x) ((f (h h)) x))))) ; <-- The Y combinator (λ (f) (λ (n) (if ((λ (p a b) (p a b)) ((λ (n) (n (λ (x) (λ (x y) y)) (λ (x y) x))) n) t nil) ((λ (n) (λ (f x) (f (n f x)))) (λ (f x) x)) ((λ (m n) (m ((λ (m n) (λ (f x) (m f (n f x)))) n) (λ (f x) x))) n (f ((λ (n) (λ (f x) (n (λ (g h) (h (g f))) (λ (u) x) (λ (u) u)))) n))))))) You can actually run this code with an appropriate definition of λ: ? (((λ (f) ((λ (g) (g g)) (λ (h) (λ (x) ((f (h h)) x))))) (λ (f) (λ (n) (if ((λ (p a b) (p a b)) ((λ (n) (n (λ (x) (λ (x y) y)) (λ (x y) x))) n) t nil) ((λ (n) (λ (f x) (f (n f x)))) (λ (f x) x)) ((λ (m n) (m ((λ (m n) (λ (f x) (m f (n f x)))) n) (λ (f x) x))) n (f ((λ (n) (λ (f x) (n (λ (g h) (h (g f))) (λ (u) x) (λ (u) u)))) n))))))) ((λ (n) (λ (f x) (f (n f x)))) ; <-- This is the number 6 expressed as a Church numeral ((λ (n) (λ (f x) (f (n f x)))) ((λ (n) (λ (f x) (f (n f x)))) ((λ (n) (λ (f x) (f (n f x)))) ((λ (n) (λ (f x) (f (n f x)))) ((λ (n) (λ (f x) (f (n f x)))) (λ (f x) x)))))))) #<COMPILED-LEXICAL-CLOSURE #x30200214436F> ? (funcall * '1+ 0) 720 Writing the code for λ is left as an exercise :-)
- duiker101 13y ago
  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?
  - tinco 13y ago
    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?
    - lisper 13y ago
      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.
      - tinco 13y ago
        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)?
        lisper 13y ago
        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.)
mekishizufu 13y ago
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 http://www.youtube.com/watch?v=FITJMJjASUs Programming with Nothing by Tom Stuart http://www.youtube.com/watch?v=VUhlNx_-wYk http://www.youtube.com/watch?v=VUhlNx_-wYk
pdpi 13y ago
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_fixed-point_combinators http://en.wikipedia.org/wiki/Fixed-point_combinator#Other_fi...)
- raldi 13y ago
  Okay, now explain how it works.
oftenwrong 13y ago
I recommend the explanations found here: http://pl.barzilay.org/lec10.txt http://pl.barzilay.org/lec10.txt

deleted 13y ago

[deleted]

Here's a CoffeeScript fixed-point combinator I wrote some time ago: y = ((y)->y y) (y) -> (f) -> (n) -> (f (y y) f) n Its a little different than the common implementation of y combinator, but looks cooler imo :) 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-1

reycharles 13y ago
You don't need turing completeness to implement the factorial function, hence it is not a proof of turing completeness.

lisper 13y ago

This is what the factorial function looks like in (almost) pure lambda calculus: ((λ (f) ((λ (g) (g g)) (λ (h) (λ (x) ((f (h h)) x))))) ; <-- The Y combinator (λ (f) (λ (n) (if ((λ (p a b) (p a b)) ((λ (n) (n (λ (x) (λ (x y) y)) (λ (x y) x))) n) t nil) ((λ (n) (λ (f x) (f (n f x)))) (λ (f x) x)) ((λ (m n) (m ((λ (m n) (λ (f x) (m f (n f x)))) n) (λ (f x) x))) n (f ((λ (n) (λ (f x) (n (λ (g h) (h (g f))) (λ (u) x) (λ (u) u)))) n))))))) You can actually run this code with an appropriate definition of λ: ? (((λ (f) ((λ (g) (g g)) (λ (h) (λ (x) ((f (h h)) x))))) (λ (f) (λ (n) (if ((λ (p a b) (p a b)) ((λ (n) (n (λ (x) (λ (x y) y)) (λ (x y) x))) n) t nil) ((λ (n) (λ (f x) (f (n f x)))) (λ (f x) x)) ((λ (m n) (m ((λ (m n) (λ (f x) (m f (n f x)))) n) (λ (f x) x))) n (f ((λ (n) (λ (f x) (n (λ (g h) (h (g f))) (λ (u) x) (λ (u) u)))) n))))))) ((λ (n) (λ (f x) (f (n f x)))) ; <-- This is the number 6 expressed as a Church numeral ((λ (n) (λ (f x) (f (n f x)))) ((λ (n) (λ (f x) (f (n f x)))) ((λ (n) (λ (f x) (f (n f x)))) ((λ (n) (λ (f x) (f (n f x)))) ((λ (n) (λ (f x) (f (n f x)))) (λ (f x) x)))))))) #<COMPILED-LEXICAL-CLOSURE #x30200214436F> ? (funcall * '1+ 0) 720 Writing the code for λ is left as an exercise :-)

duiker101 13y ago
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?
- tinco 13y ago
  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?
  - lisper 13y ago
    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.
    - tinco 13y ago
      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)?
      - lisper 13y ago
        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.)

mekishizufu 13y ago

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 http://www.youtube.com/watch?v=FITJMJjASUs Programming with Nothing by Tom Stuart http://www.youtube.com/watch?v=VUhlNx_-wYk http://www.youtube.com/watch?v=VUhlNx_-wYk

pdpi 13y ago

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_fixed-point_combinators http://en.wikipedia.org/wiki/Fixed-point_combinator#Other_fi...)

raldi 13y ago
Okay, now explain how it works.

oftenwrong 13y ago

I recommend the explanations found here: http://pl.barzilay.org/lec10.txt http://pl.barzilay.org/lec10.txt