cook@hplabsz.HPL.HP.COM (William Cook) (08/09/90)
I sent this out a couple of weeks ago, and then complained that
nobody replied (even privately!). It seems that it didn't make it
to a few sites, so here it is again. Thanks to everybody who has
written me since...
I was worried that everything was going to the dev/null.
--------------------------------------------------------------------------
I gave a presentation on the essence of object-oriented programming at the
school/workshop on the foundations of object-oriented languages (REX/FOOL)
this summer. The proceedings will be printed as a Springer volume this
fall. In summary, I contrast object-oriented programming (which I prefer to
call procedural data abstraction (PDA)) with abstract data types (ADT).
They are not the same. I can only illustrate the dichotomy here, and give
some references.
Here is an ADT for integer lists, written in ML (it would look about the
same in CLU, Ada, Modula-2, etc).
exception error;
abstype intlist = NIL | CELL of int * intlist with
val xnil = NIL;
fun null(l : intlist) = case l of
NIL => true |
CELL(x, l) => false;
fun head(l : intlist) = case l of
NIL => raise error |
CELL(x, l') => x;
fun tail(l : intlist) = case l of
NIL => raise error |
CELL(x, l') => l';
fun cons(x : int, l : intlist) =
CELL(x,l);
end;
head(cons(4, nil)) --> 4
This is called an "abstract data type" because the actual definition of
intlist is hidden, or abstracted, in the the rest of the program.
Here's an OOP version, written in a syntactically sugared version of ML (a
correct implementation is given in the appendix).
datatype IntListObject = {
null: bool,
head: int,
tail: intlistobject,
cons: int -> intlistobject
};
let MakeNil : IntListObject =
recursive self = { -- the Nil "class"
null = true,
head = raise error,
tail = raise error,
cons = fn y => MakeCell(y, self)
}
and MakeCell(x : int, r : IntListObject) : IntListObject =
recursive self = { -- the Cell "class";
null = false, -- x and r are "instance variables"
head = x,
tail = r,
cons = fn y => MakeCell(y, self)
}
This program does not have any hidden or abstract types. The full
definition of IntListObject is visible everywhere. It uses procedural
abstraction to get information hiding. Creating a list with element 4 and
then returning it works like this:
MakeNil.cons(4).head --> 4
As you can see, all of the NIL cases from the ADT are collected into the
MakeNil object, and all of the CELL cases are collected into MakeCell.
There are no case statements in the OOP version; case statements are bad
because you are always having to add new cases (in this situation, if you
add a new representation). This organizational difference has great
consequences for programming methodology. For example, consider adding an
"interval" class that represents the integer list [n...m]. In the OOP
format its easy:
MakeInterval(x : int, y: int) : IntListObject =
if x > y then -- the Interval "class";
MakeNil -- x and y are "instance variables"
else
recursive self = {
null = false,
head = x,
tail = MakeInterval(x, y+1),
cons = fn y => MakeCell(y, self)
}
Exercise: consider adding this to the ADT code.
In short: Object-oriented programming is using procedures to represent data.
That is, procedural data abstraction.
-william cook@hplabs.hp.com
REFERENCES:
Early definition and discussion of virtues of "OOP":
@article{Zilles73
,title="Procedural Encapsulation: A Linguistic Protection Mechanism"
,author = "Stephen N. Zilles"
,journal = "SIGPlan Notices"
,pages = "142-146"
,volume = 8
,number = 9
,year = 1973
}
Change of direction, away from OOP, to invent ADTs:
@article{LiskovZilles74
,author = "B. Liskov and S. Zilles"
,title = "Programming with Abstract Data Types"
,journal = "SIGPlan Notices"
,year = "1974"
,volume = "9"
,number = "4"
,pages = "50-59"
}
Comparison of OOP and ADT, summarizes most significant issues:
@incollection{Reynolds78
,author="John C. Reynolds"
,title="User Defined Types and Procedural Data Structures as
Complementary Approaches to Data Abstraction"
,booktitle="Programming Methodology, A Collection of Articles by IFIP WG2.3"
,publisher="Springer-Verlag"
,address=NY
,editor="David Gries"
,year=1978
,pages="309-317"
,note="Reprinted from S. A. Schuman (ed.),
{\em New Advances in Algorithmic Languages 1975},
Inst. de Recherche d'Informatique et d'Automatique,
Rocquencourt, 1975, pages 157-168",
}
Discussion of OOP in chapter on "data-oriented program", similar to CLOS:
@book{AbelsonSussman85
,author = "Abelson and Sussman"
,title = "The Structure and Interpretation of Computer Programs"
,publisher = "MIT Press"
,year = 1985
}
APPENDIX: ML version of OOP code
datatype intlistobject = tag of {
null: unit -> bool,
head: unit -> int,
tail: unit -> intlistobject,
cons: int -> intlistobject };
fun MakeNil() =
let fun self() = tag({
null = fn() => true,
head = fn() => raise error,
tail = fn() => raise error,
cons = fn y => MakeCell(y, self())
})
in self() end
and MakeCell(x,r) =
let fun self() = tag({
null = fn() => false,
head = fn() => x,
tail = fn() => r,
cons = fn y => MakeCell(y, self())
})
in self() end;