Version 57 of Functional Programming

Updated 2012-06-24 05:51:46 by RLE

(short 'FP') A programming paradigm, compare imperative programming - the one which Tcl and most other languages use. (*) In functional programming rather than representing a program as a series of steps that modify state (by setting variables, for instance) it's represented as a set of interdependent math-style functions which each contain just one expression. Because the only reason to include multiple lines in a function would be to modify state, in purely functional programming, all functions are one-liners; this means code runs as a cascading series of function calls, a bit like a spreadsheet. Programs tend to be viewed more like descriptions of problems than step-by-step instructions.

(*) RS: I'd say that Tcl is often used imperatively, but at bare-bones it's fully functional - just by the fact that every command returns a result - take it or leave it...

 # Functional Tcl one-liner for Unix 'sort' (part of it, at least :^)
 puts stdout [join [lsort [split [read stdin] \n]] \n]

Since explicit sequential execution isn't provided, code-flow structures like loops don't exist, so the favored method for, say, repeating an action is recursion. Languages using this paradigm tend to be fairly slow compared to imperative ones, since the actual underlying machine code of computers is much more step-by-step and there's a big loss in the translation. This is wrong--see my retraction below. -FW

IL: I thought Backus's point was that through functional language design you highly optimize in a way imperative langauges can't? FW: Yes, and years later, I have to say that I was completely wrong: among very high-level languages, functional languages can be quite ridiculously fast. My original claim was a half-baked inference that doesn't bear out in real life. For whatever reason (perhaps, in the case of Lisp, the small number of basic concepts to implement) many functional languages get native-code compilers, and Haskell performance on GHC can rival C in some situations. Between the availability of native compilers; the relative ease--contrary to my older stance--of converting functional abstractions into simple lower-level forms via techniques like tail-call optimization; and the opportunities which, as you say, functional programming offers for clever optimizations like lazy evaluation; functional languages on the whole turn out to be very quick.

See also

Functional languages include Lisp/Scheme, Haskell, OCaml, Joy, etc. -FW


RS: In what respect is Lisp more functional than Tcl? As far as I know, both languages evaluate a sequence of expressions ("commands" in Tcl) in order - in Lisp this is called "implicit PROG", and yes, they even had a GOTO :).

I'd say functional programming is a style that you can have in many languages, including Tcl, if you

  • write functions whose return value depends only on their arguments input
  • don't use side effects (including assigning to variables)
  • allow functions as values that can be arguments to, and return values of, other functions, or both (e.g. in functional composition)
  • use nested function calls instead of command sequences, so functions are just one-liners

Example, imperative (using two local variables, and return):

 proc readfile name {
   set fp [open $name]
   set data [read $fp]
   close $fp
   return $data
 }

Example, functional (no variables except function arguments), using the classic helpers K and lambda:

 proc readfile name {[lambda fp {K [read $fp] [close $fp]}] [open $name]}
 proc K {a b} {set a}
 proc lambda {argl body} {proc [info level 0] $argl $body; info level 0}

See also RPN where the non-use of variables is driven to a high degree, even for function arguments. Example from RPN again (still valid Tcl :-). No variables used at all, except for the implicit stack, the Big Variable - code inspection shows that it takes a filename from the stack, and leaves the file contents as a string on the stack:

 rpn /readfile {open dup read swap close drop} def

In Pocket Joy 2005 that would be

 : readfile  open (read) (close) cleave pop

FW: I implied (IMO) that the functional model isn't only possible with "functional languages," they're just designed with that in mind. I also realize Lisp is really pretty imperative, but it is generally called a "functional" language for whatever reason, and a lot of functional programming is done in it. Haskell is used as the standard "purely" functional language - but it still has monads and such.

OAC Monads are functional, that's the point of using them: you really can't do anything with side effects in Haskell. Monads are an extremely fancy work-around for that. :)

NEM See also Monadic TOOT for an exploration of monads in Tcl.

RHS I'd say one way Lisp is "more functional" (geared towards FP, rather than has more function) than Tcl is the fact that it generally has optimizations like Tail call optimization, which makes programming w/o variables much easier.


There must be something incredibly interesting and fascinating about this, as RS seems to be so fond of it. But LES fails to see any advantage in a style that makes code so convoluted and hard to read afterwards.

RS: One can write very convoluted code in FP, yes; but it can be beautifully simple (see filter):

 proc intersection {set1 set2} {filter $set1 {in $set2}}

In my opinion FP offers powerful abstractions that allow for simpler code - and who types less, can't make so many bugs... :)

Another example: Someone asked on the Chat how to rewrite part of a line in a file, say change "20 11" to something different. Here's how to do this in FP spirit:

 proc >> {name data} {set f [open $name w]; puts -nonewline $f $data; close $f}
 proc << name {K [read [set f [open $name]]] [close $f]}
 proc K {a b} {set a}
 >> $filename [regsub "20 11" [<< $filename] $someOtherValue] 

