CODEWITHSUNDEEP
recursionluaclojurey-combinatorfixpoint-combinators
Alex Gian
Alex Gian

Reputation: 514

Y-combinator does not seem to have any effect

I tried using the y-combinator (in both Lua and Clojure) as I thought that would allow me to exceed the size of default stack implementations when using recursion. It seems I was mistaken. Yes, it works, but in both of these systems, the stack blows at exactly the same point as it does using plain old recursion. A lowish ~3600 in Clojure and a highish ~333000 on my Android Lua implementation. It is also a bit slower than regular recursion.

So is there anything to be gained by using the y-combinator, or is it just an intellectual exercise to prove a point? Have I missed something?

===

PS. Sorry, I should have made it clearer that I am aware I can use TCO to exceed the stack. My question does not relate to that. I am interested in this a) from the academic/intellectual point of view b) whether there is anything that can be done about those function that cannot be written tail recursively.

Upvotes: 0

Views: 328

Answers (3)

Alan Thompson
Alan Thompson

Reputation: 29974

If you haven't seen it yet, there is a good explanation here: What is a Y-combinator?

In summary, it helps to prove that the lambda calculus is Turing complete, but is useless for normal programming tasks.

As you are probably aware, in Clojure you would just use loop/recur to implement a loop that does not consume the stack.

Upvotes: 0

Taylor Wood
Taylor Wood

Reputation: 16194

The Y combinator allows a non-recursive function to be used recursively, but that recursion still consumes stack space through nested function invocations.

For functions that can't be made tail-recursive, you could try refactoring them using continuation passing style, which would consume heap space instead of stack.

Here's a good overview of the topic: https://www.cs.cmu.edu/~15150/previous-semesters/2012-spring/resources/lectures/11.pdf

Upvotes: 3

brianolive
brianolive

Reputation: 1671

A “tail call” will allow you to exceed any stack size limitations. See Programming in Lua, section 6.3: Proper Tail Calls:

...after the tail call, the program does not need to keep any information about the calling function in the stack. Some language implementations, such as the Lua interpreter, take advantage of this fact and actually do not use any extra stack space when doing a tail call. We say that those implementations support proper tail calls.

Upvotes: 0

Related Questions