'''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 ** [http://www.ibm.com/developerworks/linux/library/l-highfunc/index.html%|%Higher order functions] ([https://web.archive.org/web/20070504085416/http://www-128.ibm.com/developerworks/library/l-highfunc.html?ca=dgr-lnxw07Functions%|%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. [http://www.joelonsoftware.com/items/2006/08/01.html%|%Can Your Programming Language Do This?], Joel Spolsky 2006-08-01: ** Tools ** [http://dev.crypt.co.za/incubator/doc/tcltm/control/functional.wiki%|%control::functional], by [twylite%|%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. [https://github.com/nektomk/tcl-f%|%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 ** '''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 [EIAS%|%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 programming%|%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, [Lisp%|%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 : ======none 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, [http://ep.yimg.com/ty/cdn/paulgraham/acl2.txt%|%ANSI Common Lisp], 1995) ** State ** 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 programming%|%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 Functions%|%First Class Citizens] ** 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 functions%|%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 ** Most functional languages are lexically-[scope%|%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 ** '''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 ** 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. ** [polymorphism%|%Polymorphic] Typing ** '''[polymorphism%|%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 ''[http://mitpress.mit.edu/books/definition-standard-ml%|%The Definition of Standard ML]'' for more details. ** Discussion ** [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 ======none : 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: ======none % 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... :) ** See Also ** [let2]: A let for Tcl: [Steps towards functional programming]: [Functional programming (Backus 1977)]: [Playing with recursion]: [Functional Composition]: [Functional imaging]: [BWise functional graphs], [TV]: [Multiplication tables]: [Tacit programming]: [Demand-driven computation]: http://openacs.org/api-doc/procs-file-view?version_id=2967965&path=packages/acs-tcl/tcl/ad-functional-procs.tcl%|%Functional programming procedures from OpenACS%|%: This library adds the expressive power of functional languages like LISP, Gofer or Haskell to the Tcl language https://agraef.github.io/pure-lang/%|%Pure%|%: functional programming language with full symbolic rewriting capabilities, dynamic typing, eager and lazy evaluation, lexical closures, built-in list and matrix support and an easy-to-use C interface. The interpreter uses LLVM as a backend to JIT-compile Pure programs to fast native code. It features a bi-directional binding to Tcl/Tk allowing Pure commands to be called from a Tcl interpreter and vice versa, routines to convert data to/from types compatible with each environment, and event-handling bridges to allow building of Tk GUIs. ** Page Authors ** [FW]: [wdb]: [pyk]: <> Concept | Functional Programming | Arts and crafts of Tcl-Tk programming