RHS Personally, I find the above (file operations) to be a bad choice for an example of functional programming. While some things are more natural done functionality (ie, fibonacci), other things are more natural done imperatively (file operations). For example, I find the following to read much better:

 proc << {name} {
     set fd [open $name]
     set text [read $fd]
     close $fd
     return $text
 }

File operations are, by nature, "do this, then that, then this other thing". I tend to think that the above is a prime example of why Lisp/Scheme/etc are considered "ugly" languages by some. When you want to do something that would be more naturally done in an imperative style, you likely wind up jumping through hoops and having lots of parens.

RS: I agree that << and >> are not the best of examples. My point was more to show their application,

 >> $filename [regsub "20 11" [<< $filename] $someOtherValue] 

which expresses pretty clearly the intended operation, without having to administer intermediate variables, but with nested functions instead.

On re-thinking, << can be implemented more functionally by introducing fmap (influenced by ApplyAll in Backus' FP; Joy has a comparable operator in cleave) which maps a list of functions on one argument, as variant to lmap which maps a function to a list of arguments:

 proc fmap {functions x}  {lmap f $functions {$f $x}}

#-- slight sugaring

 proc first list  {lindex $list 0}

#-- Then we can write << like this:

 proc << filename  {first [fmap {read close} [open $filename]]}

The advantage is that no local variable is needed, except for the formal parameter filename. This crystalline conciseness isn't everybody's taste, but I at least like it :)


RS: More functional fun on a Sunday evening: A classic FP operation is fold which reduces a list of values to one. The neutral element of the operation is the first argument, so I just call that "res" to save one assignment:

 proc fold {res op list} {
    foreach e $list {set res [$op $res $e]}
    set res
 }

This requires expr operators exposed as Polish function names:

 foreach op {+ - * /} {proc $op {a b} "expr {\$a $op \$b}"}

Isn't there a change now in Tcl 8.5 that allows this to be replaced?


Two typical uses of fold can now just be curried:

 interp alias {} sum     {} fold 0 +
 interp alias {} product {} fold 1 *

and used in something useful:

 proc laverage list {expr {1.*[sum $list]/[llength $list]}}

Functional composition is of course a must-have:

 proc o {f g x} {$f [$g $x]}

And another flavor of integer range generator, [iota1 5] -> {1 2 3 4 5}:

 proc iota1 n {
    set res {}
    for {set i 1} {$i<=$n} {incr i} {lappend res $i}
    set res
 }

So now we can compose factorial, instead of the recursion as seen too often (coding this I had another glimpse of the Zen of Tcl):

 interp alias {} ! {} o product iota1

Testing:

 % sum {1 2 3 4 5}
 15
 % product {1 2 3 4 5}
 120
 % laverage {1 2 3 4}
 2.5
 % ! 5
 120

Another use of FP means, by NEM and RS in the Chat on 2005-04-04: Which fixed-pitch fonts are available to Tk?

 filter [lambda f {font metrics [list $f] -fixed}] [font families]

The list inside was needed to prevent font names with spaces to be misparsed as {name size ?style?}


RS 2005-04-08: readfile again, this time fully FP-clean (in the sense of Functional programming (Backus 1977), i.e. only operating on functions, never on a single variable):

 Def readfile = o first {o {fmap {read close}} open}

with a little more sugar for interp alias:

 proc Def {name = args} {eval [list interp alias {} $name {}] $args}

This requires to let unknown know that we want auto-expansion of first word:

 proc know what {proc unknown args $what\n[info body unknown]}
 know {
   if {[llength [lindex $args 0]]>1} {
      return [uplevel 1 [lindex $args 0] [lrange $args 1 end]]
   }
 }

RS Oh my: re-reading this page again, sometimes I've coded not much less imperative than Julius Caesar. Take iota1 for example: two local variables, a loop - in FP there's different ways, mostly recursion. The case distinction needed there goes best in the expr sub-language, so first of all here's func, a tiny wrapper that allows us to code in expr language only:

 proc func {name argl body} {proc $name $argl [list expr $body]}

A recursive function typically first tests for its terminating condition(s), and finally falls back into itself:

 func iota1 n {$n == 1? 1: [concat [iota1 [- $n 1]] $n]}

This may run slower than the original, but it's FP - a one-liner which needs no other variables than its arguments.

Now let's do fold the FP way, too:

 func fold {res op list} {
    ![llength $list]? $res : [fold [$op $res [first $list]] $op [rest $list]]
 }

where, obviously,

 proc rest list {lrange $list 1 end}

But in this case I agree that functional is less readable than imperative... :)


SS 8Apr2005: There is a good introduction to functional programming at [L1 ]