OOPSILON: an Object Oriented Programming System with Incomplete Lazy
Object Notation

Brian Postow, Kenneth Regan,  Carl Smith

(bpostow@cs.umd.edu), (regan@cs.buffalo.edu), (smith@cs.umd.edu)


ABSTRACT

There are many different models of computation used within the theory
of computation, each of them has its strengths and weaknesses. For
example, Turing Machines are visually intuitive, but they do not
represent functions well. The $\lambda$ calculus is useful for
thinking about functions, but it doesn't model actual computers
well. RAM machines model real computers well, but they don't solve the
problems of either that the other two do.

A related issue that has been known for a long time is that different
models of computation have similarities to different programming
language paradigms. Obviously the $\lambda$ calculus is very similar
to functional programming languages (ML, Lisp, Scheme). RAM machines
and Turing machines can be seen as representations of the imperative
paradigm (FORTRAN, C, Pascal). Certain versions of logic can be seen
as models of computation. These are of course similar to the logical
paradigm (prolog). Each of these models is very elegant in its own
way, very much as each paradigm is elegant in its own way.

However, one modern paradigm has been left out of this list. Object
Oriented programming languages, perhaps due to their history of having
little to do with theory, have no associated model. We have tried to
fill this void by creating a model of computation that fits the Object
Oriented paradigm, and is as elegant, in its own way, as the $\lambda$
calculus or Turing Machines.

OOPSILON is based on a similar concept to the $\lambda$ calculus. Just
as in that model of computation everything is a function, in our
model, everything is an object. We model computation as a process
which builds an object, so a computation in progress is merely an
incomplete object, an object that hasn't been fully specified yet. We
represent this by allowing objects to have holes, or ports in them
which can be filled later.

In this paper, we prove that OOPSILON is Church-Rosser, Turing
Complete, and an acceptable programming system. From the first 2
properties we can see that this is a valid model of computation worth
studying. From the third, we get a unique notion of self that comes
for free from the Recursion Theorem.