4 ms·
This is unfortunately not true, though I think the factually incorrect parts (as opposed to those I simply disagree with) are due to misuse of terminology more
by benaiah 10y ago
This is unfortunately not true, though I think the factually incorrect parts (as opposed to those I simply disagree with) are due to misuse of terminology more than anything.
First, the factually incorrect:
> For a long time, lambda-calculus has been seen by a lot of programming language researchers as the foundation of programming to which every other paradigm has to be reduced.
... not really. The lambda calculus is a way to represent computation, which is Turing equivalent; it can encode any computation which a Turing machine can. You can reduce any program to either a Turing machine or the lambda calculus, as they are both capable of representing any computation. The lambda calculus is not inherently functional, or OO, it's much lower level. To be fair, lambda calculus did lead directly to Lisp, which has long been associated with functional programming (though it is also not inherently functional - see Emacs Lisp or Common Lisp).
> Eventually, it became clear that lambda-calculus isn't the basis of all other programming paradigms.
Again, no. The lambda calculus is as much a basis of all other programming paradigms as the turing machine is.
> encoding lambda-calculus into object-orientation
After the above explanation, hopefully it's clear that this statement doesn't really make sense. Again, I'm guessing that this is mostly due to incorrect use of the term "lambda calculus" - you likely meant to use another term.
On to the stuff I just disagree with:
> FP is a special case of OO
Highly disagree. FP and OO are simply two different methods of organizing and connecting code and data - in OO, you have objects that encapsulate state and expose functions to the outside world that modify and retrieve that state. In FP, you write programs as series of functions that transform data. The fundamental difference is that in OO you are treating data and its related functions as a fundamental unit together and structure your program around connecting objects together, and in FP your program is essentially a data pipeline. The other distinctions between OO and FP (immutable vs mutable state, generic collection interfaces vs specialized interfaces for different kinds of data) stem from that fundamental dichotomy.
Scala may combine the two, and may do so elegantly (I really don't know, I've never used it), but even if its particular kind of FP is encoded in an OO system, that doesn't imply that FP at large is a special case of OO. In fact, I'd argue the opposite: a method on an object is simply a function with an implied argument (the object) in a scope where that argument is inacessible from outside. You can see this clearly in pre-ES6 JS, where that's literally how an object is constructed (in the Crockford style - the prototype style is a bit different).
- mafribe 10y agoI'm afraid this is wrong. Yes, all programming languages are equivalent in the sense of the Church-Turing thesis. From the point of view of PL research that means equivalency with TMs is an uninteresting criterion for comparing PLs. Consequently, PL researchers have developed finer tools for comparing languages, typically centring around compositionality. An encoding enc from language L1 to language L2 is compositional whenever P = f(P1, ..., Pn) is a program, then enc(P) is of the form enc(f)(enc(P1), ..., enc(Pn)). This idea, that I present here in a very simplified form, has been studied quite deeply, and in this sense it has been difficult to reduce OO to FP, unlike the other way around. And yes, lambda-calculus is the essence of FP. Indeed there is no PL paradigm that is so closely connected with a single formalism as FP. a method on an object is simply ... This view is too simplistic, and doesn't scale up to include OO features such as method overriding. In summary: OO is substantially more expressive than FP.
- platz 10y agoNot really. The goals of OO features such as method overriding is accomplished by typeclasses or implicits in FP. It's just that the default polymorphic mechanism for FP is parametric polymorphism, and the default mechanism for OO is ad-hoc polymorphism. OO didn't have parametric polymorphism initially, and added it with Generics. FP didn't have ad-hoc polymophism initially, and added it later with typeclasses or implicits. Choosing OO or FP really just puts you one of the two side of the https://en.wikipedia.org/wiki/Expression_problem https://en.wikipedia.org/wiki/Expression_problem . They are more complimentary than proper subsets of each other.
- mafribe 10y agoI agree that implicits and type-classes can provide ad-hoc polymorphism, but I'm not aware that they have been reduced completely to FP without them, I'm also not aware of implicits and type-classes working in an untyped setting. If you have references to the contrary, I'd be interested to hear about it.
- platz 10y ago