[lmkg]

The term "functional programming" is overloaded, but I think there's a sensible way to split the term into two halves.

"Purely functional programming" is writing programs to resemble mathematical functions, with referential transparency and absence of side-effects and so forth. Also know as "what Haskell does."

"Function-oriented programming" is writing programs using functions as your main tool for abstraction, encapsulation, defining interfaces, unit of code division, etc. This part of functional programming is more typified by the Lisp family.

Most languages that are considered functional generally encourage both of these aspects, partly because they work well together. The confusion over definition comes from these two halves getting tangled, and some languages or programmers emphasizing one half over the other.

Non-functional languages that are becoming "more functional" are generally importing features from the "function-oriented" side of things, and adopting the "purely functional" aspect as a best practice convention, if at all. It's probably more accurate to say that they enable a functional style of programming, rather than that the are functional.

[js8]

Actually, both of those families come from lambda calculus, except in different way. Lisp comes from untyped lambda calculus (and adds things like car, cdr and eq on top of it), while Haskell (and ML) comes primarily from typed lambda calculus.

I offer a definition of "functional programming" as "based on semantics of lambda calculus".

[kazinator]

Lisp does not come from lambda calculus. Anonymous functions in Lisp get their LAMBDA name from lambda calculus, that's all. MacCarthy admitted that he didn't even understand lambda calculus properly, which is why early Lisp was dynamically scoped: lambdas didn't capture lexical variables. Whereas lambda calculus is lexical. Lexical scoping was adopted in later Lisp dialects and into Common Lisp, making those dialects retroactively related to lambda calculus. (Emacs Lisp shows the traditional behavior of dynamic scoping; therefore it couldn't be said to be related to lambda calculus.)

Lambda calculus is a formalization of number theory which builds up numbers from functions. An important result is that lambda calculus is Turing complete. It shows that we can boostrap numbers and number theory from almost out of nothing, using Church numerals.

Lisp has never built numbers out of Church numerals; it had ordinary integers.

Also, lambda calculus, typed or not, does not have its own syntax as a data type. It doesn't have symbols. You don't quote a symbol and pass it to a function and so on.

So that's basically it; there is a link between Lisp and lambda calculus due to the use of the word lambda in a related way, and a somewhat stronger link between lexically scoped Lisps (which came later) and lambda calculus.

[js8]

I guess you're right, it doesn't come so much from lambda calculus as I claimed, it was more inspired by it. Although to be fair, in the time the Lisp appeared, it was the closest thing (by a wide margin) to lambda calculus. I think it was a valiant effort to bridge the gap in that direction (and the design choices were influenced by the trade off that he also wanted a practical programming language).

Also, even languages like Haskell are not based only on theoretical lambda calculus, but they also have primitives for data types, which could be, in theory, represented by lambda expressions.

[catnaroek]

Here are some features that the lambda calculus doesn't have: n-ary functions for n other than 1, macros (or any other means to analyze its own syntax), dynamically scoped variables, physical object identities, etc. In the untyped lambda calculus, any two alpha-equivalent terms are internally indistinguishable - in fact, you can even make them externally indistinguishable using a nameless representation of syntax like “de Bruijn indices”.

So much for “Lisp comes from [the] untyped lambda calculus”.

[bad_user]

Your "function-oriented programming" has an older and more suitable term: https://en.wikipedia.org/wiki/Procedural_programming

You see, if a function isn't pure, then it isn't a (mathematical) function. But we tend to overload terms because of their marketability.

In the same way that some companies wanted to overload "open source". The general rule of thumb is that if something is desirable by the market, then it is going to get overloaded either by people not knowing what they are talking about or by sales people.

[ansgri]

Procedural programming usually does not include the use of higher-order functions, and "function-oriented" here seems proper for Lisp and some styles of Python, with their heavy use of filter/map/apply/parallel-map-reduce etc.

[bad_user]

In mathematics a function is a mapping having the property that each input is related to exactly one output. This brings with it certain properties you can rely on. In particular functions themselves are also values that can be passed around as parameters or returned by other functions, hence higher order functions.

It's regrettable that we overloaded the word "function", given we could have used procedures or subroutines to denote, you know, jumps in code that trigger effects and push/pop the call stack.

And as proof, applying filter/map and other similar operations with side-effecting procedures is a really, really bad idea, because such operators are usually implemented with lazy behavior (in order for "fusion" to happen) and laziness doesn't blend well with side effects, with the result becoming non-deterministic. E.g. at least people that worked with Map-Reduce frameworks should know what I'm talking about.

Or in other words, there is no such thing as "function-oriented", there's just local application of FP where it seems to be making sense, but with all the caveats that entails.