[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
}
----
[Category Concept] | [Arts and crafts of Tcl-Tk programming]