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
CM 16 Jan 04 : Ooops! Although it is quite irrelevant to the page :-), it seems that fibonacci(0) is 0, not 1, see a page with the first 300 Fibonacci numbers here [L1 ]. Note that Tcllib's "::math::fibonacci" function agrees.
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:
* 0 if the list is empty;
* else 1 + the length of (the rest of the list without its first element)
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;;Stefan Finzel Sometimes caching is a good idea using recursions. Consuming some static memory requires often less resources than using dynamic memory and stack at execution time, e.g.
interp recursionlimit {} 100000
proc ack {m n} {
global cache_ack
if {$m} {
if {[info exists cache_ack($m,$n)]} {
return $cache_ack($m,$n)
} elseif {$n} {
return [set cache_ack($m,$n) [ack [expr {$m - 1}] [ack $m [expr {$n - 1}]]]]
} else {
return [set cache_ack($m,$n) [ack [expr {$m - 1}] 1]]
}
} else {
# do not cache this simple case to keep cache size small
return [incr n]
}
}Speeding up execution is another lovely side effect.
% catch {array unset cache_ack}
0
% time {ack 3 6}
5670 microseconds per iteration
% time {ack 3 6}
18 microseconds per iterationWithout caching EACH call requires
# time {ack 3 6} 100
151591 microseconds per iterationPlease note only {ack 3 6} can be computed without caching. Using caching even gets {ack 3 8}.
Remember to inspect memory usage to avoid future pitfalls.
% array size cache_ack 3075 % string length [array get cache_ack] 32984
Just for fun (in less than 4 seconds):
% ack 3 15 262141
Stefan Finzel As it happens there is just a new site comparing languages http://shootout.alioth.debian.org/benchmark.php They use two recursion examples among others to evaluate the strength and quality of a language. But simply applying computer algorithmens is not everything.
The first example is the Ackermann function as already described above.
The other example is the Fibonacci benchmark which is typically very time consumptive:
proc fib {n} {
if {$n < 2} {
return 1
} else {
return [expr {[fib [expr {$n-2}]] + [fib [expr {$n-1}]]}]
}
}
% time {fib 32} 100
5789520 microseconds per iterationBut like some other examples this solution does not respect the strength of Tcl. See another solution using a caching by three more lines:
proc fib {n} {
global cache_fib
if {$n < 2} {
return 1
} elseif {[info exists cache_fib($n)]} {
return $cache_fib($n)
} else {
return [set cache_fib($n) [expr {wide([fib [expr {$n-2}]] + [fib [expr {$n-1}]])}]]
}
}
catch {array unset cache_fib}
% time {fib 32}
368 microseconds per iteration
% time {fib 32}
19 microseconds per iterationThe initial call requires less than 400 microseconds instead of more than 5.000.000 microseconds! For each fibonacci number only one cache entry is required. That makes less than 500 bytes of memory in this example! And this example using wide() works to fib(90)
% time {fib 90}
1071 microseconds per iteration
% fib 90
4660046610375530309You are able to use this trick in other languages too, mostly at the cost of readability and simplicity.But not in Tcl.
There will be arguments about algorithmen theory, and the results the benchmarks are trying to accomplish. On the other side there are a lot of software solutions restricted to raw theory while real live would allow more effective programming! ;-)