Metadata-Version: 2.1
Name: trampoline
Version: 0.1.2
Summary: Simple and tiny yield-based trampoline implementation.
Home-page: https://gitlab.com/ferreum/trampoline
Author: UNKNOWN
Author-email: code.danielk@gmail.com
License: MIT
Keywords: trampoline recursion tail call
Platform: UNKNOWN
Classifier: Development Status :: 3 - Alpha
Classifier: Intended Audience :: Developers
Classifier: License :: OSI Approved :: MIT License
Classifier: Natural Language :: English
Classifier: Operating System :: OS Independent
Classifier: Programming Language :: Python :: 3.5
Classifier: Programming Language :: Python :: 3.6
Classifier: Programming Language :: Python :: 3.7

================================
trampoline - unlimited recursion
================================
Simple and tiny yield-based trampoline implementation for python.
-----------------------------------------------------------------

This trampoline allows recursive functions to recurse virtually (or literally)
infinitely. Most existing recursive functions can be converted with simple
modifications.

The implementation is tiny: the gist of the module consists of a single
function with around 30 lines of simple python code.

Conversion from simple recursion
''''''''''''''''''''''''''''''''

Trampolined functions are generators: Instead of recursing into other functions
directly, they yield the generator of the call they want to recurse into. The
generator of the first call is invoked using the ``trampoline()`` function.

This is easiest to understand with an example.
Consider this simple recursive function:

>>> def print_numbers(n):
...     "Print numbers 0..n (recursive)."
...     if n >= 0:
...         print_numbers(n - 1)
...         print(n)
>>>
>>> print_numbers(2000) # doctest: +IGNORE_EXCEPTION_DETAIL
Traceback (most recent call last):
RecursionError: maximum recursion depth exceeded in comparison

This exhausts the stack when calling it with too large ``n``.
Compare this with our trampoline version:

>>> from trampoline import trampoline
>>>
>>> def print_numbers(n):
...     "Print numbers 0..n (trampolined)."
...     if n >= 0:
...         yield print_numbers(n - 1)
...         print(n)
>>>
>>> trampoline(print_numbers(2000)) # doctest: +ELLIPSIS
0
1
2
...
1999
2000

We added a ``yield`` statement to the recursive call, and wrapped the function
call with ``trampoline()``.

``trampoline`` takes the generator created by the ``print_numbers(2000)`` call and runs it.
The generator then yields another generator of ``print_numbers``, which then
takes over, effectively recursing into it.

When a generator returns, the yielding generator takes over again.

Of course, the trampolined function doesn't have to call itself. Any other
trampolined function generator will do.

Return values
'''''''''''''

Consider this recursive factorial:

>>> def factorial(n):
...     "Get factorial of n (recursive)."
...     if n <= 1:
...         return 1
...     return factorial(n - 1) * n
>>>
>>> print(factorial(2000)) # doctest: +IGNORE_EXCEPTION_DETAIL
Traceback (most recent call last):
RecursionError: maximum recursion depth exceeded in comparison

Again, this exhausts the stack at our ``factorial(2000)`` call.

We now want to convert it for our trampoline. But how do we get the result of
the factorial call? This uses a rarely seen feature of yield: its return value
as an expression. With this, ``trampoline`` can send the result of the callee
back to the caller. Here is the trampolined solution:

>>> def factorial(n):
...     "Get factorial of n (trampolined)."
...     if n <= 1:
...         return 1
...     return (yield factorial(n - 1)) * n
>>>
>>> print(trampoline(factorial(2000))) # doctest: +ELLIPSIS
3316275092450633241175393380576324038281117208105780394571935437...

The function is suspended at the ``yield`` expression, ``trampoline`` continues
execution with the yielded generator, and afterwards provides us with the
returned value. In the end, ``trampoline`` returns the value that was returned
by our first generator.

Python requires that we add braces around a ``yield`` expression after a
``return``, making it look a little more ugly. We can circumvent this by adding
a variable:

>>> def factorial(n):
...     "Get factorial of n (trampolined)."
...     if n <= 1:
...         return 1
...     value = yield factorial(n - 1)
...     return value * n
>>>
>>> print(trampoline(factorial(10)))
3628800

In this case, no extra braces are required.

