Steps towards functional programming

Richard Suchenwirth (whose favorite is the New Orleans function) 2001-03-16 -- Every Tcler does some functional programming sometimes - when he writes, and calls, a proc that returns a result ;-) But in my concept of functional as opposed to iterative programming, most if not all actions are called in functions, so every really functional program would be a (sometimes long) one-liner. See Lambda in Tcl for more functional programming components. Other FP rules of thumb are: no side-effects; don't use variables; recursion instead of iteration; use functional composition.

Tcl lends itself pretty well to functional programming just with the proc command. We would go even more functional if some frequent iterations are wrapped in functions. One such case is foreach, where a list is walked. I often set up an empty result list and append something for each foreach pass. This functionality can be factored out: given an iterator name, an input list, and a body (which mostly will refer to the iterator somehow), return a list of the results from applying (mapping) body to the input list, as follows:

 proc lforeach {_i list body} {
        upvar $_i i
        set res [list]
        foreach i $list {
                lappend res [uplevel 1 $body]
        set res ;# or return $res, if you prefer
 lforeach i {a bb ccc dddd} {string length $i}
 % 1 2 3 4
 set foo .5
 % .5
 lforeach i {a bb ccc dddd} {expr [string length $i]+$foo}
 % 1.5 2.5 3.5 4.5 ;# just to show that foo is visible to body

Another frequent iteration is reading lines from a file. Functionally wrapped, we give a filename and receive a list of the lines in that file:

 proc lines-of fn {
   set f [open $fn r]
   set t [read $f [file size $fn]]
   close $f
   split $t \n
 } ;# but see below for a more functional one-liner...

and here's a little averager that uses its input twice:

 proc laverage L {expr ([join $L +])/[llength $L]}

where expr [join $L +] is the functional equivalent of adding the elements of a list in a loop (see Sample math programs for detailed discussion). Having these components ready, here's a functional demo: determine the average line length in a file, all in one line:

 laverage [lforeach i [lines-of $file] {string length $i}]

Yes, this is still Tcl, though it looks quite different again... People often talk about wishes for Tcl 9.0, but my major wish is I could fully utilize what's in Tcl since 7.4 (when I started ;-)

Salt and Sugar note: for better looks, we might rewrite the top line of lforeach and laverage with some sugar arguments like this:

 proc all {list "for" _i "get" body} {

and then the example could be

 average of: [all [lines-of $file] for: i get: {string length $i}]

Matter of taste, though. Sometimes memories of COBOL (or was that Smalltalk?) come up... Or how is

 average [of {string length $i} for: i in: [lines-of $file]]

Somehow this is drifting off into natural languages... if it weren't for them brac[k]e[t]s!%

The lforeach command does the same thing as the Smalltalk collect method (Collection class incuded in the standard library). To not discover the old things again, I present also a tcl implementation of the also very useful Smalltalk methods detect and select. Detect searches for the first element that satisfies the test. Select returns the filtered list of elements that satisfy the test.

 proc ldetect {var_ref list test} {
        upvar $var_ref var
        foreach a $list {
            set var $a
            set rtest [uplevel [list expr $test]]
            if $rtest {
                return $a
 proc lselect {var_ref list test} {
        upvar $var_ref var
        set ret {}
        foreach a $list {
            set var $a
            set rtest [uplevel [list expr $test]]
            if $rtest {
                lappend ret $var
        return $ret
 # usage
 ldetect each {1 2 3 4} {$each>2}
 # would return 3
 lselect each {1 2 3 4 2 3} {$each>2}
 # would return list {3 4 3}

This kind of programming of base control commands is possible because of the uplevel command. In Smalltalk and Ruby it is possible because of genial idea of blocks that also allow to execute code in foreign context.

Afterthoughts: (1) Maybe Tcl's foreach command could be enhanced (e.g. with a switch) to return a list of its results like lforeach above. Right now it just returns an empty string.

(2) If in lforeach we changed body into a partial command (like in traces and scrollbar bindings), we could get rid of an explicit iterator:

 proc lmap {pcmd "to" list} {
   set res [list]
   foreach i $list {
      lappend res [uplevel 1 $pcmd [list $i]]
   set res
 average [lmap {string length} to: [lines-of $file]]

But this would limit the flexibility as shown in the ...+$foo example. For a more conventional (and powerful) map see Function mapping.

APL is a heavily functional language. See Playing APL on a partial reimplementation in Tcl...

Functional programs tend to have deeply recursive calls, because they depend on recursion for variable binding. Efficient functional programming therefore often depends on Tail call optimization.

Here's a more functional goodie (it has to resort to one intermediate variable) to get the list of lines from a text file:

 proc lines-of name {split [read [set f [open $name]]][close $f] \n}

The trick is the invisible concatenation of reads and closes results (where the latter is an empty string - RS)

Another nice functional wrapper, which filters a list according to a condition, was given in More graph theory:

 proc inducedCycles3 g {
    each cycle in [cycles $g] where {isInducedCycle $cycle $g}
 proc each {*i "in" list "where" cond} {
        set res {}
        upvar ${*i} i
        foreach i $list {
                if {[uplevel 1 expr $cond]} {lappend res $i}
        set res

See also Playing Haskell - Functional composition - Custom curry - Playing Joy

In 2002, it might be that the functional language most often associated with Tcl is XSLT (!). Certainly XML processing remains a growth industry, and Tcl is particularly apt for this kind of work [give references].

Arjen Markus This page provides an excellent opportunity to lay down yet another research program: using Tcl as a language for describing Software Architecture.

Just think about it a moment:

  • Tcl allows you to abstract away from petty little details as memory management. It is flexible enough to allow a wide variety of object-oriented approaches, almost without enhancements to its syntax (apart from a few border cases, like anonymous arrays in STOOOP).
  • Tcl has a built-in event-driven programming model, so that client/server applications can fairly easily be built and described in global terms.
  • Tcl has a powerful mechanism for generating and executing code "on the fly".

A more elaborate and down-to-earth example is that of a pipeline, consisting of filters like UNIX's "grep". Almost any serious UNIX user has encountered them. They can easily be described in terms of UNIX shell syntax, but what about the processes behind a pipeline?

When I first thought about it, I thought it was trivial:

   set result [filter1 [filter2 [filter3 $source]]]

Yet, it is more complicated than that - the above assumes a strict sequential execution model. Instead:

  • Processing should be done "synchronously", filter1 immediately takes up what filter2 produces from the results of filter3.

The "proper" model is instead that of the intersection (or mapping) of "infinite" sets - see Manipulating infinite sets in Tcl. A set of unknown size (possibly infinite) is queried for the first or the next item. This can then filtered by the innermost filter (filter3 in the example). The filter in itself acts as such a set and can therefore be queried in turn.

Thus, you get a cascade of filters - the pipeline according to UNIX.

When applied to finite sets, nothing actually changes. The idiom remains the same, but possible implementations might change (for performance reasons?). Yet that is an irrelevant detail in the context of functional programming or of software architecture.

RS: If you brace instead of bracketing, this can be done with Streams.

Take a look at some code from ArsDigita ACS: (both documents not accessible at the moment)

  • Functional Programming in Tcl. This library adds the expressive power of functional languages like LISP, Gofer or Haskell to the Tcl language! [L1 ]
  • Tree implementation using functional programming [L2 ]

RS 2005-02-19 - Another example: One way to construct a unit matrix (a square matrix where the main diagonal is 1, all other elements 0) is this, which uses for loops as known from C:

 proc unitmatrix1 n {
   set res {}
   for {set i 0} {$i<$n} {incr i} {
       set row {}
       for {set j 0} {$j < $n} {incr j} {
           lappend row [expr {$i==$j}]
       lappend res $row
   set res

One can factor out for functionality with an integer range generator:

 proc iota n {
    set res {}
    for {set i 0} {$i<$n} {incr i} {lappend res $i}
    set res

Now with lforeach (see on top of this page) and iota, the unit matrix generator can be done like this (or in less lines of code):

 proc unitmatrix2 n {
    lforeach i [iota $n] {
       lforeach j [iota $n] {
           expr {$i==$j}

I think it reads better than unitmatrix1 - you can concentrate on what really goes on, rather than skim over the householding of initializing and returning variables...

Appendix Section

gold 10/11/2020. Added appendix below, but original source code and text above was unchanged.


Hidden Comments Section

Please place any comments here, Thanks.