3 ms·

Has anyone on HN ever actually used one of these in code they've written? I've never understood why y-combinator is useful or impressive. Interesting, maybe, b

Has anyone on HN ever actually used one of these in code they've written? I've never understood why y-combinator is useful or impressive. Interesting, maybe, but not really useful.

ianl 15y ago
It's useful for lambda functions that recursively call themselves, you don't need these in practice because you wouldn't use a lambda. You would use a named function, therefore, they are almost purely theoretical aspect of Lambda Calculus. I can't think of any programming language that is purely lambda calculus.
- fexl 15y ago
  Fexl http://fexl.com http://fexl.com is essentially nothing more than a thin layer of lambda calculus on top of C, implemented using combinators.
kotrin 15y ago
http://www.dreamsongs.com/Files/WhyOfY.pdf http://www.dreamsongs.com/Files/WhyOfY.pdf
fexl 15y ago
I use them in the Fexl language http://fexl.com http://fexl.com . Although the Fexl language itself has syntax for recursive definitions, it translates everything to combinators internally, so there are no "symbol tables" or "environments" at run time. Therefore it uses the Y combinator to implement those recursive definitions. A while ago I wrote this detailed example: http://news.ycombinator.com/item?id=2719635 http://news.ycombinator.com/item?id=2719635 tl;dr here is a non-recursive definition of the append function for two lists: (Y \append \x\y x y \h\t cons h; append t y) If you need more parentheses for clarity, here you go: (Y (\append \x\y x y \h\t cons h (append t y)))
GregBuchholz 15y ago
"Y in Practical Programs" by Bruce McAdam: http://www.dsi.uniroma1.it/~labella/absMcAdam.ps http://www.dsi.uniroma1.it/~labella/absMcAdam.ps (or search with Google for an HTML translation).
Homunculiheaded 15y ago
I would say that the y-combinator is interesting to the such a degree that it becomes useful. Sure you won't and shouldn't use the y-combinator in any real world applications. But first off it demonstrates the true power of the lambda calculus to represent computation, and more importantly to the practical programmer is that understanding it will provide a deep insight into the nature of computation, which is profoundly useful if you ask me.
- fexl 15y ago
  It's a stretch to say that you shouldn't use them in a real application. Combinators in general can be useful for implementing functional programming languages, and those languages can be useful for applications. That may sound like bickering over a fine point, but I'm just saying that combinators can be more than a theoretical tool. It seems reasonably fast for my purposes so far, and the expansion rule is just a one-liner: https://github.com/chkoreff/Fexl/blob/master/src/Y.c https://github.com/chkoreff/Fexl/blob/master/src/Y.c
yters 15y ago
It's all about removing dependencies, and y-combinators have the fewest dependencies for accomplishing the greatest number of functions.

Has anyone on HN ever actually used one of these in code they've written? I've never understood why y-combinator is useful or impressive. Interesting, maybe, but not really useful.

ianl 15y ago

It's useful for lambda functions that recursively call themselves, you don't need these in practice because you wouldn't use a lambda. You would use a named function, therefore, they are almost purely theoretical aspect of Lambda Calculus. I can't think of any programming language that is purely lambda calculus.

fexl 15y ago
Fexl http://fexl.com http://fexl.com is essentially nothing more than a thin layer of lambda calculus on top of C, implemented using combinators.

kotrin 15y ago

http://www.dreamsongs.com/Files/WhyOfY.pdf http://www.dreamsongs.com/Files/WhyOfY.pdf

fexl 15y ago

I use them in the Fexl language http://fexl.com http://fexl.com . Although the Fexl language itself has syntax for recursive definitions, it translates everything to combinators internally, so there are no "symbol tables" or "environments" at run time. Therefore it uses the Y combinator to implement those recursive definitions. A while ago I wrote this detailed example: http://news.ycombinator.com/item?id=2719635 http://news.ycombinator.com/item?id=2719635 tl;dr here is a non-recursive definition of the append function for two lists: (Y \append \x\y x y \h\t cons h; append t y) If you need more parentheses for clarity, here you go: (Y (\append \x\y x y \h\t cons h (append t y)))

GregBuchholz 15y ago

"Y in Practical Programs" by Bruce McAdam: http://www.dsi.uniroma1.it/~labella/absMcAdam.ps http://www.dsi.uniroma1.it/~labella/absMcAdam.ps (or search with Google for an HTML translation).

Homunculiheaded 15y ago

I would say that the y-combinator is interesting to the such a degree that it becomes useful. Sure you won't and shouldn't use the y-combinator in any real world applications. But first off it demonstrates the true power of the lambda calculus to represent computation, and more importantly to the practical programmer is that understanding it will provide a deep insight into the nature of computation, which is profoundly useful if you ask me.

fexl 15y ago
It's a stretch to say that you shouldn't use them in a real application. Combinators in general can be useful for implementing functional programming languages, and those languages can be useful for applications. That may sound like bickering over a fine point, but I'm just saying that combinators can be more than a theoretical tool. It seems reasonably fast for my purposes so far, and the expansion rule is just a one-liner: https://github.com/chkoreff/Fexl/blob/master/src/Y.c https://github.com/chkoreff/Fexl/blob/master/src/Y.c

yters 15y ago

It's all about removing dependencies, and y-combinators have the fewest dependencies for accomplishing the greatest number of functions.