Exceptions
''''''''''

Exceptions are handled just as one might expect:

>>> def factorial(n):
...     "Get factorial of n (trampolined). Unless we don't like the number."
...     if n <= 1:
...         return 1
...     if n == 500:
...         raise Exception("I don't like this number")
...     return (yield factorial(n - 1)) * n
>>>
>>> print(trampoline(factorial(1000)))
Traceback (most recent call last):
  File "/usr/lib/python3.7/doctest.py", line 1329, in __run
    compileflags, 1), test.globs)
  File "<doctest README.rst[10]>", line 1, in <module>
    print(trampoline(factorial(1000)))
  File "trampoline.py", line 39, in trampoline
    raise exception
  File "trampoline.py", line 21, in trampoline
    res = stack[-1].throw(ex)
...
  File "<doctest README.rst[9]>", line 7, in factorial
    return (yield factorial(n - 1)) * n
  File "trampoline.py", line 21, in trampoline
    res = stack[-1].throw(ex)
  File "<doctest README.rst[9]>", line 7, in factorial
    return (yield factorial(n - 1)) * n
  File "trampoline.py", line 21, in trampoline
    res = stack[-1].throw(ex)
  File "<doctest README.rst[9]>", line 7, in factorial
    return (yield factorial(n - 1)) * n
  File "trampoline.py", line 25, in trampoline
    res = next(stack[-1])
  File "<doctest README.rst[9]>", line 6, in factorial
    raise Exception("I don't like this number")
Exception: I don't like this number

As seen in this example, event tracebacks are preserved, hiding no information
in error cases. There is just one additional stack frame of the ``trampoline``
function for each generator-yield.

This also means that yields work just fine inside ``with`` blocks.

Tail Calls
''''''''''

A trampolined function can raise ``TailCall`` (which is an exception) passing
it the generator of the next function call:

>>> from trampoline import TailCall
>>>
>>> def factorial(n, x=1):
...     "Get factorial of n (trampolined)."
...     if n <= 1:
...         return x
...     raise TailCall(factorial(n - 1, x * n))
...     yield # just to make this a generator
>>>
>>> # This could take some seconds (the numbers are extremely large)
>>> print(trampoline(factorial(100000))) # doctest: +ELLIPSIS
282422940796034787429342157802453551847749492609122485057891808654...

This implementation uses constant memory, and theoretically works with any
``n`` (until the result gets too large).

Beware that we still need to have a generator function, so there has to be a
``yield`` in the function, reachable or not. The

::

    raise TailCall(...)
    yield

idiom is recommended if the function doesn't yield any other calls.

Suggestions
'''''''''''

Expose a wrapper
````````````````

If you want to hide the trampolined-ness of a function and simplify its usage,
expose a wrapper function that calls the trampolined function with
``trampoline``:

>>> def exposed_factorial(n):
...     "Get factorial of n."
...     return trampoline(factorial(n))
>>>
>>> print(exposed_factorial(42))
1405006117752879898543142606244511569936384000000000

Just make sure to always use the trampolined version from other trampolined
functions. Otherwise it will recurse as usual, taking no advantage of the
trampoline.

Use it in classes
`````````````````

``trampoline`` works just fine with methods.

>>> class Node(object):
...
...     def __init__(self, name, children=()):
...         self.name = name
...         self.children = children
...
...     def do_print(self, prefix=""):
...         print(prefix + self.name)
...         for child in self.children:
...             yield child.do_print(prefix="  " + prefix)
>>>
>>> root = Node("root", [Node("first", [Node("one")]), Node("second", [Node("two"), Node("last")])])
>>> trampoline(root.do_print())
root
  first
    one
  second
    two
    last

Subclasses can extend or override these trampolined methods to provide their
own implementation. Just make sure to always ``yield`` super calls when
extending a trampolined method.

Caveats
'''''''

Lastly, there are some downsides to consider.

Yield
`````

As we use ``yield`` for recursion, we cannot use it to yield actual values.

Simple cases could be rewritten with a callback function or by appending or
returning a list.

Memory consumption
``````````````````

Recursing hundreds of thousands of times allocates a lot of objects for local
variables and for the generators themselves, which all need to exist at the
same time. When overdoing it, this can easily lead to multiple gigabytes on the
stack.

Of course, if we mess up our exit condition and recurse infinitely, we will
exhaust our memory.

Use tail calls if they are an option. Otherwise an iterative approach may be
preferable.

Performance
```````````

As said above, when recursing extremely deeply, the stack may get rather large.
These objects not only have to be allocated, but need to be freed as well when
done, which slows down the return path.

Function call and exception handling overhead may come into play for functions
that don't recurse deeply or use a lot of tail calls. This should only matter
for functions that don't do a lot of work. A simple tail-calling count-down
from one million takes about one second on a mediocre laptop.

Tracebacks
``````````

When an exception occurs at ridiculous recursion depth, displaying the
traceback may take a while, depending on the exception handler and formatter.
Reducing ``sys.tracebacklimit`` may help. Of course, the traceback will then be
cut off. Python's default traceback limit applies here too, printing the last
1000 frames.

Tail calls don't have this problem, as they don't appear in tracebacks.

.. vim:set sw=4 et: