Functional Programming

Functional Programming, or FP, is a programming paradigm based on the concept of expressing the behaviour of a program as a mathematical functional model rather than as explicit sequences of instructions to a processor, which is the primary concept in imperative programming. Functional languages tend to be either completely side-effect-free or to carefully partition off those facilities for doing computations that may have side effects. They are very common among people developing advanced logic systems, and have some popularity in other fields as well. Functional languages include Lisp/Scheme, Haskell, OCaml, Joy, etc. Tcl isn't usually considered a functional language because it isn't designed to that specific end, but it is as amenable to functional programming as Lisp. If Haskell is a statically-typed functional language and Lisp is a dynamically-typed functional language, it might be fair to call Tcl a denotationally-typed functional language; each value denotes an object in a given context, and each command provides the context.

Reference edit

Higher order functions (alternate), Jonathan Bartlett, 2005-03-31: SS 2005-04-08: a good introduction to functional programming, including foldl, foldr, filter, map, curry, lambda, compose, etc.
Can Your Programming Language Do This?, Joel Spolsky 2006-08-01

Tools edit

control::functional, by Trevor Davel: Enhanced support for functional programming in Tcl, with implementations of some common higher-order functions
fptools: A grab bag of functions that can be useful for FP.
tcl-f: Provides loadable Tcl extension for programming in functional manner. This package introduces lazy evaluation, functional iterators and combinators, and other features of the functional world.
underscore.tcl: Inspired by Underscore.js - This package provides a collection of different utility methods, that try to bring functional programming aspects known from other programming languages like Ruby or JavaScript to Tcl.

Description edit

Functional programming derives its name from mathematical functions, which are mappings from a set of inputs to a set of outputs. A mathematical function does not actually perform any work, but instead describes a models of a process or phenomenon, and explains by means of a formula what the function produces for some set of inputs. Given the same inputs, a pure function always produces the same result. This is known as referential-transparency.

In order to be referentially-transparent, the value a function produces must not depend on the state of anything outside the function. The Tcl command clock seconds, for example, is not referentially-transparent because it produces different values even when the input values are identical. However, there is a loophole that is used to encapsulate state into a stateless functional model. For example, if one defines a value a as "the current time in seconds since the epoch", a function can then be formulated to always return a, which just happens to be the current time in seconds. Thus, the function always returns the same thing, a, making it stateless. However, at the time of application, a is bound to the current time, a thing in the stateful physical universe, which is a specific value at that moment. In some functional languages, this slight-of-hand goes by the name, monad.

A program written in functional programming language is a mathematical model that describes how such a program would behave, and it is up to the interpreter/compiler to read the description and simulate the described program. Programmers working in functional languages can say that their programs have no side effects, because they aren't actually programs at all, but descriptions which allow another program, the interpreter, to simulate the described program.

As a higher-level language, Tcl provides only everything is a string, and actively manages those values, generating and caching structured internal representations of those values when it is useful to do so. Likewise, functional programming languages provide a higher-level modeling environment, and actively manages the programs that it can generate or simulate from those models.

A purely-functional programming language would not actually do anything, which would not be very useful, so monads or their moral equivalent are also used to partition off imperative tasks from the functional model, allowing the results of those imperative task to be injected back into the stateless model in the same way that the current time was injected in the description above. Sometimes, as is the case in Haskell, a special syntax is provided for writing out the imperaive parts. As much of the program as possible is written as a mathematical functional model, and the remainder is stuffed into the equivalent of Haskell monads, although sometimes not as cleanly, depending on the design of the language.

Not all functional languages encapsulate imperative sections with the same level of rigour. Tcl freely admits both imperative and functional programs, Common Lisp and Scheme provide a syntax more explicitly for functional programming, and Haskell takes it a step further by incorporating a type system in which only functions of specific types may have side effects. The functional portions of the program remain blissfully free of the burden of tracking the state of the external world.

What does encapsulation of imperative tasks in a world of static functions look like ? A shell example is illustrative :

find | grep mydocument | xargs -n 1 sed 's/Acme (Corp)/Emca \1/g' > outfile

