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 Cee Language functions which are just procedures, are analogous to mathematical equations: they declare a relationship between two or more entities.
Functional Programming, 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.
Functional Programming Languages, which support this style of programming, provide at least some of the following features:
First Class functions
Monadic effects [On Monads]
These features enable or support the following aims:
shorter programs (lower lines-to-effect ratio)
program correctness
expressive programs
... and thus overall improved productivity. Functional Programming is also very enjoyable.
Although some of these features exist in Object Oriented languages, or may be simulated via Object Functional Patterns, Functional Programming really requires (and allows) a paradigm shift. Object Functional languages try to combine the best of both worlds.
Books
Khan, Aslam. Grokking Functional Programming. Manning Publications (2015). p. 475. ISBN 9781617291838
This document www.ccs.neu.edu 
is a very good explanation of Functional Programming. It gently takes you through the features, and may produce that required paradigm shift. -- Peter Lynch
A classic example, to provide a feel for what Functional Programming is like, is the Quick Sort algorithm, using Pattern Matching, List Comprehensions and recursion.
In Haskell Language (see Quick Sort In Haskell):
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 Filter Function and of Sections (still in Haskell Language):
qsort [] = [] qsort (x:xs) = (qsort (filter (<x) xs)) ++ [x] ++ (qsort (filter (>=x) xs))
Or with partition (still in Haskell Language):
qsort [] = [] qsort (x:xs) = qsort lt ++ [x] ++ qsort gte where (lt,gte) = partition (<x) xs
In Erlang Language:
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 Quick Sort 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 Quick Sort tend to have that drawback. For this reason, I think that Merge Sort is often a better choice for functional languages. --Andrew Koenig
The also have in common that two of them use Syntactic Sugar to perform the list filtering. For that reason, the second Haskell implementation is a better example here, since it shows off a more normal Higher Order Function than the first implementation, which is a little more of a trick. At least the way I see it.
Andrew Koenig's comment about Merge Sort being a better fit for functional programming than Quick Sort is borne out by experiment. In 2002, the GHC implementation of Haskell replaced the stable Quick Sort implementation in its standard library with Merge Sort:
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 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 Andrew Koenig's suspicion about Merge Sort being quicker, but also says that Merge Sort uses far more memory.
An important part of (pure) Functional Programming philosophy is Referential Transparency, which requires writing Side Effect Free functions. In order to encourage this, variables are Single Assignment, 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 Functional Programming Languages.
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 Object Oriented 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 Object Oriented programming which encourages pushing behaviour into class methods and making decisions low down by overriding them in subclasses. (Document example moved to Functional Modeling).
Single Assignment, Call By Value 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 Tail Call Optimization. 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 Lazy Evaluation.
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.
See also the following Wiki pages:
Some external links:
John Hughes classic paper Why Functional Programming Matters
FAQ for comp.lang.functional: www.cs.nott.ac.uk
List of real-world applications using Functional Programming: homepages.inf.ed.ac.uk
Discussion of the relationship between Functional Programming and Flow Based Programming in www.jpaulmorrison.com - FP people can skip the early section!.
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 Syntax Game 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. Declarative Programming (for example Functional Programming and Logic Programming) 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 Garbage Collection, we can automate various things to relieve us of the repetitive minutiae. That's why we have computers. If you're happier programming in Assembly Language 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 Domain Specific Language 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.) -- Brian Slesinsky
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 Tail Call Optimization. Moreover, I don't think that would suffice to make it feel like a functional program. -- Dominic Williams
Java is sorely lacking Higher Order Functions. 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 Higher Order Functions a lot, you need real Lexical Closures to be easy to write on the fly (not through something cumbersome like Anonymous Inner Classes). And even with all that (which you do get in Ruby Language), it still would not feel much like Functional Programming without Pattern Matching... -- Dominic Williams.
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 Higher Order Function 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?
z505.com
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 Blub Paradox. 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. Blub Paradox is FP's version of the You Just Dont Get It claims of the OOE-ers. Measure it or shove it, FPers! -t
See also Functional Programming Discussion
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 Referential Transparency.
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 Functional Programming Languages 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 Fudgets Library such a design has actually worked out pretty well.
Extend the type system with data types that can be used only once (Unique Types). 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. Clean Language does this. It works, though the explicit passing around of the world can get annoying.
Use monads to hide the state (see On Monads). The hidden state can be queried, but old values are inaccessible. As with Unique Types it doesn't matter if an in-place update is done behind the scenes. Haskell Language does this. Monadic Programming 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 Haskell Language 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. Haskell Language provides mutable arrays, of course hidden in a monad, exactly for this reason.
The highlighted part is really insightful. (Similar idea to the Unix Way). Probably the majority of code being written is devoted to reading Data Base's and emitting Extensible Markup Language, 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 Mark And Sweep 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 Lazy Evaluation.
Now, suppose you have the objects in the heap sorted by age (very easy with a Copying Collector for example). The Mark And Sweep 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. -- Luke Gorrie
Something else thats worth noting about languages without destructive updates, is that Reference Counting 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. Reference Counting may be inefficient, but its probably the easiest form of automatic memory management one could implement.
except for Lazy Evaluation. With Strict Evaluation, the above holds.
Would I be incorrect to say that Functional Programming 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, Reply = Get Reply("Where do you want to go today?") Customer Address = Get Data("Customers", "Address", Customer Id) 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? -- Peter Lynch
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!
Machine:
What about it?
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:
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?
Human:
Please.
Machine:
No need to be polite, I'm only a machine! To you and...?
Human:
Just to me!
Machine:
Here you are... grumpy
Ok, maybe you're right after all!)
See original on c2.com