4 ms·
I'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 m
by mafribe 10y ago
I'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 agoWell if one is looking for proofs, I think this is hard while remaining abstract from specific languages. I could counter that support for parametric polymorphism is poor in OO langs as much as you claim support for ad-hoc polymorphism is poor in FP langs. (but I don't place much stock in any of the aforementioned claims outside of some kind of artifical, academic context) Real-world problems that aren't an academic edge-cases will be supported by both FP and OO. Multimethods give you ad-hoc polymorphism in an uptyped setting.
- mafribe 10y agoParametric polymorphism is a concept that is orthogonal from the FP/OO distinction. You can define parametric polymorphism for parallel computation for example.
- tathougies 10y ago> In summary: OO is substantially more expressive than FP. In the same way assembly is substantially more expressive than C. Expressiveness in the way you've defined here is the least interesting aspect of a programming language. Since it's well established that OO and FP are equivalent in the sorts of things you can compute, you ideally want a paradigm that makes it easy and intuitive to code up computations versus one that is strictly 'expressive'. > This view is too simplistic, and doesn't scale up to include OO features such as method overriding. I'm pretty sure this is simply false. Modern Haskell with GADTs for example can easily encode any aspect of OO, including method overriding. Do you have a counter-example in mind?
- mafribe 10y agocounter-example in mind? I note that GADTs are types, so this might not scale to an untyped setting. Anyway, I'm not following research on GADTs closely, but you show me a sound and complete, compositional encoding of (idealised) object-calculi a la Abadi/Cardelli using (idealised) Haskell?