Trampolined style | Proceedings of the fourth ACM SIGPLAN international conference on Functional programming

Trampolining is a style of writing programs in which a single “scheduler” runs all the other functions and performs all transfers of control. The functions (also called as threads) run in discrete steps: This means that a thread runs for some amount of time, then returns control to the scheduler which can schedule other threads or continue that thread.

A thread/function has type $T(\alpha )$ which means it is a thread which will eventually return a value of type $\alpha$. However, since execution proceeds in discrete steps it can either return a value or another thread to the scheduler. So the type becomes $T(\alpha )=\alpha +(unit\to T(\alpha ))$ . To do this there are additional functions that such a thread will use:

1. $bounce$: This function is called with a lambda that takes a unit. All recursive tail calls are called as bounce (lambda () ...)
2. $return$: This is called when the function wishes to return a value. It can do so by calling (return ...)

Consider this factorial implementation using this method

(define fact-acc
	(lambda (n acc)
		(cond
			[(zero? n) (return acc)]
			[else 
				(bounce 
					(lambda ()
						(fact-acc (- n 1) (* acc n))
					))])))

In the simplest case where bounce evaluates the lambda directly and return is the identity function, we can see this function boils down to a simple sequential factorial computation.

Thunk

A thread returning a lambda with its remaining computation can also be called a thunk which will be executed later

A scheduler can be made which can execute any number of threads by running each of them one by one till one of them completes.

We can define a thread in LISP as a record case with two cases: done and doing. The former holds the value while the latter holds a thunk for later evaluation. Thus we can have the defintions of return and bounce:

(define return
	(lambda x
		(make-done x)))
		
(define bounce
	(lambda thunk
		(make-doing thunk)))

Composition

(Section 3.1)

How do we compose functions written in the trampolined style? Suppose we have two functions $f:\alpha \to T(\alpha )$ and $g:\alpha \to T(\alpha )$. We want to evaluate a composition of these, take the result from $g$ and then feed it to $f$.

We first define a helper function that will take a function and a thread and then feed the result of the thread to the function

(define sequence
	(lambda (f thread)
		((record-case thread
			[done (value)
				(f value)]
			[doing (thunk)
				(sequence f (thunk))]))))

Then we can define the sequential operator

(define seq-comp
	(lambda (f g) 
		(lambda x
			(sequence f (g x)))))

Dynamic Thread Creation

(Section 4)

In this section, we see how a thread can be allowed to create more threads of computation. This requires modifying the type so $T(\alpha )=\alpha +(unit\to list(T(\alpha )))$. Thus a thread can return more threads or it can return an empty list if it wants to terminate. Communication between threads has to be done through shared variables.

The definitions of $return:\alpha \to list(T(\alpha ))$ and $bounce:(unit\to list(T(\alpha )))\to list(T(\alpha ))$ also change due to the change in type:

(define return
	(lambda x) 
		(list (make-done x)))
	
(define bounce
	(lambda thunk)
		(list (make-doing thunk))))