Theory behind object oriented programming

Question

Alonzo Church's lambda calculus is the mathematical theory behind functional languages. Has object oriented programming some formal theory ?

Answer 1

Object-oriented is a bit of a misnomer and I don't really think classes or type systems have much to do with OO programming. Alan Kay's inspiration was biological and what's really going on that matters is communication. A better name would be message-oriented programming. There is plenty of theory about messaging, for example Pi calculus and the actor model both have rigorous mathematical descriptions. And that is really just the tip of the iceberg.

Answer 2

In 2000 in my degree thesys I proposed this model; very shortly:

y + 1 = f(u, x)
x + 1 = g(u, x)

where:

• u: input
• y: output
• x: state
• f: output function
• g: state function

Formally it's very similar to finite state machine, but the difference is that U, Y, S are set not finite, but infinite (numerable) and f and g are Touring Machine (TM).

f and g togheter form a class; if we add an initial state x0 we have an object. So OOP in something more than a TM a TM is a specific case of OOP. Note that the state x is of a different level than the state "inside" the TM. Inside the TM there are not side effect, the x state count for side effect.

Answer 3

Object Orientation comes from psychology not math.

If you think about it, it resembles more how humans work than how computers work. We think in objects that we class-ify. For instance this table is a seating furniture.

Take Jean Piaget (1896-1980), who worked on a theory of children's cognitive development. Wikipedia says:

Piaget also had a considerable effect in the field of computer science and artificial intelligence.

Some cognitive concepts he discovered (that imply to the Object Orientation concept):

Classification The ability to group objects together on the basis of common features.

Class Inclusion The understanding, more advanced than simple classification, that some classes or sets of objects are also sub-sets of a larger class. (E.g. there is a class of objects called dogs. There is also a class called animals. But all dogs are also animals, so the class of animals includes that of dogs)

Read more: Piaget's developmental theory http://www.learningandteaching.info/learning/piaget.htm#ixzz1CipJeXyZ

Answer 4

IMO a good example of what makes a successful OO language could be found by comparing the similarities between JAVA and C#. Both are extremely popular and very similar. Though I think the general idea of a minimum OO language can be found by looking at Simula67. I believe the general idea behind Object Oriented programming to be that it makes it seem like the computer thinks more like a human, this is supported by things like inheritance (both class "mountain bike" and "road bike" belong to parent class "bicycle", and have the same basic features). Another important idea is that objects (which can be executable lines of code) can be passed around like variables, effectively allowing the program to edit itself based on certain criteria (although this point is highly arguable, I cite the ability to change every instance of an object based on one comparison). Another point to make is modularity. As entire programs could effectively be passed around like a variable (because everything is treated as an object), it becomes easier to modify large programs, by simply modifying the class or method being called, and never having to modify the main method. Because of this, expanding the functionality of a program can become much simpler. This is why web businesses love languages like C# and JAVA (which are full fledged OO). Gaming companies like C++ because it gives them some of the control of an imperative language (like C) and some of the features of object orientation (like C# or JAVA).

Answer 5

The history (simplified) goes that way :

First came the spagetti code. Then came the procedural code (Like C and Pascal). Then came modular code (Like in modula). Then came the object oriented code (Like in smalltalk).

Whats the porpuse of object oriented programming ?

You can only understand if you recall history.

At first code was simply a sequence of instructions given to the computer (Literally in binary representation) Then came the macro assemblers. With mneomonics for instructions. Then people detected that sometimes you have code that is repeated around. So they created GOTO. But GOTO (Or branch or jump etc) cannot return back to where it was called, and cannot give direct return values, nor can accept formal parameters (You had to use global variables). Against the first problem, people created subroutines (GOSUB-like). Groups of instructions that could be called repeatedly and return to where it was called. Then people detected that routines would be more usefull if they had parameters and could return values. For this they created functions, procedures and calling conventions. Those abstractions where called on top of an abstraction called the stack. The stack allows formal parameters, return values and something called recursion (direct or indirect). With the stack and the ability for a function to be called arbitrarely (even indirectly), came the procedural programming, solving the GOTO problem. But then came the large projects, and the necessity to group procedures into logical entities (modules).

Thats where you will understand why object oriented programming evolved.

