[Tutor] recursion and trampolines

[Guillermo Fernandez Castellanos]

Hi,

I readed the recursion and trampolines, and I had a (very quick...) look
  at the article. Though, there is a few points I don't really get...
What does this line exactly do?
->         bouncer = bouncer[1](*bouncer[2])

I surrounded it by "print bouncer" before and after, and the result was
the same for both cases!

Then, I put a few prints to see the flow ('print "trampolin"' after the
trampolin function, ...), runned it and the result was for a fact(5):

$ python trampolineExample.py
entry function fact
entry function trampoline
executing first bounce function
entry function bounce
bouncer before: ['bounce', <function trampolined_fact at 0x007CBAF0>, (5,)]
entry function bounce
bouncer after: ['bounce', <function trampolined_fact at 0x007CBAF0>, (4, 5)]
bouncer before: ['bounce', <function trampolined_fact at 0x007CBAF0>,
(4, 5)]
entry function bounce
bouncer after: ['bounce', <function trampolined_fact at 0x007CBAF0>, (3,
20)]
bouncer before: ['bounce', <function trampolined_fact at 0x007CBAF0>,
(3, 20)]
entry function bounce
bouncer after: ['bounce', <function trampolined_fact at 0x007CBAF0>, (2,
60)]
bouncer before: ['bounce', <function trampolined_fact at 0x007CBAF0>,
(2, 60)]
entry function bounce
bouncer after: ['bounce', <function trampolined_fact at 0x007CBAF0>, (1,
120)]
bouncer before: ['bounce', <function trampolined_fact at 0x007CBAF0>,
(1, 120)]
entry function bounce
bouncer after: ['bounce', <function trampolined_fact at 0x007CBAF0>, (0,
120)]
bouncer before: ['bounce', <function trampolined_fact at 0x007CBAF0>,
(0, 120)]
entry function land
bouncer after: ['land', 120]

Well... I have to admit that this, to me, is not much different from a:
i=5
result=1
while i>0:
     result*=i
     i-=1

specially when we see the arguments passed to the function 'bounce' (see
my execution before):
(5,)
(4, 5)
(3, 20)
(2, 60)
(1, 120)
(0, 120)

Where is the advantage of such trampolin schema that you described? I am
sure there is one.I simply don't see it :-(

Thanks,

G

> That being said, there is a technique to work around the lack of tail
> recursion, called "trampolined style".
> 
>     http://www.cs.indiana.edu/hyplan/sganz/publications/icfp99/paper.pdf
> 
> It allows us to write recursive programs that avoids growing the call
> stack, even in languages that don't natively support tail call
> elimination.
> 
> 
> Here's a concrete example of a trampolined version of that factorial
> function, using the trampolining technique:
> 
> ###
> def trampolined_fact(n, k=1):
>     if n == 0:
>         return land(k)
>     return bounce(trampolined_fact, n-1, k*n)
> 
> 
> def fact(n):
>     """Returns the factorial of n."""
>     return trampoline(trampolined_fact, n)
> 
> 
> def trampoline(function, *args):
>     """Bounces a function over and over, until we "land" off the
>     trampoline."""
>     bouncer = bounce(function, *args)
>     while True:
>         bouncer = bouncer[1](*bouncer[2])
>         if bouncer[0] == 'land':
>             return bouncer[1]
> 
> 
> def bounce(function, *args):
>     """Bounce back onto the trampoline, with an upcoming function call."""
>     return ["bounce", function, args]
> 
> 
> def land(value):
>     """Jump off the trampoline, and land with a value."""
>     return ["land", value]
> ###