C[omp]ute

From: "andrew cooke" <andrew@...>

Date: Wed, 11 Feb 2009 09:17:38 -0300 (CLST)

The Python stack is notoriously restricted, and Python does not have tail
optimisation, so any code that uses recursion can quickly fail.

Enhanced generators (available since Python 2.5) provide a solution, but
one that has some limitations.

In short - generators can be used to implement trampolining.  The program
stack then becomes an array on the heap and is "unlimited" in size.

The simplest way to implement this is to rewrite a program by:

  1 - replace "return x" with "yield (True, x)"

  2 - replace "f(x)" with "yield (False, f, x)"

The program can then be run with code something like (untested):

  def run(f, args):
    stack = [f]
    while stack:
      result = stack[-1].send(args)
      if result[0]:
        stack.pop()
        args = result[1:]
      else:
        stack.push(result[1])
        args = result[2:]
    return args

That's not quite correct as it assumes that everything (ie all the "f"s
above) is already a generator.  And it doesn't handle exceptions.

There's more here - http://www.python.org/dev/peps/pep-0342/

And I'm still unclear on what happens when a function yields (in the
original form).  But I think this is the right track...

The main restriction is that *every* function needs to be aware of the new
protocol (unless they simply return values returned from sub-calls, I
think, since these will now be generators rather than "real" values).

I assume this is all "obvious" if you understand what coroutines are, but
the details seem pretty complex to me.

Andrew