[Tutor] recursion and trampolines

[Danny Yoo]

[Note: my post below is slightly advanced, and highly impractical.
*grin*]


On Fri, 27 Aug 2004, Guillermo Fernandez Castellanos wrote:


> 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])



Hi Guillermo,


It's an ugly hack.  *grin*


I used a list to simulate a "union" data structure with either two or
three fields.  This "bouncing" data structure is either:

    ['bounce', someFunction, argumentsToThatFunction]

or

    ['land', someValue]

So I'm using the first field as a kind of 'type tag', and the remainder of
the list depends on which kind of bouncer the code is generating.  Python
doesn't natively have this kind of "discriminated union" type, so the code
here simulates it with lists.



If we write two helper functions to make it more readable:

###
def getBounceFunction(bouncer):
    return bouncer[1]

def getBounceArgs(bouncer):
    return bouncer[2]
###


then the snippet:

    bouncer = bouncer[1](*bouncer[2])

can be rewritten to:

    bouncer = apply(getBounceFunction(bouncer),
                    getBounceArgs(bouncer))




[rest of the bounce code cut]

> 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)


Yes, exactly right.  That 'while' loop ends up being equivalent to the
bouncing factorial function.  A Lisp or Scheme programmer would say that
loops and recursion do the exact same thing.  That's why there aren't any
native looping statements in the Scheme language: Scheme programmers do
everything with recursion.  It's a weird thought at first, but the code
above proves that it can work.



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

No, your first instincts were right.  Part of it is purely academic and
just for my personal amusement: I think it's funny to think about a
bouncing function.  *grin*

I have to clarify: most programmers don't ever have to do anything like
this: I'm definitely not saying for people to program this way.  This is
certainly not practical!  But as an academic exercise, I thought it was
fun to write.



There is a neat thing about trampolines: it's possible to simulate threads
with them.  As a concrete example:

###
"""Bouncers can be of two types: a 'bounce' or a 'land'."""

def bounce(function, *args):
    return ["bounce", function, args]


def land(value):
    return ["land", value]


def big_trampoline(bouncers):
    """A big trampoline keeps its bouncers up in the air until one of
    them lands."""
    bouncer_queue = bouncers[:]
    while True:
        bouncer = bouncer_queue.pop()
        bouncer = bouncer[1](*bouncer[2])
        if bouncer[0] == 'land':
            print "bouncer finished:", bouncer
            print "exiting the trampoline!"
            break
        else:
            bouncer_queue.insert(0, bouncer)


def tramped_sayHello():
    print "hello world"
    return bounce(tramped_sayHello)


def tramped_sayHola():
    print "hola world"
    return bounce(tramped_sayHola)


def tramped_countUpToFive(n):
    if n == 5:
        return land(None)
    print n
    return bounce(tramped_countUpToFive, n+1)


if __name__ == '__main__':
    baby_bouncers = [bounce(tramped_sayHello),
                     bounce(tramped_sayHola),
                     bounce(tramped_countUpToFive, 0)]
    big_trampoline(baby_bouncers)
###



When we run this program, we can see a surprising result:

###
0
hola world
hello world
1
hola world
hello world
2
hola world
hello world
3
hola world
hello world
4
hola world
hello world
bouncer finished: ['land', None]
exiting the trampoline!
###


In effect, we're threading between the three functions!  Trampolines show
that, in theory, threaded programming can be done without OS support.
Again, no one in their right mind would ever write threads this way, by
hand.  *grin*


Hope this was interesting!