5 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?
  - ygra 13y ago
    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 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).
  - 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.
      - 13y ago
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?
- ygra 13y ago
  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 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).
- 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.
    - 13y ago

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