[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.

----
See also [Tail call optimization]

----
[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).

<<categories>> Concept | Arts and crafts of Tcl-Tk programming