9
$\begingroup$

This is a question I asked in mathematics SE forum, and I was referred here. So here is the question-

I'm a newbie in both formal mathematics and theoretical computer science, so please bear with me if you find my question is not properly framed. Object Oriented Modeling seems very useful in defining complex interactions when simulating real world. But it's mostly used in programming. I was wondering if we have a similar concept in mathematics. When we're doing programming, we can understand the concept of "Objects" and "Object Oriented Programming" and just implement it. But do we have formal definition of "Objects" in terms of Set Theory? Or for that matter, any other formal mathematical theory?

Can we implement/ formally define three primary object orient modeling concepts- 1. Encapsulation 2. Inheritance 3. Polymorphism

I know question is too broad, but would really appreciate if you can provide some pointers as well so that I can understand these concepts better.

$\endgroup$
  • 2
    $\begingroup$ There are really two questions as I see it. One is asking for a formalism of object-oriented concepts. The other is asking for object-oriented concepts in mathematics. Perhaps it would be better to ask two separate questions. There's plenty of material out there answering the first question, though probably only a little for the second. (And maybe tomorrow I'll find time to answer the question.) $\endgroup$ – Dave Clarke May 5 '12 at 19:58
  • $\begingroup$ Thanks.. could you please suggest me a material for the formalization of object oriented concepts that is considered as standard or "text book"? I'll wait for your answer for second one.... :) $\endgroup$ – user1260776 May 5 '12 at 20:14
  • 2
    $\begingroup$ The standard book (of a few years ago) is A Theory of Objects. More recent work is Featherweight Java. There's also a series of workshops called Foundations of Object-Oriented Languages which deals with these issues. $\endgroup$ – Dave Clarke May 5 '12 at 20:17
  • $\begingroup$ Thanks! Will go through them... Also, I stumbled upon " lambda calculus" which is closely related to my question.. $\endgroup$ – user1260776 May 5 '12 at 20:31
9
$\begingroup$

The answer is complicated, for two reasons.

  1. Different people in Computer Science interpret the term "object" differently. One is that an object consists of some data and operations packaged together. The other is that an object is all that but also has "state," i.e., it is some form of a changeable entity.

  2. There are deep philosophical issues to do with what "change" means (and what "entity" means, as it is constantly changing), and whether mathematical descriptions actually capture changeable entities.

Object in the sense of data + operations: That is pretty standard in mathematics. Take any group theory text book. It will have somewhere a definition such as $h_g(x) = g x g^{-1}$. (It is a conjugation operator.) The $h_g$ is an "object" in this terminology. It has some data ($g$) and an operation $x \mapsto g x g^{-1}$. Or you can make it more object-y by taking the pair $\langle g, x \mapsto gxg^{-1}\rangle$ or the triple $\langle g, x \mapsto gxg^{-1}, x \mapsto g^{-1}xg\rangle$. You can construct these kind of "objects" in any functional programming language that has lambda abstraction and some way to form tuples. Abadi and Cardelli's "Theory of Objects" deals with objects of this kind extensively.

Objects with state (or objects that change): Does mathematics have such things? I don't think so. I haven't seen a mathematician talk about anything that changes, not in his/her professional life. Newton used to write $x$ for the position of a particle, which is supposedly changing, and $\dot{x}$ for its rate of change. Mathematicians eventually figured out that what Newton was talking about was a function $x(t)$ from real numbers into a vector space, and $\dot{x}$ was another such function which was the first derivative of $x(t)$ with respect to $t$. From this, many deep-thinking mathematicians have concluded that change doesn't really exist and all you have are functions of time. But what was changing in Newtonian mechanics wasn't the position, but the particle. The position is its instantaneous state. No mathematician or physicist would pretend that a particle is a mathematical idea. It is a physical thing.

So it is with objects. They are "physical" things, and the states are their mathematical attributes. For a nice discussion of this aspect, see the Chapter 3 of Abelson and Sussman's Structure and Interpretation of Computer Programs. This is a text-book at MIT and they teach it to all scientists and engineers, who I think understand "physical" things perfectly fine.

The fact that particles aren't mathematical doesn't mean that we can't deal with them mathematically. If you ask a mathematician to model a two-particle system, he will immediately make up two functions and call them $x_1(t)$ and $x_2(t)$. So, the two particles reduces to two meaningless indices (1 and 2). This is the mathematician's way of saying we don't know what those particles are and we don't care. All we need to know is that their positions evolve independently (or separately). So, we will model them by two separate functions.

Similarly the standard mathematical way to model object-oriented programs is to treat each object as an index into the state space. The only difference is that since objects come and go, and the structure of the system is dynamic, we need to extend it to a "possible world" model where each world is basically a collection of indices. Allocation and deallocation of objects would involve moving from one world to another.

