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

----
[Category Control Structure]