Page started by Lars H, 9 July 2004.
For some time now I've been toying with an idea concerning Tcl and functional programming. Recursion is the fundamental concept in functional programming (in the purer installations it is even the only way to handle iteration), but recursively heavy algorithms are usually not a good idea in Tcl, because the cost of recursion is comparatively large, and certainly larger than in the average functional language. One interpretation of this is that Tcl is useless for functional programming, but since I don't believe in that my conclusion must instead be that straightforward recursion is in Tcl a too primitive control structure to be the single solution to all problems. There has to be other things that can do better; the only problem is figure out what they are!
Tail call optimization is one thing. Even languages with low cost for recursive calls tend to suck if they haven't got this built in; it is what pure functional languages use to achieve decent loop performance. But perhaps it is, for practical purposes, rather a distinct control structure which can be dressed out as a recursion? Consider the following command
proc iterate {vars vals body} {
while {![
catch {
uplevel 1 [list foreach $vars $vals break]
uplevel 1 [list if 1 then $body]
} vals
]} {} ; # Empty while body
return $vals
}Syntax-wise it is like foreach, but it only uses the given list of values on the first iteration. On the second iteration, it uses the result from the first iteration, on the third iteration it uses the result from the second iteration, etc. However if one uses the return command in the body then the iterate command returns with that result (break would have been more natural, but that does not support returning a value).
To see how this can be equivalent to a tail recursion, consider the following tail call optimizable implementation of the factorial function.
proc factorial1 { n { result 1. } } {
if {$n <= 1} then {return $result}
factorial1 [expr {$n-1}] [expr { $n * $result }]
}The corresponding implementation using iterate is
proc factorial2 {n} {
iterate {n result} [list $n 1.] {
if {$n <= 1} then {return $result}
list [expr {$n-1}] [expr { $n * $result }]
}
}Is factorial2 more natural than factorial1? That is probably to equal parts a matter of custom and personal taste. For things usually described as functions (e.g. the factorial) the factorial1 style is natural, but for things more commonly described as sequences (or a family of sequences) the factorial2 style has a point.
In terms of speed, and despite what was said above concerning recursion overhead, factorial1 wins by roughly a factor 5. Furthermore if one removes the seemingly pointless "if 1 then" (which is there to force byte-compilation of $body) from the definition of iterate then it will be more like a factor 20! From that one can learn that the overhead of a script level implementation of this kind of control structure is generally much larger than the overhead of recursion, so speed comparisons are probably uninteresting unless one reimplements the control structure commands in C. I'll leave the speed issue at that (unless someone jumps in to show how to make a Critcl implementation of this kind of command). Besides, the fastest Tcl implementation of the factorial is anyway the straightforward iterative one, not any functional programming variant.
iterate is however only a warm-up, the main topic here is bifurcation. A problem with tail call optimization is that there must not be any post-processing of the tail call result, whereas most naive recursive definitions of a function does post-process the result before returning it. The naive definition of a recursive factorial is rather
proc factorial0 {n} {
if {$n>1} then {
return [expr {$n * [factorial0 [expr {$n-1}]]}]
} else {
return 1
}
}The idea of the bifurcation command is to provide something similar to recursion by mimicing the fork/join of parallel processes. The body of iterate is split in two parts: one which spawns "recursive" calls and one which joins the results from these spawned calls back up. The factorial implementation there is
proc factorial3 {x} {
bifurcation [list $x] n {
if {$n > 1} then {
spawn result [expr {$n-1}]
} else {
expr 1
}
} result {
expr {$n * $result}
}
}but as the name hints, it is really meant to support recursions which branch out to multiple recursive calls at each step.
[As for the implementation, I think that will have to wait until some other day. It's getting late enough as it is.]