Version 4 of Trampoline

Updated 2005-08-01 16:57:59 by suchenwi

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]]]"}
}
% fac 5
[expr 5 * [fac 4]]
% 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 | Tail call optimisation (both have their merits :)

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
}