[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 [http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibtable.html#fib100]. 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;;

----
[Category Mathematics] | [Category Concept]