This is a series of blog entries that introduce three devices written using the yield operator for Scheme. Previously I had the following entries that described the requisite features of a complete yield operator and an implementation of such a yield operator for Scheme.

Yield the Magnificent

Yield Implementation for Scheme

Trampolines, Pipelines and Pi are programming devices or constructs that are built on top of the yield and purely the functional subset of Scheme.

There are many ways one can look at the power provided by the yield operator. One way to look at the yield is that it is a call-tree walker. It can move information up and down the call tree. If the yield implementation is sufficiently flexible, it can walk up and down several call-trees which exist concurrently.

Another way to look at the yield is to think of it as adding input and output capabilities to a function in functional system. A function during the process of computing its value changes state, creates temporary variables etc. When the result or return value of the function is computed the state of the function collapses and the value is returned. Yield offers a way for functions to do input and out with other functions while they maintain state. More about this later.

Trampolines

I want to start off by introducing the simplest of the three devices, the trampoline – sometimes I refer to this construct as the trampoline process as well. (Note: The name trampoline is used only in the context of the yield based programming device I describe here and is not a logical extension of other trampoline constructs you may have encountered before.)

The trampoline was introduced to address the following scenario – in a purely functional context what is the meaning of a parameter code block that is passed to an iterator cannot affect the caller’s state. Such a parameter code block is always a closure, in a functional context. On invoking a closure, the closure cannot maintain or modify state in the caller without resorting to some sort of a side effecting operation such as an assignment.

The trampoline packages such a computational effect so that the programmer need not think in non-functional terms when using the yield. Instead of using a set! or an assignment as the computational effect, the trampoline device uses a jump as the computational effect.

To illustrate what I mean, one has to look at the relation ship between the caller and a yielding callee in an imperative language. The flow of control is almost always as follows for a Ruby or C# yield (yes, I am abstracting out many details here) –

1. caller calls iterator, control transfers to iterator
2. iterator does some computation and produces a values, yields it
3. control transfers to caller,
4. caller does something with the value – this something is usually a side effect
5.  caller returns a value to iterator, control transfers back to iterator
6. steps 2 to 6 can repeat any number of times till the iterator returns.

The problem with this functional programming land is that the there is no use in yielding the value if the caller cant to anything with it – an alternative is pass an environment back and forth between the caller and iterator or some such thing, which is always tedious to manage.

The trampoline does the following. The trampoline becomes the caller for two functions, both of which are iterators that concurrently maintain state. One iterator place the role of the caller in the imperative case and the other one plays the role of the callee. Since the function playing the roles of the caller is an iterator, its free to maintain any sort of local state it chooses.

The trampoline device is a simple device, but to see the correct analogy that argues its purpose is a little tricky. Another way to look at a trampoline is to look at it as two iterators such that when one yields control passes to the other and when the other yields control passes back to the first. The process terminates when one of the two iterators terminate.

Here is an example of code that uses the trampoline. When the trampoline process terminates, a list of values that are the return (or last yielded values) of both iterators is returned.

This is an iterator that adds values that it gets yielding the current sum at any point.

(define adder

  (lambda-iter ()

     (let loop ((s 0))

       (loop (+ s (yield s))))))

This is an iterator that yields the first ‘n’ Fibonacci numbers

(define fibonacci

  (lambda-iter (n)

    (let loop ((a 1)(b 1)(n n))

      (if (not (zero? n))

          (begin

            (yield a)

            (loop b (+ a b) (sub1 n)))))))

To sum the first n Fibonacci numbers, one create a simple trampoline between the iterators

(printf "Sum = ~a~n"

        (cadr (trampoline-process (fibonacci 10) (adder))))

The cadr is there because the trampoline returns a list of two values, the last value obtained from the Fibonacci and the last value obtained from the adder. We are interested in the sum yielded by the adder and so we take the cadr.

The trampoline process that is implemented in the library that I have shared below is a slight generalization of this idea – the generalization being that the trampoline process can take any number of iterators as arguments creates a circular list of control transfer using yield. While having two iterators in a trampoline can be thought of as the equivalent of an imperative caller and callee, there is no simple parallel I can think of for three of more iterators in a trampoline. Below is a diagram of trampoline with three iterators.

I frequently use a trampoline while programming in scheme using yield. While it may not be easy to see why trampolines are useful just by using a simple example like the above, they useful in managing code complexity when each of the iterators involved has to do a non trivial computation.

As an example I wrote a CPS transformer for a subset of scheme last semester, at the heart of which was a trampoline. One iterator would recursively walk down the source expression tree and would yield out values. The other iterator would reconstruct a CPSed expression. So it gives you the conceptual clarity of writing a two pass CPSer while in effect only one pass happens. (Of course I could mash both the analysis and construction phases into one big hairy ball of mutually recursive functions, but that would not let me focus on one problem at a time and possible build them up as reusable iterator components. This of course was a little non traditional and might not have been easy on the evaluator of the assignment).

Download Sources for Yield, the Trampoline and the Sample Code above.

In the next related entry I hope to discuss the Pipeline device (aka the Pipe device).