[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}]]
   }
 }
----
[Category Mathematics] | [Category Concept]