What are the core concepts in functional programming?

Question

In object-oriented programming, we might say the core concepts are:

1. encapsulation
2. inheritance,
3. polymorphism

What would that be in functional programming?

Solution 1

There's no community consensus on what are the essential concepts in functional programming. In Why Functional Programming Matters (PDF), John Hughes argues that they are higher-order functions and lazy evaluation. In Wearing the Hair Shirt: A Retrospective on Haskell, Simon Peyton Jones says the real essential is not laziness but purity. Richard Bird would agree. But there's a whole crowd of Scheme and ML programmers who are perfectly happy to write programs with side effects.

As someone who has practiced and taught functional programming for twenty years, I can give you a few ideas that are widely believed to be at the core of functional programming:

• Nested, first-class functions with proper lexical scoping are at the core. This means you can create an anonymous function at run time, whose free variables may be parameters or local variables of an enclosing function, and you get a value you can return, put into data structures, and so on. (This is the most important form of higher-order functions, but some higher-order functions (like qsort!) can be written in C, which is not a functional language.)

• Means of composing functions with other functions to solve problems. Nobody does this better than John Hughes.

• Many functional programmers believe purity (freedom from effects, including mutation, I/O, and exceptions) is at the core of functional programming. Many functional programmers do not.

• Polymorphism, whether it is enforced by the compiler or not, is a core value of functional programmers. Confusingly, C++ programmers call this concept "generic programming." When polymorphism is enforced by the compiler it is generally a variant of Hindley-Milner, but the more powerful System F is also a powerful basis for functional languages. And with languages like Scheme, Erlang, and Lua, you can do functional programming without a static type system.

• Finally, a large majority of functional programmers believe in the value of inductively defined data types, sometimes called "recursive types". In languages with static type systems these are generally known as "algebraic data types", but you will find inductively defined data types even in material written for beginning Scheme programmers. Inductively defined types usually ship with a language feature called pattern matching, which supports a very general form of case analysis. Often the compiler can tell you if you have forgotten a case. I wouldn't want to program without this language feature (a luxury once sampled becomes a necessity).

Solution 2

In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state. Functional programming has its roots in the lambda calculus, a formal system developed in the 1930s to investigate function definition, function application, and recursion. Many functional programming languages can be viewed as embellishments to the lambda calculus. - Wikipedia

In a nutshell,

1. Lambda Calculus
2. Higher Order Functions
3. Immutability
4. No side-effects

Solution 3

Not directly an answer to your question, but I'd like to point out that "object-oriented" and functional programming aren't necessarily at odds. The "core concepts" you cite have more general counterparts which apply just as well to functional programming.

Encapsulation, more generally, is modularisation. All purely functional languages that I know of support modular programming. You might say that those languages implement encapsulation better than the typical "OO" variety, since side-effects break encapsulation, and pure functions have no side-effects.

Inheritance, more generally, is logical implication, which is what a function represents. The canonical subclass -> superclass relation is a kind of implicit function. In functional languages, this is expressed with type classes or implicits (I consider implicits to be the more general of these two).

Polymorphism in the "OO" school is achieved by means of subtyping (inheritance). There is a more general kind of polymorphism known as parametric polymorphism (a.k.a. generics), which you will find to be supported by pure-functional programming languages. Additionally, some support "higher kinds", or higher-order generics (a.k.a. type constructor polymorphism).

What I'm trying to say is that your "core concepts of OO" aren't specific to OO in any way. I, for one, would argue that there aren't any core concepts of OO, in fact.

Solution 4

Let me repeat the answer I gave at one discussion in the Bangalore Functional Programming group:

A functional program consists only of functions. Functions compute values from their inputs. We can contrast this with imperative programming, where as the program executes, values of mutable locations change. In other words, in C or Java, a variable called X refers to a location whose value change. But in functional programming X is the name of a value (not a location). Any where that X is in scope, it has the same value (i.e, it is referentially transparent). In FP, functions are also values. They can be passed as arguments to other functions. This is known as higher-order functional programming. Higher-order functions let us model an amazing variety of patterns. For instance, look at the map function in Lisp. It represents a pattern where the programmer needs to do 'something' to every element of a list. That 'something' is encoded as a function and passed as an argument to map.

