25
$\begingroup$

Object oriented programming (OOP) is a programming model where code and data are encapsulated into units called objects that behave semi-autonomously. Interaction between objects is arranged through subroutines called methods that are object specific. Modularity of objects makes for an easy transferability between different applications. Objects are arranged into hierarchies of classes with objects at lower levels inheriting methods from the upper level classes but also adding more specialized ones of their own. So classes can be used as object constructors.

It is hard not to notice the structural analogy between OOP and the mathematical category theory with objects related by specialized morphisms and arranged into categories with transferability corresponding to categorical “up to isomorphism”. The analogy is well known and goes deeper, e.g. there are OOP analogs of some functorial constructions (inheritance, polymorphism, etc.). In fact OOP is somewhat of a constructivist implementation of the category theory. Were such parallel structures really developed independently from completely different motivations?

The category theory was created by Eilenberg and Mac Lane in mid 1940-s while formalizing homological algebra, and it seems that most of the motivation came from algebraic topology, and in 1950-s also from algebraic geometry, when Grothendieck and Bourbaki got involved. Not from the theories of algorithms and formal languages, also actively studied at the time. Similarly, OOP was originally developed by MIT AI group (McCarthy, Minsky, Sutherland , etc.) in late 1950-s, and much of the overall structure and terminology is due to Dahl and Nygaard from Norwegian Computing Center in early 1960-s.

Were such parallel structures really developed independently from completely different motivations? Mac Lane held a position at Harvard from 1938 to 1947, so perhaps he left a mark in Cambridge, where MIT is also located, but this is very tenuous. McCarthy, who created LISP in 1958 at MIT was explicitly motivated by Church’s lambda calculus, but that belongs more to the general theory of algorithms than categories per se. There is no connection I could find to Dahl or Nygaard. Even later relations between mathematics and programming that are pointed out, like Curry-Howard correspondence (“every proof is a program”) and Martin-Löf’s work on type theory, are not specifically categorical. Lawvere is mentioned as categorifying the Curry-Howard correspondence later, but I am not sure if even he was motivated by OOP.

Were creators of OOP influenced, directly or by osmosis, by the category theory structures (perhaps lectures on category theory were offered at MIT at the time, and somebody from AI group attended them)? When was the analogy first explicitly made, and how did it influence both areas?

$\endgroup$
  • $\begingroup$ Having learned enough about OOP last week to give you something remotely intelligent: The Wikipedia page on OOP says that Alan Kay says he was influenced by LISP; the LISP page says it was influenced by lambda calculus. Perhaps there's a connection there, although lambda calculus is connected to programming in a lot of ways. Oh, and this notes a connection between category theory and lambda calculus. So maybe yes. $\endgroup$ – HDE 226868 Dec 10 '14 at 2:24
  • $\begingroup$ Actually, that does kind of look like a connection. $\endgroup$ – HDE 226868 Dec 10 '14 at 2:27
  • 5
    $\begingroup$ As far as I know, OOP is still not influenced by category theory. The major theoretical work on OOP isCardelli's A Theory of Objects (1996) which long postdates the prominence of OOP, and which is not overtly category-theoretic. $\endgroup$ – MJD Dec 10 '14 at 21:40
10
$\begingroup$

I'm not a programmer, but I'll try to post a coherent answer.

One of the major developers of OOP was Alan Kay. Kay himself has mentioned that LISP had an influence on him when he was developing the idea of OOP. from this page:

The second phase of this was to finally understand LISP and then using this understanding to make much nicer and smaller and more powerful and more late bound understructures.

LISP, in turn, was strongly influenced by lambda calculus. This powerpoint gives a good idea of how fundamentally related the two are.

Lambda calculus, in turn, was heavily influenced by category theory. This page notes that the two are related; however, the connection is not clearly explained beyond this:

Also, there are relationships between typed lambda calculus, proof theory and category theory.

This answer isn't much, but it's the beginnings of a connection. I will add more tomorrow.


I didn't want to cite Wikipedia, but I should note that some pages led me to the connections. Here they are:

Object-oriented programming $\to$ LISP $\to$ Lambda calculus $\to$ category theory

$\endgroup$
  • 10
    $\begingroup$ Lambda calculus was invented by Church in the 1930s, long before category theory. The connections between category theory and lambda calculus only became clear much later. $\endgroup$ – MJD Dec 10 '14 at 21:37
  • $\begingroup$ @MJD True, but couldn't its development have been influenced by category theory? Category theory clearly wasn't its precursor, but it does appear to have influenced it. $\endgroup$ – HDE 226868 Dec 10 '14 at 21:39
  • 2
    $\begingroup$ My impression is that "categorical" traits first clearly appear in Dahl and Nygaard's Simula 67. But it seems that interaction between lambda calculus and category theory happened after 1969, when Howard linked it to combinatory logic: "Joachim Lambek showed in the early 1970s that the proofs of intuitionistic propositional logic and the combinators of typed combinatory logic share a common equational theory which is the one of cartesian closed categories" en.wikipedia.org/wiki/… $\endgroup$ – Conifold Dec 12 '14 at 6:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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