When you have a module, you have module local variables.

Think about this :

Module MyScreenModule;

Var X, Y : Integer;

Procedure SetX(value : Integer);
Procedure SetY(value : Integer);

End Module.

There are X and Y variables that are local to that module. In that example, X and Y holds the position of the cursor. But lets suppose your computer has more than one screen. So what can we do now ? X and Y alone arent able to hold the X and Y values of all screens you have. You need a way to INSTANTIATE that information. Thats where the jump from modular programming goes to object oriented programming.

In a non object oriented language you would usually do :

Var Screens :  Array of Record X, Y : Integer End;

And then pass a index value to each module call :

Procedure SetX(ScreenID : Integer; X : Integer);
Procedure SetY(ScreenID : Integer; Y : Integer);

Here screenid refers to wich of the multiple screens that you are talking about.

Object oriented inverts the relationship. Instead of a module with multiple data instances (Effectively what screenid does here), you make the data the first class citizen and attach code to it, like this :

Class MyScreenModule;

Field X, Y : Integer;

Procedure SetX(value : Integer);
Procedure SetY(value : Integer);

End Class.

Its almost same thing as a module ! Now you instantiate it by providing a implicit pointer to a instance, like :

ScreenNumber1 := New MyScreenModule;

And then proceed to use it :

ScreenNumber1::SetX(100);

You effectively turned your modular programming into a multi-instance programming where the variable holding the module pointer itself differentiates each instance. Gotcha ?

Its an evolution of the abstraction.

So now you have multiple-instances, whats the next level ?

Polymorphism. Etc. The rest is pretty standard object oriented lessons.

Whats the point ? The point is that object oriented (like procedures, like subroutines etc) did not evolve from a theoretical standpoint but from the praxys of many coders working around decades. Its a evolution of computer programming, a continual evolution.

Answer 6

What about Petri nets? Object might be a place, a composition an arc, messages tokens. I have not though about it very thoroughly, so there might be some flaws I am not aware of, but you can investigate - there is a lot of theoretical works related to Petri nets.

I found this, for example:

• http://link.springer.com/book/10.1007%2F3-540-45397-0
• Readable PDF: http://www.informatik.uni-hamburg.de/bib/medoc/M-329.pdf

Answer 7

Abadi and Cardelli have written A Theory Of Objects, you might want to look into that. Another exposition is given the venerable TAPL (IIRC, they approach objects as recursive records in a typed lambda calculus). I don't really know much about this stuff.

Answer 8

One formal definition I've run into for strongly defining and constraining subtyping is the Liskov Substitution Principle. It is certainly not all of object-oriented programming, but yet it might serve as a link into the formal foundations in development.

Answer 9

OOP is a bit of a mixed bag of features that various languages implement in slightly different ways. There is no single formal definition of OOP but a number of people have tried to describe OOP based on the common features of languages that claim to be object oriented. From Wikipedia:

Benjamin Cuire Pierce and some other researchers view as futile any attempt to distill OOP to a minimal set of features. He nonetheless identifies fundamental features that support the OOP programming style in most object-oriented languages:

• Dynamic dispatch – when a method is invoked on an object, the object itself determines what code gets executed by looking up the method at run time in a table associated with the object. This feature distinguishes an object from an abstract data type (or module), which has a fixed (static) implementation of the operations for all instances. It is a programming methodology that gives modular component development while at the same time being very efficient.
• Encapsulation (or multi-methods, in which case the state is kept separate)
• Subtype polymorphism
• object inheritance (or delegation)
• Open recursion – a special variable (syntactically it may be a keyword), usually called this or self, that allows a method body to invoke another method body of the same object. This variable is late-bound; it allows a method defined in one class to invoke another method that is defined later, in some subclass thereof.

Answer 10

I'd check out wikipedia's page on OO http://en.wikipedia.org/wiki/Object-oriented_programming It's got the principles and fundamentals and history.

My understanding is that it was an evolutionary progression of features and ideas in a variety of languages that finally came together with the push in the 90's for GUI's going mainstream. But i could be horribly wrong :-D

Edit: What's even more interesting is that people still argue about "what makes an OO language OO"..i'm not sure the feature set is even generally agreed upon that defines an OO language.