As we saw, the most notable feature of FP is it's side-effect freeness. If a function does something more than computing a value from it's input, then it is causing a side-effect. Such functions are not allowed in pure FP. It is easy to test side-effect free functions. There is no global state to set-up before running the test and there is no global state to check after running the test. Each function can be tested independently just by providing it's input and examining the return value. This makes it easy to write automated tests. Another advantage of side-effect freeness is that it gives you better control on parallelism.

Many FP languages treat recursion and iteration correctly. They does this by supporting something called tail-recursion. What tail-recursion is - if a function calls itself, and it is the last thing it does, it removes the current stack frame right away. In other words, if a function calls itself tail-recursively a 1000 times, it does not grow the stack a 1000 deep. This makes special looping constructs unnecessary in these languages.

Lambda Calculus is the most boiled down version of an FP language. Higher level FP languages like Haskell get compiled to Lambda Calculus. It has only three syntactic constructs but still it is expressive enough to represent any abstraction or algorithm.

My opinion is that FP should be viewed as a meta-paradigm. We can write programs in any style, including OOP, using the simple functional abstractions provided by the Lambda Calculus.

Thanks, -- Vijay

Original discussion link: http://groups.google.co.in/group/bangalore-fp/browse_thread/thread/4c2cfa7985d7eab3

Solution 5

Abstraction, the process of making a function by parameterizing over some part of an expression.

Application, the process of evaluating a function by replacing its parameters with specific values.

At some level, that's all there is to it.

View more solutions

Comments

[Sasha Chedygov]

Not really, there's a lot more to FP than just that.

[nullException]

+1 for correctness, -1 for using a 4 letter word like 'paradigm'. (now i have to wash my keyboard...)

[Nosredna]

paradigm is two consecutive 4-letter words.

[Ben Griswold]

@Javier - My next SO question, "What product(s) do you use to wash your keyboard?" :)

[Jay Atkinson]

Argh! ::rolls eyes at the SOAP pun::

[CaptainCasey]

He referenced where it's from and it's a good answer. However, I'd be giving this +1 for the dot points.

[Nathan Shively-Sanders]

Could you change Immutability to Recursion? Immutability and No side-effects are redundant so one of them should go.

[josesuero]

they're not redundant. this C code has no side effects, but it's not immutable: int i = 1; i = 2; and this has side effects, but does not mutate any state: printf("hello world");

[Ben Griswold]

@Norman Ramsey - I included the reference to Wikipedia for additional detail, but as @CaptainCasey noted, my answer is the list (now in bold.)

[Ben Griswold]

@Nathan Sanders - In (pure) FP, nothing happens outside of the function. Functions take inputs and provide outputs. Thus, there are no side-effects (change of state, writing to disk, etc). In FP, data is immutable. Once a value is assigned to an identifier, it never changes. Functions do not alter parameter values and the results that functions return are completely new values. Iteration (or looping) in functional languages is usually accomplished via recursion. Though Recursion is used in FP due to immutablility, they aren't the same thing. I understand where you are coming from though.

[ralphtheninja]

Not sure I agree with "No side-effects". There are many side effects in e.g. Lisp.

[Ben Griswold]

@Magnus Skog - Pure functional programming languages are side-effect free. There are languages, like Lisp and F#, which are multi-paradigm which may be primarily based on functional programming concepts but break some of the rules. An example of a pure functional language is Haskell.

[CodexArcanum]

Seconding this, OO and Functional can work together. Some functional language (CAML, or OCAML to be specific) pull in OO concepts and some OO languages (like D and even C#) use functional concepts. I would say that "Objects" are pretty core to the idea of OO programming though. ;)

[Apocalisp]

Then you just have the problem of defining what an "object" is exactly, and how it differs from things that aren't objects. Good luck.