Functional Programming
Functional ProgrammingFunctionalProgramming 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:
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.
In HaskellLanguage (see QuickSortInHaskell):
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) xsIn 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):
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.
See also the following Wiki pages:
Supposedly the:
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.
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?
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:
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 reclaimThis 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 reclaimMuch 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,
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? -- 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! 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:<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? Human:Please. Machine:No need to be polite, I'm only a machine! To you and...? Human:Just to me! Machine:Here you are... grumpyOk, maybe you're right after all!)
See also: ProgrammingParadigm, FunctionalFunctions, FunctionalInImperative
EditText of this page
(last edited December 24, 2014)
or FindPage with title or text search