Seen as a program, this set of commands is stateless. There are no global variables that can be tampered with to produce some unexpected state. The "statements" in this program are themselves independent programs, and they are chained together by an operation known as a pipe. This pipe belongs to neither of the progams surrounding it, but is maintained by the larger system, such that each program is naturally isolated and concerns itself only with its own state. In functional programming, the analogues to these pipes are called monads. Monads internally keep track state of their own operations, and they are logically separate from the functional part of the program. Whatever internal state they maintain is entirely opaque to the elements on either side of it, except for whatever can be discerned by interacting with the interface to the monad. Monads are the components that allow the rest of the program to remain purely functional.

Because the only reason to include multiple lines in a function would be to modify state, in purely functional programming, functions are logically 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. (Paul Graham, ANSI Common Lisp

, 1995)

State edit

In EIAS, NEM 2010-12-15 states: One aspect of EIAS that is worth consideration is how it has kept Tcl "pure" in some sense. Part of EIAS that is little mentioned is that Tcl's strings are immutable. This means that Tcl's value space is purely functional, in the Haskell sense. All side-effects are confined to the shadow world of commands and variables and other second-class entities. What this means is that Tcl now possesses some very powerful purely functional data-structures that are somewhat better than those available in other languages. For instance, I cannot think of another popular language that supplies O(1) purely functional dictionaries and lists (arrays) out of the box (or even in the library). Not to mention efficient unicode and binary strings.

First Class Citizens edit

One hallmark of functional programming languages is that functions are passed to other functions as arguments. When a programming language supports this feature, it is said that in that language, functions are first-class citizens. When a functions can be passed as values to another function, other types of values can be considered to be functions, and indeed are often implemented as such.

Let edit

Most functional languages are lexically-scoped, and so provide a function called let, which indicates that a variable is bound to a definition in the scope of let function, rather than some enclosing scope. In Tcl, the scope of a command is strictly local, and there is no need for a let command, though commands like global, variable, upvar, and namespace upvar, do the inverse, linking local variables to variables in other scopes.

Lazy Evaluation edit

Lazy Evaluation means that the language only evaluates expressions when it needs to. What this means is that if you write a function that returns the first of its two arguments (discarding the second) and then call that function with the expressions "1+2" and "1/0" as first and second arguments respectively, you won't get an error but instead the value "3".". - RS: In Tcl we have this in if and expr:

expr {$i==0? $i+2: 1./$i}
if {$i==0} {expr {$i+2}} else {expr {1./$i}}

VK: 2006-11-19: bad example of laziness. I can't imagine how these lines will ever divide by 0. Only if a language will precalculate all its possible branches... but this is not realistic. These lines, even writen in C (very non-lazy language) will not divide by 0.

NEM: Yes, but only because 'if' and the conditional operator in C are also lazy (well, non-strict). Pretty much all languages have some mix of strict and non-strict operations. The difference with Haskell is that it is lazy by default, which allows the definition of if to be rather neat:

if True  t e = t
if False t e = e

NEM: Haskell's laziness allows you to deal with infinite lists as well:

take 10 [1..]
--> [1,2,3,4,5,6,7,8,9,10]

The values are computed as they are needed.

Mutation of Data edit

As the programmatic implementation of math itself, functional programming views data as idealized values. The messy physical details of computational operations such as slicing and subsetting specific datasets is left to the implementation, and is not exposed at the language level. In this area, Tcl once again shows off its flexibility. With its EIAS paradigm and wonderfully-engineered copy-on-write semantics, it provides a great platform upon which to do functional programming, while not restricting the ability to program in other paradigms when desired. Commands such as lreplace, which return a new value, hint at the capabilities of Tcl in this regard.

Polymorphic Typing edit

Polymorphic typing is a scheme for defining the types of things like lists, trees and other constructed types that allows for a very high degree of type safety even with extremely complex use. The full theory is a bit long to go into here, but it is based on type variables. Anyone interested should read things like The Definition of Standard ML for more details.

Discussion edit

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]

FW: 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.

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.

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 functional programming offers powerful abstractions that allow for simpler code - and who types less, can't make so many bugs... :)

Another example: Someone asked in the Tcl Chatroom 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 functional programming 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}"}

or, in Tcl 8.5 or later:

namepsace import ::tcl::mathop::*

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... :)

Page Authors edit

FW
wdb
pyk

Category Concept

Category Functional Programming

Arts and crafts of Tcl-Tk programming