Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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.



I use them in the Fexl language 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

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)))


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.


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


"Y in Practical Programs" by Bruce McAdam:

http://www.dsi.uniroma1.it/~labella/absMcAdam.ps (or search with Google for an HTML translation).


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 http://fexl.com is essentially nothing more than a thin layer of lambda calculus on top of C, implemented using combinators.



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




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: