Trampolining - An exercise in recursion and not blowing your stack!

This exercise was developed for the October 2013 Boston Software Craftsmanship Group Meeting

Discussion:

1. Tail call optimization
2. Tail calls vs tail recursion
1. http://stackoverflow.com/questions/12045299/what-is-difference-between-tail-calls-and-tail-recursion
3. Continuation Passing Style & Continuations
1. http://en.wikipedia.org/wiki/Continuation_passing_style
2. http://en.wikipedia.org/wiki/Continuation
4. Trampoline
1. Trampolining is a technique to implement tail-recursive optimization without consuming stack space (under the hood you're turning your recursive calls into a loop). It's commonly used in lisp compilers that compile down to C. If you implement your own trampoline you'll be able to make trampolined tail calls without blowing your stack.
2. A trampoline is an outer function which iteratively calls an inner function. The inner function returns a thunk (or a continuation) of another function to call or the result. To turn a tail recursive function into one that can be trampolined all you need to do is return a thunk wrapping your recursive call. It's called a trampoline because it bounces from function to function. Boing, boing, boing, boing, omg I got a result.

THE EXERCISE

• Pick a stack based language of your choice (I'd recommend something with functions as first class objects)
• Write the following two recursive functions:
• Factorial
• isEven / isOdd a mutually recursive function see: http://en.wikipedia.org/wiki/Mutual_recursion#Basic_examples for details
• Blow your stack!
• Re-write to be tail recursive (you may need an accumulator)
• Blow your stack!
• Write a trampoline, re-write your recursive functions to operate in that world
• No more blowing your stack!

LEARNINGS

You should come away from this exercise with a better understanding for a good number of functional programming terminology. Experience thinking about recursion and how to rewrite recursive functions as tail recursive. And maybe after we run the exercise you'll help me update this section!

HANDY LINKS

Blogs:

http://volgarev.me/blog/62412678347
http://raganwald.com/2013/03/28/trampolines-in-javascript.html
http://pramode.net/clojure/2010/05/08/clojure-trampoline/
http://jakemccrary.com/blog/2010/12/06/trampolining-through-mutual-recursion/
http://kix.in/2007/12/30/the-trampoline/
http://blog.functionalfun.net/2008/04/bouncing-on-your-tail.html
"The one kind of message says, "I want to bounce: please call me again with these parameters"; the other kind says, "I've had enough bouncing: here's the final answer"."
http://programmers.stackexchange.com/questions/157684/what-limitations-does-the-jvm-impose-on-tail-call-optimization

Wikipedia:

http://en.wikipedia.org/wiki/Tail_call
https://en.wikipedia.org/wiki/Thunk_(functional_programming)

Academic:

"No assembly required : compiling Standard ML to C" http://repository.cmu.edu/cgi/viewcontent.cgi?article=3011&context=compsci
"CONS Should Not CONS Its Arguments, Part II: Cheney on the M.T.A." http://home.pipeline.com/~hbaker1/CheneyMTA.html

NOTES

Depending on your language and chosen implementation, it may be helpful to be able to check if variable is a function. In clojure you can do that easily with fn? In javascript the following code should work:

function isFunction(functionToCheck) {

 var getType = {};

 return functionToCheck && getType.toString.call(functionToCheck) === '[object Function]';

}

If you need a little help see https://github.com/zdsbs/trampoline-exercise for some sample code.