4 ms·
Elaborate for the ignorant.
by zxcdw 14y ago
Elaborate for the ignorant.
- kd0amg 14y agoThe Y combinator is a way to express recursion in lambda calculus. Tail call optimization (turning certain function calls into GOTOs) is the traditional way to keep from overflowing the control stack in languages based on lambda calculus.
- qznc 14y agoThe 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_combinator 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.
- kragen 14y agoIf 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.
- qznc 14y agoYou 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.
- kragen 14y agoYes, as I mentioned in another comment in this thread, TCE falls out automatically from combinator-graph reduction.