There is a problem though. Unlike in mechanics, we want the state of our objects to be encapsulated. But the mathematical descriptions of objects put states all over the place, completely destroying encapsulation. There is a mathematical trick called "relational parametricity" which can be used to cut things back to size. I won't go into it now, except to emphasize that it is a mathematical trick, not a very conceptual explanation of encapsulation. A second way of modelling objects mathematically, with encapsulation, is to finesse the states and describe the object behaviour in terms of observable events. For a good discussion of both of these models, I can refer you to my paper titled Objects and classes in Algol-like Languages.


[Note added:]

A nice analysis of the mathematical underpinnings of objects can be found in William Cook's article "On Understanding Data Abstraction, Revisited".

$\endgroup$
  • 2
    $\begingroup$ I knew someone here would be able to answer... $\endgroup$ – Andrej Bauer May 7 '12 at 6:39
  • $\begingroup$ Thanks Uday, for your time, and detailed answer. When I asked this question, I was thinking only in sense of "data + operations", and it never occurred to me that group theory can represent "OBJECT" as "data+operations". Also, I'll also go through the links you've referred. $\endgroup$ – user1260776 May 7 '12 at 8:16
  • $\begingroup$ @AndrejBauer. Yeah, I probably went overboard. The OP was probably using "mathematics" just as a word for formalisation, as opposed to a discipline. $\endgroup$ – Uday Reddy May 7 '12 at 8:29
  • $\begingroup$ @Uday, I might not have phrased question properly, but when I meant "mathematics", I clearly meant formal mathematics. My thought was "'set theory' forms foundation of mathematics,how to 'explain' or 'derive' objects of OO Modeling in terms of set theory.How do we put together all these- Set Theory, Objects, and Formal logic (like first order logic) ..." Though I don't understand your answer fully, I'm able to get "sense" of what you said,& I assure you, this is the answer I was expecting. Thank you!!(my ideas r not completely organized,plz forgive me i'm still newbie :)) $\endgroup$ – user1260776 May 7 '12 at 9:59
  • 2
    $\begingroup$ @user1260776. I understand. But my point is that "formal" and "mathematics" are different ideas. You can formalize concepts without reducing them to (or deriving them from) mathematics. Newton formalized mechanics but didn't bother to reduce "particles" to "sets". I am personally quite happy to follow Newton's lead and admit things that I don't reduce to sets. But, I guess we have to know when to reduce and when not to reduce. Having been trained as a Physicist, I find that quite easy to do. For many other Computer Scientists, it may not be so easy. $\endgroup$ – Uday Reddy May 7 '12 at 11:13
0
$\begingroup$

think theres a pretty good theoretical description of objects in the old classic book "structure and interpretation of computer programs"[1] by abelson & sussman, based on scheme (a lisp variant). now free online! this does show how the concept of object orientation can be embedded even into the lambda calculus (~aka Lisp) if you have some mechanism to store local state. as I understand it, this was a std MIT textbook for many yrs. not saying this is the best ref on the subj; am sure there are other better ones at this pt.

I dont think this has been totally formalized anywhere Ive heard of but loosely speaking objects are basically composed of code + data in the form of

  • methods (with parameters)
  • state, ie instance variables

in some encapsulated form. arguably other aspects such as inheritance are not fundamental. as is stated in abelson & sussman, what they call "syntactic sugar".

[1] structure & interpretation of computer programs by abelson & sussman

$\endgroup$
  • 3
    $\begingroup$ Of course objects in the object-oriented programming sense have been formalized. There are books by Abadi & Cardelli, Castanga, and Kim Bruce devoted to the topic. There has been 10 years of workshops in the FOOL series devoted to the foundations of object-oriented programming. The conferences ECOOP and OOPSLA regularly had papers on the foundations of OO. Indeed, the first paper on the semantics of OO is about 20 years old. $\endgroup$ – Dave Clarke May 7 '12 at 5:48
  • $\begingroup$ @vzn, thanks for the answer. I'll go through the books you've suggested... $\endgroup$ – user1260776 May 7 '12 at 10:03
  • $\begingroup$ DC-- I phrased that poorly. more accurately, think its safe to say that formal definitions of what exactly constitutes an "object" or what are the key/fundamental components of OOP tend to vary significantly in the literature. the definitions have probably significantly expanded over time. for example I suspect inheritance was added later and the original idea was mainly just code+data in an encapsulated form. $\endgroup$ – vzn May 8 '12 at 1:01
  • $\begingroup$ another example of an OOP feature that is not agreed on as fundamental from what I can tell is multiple inheritance which is seen in eg C++ but intentionally avoided in java in favor of interfaces instead. etc $\endgroup$ – vzn May 8 '12 at 1:06

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.