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

The Y Combinator is something important in the theory of functional programming. It takes one function as argument and applies it to itself ad infinitum. Together with lazy evaluation this is how you can implement recursion in a language which does not natively support it, namely (lazy) lambda calculus.

http://en.wikipedia.org/wiki/Fixed-point_combinator#Y_combin...

Actually, TCO and Y are not really related with each other apart from the fact that you usually learn about them in the same course about functional programming.



If you write your loops with the Y-combinator, you need tail-call elimination to keep them from overflowing the stack when they run for enough iterations, because the way your function f goes on to the next iteration of itself is by calling the (Y f) that was passed as its first argument.


You can write a lambda calculus interpreter which does beta-reduction. In this case, there is no stack which could overflow. Just a lambda expression, which is reduced to another expression.


Yes, as I mentioned in another comment in this thread, TCE falls out automatically from combinator-graph reduction.




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

Search: