# Functional Programming

FunctionalProgramming is when functions, not objects or procedures, are used as the fundamental building blocks of a program. Functions in this sense, not to be confused with CeeLanguage functions which are just procedures, are analogous to mathematical equations: they declare a relationship between two or more entities.

FunctionalProgramming, however, is not about mathematics but about abstraction and reducing complexity: as such, it provides a powerful paradigm in which to tackle complex, real-world programming tasks.

FunctionalProgrammingLanguages, which support this style of programming, provide at least some of the following features:

These features enable or support the following aims:

• shorter programs (lower lines-to-effect ratio)
• program correctness
• expressive programs

... and thus overall improved productivity. FunctionalProgramming is also very enjoyable.

Although some of these features exist in ObjectOriented languages, or may be simulated via ObjectFunctionalPatterns, FunctionalProgramming really requires (and allows) a paradigm shift. ObjectFunctional languages try to combine the best of both worlds.

Books

This document http://www.ccs.neu.edu/home/dorai/t-y-scheme/t-y-scheme.html is a very good explanation of FunctionalProgramming. It gently takes you through the features, and may produce that required paradigm shift. -- PeterLynch

A classic example, to provide a feel for what FunctionalProgramming is like, is the QuickSort algorithm, using PatternMatching, ListComprehensions and recursion.

``` qsort []= []
qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_greq_x
where
elts_lt_x= [y | y <- xs, y < x]
elts_greq_x = [y | y <- xs, y >= x]

```
Or, taking advantage of the FilterFunction and of Sections (still in HaskellLanguage):

``` qsort []= []
qsort (x:xs) = (qsort (filter (<x) xs)) ++ [x] ++ (qsort (filter (>=x) xs))

```
Or with partition (still in HaskellLanguage):

``` qsort []= []
qsort (x:xs) = qsort lt ++ [x] ++ qsort gte
where (lt,gte) = partition (<x) xs

```
In ErlangLanguage:

``` qsort([]) -> [];
qsort([X|T]) ->
ElementsLessThanX = [Y || Y<-T, Y<X],
ElementsGreaterEqualToX = [Y || Y<-T, Y>=X],
[qsort(ElementsLessThanX),X,qsort(ElementsGreaterEqualToX)].

```
A stray thought: These implementations of QuickSort have in common that they use the first element as a pivot. This is a very bad choice of pivot, because it tends to make the execution time quadratic when the input is already sorted. This undesirable property is not a forced consequence of functional programming, but because functional languages tend to prefer list-like data structures, the simple implementations of QuickSort tend to have that drawback. For this reason, I think that MergeSort is often a better choice for functional languages. --AndrewKoenig

The also have in common that two of them use SyntacticSugar to perform the list filtering. For that reason, the second Haskell implementation is a better example here, since it shows off a more normal HigherOrderFunction than the first implementation, which is a little more of a trick. At least the way I see it.

AndrewKoenig's comment about MergeSort being a better fit for functional programming than QuickSort is borne out by experiment. In 2002, the GHC implementation of Haskell replaced the stable QuickSort implementation in its standard library with MergeSort:

``` sortBy cmp l = mergesort cmp l
sort l = mergesort compare l

mergesort :: (a -> a -> Ordering) -> [a] -> [a]
mergesort cmp = mergesort' cmp . map wrap

mergesort' :: (a -> a -> Ordering) -> [[a]] -> [a]
mergesort' cmp [] = []
mergesort' cmp [xs] = xs
mergesort' cmp xss = mergesort' cmp (merge_pairs cmp xss)

merge_pairs :: (a -> a -> Ordering) -> [[a]] -> [[a]]
merge_pairs cmp [] = []
merge_pairs cmp [xs] = [xs]
merge_pairs cmp (xs:ys:xss) = merge cmp xs ys : merge_pairs cmp xss

merge :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
merge cmp xs [] = xs
merge cmp [] ys = ys
merge cmp (x:xs) (y:ys)
= case x `cmp` y of
GT -> y : merge cmp (x:xs)   ys
_  -> x : merge cmp    xs (y:ys)

wrap :: a -> [a]
wrap x = [x]

```
The accompanying documentation confirms AndrewKoenig's suspicion about MergeSort being quicker, but also says that MergeSort uses far more memory.

An important part of (pure) FunctionalProgramming philosophy is ReferentialTransparency, which requires writing SideEffectFree? functions. In order to encourage this, variables are SingleAssignment, or immutable: once they are initialized, their value cannot be changed. Arguments to functions may only be passed by value, and rather than modify arguments, functions must return new variables.

This alone has several implications on the style of programming (compiler implementation and performance aspects are discussed later):

• Since functions cannot modify arguments, they need to be able to return more than one piece of information: therefore tuples and lists are widely used, and may be created on the fly in most FunctionalProgrammingLanguages.
• Since variables, even within functions, are immutable, writing loops using counters is impossible or at best unwieldy: the dominant style of algorithm is therefore recursive.
• Since functions cannot modify variables, they cannot store state between successive calls. Thus data and functions are kept completely separate, which is the opposite philosophy to ObjectOriented encapsulation.
• There may be a need for a data structure to represent the global state and top-level functions that operate on the global state. Most other functions only operate on a small part of the data, so the top-level functions extract pieces of the global state, pass them to lower-level functions, and construct a new global state using the results. (Incidentally, this makes it trivial to instantiate multiple copies of the entire application. For example, maintain a copy of the entire program state as it existed five minutes ago, and revert to it if there is an error.)
• The emphasis is on writing pure, generic functions which could work in any environment, and choosing actual program behaviour at the top of the call hierarchy. This is in contrast to ObjectOriented programming which encourages pushing behaviour into class methods and making decisions low down by overriding them in subclasses. (Document example moved to FunctionalModeling).

SingleAssignment, CallByValue and recursion comes with an implementation cost: lots of garbage generation, potentially huge stack, and lots of copying. In a naive implementation, all state changes generate garbage. Functional languages have optimizing compilers to get rid of the bloat with tricks such as turning copying code into modify-in-place behind the scenes, and TailCallOptimization. On the one hand, functional languages provide many more opportunities for optimization, since everything can be inlined and refactored safely by the compiler. On the other hand, functional programs require a good optimizer to get decent performance. Some languages have automatic LazyEvaluation.

Functional languages do not require good optimizers, that is a myth. For example, OCaml, one of the most performant functional languages around, uses a straightforward compiler that has a well-designed compilation scheme but does no fancy optimizations at all. What you need, though, is a well-engineered runtime system. In particular, you want to optimize your memory layout and garbage collector for small objects, high allocation rates, and short lifetimes. That is quite different from a typical OO runtime.

Supposedly the:

• fun was put in functional programming by STL of C++ fame (?)
• funk was put in functional programming by Haskell (?)

Discussion:

Functional programming is pure nonsense.. the print("hello world") is still a procedure in any language (it affects the state and modifies the screen too). It's actually just a big SyntaxGame and a form of different procedural programming. Eventually the program does something.

• Programming in general is intended to cause things to happen, the question is how the things to happen are specified. DeclarativeProgramming (for example FunctionalProgramming and LogicProgramming) allow the programmer to concentrate on what has to happen, and let the question of the steps required to make them happen be decided elsewhere. Just like GarbageCollection, we can automate various things to relieve us of the repetitive minutiae. That's why we have computers. If you're happier programming in AssemblyLanguage then please feel free to do so.
• Gotta love the people who bring up assembly language when that has nothing to do with the discussion, such as the print statement being a procedural call - not declarative.

Of course functional programs do something. They take in parameters and return a result.

It's not true that print() is a procedure in any language. In Haskell, print() returns an IO object. It does NOT affect the state or the screen. Of course, eventually this IO object has to be executed to affect the screen - but the point is that the print function itself does NOT have side effects, and IS referentially transparent.

Meh. `print "foo"` is essentially a procedure in a DomainSpecificLanguage called IO. The Haskell print function returns a representation of this procedure. To the extent program logic and behavior is expressed through the IO language, we're doing imperative programming. The fact that the Haskell function is pure is only relevant for reasoning about program construction. Reasoning doesn't stop at program construction, and `print` is definitely not referentially transparent within the IO language.

You could write a Java program that feels very much like a functional program by not using mutable static variables and making all objects immutable. (Local variables don't matter so much because they're well encapsulated.) -- BrianSlesinsky

Although I have not tried this in Java, I would imagine it to be rather difficult and frustrating without the corresponding facilities such as on the fly generation of tuples, list manipulations, and TailCallOptimization. Moreover, I don't think that would suffice to make it feel like a functional program. -- DominicWilliams

Java is sorely lacking HigherOrderFunctions. To effectively write functional programs you want recursion schemata like "map" and "fold" and these must be polymorphic. While Java can emulate these, wrapping every function in an object is cumbersome at best. You also lose the powerful type system of the ML-family languages.

Indeed. And then to use HigherOrderFunctions a lot, you need real LexicalClosures to be easy to write on the fly (not through something cumbersome like AnonymousInnerClasses). And even with all that (which you do get in RubyLanguage), it still would not feel much like FunctionalProgramming without PatternMatching... -- DominicWilliams.

You can write functional like programming in any language, and it gets hard to do in some languages. The question is whether massaging data into more and more functions is useful, especially since performance considerations are still prevalent today on web servers and such (despite what people think with today's processing power). Massaging more functions into more functions isn't any way we can clearly map it to a computer processor in our minds, and when it comes to mapping the code to the computer - we're at a loss. I many times wonder whether people just throw around phrases like HigherOrderFunction just to be be hip and cool, and just to make programming sound complex and hard. Doing silly stuff like in the below screenshot is hip, and cool, but I really question whether massaging stuff into other functions is the way humans think - and whether the benefits are worthwhile. Recursion, abusing functions instead of clearly written structured code like iterators and loops, sending other functions into other functions.. that is all academically interesting, But does it get us anywhere? Or really is it just hip, cool, complex, and wizardry? How often do we really need to massage functions into other functions, and reuse functions that pass each other functions? Is it all in people's mind, that this functional magic is so beneficial to society?

In above screenshot I push stuff around into other functions instead of rewriting the same loop each time (reusing chunks of code, similar to how functional programming reuses functions in functions in functions). But really, how useful is this? Is this just wizardry and is it over hyped that the idea of reusing functions inside functions inside functions some how magically improves a programmers life or company profits?

• Your "argument" seems to be that functional programming doesn't match the way you map processes to computers. If you only think in terms of fundamental computer operations, then you are limited in your thinking. If you can't think in higher level abstractions, then you are limited in your thinking. You appear to suffer from the BlubParadox. I suggest you read, and do all the exercises in, the SICP book. It's a mind-expanding experience. It's clear from other contributions on this wiki that you'll take no one's advice or experience.

• A false dichotomy between low-level thinking and FP. There are plenty of non-FP abstractions that are quite useful. If you measure a benefit and demonstrate the higher numeric score, I will pay attention. But I will ignore most non-scientific hype and bullshit because there's too much of it. The functional fans are sounding a lot like the OOP-everywhere fans of the last decade. BlubParadox is FP's version of the YouJustDontGetIt claims of the OOE-ers. Measure it or shove it, FPers! -t

How do data items persist?

On the stack. In a sequential, batch program, data is initialized and transformed in a top-level function. In a long-lived program like a server, a top level looping function is called recursively, passing global state from one call to the next.

Pure functional languages have REAL PROBLEMS referring to large stateful objects, because you lose ReferentialTransparency.

This is not true. You can hold state in a top level function, pass bits of it to pure functions, use their results to construct a new global state. There are no side effects here. In practice, a program without side-effects is not very useful, so it is common in functional programs to have mostly pure functions, glued together by some impure stuff. This does not take anything away from the usefulness of the functional paradigm.

Some issues with representing state: modifying an element of an array in a functional language is inefficient because you have to copy the whole array (though the compiler could optimize this out if you throw away the reference to the old copy). Tree structures might be more efficient since you only copy the nodes from the root to the element being modified. It seems like it would be rather hard to know whether code is efficient because many ways of optimizing code cannot be expressed - the compiler must do it for you.

Most FunctionalProgrammingLanguages use lists and tuples (from which arbitrary structures may be built), not arrays. Moreover, the functional paradigm aims to be at a more abstract level: such implementation details are left to optimizing compilers.

I think I am missing something rather basic. How is a data value ever changed (or even entered)? If someone mistypes a text string, how does correcting it in a clone class help?

Assuming you're familiar with java: How do you deal with a String object that's been mistyped? You create a new, corrected String, and throw away the old one. It's the same thing here.

Pure functional languages preclude any sort of side effect. Not only can no data be modified in place, it is also impossible to change bits on persistent storage or even read input from somewhere. Clearly, no interactive program can be written this way. Three solutions are in use:

• Represent input and output as lists of commands to some enclosing system. Many of these stream processors can be combined. Though this is somewhat cumbersome, it works. In the FudgetsLibrary? such a design has actually worked out pretty well.

• Extend the type system with data types that can be used only once (UniqueTypes). As the old value becomes inaccessible, the program doesn't mind if the compiler decides to do an in-place update. The world is represented by a special token and side-effecting functions conceptually produce a new world. CleanLanguage does this. It works, though the explicit passing around of the world can get annoying.

• Use monads to hide the state (see OnMonads). The hidden state can be queried, but old values are inaccessible. As with UniqueTypes it doesn't matter if an in-place update is done behind the scenes. HaskellLanguage does this. MonadicProgramming is actually quite convenient, not only for hiding side effects. If overdone, it starts looking like procedural code.

Concerning the need for mutable state: it is needed for truly interactive programs, in one form or another. Many programs are not that interactive, they can be neatly split into input, processing and output. Such programs work really well in a pure functional setting. In HaskellLanguage it is quite common to write a monadic main function that does input, calls processing, then does output.

Apart from that there are some algorithms that seem to incur an inefficiency if done purely functional. These are algorithms with state that is to be mutated in random order with constant access time, graph algorithms are typical. Without mutable arrays, the run time takes an additional logarithmic hit. HaskellLanguage provides mutable arrays, of course hidden in a monad, exactly for this reason.

The highlighted part is really insightful. (Similar idea to the UnixWay). Probably the majority of code being written is devoted to reading DataBase's and emitting ExtensibleMarkupLanguage, or vice versa, or one or the other, or something similar. If this is what you're doing anyway, pure FP loses you nothing and gains you a whole lot of bug-proofing.

I don't know much about garbage collection, but I've been interested to hear about a couple of the tricks/properties that are possible with functional languages, Erlang in particular. I'd like to share them with you guys, with the disclaimer that they're just some ideas I heard and like, and I don't know much about how things are implemented in practice. Do correct me on any mistakes I make.

Take a MarkAndSweep scheme as an example. The basic idea is that you have a "root set" of objects that are directly accessible because (depending on the language) they're in global variables, in a stack frame or local variable of an active thread, etc. When you want to garbage collect, you follow all the references out of your root set and "mark" each object that you reach. After you've done this, anything that's not marked can be reclaimed. In pseudocode:

``` for each element of root set:
spider out through code marking each reachable object
for each element of heap
if (marked) keep
else reclaim
```
This process spiders out until it finds every object that can be accessed and marks it, after which time you can walk through the heap from start to finish and throw away anything that's not marked.

Now in a language which doesn't support destructive operations, there's a special property: objects can only reference other objects that are older than themselves - because the newer ones didn't exist.

Note that this property depends on the language implementation not doing certain other optimizations, and usually does not hold for implementations of functional languages that support LazyEvaluation.

Now, suppose you have the objects in the heap sorted by age (very easy with a CopyingCollector? for example). The MarkAndSweep can be simplified into one pass, based on the fact that if an object hasn't been marked by any of the objects newer than itself, then it can't be marked at all due to the lack of forward reference. In pseudocode:

``` for each object on the heap, newest to oldest:
if (marked) mark all directly accessible objects, and keep
else reclaim
```
Much faster and simpler. Also, since the heap isn't changing, just being appended to, you can do the GC incrementally very easily.

Also, in Erlang you have a lot of separate processes, many of which are small and short-lived. Each of these processes has its own heap, and can be garbage collected separately. Now, for short-lived processes which do something quick like send an email and then terminate, it may not be necessary to do a fine-grained GC of the heap - just let it run and make some garbage, and when its finished just throw the whole heap away. So garbage collection can be "free" for these short-lived processes, and you may have many of them. -- LukeGorrie

Something else thats worth noting about languages without destructive updates, is that ReferenceCounting becomes a viable memory management scheme all on its own; cyclic garbage is impossible. Reference counted objects are collected as soon as they are unreachable, which is useful when timing is important. ReferenceCounting may be inefficient, but its probably the easiest form of automatic memory management one could implement.

except for LazyEvaluation. With StrictEvaluation, the above holds.

Would I be incorrect to say that FunctionalProgramming can be summarized by this -

``` "Result = Process(Data)"
Where "Result" is the variable representing the output of the function called "Process"
and "Data" is the list of arguments?

```
No, it's Result(Process(Data)) :)

If so, this appears to me to be the most intuitive interface to programming of all.

``` For example,
Choice = Get Selection("Please select one of these", "Dog,Cat,Fox")
Notify("The customer you have selected is a bad payer")

```
Given that we will one day (soon?) be talking to the machine, is it not a model we will have to embrace eventually anyway? -- PeterLynch

How does "talking to the machine" have any bearing on this? Besides the complexity that speech recognition adds, how is talking different from typing? If you mean to imply that functional is somehow more human than the alternatives, or that there is some subset of human requirements that can only be expressed in a functional way, then my reply would be simply: No, we will not have to embrace the model eventually. (And no, it is not the most intuitive interface of all, although there may be a subset of humanity for which it is more intuitive than, say, the simple imperative, e.g.:

``` Human:Gas Bill!
Human:Have I paid it?
Machine:Which one?
Human:The latest one, of course!
Machine:You mean April 2004?
Human:No, there should be one for July...
Machine:I don't know anything about that...
Human:OK, what's their number?
Machine:Their phone number?
Human:Yes.
Machine:Whose?
Human:The gas company's
Machine:Which one?
Human:The one who sends the bills
Machine:The gas company who sends the gas bills?
Human:Yes.
Machine:Which ones?
Human:The last one.
Machine:You mean April 2004?
Human:<sigh> I suppose so.
Machine:I don't know, is it on the bill?
Human:I suppose so, let's have a look...
Machine:Shall I display your April 2004 gas bill?