Documentation
Not logged in

Copyright (C) 2009-2010, Trevor Davel <twylite AT crypt DOT co DOT za>
See the file "LICENSE.txt" (Tcl/Tk License) for information on usage and redistribution of this file, and for a DISCLAIMER OF ALL WARRANTIES.


Navigation: control::functional manual | TIP: Higher-order functions in Tcl.

A review of FP and higher order functions in Tcl

The control::functional module has not been developed in isolation. Approaches by other languages have been considered, as well as existing Tcl implementations.

Review of non-Tcl implementations

I'll admit to a shoddy research job for this bit: I used the Wikipedia.

foldl

Most languages that support 'left fold' also support 'left fold without initial value'. The syntax foldl(func, ?initial?, list) is common.

foldr

'Right fold' is less widely supported than 'left fold', and 'right fold without initial value' even more so. The names suffix 'r' or 'right' is commonly used to distinguish this function from (left) 'fold' or 'reduce'. The syntax foldr(func, initval, list) is common.

filter

This function goes by many names including 'filter', 'find_all', 'grep', 'where' and 'select'. I prefer the name recognised in theory: 'filter'. The predicate is a function that returns a boolean. The syntax filter(pred, list) is almost universal.

map

A number of langauges support 'map' with 2 or more arguments. Most adopt the syntax map(func, list1, list2, ...).
Where the lists differ in length one of five strategies may be employed:

Command prefixes

The Wiki has a page on command prefixes that provides good background on the concept. It discusses the various ways a command prefix may be called, and provides comparisons to scripts, commands and lambdas.

Review of complete Tcl implementations

So far as I have discovered the only reasonably complete implementations of higher-order functions for Tcl are:

Tcllib's struct::list

Provides map (over a single list), filter, fold (left fold with initial value), and iota, but no foldr. Also provides struct::list split which is similar to filter but splits the input set into two lists using a predicate.
Uses a command prefix, which is invoked as [uplevel 1 [linsert $cmdprefix end $arg1 $arg2 ...] ].
The command prefix is the last argument to the function, which can make partial application difficult, and reduces visual accessibility when chaining higher-order functions.

Wub's functional-1.0.tm

Provides map (over a single list), filter, foldl (with initial value), foldr (with initial value), and iota. Also provides compose and helper functions lambda and curry.
Uses a command prefix, which is invoked as [uplevel 1 {*}$func [list $arg1 $arg2 ...] ]. In my opinion $func is over-expanded which leads to some awkward quoting by the caller and an inconsistent model of what 'a function' is.
The command prefix is the first argument to each higher-order function. curry uses lappend to add arguments to a command prefix, but the extra expansion when the command is invoked allows inline currying using [list $func arg1 arg2 ...] (producing a function that cannot - in turn - be curried in the same fashion).
    % package require functional
    1.0
      
    # Various ways to do the same thing
      % map {list a b} {1 2 3}
      {a b 1} {a b 2} {a b 3}
      % map [list {list a b}] {1 2 3} ;# unexpected
      {a b 1} {a b 2} {a b 3}
      % map [curry {list} a b] {1 2 3}
      {a b 1} {a b 2} {a b 3}
      % map [curry {list} {a b}] {1 2 3} ;# very unexpected
      {a b 1} {a b 2} {a b 3}
      % map [curry [curry {list} a] b] {1 2 3}
      {a b 1} {a b 2} {a b 3}
    
    # Procs with names that are lists
      % proc {nasty name} {args} { return $args } ;# equivalent to [list]
      % map {nasty name a b} {1 2 3} ;# didn't really expect this to work
      invalid command name "nasty"
      % map {{nasty name} a b} {1 2 3} ;# intuitively this should work
      invalid command name "nasty"
      % map [list {{nasty name} a b}] {1 2 3}
      {a b 1} {a b 2} {a b 3}
      % map [list {{nasty name}} a b] {1 2 3} ;# currying via [list]
      {a b 1} {a b 2} {a b 3}
      % map [curry {{nasty name}} a b] {1 2 3} ;# unexpected
      invalid command name "nasty"
      % map [curry {{{nasty name}}} a b] {1 2 3} ;# very unexpected
      {a b 1} {a b 2} {a b 3}
      
    # Recursive currying      
      % map [curry [curry {{{nasty name}}} a] b] {1 2 3}
      {a b 1} {a b 2} {a b 3}
      % set f [list {{nasty name} a}]
      {{nasty name} a}
      % map $f {1 2 3}
      {a 1} {a 2} {a 3}
      % map [list $f b] {1 2 3} ;# can't use a [list]-type curry recursively
      invalid command name "{nasty name} a"
      % set f [curry {{{nasty name}}} a]
      % map [list $f b] {1 2 3} ;# or on a curried function
      invalid command name "{nasty name}" 
      
    # functional-1.0.tm's model for a function is:
    #   set func [list [list $cmd $arg ...] $extraarg]
    # where [lindex $func 0] is expanded, and extraargs are concatenated to this expanded list

NEM's ''funtcl'' on More functional programming

A pre-8.5 package that provides its own apply (as funtcl::apply).
Supports map (over a single list), filter, foldl (with initial value), foldr (with initial value) and compose.
Uses a command prefix, which is invoked as [eval $func [list $arg1 ...] ]. The package also provides an unknown with leading word expansion that invokes via uplevel.
The command prefix is the first argument to each higher-order function.

Review of partial Tcl implementations

There are also a number of Additional list functions that smell like higher-order functions:

Various implementations of fold, iota, map and filter are presented in Category Functional Programming:

List comprehensions

List Comprehension can offer a more natural syntax for constructing and transforming lists, however it is out of scope for this proposal. I envisage a list comprehension implementation built on map/filter, or possibly arising as a consequence of the implementation of map/filter.