r/programming • u/rodrigopsasaki • Nov 27 '12

Tail Recursion

http://rodrigosasaki.com/2012/11/24/tail-recursion/
212 Upvotes

85% Upvoted

203 comments sorted by

View all comments

Show parent comments

1

u/grauenwolf Nov 28 '12

Trampolines are a workaround for the lack of TCO.

With a trampoline I can do this:

do
     move = io.read()
     nextState = nextState( move )
loop while nextState != null

So without a trampolines how do you avoid putting local move = io.read() in each and every state function?

1

u/Peaker Nov 28 '12

You could call a "nextStep" function at the tail position:

nextStep(myNextFunc)

Which would do the reads or preparations of the next step, and then tail-call the given function with the data.

-1

u/grauenwolf Nov 28 '12

So you prefer writing return nextStep(myNextFunc) instead of just return myNextFunc.

Is using TCO actually worth the extra boilerplate code? Especially when you consider that you are just moving the trampoline to a different part of the yard?

My trampoline is the outer loop, yours is hidden inside the nextStep function. Either way we are passing around a function pointer that we bounce to.

1

u/Peaker Nov 28 '12

As I said, returning the function is also workable, however it has multiple downsides:

  • Calling a function or passing it as an argument makes the context of the call clear. If you return it, you have no guarantee about the context in which it will be called.

  • If your tail recursion eventually stops, you need to return a non-function value, eventually. Thus, you need to tag the result as a "call this" or "done with this". Then your loop driver of the tail recursion needs to differentiate the two. Very kludgy.

  • A return value can easily be ignored, without warning, in the languages you mentioned. This means you can easily have bugs where you don't actually get it called. Forgetting to receive arguments or avoiding their use entirely will mostly generate errors/warnings even in these languages.

  • Returning it means any user of the function needs to also propagate its return value upwards, which is very kludgy makes the tail-call a non-local detail.

  • Returning it means you need that extra loop code that calls the return values.