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