(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 
   * [Steps towards functional programming]
   * [Functional programming (Backus 1977)]
   * [Playing with recursion]
   * [Functional imaging]
   * [TV]: [BWise functional graphs]
   * [Multiplication tables]
   * [Tacit programming]
   * [Demand-driven computation]

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 [http://www-128.ibm.com/developerworks/library/l-highfunc.html?ca=dgr-lnxw07Functions]

-----
See http://dev.crypt.co.za/incubator/doc/tcltm/control/functional.wiki%|%control::functional%|%: Enhanced support for functional programming in Tcl, with implementations of some common higher-order functions. Includes foldl, foldr, filter, map, curry, lambda, compose, etc.

<<categories>> Concept | Functional Programming | Arts and crafts of Tcl-Tk programming