Lambda calculus serves as a foundation for all sorts of functional languages and its various extensions are compiler targets for languages like Haskell, ML, etc. So what is the equivalent for object oriented languages? Is there a minimal object calculus that serves as the foundation for object oriented languages?

  • $\begingroup$ Perhaps you should start by identifying a calculus that models imperative computations, I'm not familiar with one. If you just mean a type system algebra that meshes with the object concept, I would encourage you to define the characteristics of the OO type system you want to know of an algebra that resembles. Many people find different parts of OO type systems intrinsic to the universal concept of "OO", so identifying your concept of it would help. $\endgroup$ – Jimmy Hoffa Dec 8 '14 at 16:58
  • $\begingroup$ The original lambda calculus is untyped so I'm not talking about types. $\endgroup$ – davidk01 Dec 8 '14 at 17:04
  • 1
    $\begingroup$ You might also be interested in the question “Modeling objects as functions”. In my answer to that question, I showed how to implement a simple object using only functional parts of JavaScript (== lambda calculus), including things such as inheritance and private fields. After all, objects are just closures. (However, that example does not feature “open recursion” which is e.g. needed for the Strategy Pattern) $\endgroup$ – amon Dec 8 '14 at 17:15
  • $\begingroup$ You're not talking about types, but the type system is the defining characteristic of "OO", without the type system you're talking about procedural programming... so which is it? Procedural/imperative programming, or the OO type system? If it's just procedural/imperative then you just want a calculi that models imperative computation to which monadic composition is the best model I'm familiar with, though there are surely others. $\endgroup$ – Jimmy Hoffa Dec 8 '14 at 18:24
  • 1
    $\begingroup$ See: cs.stackexchange.com/questions/18963/… $\endgroup$ – Dave Clarke Dec 9 '14 at 18:37

So what is the equivalent for object oriented languages?

Lambda calculus.

I mean, there is Cardelli's object calculus (and a handful of derivatives), but in general, there's nothing fancy about object oriented languages that requires a new approach to computation.

It's well known (see TaPL for example) how to extend/encode Records and Mutation (and sub-typing/dispatch) onto/in lambda calculus. The underlying structures don't need to change, even though there are often layers above it that add semantic restriction and make things more usable (member access, implied this, object layouts, etc).

  • 2
    $\begingroup$ You're effectively making a turing tar pit argument here I think, because lambda calculus can model this it is the model - I don't really agree. Yes it can, but as you mention Cardelli's object calculus is a better derivation to fit. There are others as well, but the more I think about it, the only difference between OO and procedural programming is the type system, so a type algebra may be a better formalism. Given your argument The Actor Model is a better answer because it more easily models an OO system than direct lambda calculus. $\endgroup$ – Jimmy Hoffa Dec 8 '14 at 18:25
  • 1
    $\begingroup$ I guess the question sounds more to me like "what is the closest formal system to OO programming?" given that there is none that OO is founded on. Lambda calculus is not the closest formal system to OO, certainly. $\endgroup$ – Jimmy Hoffa Dec 8 '14 at 18:26
  • 3
    $\begingroup$ @JimmyHoffa - I read the question as "All these people use lambda calculus as their formalism when designing/implementing functional programming languages. What do people use for OO languages?". In my experience, people still use lambda calculus for OO languages (if they use anything). $\endgroup$ – Telastyn Dec 8 '14 at 18:36
  • $\begingroup$ I don't think they do use anything... The design of OO languages has been influenced, near as I can tell, none at all by formalisms but the opposite is not true, there are formalisms derived to model OO language concepts, and those are worth mentioning. $\endgroup$ – Jimmy Hoffa Dec 8 '14 at 18:45

While not really an answer to your specific question, I will suggest that those OO langs that do have lambdas (or specifically do not) usually do so for practical reasons. The recent inclusion of lambdas/closures in Java 8 is a case-in-point.

This generated a lot of discussion, even well before Java 8. There is a dense website dedicated to this specific implementation that has a lot of technical and theoretical discussion that might be of interest?

Specifically, check out Bloch's "Controversy" slides.

  • 1
    $\begingroup$ this is not what he is referring to with the term "lambda" $\endgroup$ – Jimmy Hoffa Dec 8 '14 at 18:21
  • $\begingroup$ Well, not exactly, but the links I provided speak directly to "objects as functions" in Java, and the challenges and controversy surrounding a portion of the language satisfying the lambda calculus. Some of those links discuss the formal application of the calculus in an OO environment. $\endgroup$ – jdv Dec 8 '14 at 19:05
  • 1
    $\begingroup$ That's fine but my question was more about a minimal formal essence of an object system the same way lambda calculus is the minimal essence of functional languages. $\endgroup$ – davidk01 Dec 8 '14 at 19:07
  • $\begingroup$ Fair enough. I thought that a practical example of how some of that theory was applied to a shipping OO language might apply here. Java is bad example, of course, because it is intended to be so practical. I suppose more to the point is how something like Ruby could be formalized... $\endgroup$ – jdv Dec 8 '14 at 19:12
  • $\begingroup$ Right. Some formal object semantics for ruby would be interesting. $\endgroup$ – davidk01 Dec 8 '14 at 20:16

Not the answer you're looking for? Browse other questions tagged or ask your own question.