I'm confused that you seem to think that "FP" means immutability. I think that most lisps and schemes, for example, have had mutable state. ML does. I think APL does? I think Erlang does, even though it says it doesn't? It's just a few Johnny-come-lately languages that do this immutability-is-the-default thing. Heck, even Clojure doesn't commit to it. Although I agree that lots of them discourage the use of mutability (including ML, APL, and Erlang).

To my way of thinking, OO means "big bundles of state, with really aggressive encapsulation". And FP means first-class functions, and more pipelining/chaining with less encapsulation. Smart data, vs functions-plus-dumb-data.

And so I think that OO isn't technically incompatible with immutability, but it fits better with FP. And OO isn't technically incompatible with purity, but it fits a LOT better with FP.

Functional Programming as I've always heard the term defined is the style of programming that avoids mutable state in favor of computation over immutable data structures. From Wikipedia:

> In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids changing-state and mutable data. https://en.wikipedia.org/wiki/Functional_programming

See also "total functional programming", which takes the concept a step further, and only permits programs that provably terminate (limiting the kind of state that can be manipulated even locally within functions).

My two pence: FP contrasts with the procedural style of programming, which focuses on mutating state, working with functions that have side-effects.

For example, in a procedural program it would be perfectly normal to call an operation on a file object, passing it a buffer object as input, while expecting it to fill the buffer with the file contents, and while returning no value and throwing an exception on error. In functional program this would be discouraged, in favor of something like an operation on the file that reads the file contents, returning a buffer as output.

I would consider both of these styles properly orthogonal to object oriented style, which is a style which permits there to be many different instances of a particular interface with different behavior. OOP focuses on identifying abstractions and implementing code in terms of abstractions. For example, both the file object and the buffer might provide the abstraction of being sequences of bytes. OOP allows a form of generic programming where I can write an algorithm that operates on all instances of the sequence-of-bytes interface without concern to which particular implementation the code is interacting with at the time. Code can be written in both an OOP and FP style if object methods avoid modifying object state.

In practice, however, a lot of object oriented code choose to assign objects local state that is manipulated via side effects from method calls. For example, a method on a string that modifies the string by appending to it is a method that follows procedural style. By comparison, a method that concatenates the original string with the input string and returns a new string is a method following FP style. Both approaches have tradeoffs. Object orientation means that there can be multiple different concrete string implementations complying with the string interface, that can be passed interchangeably to code written against the interface. The Unix file descriptor pattern is a form of object orientation, since file descriptors may refer to several different resource types supporting similar methods via syscall. Object systems tend to allow the creation of new implementations later without mandatory coordination with existing code using that object interface.

I've seen the WP page. If that's what FP is, then I think that means that either

  * think Lisps and Schemes aren't true FP, or
  * think that Lisps and Schemes avoid mutable state

Which one of those is your belief? I'm not a serious user of any allegedly-FP language, so maybe I misunderstand the history of FP. Note that I concede that Lisp seems to be less obsessed with mutating state than most procedural languages, but I think saying that it "avoids" it is an overreach.

Of course, some people could claim that "old" FP languages like Lisp and Scheme aren't truly FP.

As for your definition of OO, I think the word that describes abstraction across various instance-types is "polymorphism". That's when code can be written that handles multiple types, either because the typing system allows it, or because the typing system is so flexible that it fails to forbid it. Functional code is usually highly polymorphic, whether it's an aggressively static type system (Haskell with type classes) or an aggressively late-binding dynamic type system (typical Lisp, before anyone bothered to invent the phrase "duck typing").

Again, the central concept of OO, at least according to Alan Kay (the inventor/definer of the term), who said in 2003 (later than other definitions of his I could find) "OOP to me means only messaging, local retention and protection and hiding of state-process, and extreme late-binding of all things." I think it's pretty clear that statefulness is pretty essential to that definition.

http://userpage.fu-berlin.de/~ram/pub/pub_jf47ht81Ht/doc_kay...

Popular is not always (or even often???) the best way to go ;-) Being on the fringe usually means you've thought about it more than most people.

I'm an OO guy who has been moving more and more in the FP direction. I look at it a bit differently that you, but basically have the same conclusion (I think).

Rather than saying OO and FP are orthogonal, I tend to feel that OO and FP are essentially the same, but that popular OOP misses the point completely.

If I have a struct and a set of functions, where the first argument of the function is always the struct, how is that different than having an object with a set of methods? It might (or might not) be implemented under the hood differently, but whether I write the object on the left, or as the first parameter, it's all the same.

With respect to mutability, most FP languages don't allow mutable data structures. I can likewise restrict myself to immutable data structures in OO languages. Most people don't. Unless you have a specific performance issue in mind, I think this is usually a mistake. I think the fact that mutable data structures are popular, is not equivalent to saying the OO encourages mutable data structures. It's equivalently bad in both camps (which I suppose is the meaning of "orthogonal" ;-) ). Immutability has memory management considerations which I will discuss in a minute.

WRT polymorphism, with OO languages, ad-hoc polymorphism (operator overloading) is essential, while parametric polymorphism (generics) is optional. With FP, it tends to be exactly the opposite. But if you consider that both ad-hoc polymorphism and parametric polymorphism are useful tools in both approaches, I think it's kind of a moot point.

The rest of it boils down to coupling and cohesion. In OO, you have encapsulation which forces you to reduce your coupling in certain ways. You tend to have cohesive code in that all functions dealing with a particular data structure are grouped with that data structure. In FP, you have cohesive code in that all your functions doing a particular operation are grouped together. Coupling is not strictly enforced, but writers of good FP code enforce it themselves. But it's not like you can't do both styles in both systems. It's just that the language implementations make one style easier than the other.

The only place that I see which is very different is in garbage collection. If you are using immutable data structures, it is hard to know when to deallocate the memory. So you need some kind of garbage collection (even if it is just reference counting). Having it built in to the language makes it very convenient, but it is hardly a show stopper if you have to write your own (or use a library).

With C++ there is an idiom (which I still think is a good one) where you try to only allocate memory on the stack. Everything is a local variable and you send those local variables to functions that fill in the data for you. That way you can explicitly understand the lifetime of every data structure in the system. I've done a lot of embedded code where I needed to keep track of every byte of code and to know exactly where it is allocated and deallocated. Techniques like this help, but it is obviously not immutable. I don't know how to do this kind of thing with traditional FP languages.

But really, it's only the very last thing that strikes me as being particularly different. The rest is syntax and how much typing I need to do. It's more that the language designers have idioms that they prefer and make those idioms easier. FP and OO seem to share the same pool of idioms, though.