## Trampoline

Richard Suchenwirth 2005-04-09 - A trampoline is a software device to repeatedly call some code until a terminal condition is met. It can give the effect of recursion without consuming much stack. Slightly rewritten from Playing TRAC, here is a simple trampoline:

``` proc trampoline form {
while 1 {
set new [subst \$form]
if {\$new eq \$form} break
set form \$new
}
set form
}```

Testing with the classic factorial - either constant 1 is returned, or a bracketed expression for the next trampoline jump:

``` proc fac n {
expr {\$n<=1? 1: "\[expr \$n * \[fac [incr n -1]]]"}
}```

Direct call returns a string to be substituted:

``` % fac 5
[expr 5 * [fac 4]]```

But on a trampoline, it jumps:

``` % trampoline {[fac 5]}
120```

In the dialect developed in Playing TRAC, factorial looks like this:

` DS fac {[GR \$1 1 "\[ML \$1 \[CL fac [SU \$1 1]]]" 1]}`

The structural similarity should be evident.

RS 2005-08-01: A different approach that does not go over string reps every time (which is known as inefficient when doing arithmetics). The "trampolined" function returns 1 if it can continue, and modifies variables in caller's scope via upvar:

``` proc facstep {_in _res} {
upvar 1 \$_in in  \$_res res
if {\$in>1} {
set res [expr {\$res * \$in}]
incr in -1
return 1
} else {return 0}
} ```

The trampoline bounces the step function as long as it promises to deliver more:

``` proc fac in {
set res 1
while {[facstep in res]} {}
set res
} ```

Larry Smith I once used something like this to provide pseudo-multitasking in a single-thread environment. It was a Turbo-Pascal program, of all things, on an original IBM 8088 PC. Background tasks had no loops. They went once through and returned 1 if they should be called again. These tasks were called over and over, as appropriate depending on the return values, while busy-waiting for the key strobe. The system was quite flexible and very easy to understand and code.

DKF: It should be noted that Tcl 8.6's NRE uses a trampoline at the level of the C stack. It's almost an identical concept to above, except that there's a somewhat more sophisticated mechanism in place (so there may be multiple scheduled continuations instead of just one).

 Category Concept Arts and Crafts of Tcl-Tk Programming