Arjen Markus As I have been reading a book on Computability theory and been thinking about sundry related, more or less theoretical subjects, I thought it was time to bring in some practical work. Functional programming seems a very powerful way to do things (see Steps towards functional programming), even though strange if you have a procedural background like me.
So, what about the Fibonacci series:
Fib(0) = 1 Fib(1) = 1 n >= 2: Fib(n) = Fib(n-1) + Fib(n-2)
Every one ought to know this one. Another famous recursive function is the Ackermann function:
Ack(0,n) = n+1 Ack(m,0) = Ack(m-1,1) Ack(m,n) = Ack(m-1,Ack(m,n-1))
They are simple to write down and relatively easy to code in a language that allows recursive function calls.
But my goal is broader: can we not use Tcl's amazing flexibility and build a new control construct that comfortably encodes such functions?
Yes, it took some experimenting, but have a look at this:
proc recurs { vars actions } {
foreach {cond action} $actions {
set _handle_ 1
foreach v [uplevel subst [list $vars]] c [uplevel subst [list $cond]] {
if { $v != $c } {
set _handle_ 0
break
}
}
if { $_handle_ } {
uplevel $action
break
}
}
}
proc fib { m } {
recurs { $m } {
0 { set v 1 }
1 { set v 1 }
$m {
set m1 [expr {$m-1}]
set m2 [expr {$m-2}]
set v [expr {[fib $m1]+[fib $m2]}]
}
}
return $v
}
proc ack { m n } {
recurs { $m $n } {
{ 0 $n } { set v [expr {$n+1}] }
{ $m 0 } { set v [ack [expr $m-1] 1] }
{ $m $n } {
set m1 [expr $m-1]
set n1 [expr $n-1]
set v [ack $m1 [ack $m $n1]]
}
}
return $v
}
for { set i 0 } { $i < 10 } { incr i } {
puts [fib $i]
}
puts "Ackermann: [ack 2 2]"
puts "Ackermann: [ack 3 3]"The heart of this implementation is the new construct recurs which takes a list of variables and a bunch of cases with associated actions. To be flexible, I designed the construct in such a way that you can use unevaluated expressions - {$m 0} for instance - to keep close to the mathematical original.
Warning: the Ackermann function is a nasty one, if you use too large values for the arguments, then it will take ages before the evaluation completes.
While testing, I thought my beautiful construct was faulty (it worked for one variable, but not for two) and I spent quite some time figuring out why. Until I did a manual calculation and found out that Ack(2,2) already takes in the order of 30 evaluations of Ack(m,n).
Other references:
Super-exponential growth in text manipulation
RS wonders if using expr as case dispatcher would not make leaner, faster code, while at the same time looking not much worse:
proc fib m {
expr {
$m<=1 ? 1
: [fib [expr {$m-1}]] + [fib [expr {$m-2}]]
}
}RS: In the LISP/Scheme worlds recursion is a popular programming paradigm which allows brief code. Tcl can well use recursion, but without tail call optimization, we soon hit the limits. Consider the following silly code, where the length of a list is measured recursively:
proc llength-rec list {
if {$list==""} {
return 0
} else {
expr {1+[llength-rec [lrange $list 1 end]]}
}
}This is silly because Tcl lists, as opposed to Lisp lists, just know how long they are.. But it's also terribly slow and limited to not-too-long lists. Here is a list generator where you specify how long a list you want:
proc make-list n {
set list {}
for {set i 0} {$i<$n} {incr i} {lappend list $i}
set list
}
% make-list 5 => {0 1 2 3 4}
% llength-rec [make-list 50]
50
% llength-rec [make-list 500]
too many nested evaluations (infinite loop?)and it took 10 seconds for this error to appear... So for the time being, don't overuse recursion in Tcl - iteration (with for, foreach, while) is mostly more efficient.
EB The recurs construct is similar to pattern matching in language like CAML or Haskell (see Playing Haskell). This gives really good looking to such functions:
let rec Ack = fun
(0,n) -> n+1
| (m,0) -> Ack (m-1, 1)
| (m,n) -> Ack (m-1, Ack (m, n-1));;
let rec llength = fun
[] -> 0
| _::L -> 1 + llength L;;