On Functional Programming:

While “Rees on OO” is impossible to reach, we can still try:

Functional programming is a set of different features. These features are taken, in an à la carte fashion by people in order to argue that their particular set is what constitutes FP. Thus there is no defining factor making a language functional, and thus no archetypal FP-language.

Mind you, every programming language can often be recast in a setting in which the ideas of the λ-calculus are present. This is seen in, for instance, SSA-form where a program is compiled to what is essentially a functional core, after which it is handled as a functional program. See Andrew Appel’s “SSA is functional programming”. In turn, any program going through the LLVM compiler, is factored through a functional program in the LLVM IR. Also, the internal graph-representation of the LLVM IR is a functional program, which somewhat hints at the massive concurrency boost possible in the setting: individual components of the graph can be executed in parallel in many situations.

The (incomplete) feature set of functional programming are:

(1) Functions as first-class values — If you can pass a function as a parameter, or return a function from a function.
(2) Pure functions — A function which only relies on its input to produce an output and has no side effects.
(3) Referential transparency — The idea any expression can be substituted for its computed value without altering the programs behavior.
(4) Controlled effects — The programming language has means by which one declares effectful computations and ways to shield parts of the program from certain bad effects.
(5) One, rather than two, syntactic classes — Everything is an expression. There are no statements in the language.
(6) No loops — Repetition is expressed solely via recursion.
(7) Immutable values — Once a value is bound, there is no way to mutate the value.
(8) Algebraic Datatypes — The language has algebraic datatypes, or some way to easily emulate them.
(9) Product types — The ability to form type pairs, in an ad-hoc fashion. Generalizes to records.
(10) No Null — There is no concept of a “null” value in the language. Instead, algebraic datatypes is used to create one ad-hoc when needed.
(11) A function always returns a value — There is no “void” construction or “procedure”. Rather the “unit”-value, often written as (), is used.
(12) A function takes exactly one value — The value might be a tuple and this is used to emulate multi-valued functions.
(13) Currying — The idea of “exponentials” being embedded in the language.
(14) Lexical scoping — The language is strictly built in the ideas of lexical scoping.
(15) Closures — The language has closures built-in.
(16) Pattern matching — The ability to destructure/deconstruct data based on its structure rather than projecting data out of a single value.
(17) Lack of subtyping — The language does not have a construct for subtyping, and thus have no common notion of “OO”. In it’s place, other type constructions are used, herein row-types.
(18) Safety — The language is safe in the notion a program cannot segfault.
(19) Type Safety — The language has type safety: the idea that well-typed programs can’t go wrong.
(20) No Globals — There is no concept of a global value in the language.
(21) α-conversion — The language has the property of alpha conversion.
(22) β-reduction — The β reduction rule plays a central part in the evaluation strategy of the language.
(23) η-conversion — The η-conversion rule holds.
(24) Substitution as a principle — Substitution holds as a central principle throughout the language.
(25) Lazy evaluation — Only compute on the subexpressions needed for the result. That is, if the program has an evaluation order which avoids an infinite loop, then find that evaluation order and execute it.
(26) Programmer defined infix and mixfix operators — The ability to extend the language with new fixity operators as the programmer needs them.

There are definitely more than these, but it is a start from the top of my head. Most programming languages have some of them. The programming languages which has many of them are usually considered “more functional”. In the view of Bob Harper, note a language such as Standard ML or OCaml works by integrating the above list into a language which also allows you to program imperatively. And Haskell or Clean works by separating the above list from a world in which you program imperatively.

Also note I avoided going too much into static/dynamic typing in the above. It is a completely different Pandora box for another time.