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