Overview

Introduction

Trampolinen is a Python package that provides a decorator for writing programs that use deeply recursive function calls or tail calls. In addition, Trampolinen provides an implementation of lazy values (values that are computed only when demanded, by calling a function and caching the result), using the decorator to support deeply nested lazy values.

Examples

Inorder binary tree traversal

from collections import namedtuple
from trampolinen import Trampolining, Ycall, Ytailcall

class Tree(namedtuple("Tree", ( "left", "value", "right" ))):
    @Trampolining
    def inorder_reduce(self, fn, acc):
        if self.left is not None:
            acc = yield Ycall(self.left.inorder_reduce, fn, acc)
        acc = yield Ycall(fn, acc, self.value)
        if self.right is not None:
            acc = yield Ytailcall(self.right.inorder_reduce, fn, acc)
        yield acc

t = Tree(Tree(None, 2, Tree(None, 4, None)), 1, Tree(None, 3, None))
def collect(acc, value):
    acc.append(value)
    return acc
print t.inorder_reduce(collect, []) # prints [2, 4, 1, 3]

Lazy (incremental) quicksort

from trampolinen.lazy import Lazy, LazyVal, Ytailcall

def lazy_quicksort(a):
    def partition(low, high):
        pivot = a[low]
        i = low
        for j in range(low + 1, high):
            if a[j] < pivot:
                i += 1
                a[j], a[i] = a[i], a[j]
        a[low], a[i] = a[i], a[low]
        return i
    def lazy_quicksort_helper(low, high, rest):
        if low < high:
            pos = partition(low, high)
            right = Lazy(lazy_quicksort_helper, pos + 1, high, rest)
            mid = LazyVal(( a[pos], right ))
            return Ytailcall(lazy_quicksort_helper, low, pos, mid)
        else:
            return rest.ytailforce()
    return Lazy(lazy_quicksort_helper, 0, len(a), LazyVal(None))

a = lazy_quicksort([2, 3, 4, 5, 1])
print a.force()[0] # partially sort and prints 1
print a.force()[1].force()[0] # sort some more and prints 2