Objects and classes in Algol-like languages.
Many object-oriented languages used in practice descend from Algol. With this motivation, we study the theoretical issues underlying such languages via the theory of Algol-like languages. It is shown that the basic framework of this theory extends cleanly and elegantly to the concepts of objects and classes. Moreover, a clear correspondence emerges between classes and abstract data types, whose theory corresponds to that of existential types. Equational and Hoare-like reasoning methods and relational parametricity provide powerful formal tools for reasoning about Algol-like object-oriented programs. 2002 Elsevier Science (USA)
Introduction
Object-oriented programming first developed in the context
of Algol-like languages in the form of Simula 67 [17]. The
majority of object-oriented languages used in practice claim
either direct or indirect descent from Algol. Thus, it seems
entirely appropriate to study the concepts of object-oriented
programming in the context of Algol-like languages. This
paper is an effort to formalize how objects and classes are
used in Algol-like languages and to develop their theoretical
underpinnings.
The formal framework we adopt is the technical notion
of "Algol-like languages" defined by Reynolds [51]. The
Idealized Algol of Reynolds is a typed lambda calculus with
base types that support state-manipulation (for expressions,
commands, etc. The typed lambda calculus framework
gives a "mathematical" flavor to Idealized Algol and sets
it within the broader programming language research. Yet,
the base types for state-manipulation make it remarkably
close to practical programming languages. This combination
gives us an ideal setting for studying various programming
language phenomena of relevance to practical languages like
C++, Modula-3, Java etc.
Reynolds also argued [50, Appendix] that object-oriented
programming concepts are implicit in his Idealized Algol.
The essential idea is that classes correspond to "new" operators
that generate instances every time they are invoked.
This obviates the need for a separate "class" concept. The
idea has been echoed by others [46, 2]. In contrast, we
take here the position that there is significant benefit to
directly representing object-oriented concepts in the formal
system instead of encoding them by other constructs. While
the effect of classes can be obtained by their corresponding
"new" operators, not all properties of classes are exhibited
by the "new" operators. Thus, classes form a specialized
form of "new" operators that are of independent interest.
In this paper, we define a language called IA + as an
extension of Idealized Algol for object-oriented programming
and study its semantics and formal properties. An
important idea that comes to light is that classes are abstract
data types whose theory corresponds to that of existential
types [35]. In a sense, IA + is to Idealized Algol what SOL is
to polymorphic lambda calculus. However, while SOL can
be faithfully encoded in polymorphic lambda calculus [45],
IA + is more constrained than Idealized Algol. The corresponding
encoding does not preserve equivalences. Thus,
IA + is a proper extension.
Related work A number of papers [19, 1, 11, 18] discuss
object-oriented type systems for languages with side effects.
It is not clear what contribution these type systems make
to reasoning principles for programs. A related direction is
that of "object encodings." Pierce and Turner [44] study
the encoding of objects as abstract types, which bears some
similarity to the parametricity semantics in this paper. More
recent work along this line is [12]. Fisher and Mitchell [20]
also relate classes to data abstraction. This work assumes
a functional setting for objects, but some of the ideas deal
with "state." Work on specification of stateful objects includes
[5, 28, 29, 30] in addressing subtyping issues and [3, 6]
in addressing self-reference issues. The major developments
in the research on Algol-like languages are collected in [43].
Tennent [58] gives a gentle introduction to the concepts as
of 1994.
2 The language IA
The language IA + is an extension of Idealized Algol with
classes. Thus, it is a typed lambda calculus with base types
corresponding to imperative programming phrases. The
base types include:
ffl comm, the type of commands or state-transformers,
and
ffl exp[ffi], the type of state-dependent expressions giving
ffi-typed values,
ffl val[ffi], the type of phrases that directly denote ffi-typed
values (without any state-dependence).
Here, ranges over a collection of "data types" such as
int(eger) and bool(ean) whose values are storable in vari-
ables. The "types" like exp[ffi] and comm are called "phrase
types" to distinguish them from data types. Values of arbitrary
phrase types are not storable in variables. 1
The collection of phrase types (or "types," for short) is
given by the following syntax:
where fi ranges over base types (exp[ffi], comm and val[ffi]).
Except for cls ' types, the remaining type structure is that
of simply typed lambda calculus with record types and sub-
typing. See, for instance, Mitchell [34, Ch. 10] for details.
The basic subtypings include
a collection of types '
called "state-dependent" types, and
ffl the standard record subtyping ("width" as well as "depth"
subtyping).
Our interpretation of subtyping is by coercions [34, Sec. 10.4.2].
The parameter passing mechanism of IA + is call-by-name
(as is usual with typed lambda calculus). The second coercion
above makes available Algol's notion of call-by-value.
An "expression" argument can be supplied where a "value"
is needed.
The type cls ' is the type of classes that describe the
behavior of '-typed objects. An "object" is an abstraction
that encapsulates some internal state represented by "fields"
and provides externally visible operations called "methods."
A class defines the fields and methods for a collection of
objects, which are then called its "instances." The distinction
between classes and instances arises because objects are
stateful. (If a class is stateless, then there is no observable
difference between its instances and there would be little
point in making the class-instance distinction.) Classes represent
the abstract (or "mathematical") concept of a behavior
instances represent the concrete (or "physical")
realizations of the behavior.
For defining classes, we use a notation of the form:
class '
fields C1
methods M
init A
The various components of the description are as follows:
ffl ' is a type (the type of all instances of this class), called
the signature of the class,
are identifiers (for the fields),
are terms denoting classes (of the respective
fields),
ffl M is a term of type ' (defining the methods of the
class), and
1 It is possible to postulate a data type of references (or pointers)
ref ', for every phrase type ', whose values are storable in variables.
This obtains the essential expressiveness that the object-oriented
programmer desires. Unfortunately, our theoretical understanding
of references is not well-developed. So, we omit them from the main
presentation and mention issues relating to them in Sec. 4.3.
ffl A is a comm-typed term (for initializing the fields).
Admittedly, this is a complex term form but it represents
quite closely the term forms for classes in typical programming
languages. Moreover, we will see that much of this
detail has a clear type-theoretic basis.
It is noteworthy that we cannot define nontrivial classes
without first having some primitive classes (needed for defining
fields). We will assume a single primitive class for (mu-
table) variables via the constant:
If x is an instance of Var[ffi] (a "variable"), then x:get is a
state-dependent expression that gives the value stored in x
and x:put(k) is a command that stores the value k in x. 2
We often use the abbreviation:
for the signature type of variables. We assume the subtyp-
ings:
whose coercion interpretations are the corresponding field
selections.
Note that the type var[ffi] is different from the class Var[ffi].
Values of type var[ffi] need not be, in general, instances of
Var[ffi]. For instance, the following (trivial) class has instances
of type var[int]:
class
fields
methods
init skip
Instances of this class always give 0 for the get message and
do nothing in response to a put message. Yet they have
the type var[int]. In essence, the type of an object merely
gives its signature (the types of its methods), whereas its
class defines its behavior. A tighter integration of classes
and types would certainly be desirable. We return to this
issue in Sec. 4.1.
As an example of a nontrivial class, consider the following
class of counter objects:
class
finc: comm, val: exp[int]g
fields
cnt
methods
init
A counter has a state variable for keeping a count; the inc
method increments the count and the val method returns
the count. (The definition of the inc method could have
also been written as cnt := cnt using the subtypings of
var[ffi]. We use explicit coercions for clarity.)
We assume that all new variables come initialized to some specific
initial value init ffi . It is also possible to use a modified primitive
cls var[ffi] that allows explicit initialization via a
parameter.
One would want a variety of combinators for classes. The
following "product" combinator for making pairs of objects
is an essential primitive:
cls '1 \Theta cls '2 ! cls ('1 \Theta '2)
An instance of a class C1   C2 is a pair consisting of an
instance of C1 and an instance of C2 . Other useful combinators
abound. For instance, the following combinator is
motivated by the work on "fudgets" [14]:
An instance of F1 !? F2 is a pair (a; b) where a is an instance
of F1 (b) and b an instance of F1 (a). The two objects are
thus interlinked at creation time using mutual recursion.
Common data structures in programming languages such
as arrays and records also give rise to class combinators.
The array data structure can be regarded as a combinator
of type:
array
so that (array C n) is equivalent to an n-fold product C
C, viewed as a (partial) function from integers to C-objects.
The record construction
record C1
is essentially like C1   \Delta \Delta \Delta   Cn except that its instances are
records instead of tuples.
For creating instances of classes, we use the notation:
new C
which is a value of type
the signature of class C. For example,
new Counter -a. B
creates an instance of Counter, binds it to a and executes
the command B. The scope of a extends as far to the right
as possible, often delimited by parentheses or begin-end
brackets.
The type of newC illustrates how the "physical" nature
of objects is reconciled with the "mathematical" character of
Algol. If new C were to be regarded as a value of type ' then
the mathematical nature of Algol would prohibit stateful
objects entirely. For example, a construction of the form
let new Counter
in a.inc; print a.val
would be useless because it would be equivalent, by fi-reduction,
to:
(new Counter).inc; print (new Counter).val
thereby implying that every use of a gives a new counter and
no state is propagated. The higher order type of newC gives
rise to no such problems. This insight is due to Reynolds [51]
and has been used in several other languages [37, 56].
2.1 The formal system
We assume a standard treatment for the typed lambda calculus
aspects of IA + . The type rules for cls types are shown
in Fig. 1. Note that we have one rule for the introduction
of cls types and one for elimination. We show a single
field in a class term for simplicity. This is obviously not
fields C x methods M init
cls Intro
cls Elim

Figure

1: Type rules for cls types
cls '1 \Theta cls '2 ! cls ('1 \Theta '2 )
(where

Figure

2: Essential constants of IA
a limitation because the   combinator of classes can be used
to instantiate multiple classes. It is significant that the
initialization command is restricted to acting on the field x.
We do not allow it to alter arbitrary non-local objects. The
methods term M , on the other hand, can act on non-local
objects. This is useful, for instance, to obtain the effect
of "static" fields in languages like C++ and Java. If a class
term does not have any free identifiers, we call it a "constant
class."
The restriction that the initialization command should
have no free identifiers other than x is motivated by reasoning
considerations. Programmers typically want to assume
that the order of instance declarations is insignificant. If the
initializations were to have global effects, the order would
become significant. However, the restriction as stated in
the rule is too stringent. One would want the initialization
command to be able to at least read global variables. In


Appendix

A, we outline a more general type system based
on the ideas of [50, 48] that allows read-only free identifiers.
The important constants of IA are shown in Fig. 2.
(The constants for expression and value types are omitted.)
The constant skip denotes the do-nothing command and ";"
denotes sequential composition. The letval operator sequences
the evaluation of an expression with that of another
expression or command. More precisely, letvalef evaluates
e in the current state to obtain a value x and then evaluates
f x. (Note that this would not make sense if letval e f were
of type val[ffi 0 ].) The infix operator ":=" is a variant of letval
defined by:
a
For example, the command (cnt.put := cnt.get + 1) in the
definition of the Counter class involves such sequencing. The
letval operator is extended to higher types as follows:
letval
(fst
letval
Thus, all "state-dependent" types (as defined in Appendix
have letval operators, and we have a coercion:
which serves to interpret the subtyping (val[ffi] ! ') !:
The equational calculus for the typed lambda calculus
part of IA + is standard. For cls type constructs, we have
the following laws:
new (class ' fields C x methods M init
new C -x:
(j) (class ' fields C x methods x init skip)
(fl) new C1 -x: new C2 -y: M
new C2 -y: new C1 -x: M
The (fi) law specifies the effect of an Intro-Elim combination.
The (j) law specifies the effect of an Elim-Intro combination
where the "Elim" is the implicit elimination in field declara-
tions. The (fl) law allows one to reorder new declarations.
Note that it is important for initializations to be free from
global effects for the (fl) law to hold.
The interaction of new declarations with various constants
is axiomatized by the following equational axioms
new c -x:
new c -x: a; new c g (2)
new c -x: g(x);
ae
new c -x:
letval e -z: h x z
oe
ae
letval e -z:
new c -x: h x z
oe
new c -x: if p (f x) (g
(In the presence of nontermination, the first equation must
be weakened to an inequality new c -x: skip v skip.) These
equations state that the new operator commutes with all the
operations of IA + . Any computation that is independent of
the new instance can be moved out of its scope. Notice
that we can derive from the second equation, by setting
the famous equation:
new c -x: a = a (6)
which has been discussed in various papers on semantics of
local variables [31, 32, 40]. Compilers (implicitly) use these
kinds of equations to enlarge or contract the scope of local
variables and to eliminate "dead" variables. By formally
introducing classes as a feature, we are able to generalize
them for all classes.
In [50,

Appendix

Reynolds suggests encoding classes
as their corresponding "new" operators. This involves the
cls
(class ' fields C x methods M init
new C -x: A; p(M)
new
3 Note that these axioms are equations of lambda calculus, not
equational schemas. The symbols c; a;
can never be substituted by terms that capture bound identifiers. For
instance, in equation (2), a cannot be substituted by a term that has
x occurring free.
For instance, the class Counter would be encoded as an
tunately, arbitrary functions of this type do not satisfy the
axioms of new listed above. (This means that Reynolds's
encoding does not give a fully abstract translation from
IA + to Idealized Algol.) Our treatment can be seen as a
formalization of the properties intrinsic to "new" operators
of classes.
2.2 Specifications
An ideal framework for specifying classes in IA + is the specification
logic of Reynolds [52]. Specification logic is a theory
within (typed) first-order intuitionistic logic (and, hence, its
name is somewhat a misnomer). We use the intuitionistic
connectives "&", "=)", "8" and "9". The types include
those of Idealized Algol and an additional base type assert
for assertions (state-dependent classical logic formulas). The
atomic formulas of specification logic include:
ffl Hoare triples, fPg A fQg, for command A and assertions
P and Q, and
ffl non-interference formulas, A #; B, where A and B are
terms of arbitrary types.
Note that assertions form a "logic within logic." One can
use classical reasoning for them even though the outer logic
is intuitionistic. A non-interference formula A # B means
intuitively that A and B do not access any common storage
locations except in a read-only fashion. definition
of the property uses a possible-world semantics [41].) We use
a symmetric non-interference predicate (from [38]), which is
somewhat easier to use than the original Reynolds's version.
The proof rules for the non-interference predicate are the
are the free identifiers of A and B respectively).
2. A # B if both A and B are of "passive" types.
3. A # B if either A or B is of a "constant" type.
Passive types are those that give exp[ffi]-typed values and
constant types are those that give val[ffi]-typed values. See


Appendix

A for further discussion. The effect of the non-interference
predicate is best illustrated by the proof rule:
which states that two non-interfering commands can be freely
reordered. The survey article of Tennent [58] has a detailed
description of specification logic.
For handling IA + , we extend specification logic with cls
types and a new formula of the form:
Inst C x: OE(x)
where C is a class, x an identifier (bound in the formula)
and OE(x) is a formula. The meaning is that all instances
x of class C satisfy the formula OE(x). An example is the
following specification of the variable class:
Inst Var[ffi] x.
Inst Queue q.
8x,y: val[int]. 8g: exp[int] ! comm. g # q =)

Figure

3: Equational specification of a queue class
Inst Queue q.
9elems: list val[int] ! assert.
8k: val[int]. 8s: list val[int].
ftrueg q.init felems([ ])g

Figure

4: Hoare-triple specification of queues
Thus, the Hoare logic axiom for assignment becomes an
axiom of the variable class. One can also write equational
specifications for classes. For example, consider the specification
of counters by:
Inst Counter x.
The quantified function identifier g plays the role of a "con-
version" function, to convert expressions into commands. As
a less trivial example, an equational specification of a Queue
class is shown in Fig. 3. Its structure is similar to that of
the Counter specification.
Specification logic allows the use of both equational reasoning
and reasoning via Hoare-triples. The choice between
them is a matter of preference, but Hoare-like reasoning
is better understood and is often simpler. As illustration,
we show in Fig. 4, a Hoare-triple specification of Queue.
The specification asserts the existence of an elems predicate
representing an abstraction of the internal state of the queue
as list. (We are using an ML-like notation for lists.) Note
that the logical facilities of specification logic allow us to
specify the exitence of an abstraction function which would
be implementation-dependent.
For example, Fig. 5 shows an implementation of the
Queue class using "unbounded" arrays. 4 To show that it
meets the Hoare-triple specification, we pick the predicate:
A Queue-state represents a queue with elements
and the list of array elements between f +1 and r is s. Note
that the predicate incorporates both the "representation
invariant" and the "representation function" in America's
terminology [5]. In fact, all of America's theory for class
specifications is implicit in specification logic.
4 We are using "unbounded" arrays as an abstraction to finesse
the technicalities of bounds. Clearly, both the specification and
the implementation of Queue can be modified to deal with bounded
queues.
class queue
fields (UnboundedArray Var[int]) a;
methods
init (f := 0; r :=

Figure

5: An implementation of queues
Specification logic is also able to express "history proper-
ties" recommended by Liskov and Wing [30]. For example,
here is a formula that states that a counter's value can only
increase over time:
Inst Counter x.
Using Inst-specifications, we formulate the following proof
rule for new declarations:
Inst C x: OE(x)
/(new C g)
where x does not occur free in any undischarged assump-
tions, the terms A i and the formula /(\Gamma). This states that,
to prove a property / for (newC g), we need to prove / for
(g x), where x is an arbitrary instance of C, assuming the
specification OE(x) and the fact that x does not interference
with anything unless C interferes with it. The terms A i can
be any terms whatever but, in a typical usage of the rule,
they are the free identifiers of /(gx). These non-interference
assumptions arise from the fact that x is a "new" instance.
The rule for inferring Inst-specifications is:
Inst C z: /(z)
OE(M)
Inst (class ' fields C z init A methods M) x: OE(x)
where z does not occur free in any undischarged assump-
tions, the terms A i and the formula OE(\Gamma).
Inst-specifications are not always adequate for capturing
the entire behavior of class instances. Since they specify
the behavior of instances in arbitrary states, they miss the
specification of initial state and the final state transforma-
tions. Additional axioms involving new-terms are necessary
to capture these aspects. For example, the Counter class
satisfies the following "initialization" axiom:
new Counter -x. g(x.val); h(x)
new Counter -x. g(0); h(x)
which specifies that the initial value of a counter is 0. The
"finalization" axiom:
new Counter -x. g(x); h(x.inc)
new Counter -x. g(x); h(skip)
states that any increment operations done just before deallocation
are redundant.
The denotational semantics of IA brings out important
properties of classes and objects. We consider two styles of
semantics: parametricity semantics along the lines of [42],
which highlights the data abstraction aspects of classes, and
object-based semantics along the lines of [49], which highlights
the class-instance relationship.
3.1 Parametricity semantics
As pointed by Reynolds [53], parametricity has to do fundamentally
with data abstraction. Since classes incorporate
data abstraction, one expects parametricity to play a role
in their interpretation. We follow the presentation of [42,
Sec. 2] in our discussion. In particular, we ignore recursion
and curried functions. The later discussion in [42] in handling
these features is immediately applicable.
A type operator T over a small collection of sets S is a
ffl the "set part" T set assigns to each set X 2 S, a set
set (X), and
ffl the "relation part" T rel assigns to each binary relation
(We normally write both T set and T rel as simply T , using
the context to disambiguate the notation.) Similarly, n-ary
type operators with n type variables can be defined.
The type operators for constant types, variable types,
product and function space constructors are standard. For
example, for the function space constructor, we have the
relation part:
The relation part for a constant type K is the identity
relation, denoted \Delta K . We define quantified type operators
for a universal quantifier 8 and an existential quantifier 9:
ffl The type operator 8Z: T (X; Z) represents parametrically
polymorphic functions p with components pZ 2
Formally, its set part consists of all S-indexed
families fpZgZ2S such that, for all relations S: Z
Its relation part, which can be
written as 8S: T (R; S) for any R: X defined
by
Z gZ2S
ffl The operator 9Z: T (X; Z) represents data abstractions
that implement an abstract type Z with operations of
type T (X; Z). To define it formally, consider "imple-
mentation" pairs of the form hZ; pi where Z 2 S and
Two such implementations are said to
be similar, hZ; pi - hZ there exists a relation
(Any such relation S is termed a simulation.) The
set part 9Z: T (X; Z) consists of equivalence classes of
implementations under the equivalence relation -   .
Write the equivalence class of hZ; pi as hjZ; pji. The
relation part 9S: T (R; S) for any relation R: X
is the least relation such that
The basic reference for parametricity is Reynolds [53], while
Plotkin and Abadi [45] define a logic for reasoning about
parametricity. The notion of existential quantification is
from [35], but the parametricity semantics is not mentioned
there. The idea of simulation relations for abstract type
implementations dates back to Milner [33] and appears in
various sources including [9, 27, 25, 36, 54].
The types ' of IA are interpreted as type operators [[']]
in the above sense. The parameters for the type operators
are state sets. Typically they capture the states involved
in the representation of objects. The relation parts of the
operators specify how two values of type ' are related under
change of representation. Here is the interpretation:
Note that the meaning of a class is a data abstraction. It
involves a state set Z for the internal state of the instances,
a component of type [[']](Q \Theta Z) for the methods of the class
and a component of type Z for the initial state. Two such
implementations with internal state sets Z and Z 0 are similar
(and, hence, equivalent) if, for some relation S: Z $ Z 0 , the
initial states are related by S and their methods "preserve"
S according to the relation
For example, consider the following class as an alternative
to Counter:
st
methods
The meanings of Counter and Counter2 can be calculated
as follows:
The two implementations are similar because there is a simulation
relation S: Int $ Int given by
\Gamman
which is preserved by the two implementations. Hence, the
two abstractions (equivalence classes) are equal:
Thus, the parametricity semantics gives an
extremely useful proof principle for reasoning about equivalence
of classes.
The interpretation of terms is as follows. A term M of
function
We write [[M the component of [[M at Q. The semantics
of Algol phrases is as in [42]. An important point to
recall from that paper, Sec. 3.2, is the fact that parametricity
makes available certain "expand" functions:
expand
For every value v 2 [[']](Q), there is a unique expanded value
in [[']](Q\ThetaZ) that acts the "same way" as v does. We use the
abbreviated notation v " Q\ThetaZ
Q to denote expand ' [Q; Z](v).
For example, if the expanded
command
leaves the Z component unchanged. These expand functions
play a crucial role in interpreting instance declarations and
inheritance. They also have significance in interpreting con-
stants. A "constant value" in [[']](Q) is a value of the form
Qobtained by expanding a value in the unit state set.
So, we only need to specify the interpretation of a constant
in the unit state set.
The semantics of class constructs is as follows:
fields C x methods M init
-q: fst (pZ (m)(q; z))
where hjZ; (m;
A class definition builds an abstract type as illustrated with
Counter above. The new operator "opens" the abstract
type and passes to the client procedure P the representation
and the method suite of the class. Thus, an "instance"
is created. Note that, in the normal case where P is an
abstraction -x: M , its meaning is \LambdaZ: -m:
the body term M will now use the expanded
state set Q \Theta Z. Every time the class C is instantiated, a
new Z component is added to the state set in this fashion.
Thus, every "opening" of the abstract type gives rise to a
new instance with its own state component that does not
interfere with the others.
In comparing this operation with the object encoding
proposed by Pierce, Turner and others [44, 12], we note that
they treat objects as abstract types whereas we treat classes
as abstract types. Thus, some of the bureaucratic opening-
closing code that appears in their model is finessed here.
Message send in our model is simply the field selection of a
record. Nevertheless, the idea of abstract types appears in
both the models, and the implications of this commonality
should be explored further.
The class constants have the following interpretation:
init
hjZ1 \Theta Z2 ; ((m 0
The Var[ffi] class denotes a state set [[ffi]] with get and put
operations on it. The   operator combines two classes by
joining their state sets. The method suites of the individual
classes are expanded to operate on the combined state set.
Theorem 1 The parametricity model satisfies all the equivalences
and axioms of Sec. 2.1.
The plain parametricity semantics described above does
not handle the equality relation in a general fashion. In
implementing data abstractions, it is normal to allow the
same abstract value to be represented by multiple concrete
representations. In our context, this means that the equality
relation for abstract states is, in general, not the same as
the equality relation for concrete states. It corresponds to a
partial equivalence relation (per) for concrete states [24].
For example, in the Queue implementation of Fig. 5, an
empty queue is represented by any state in which f and r
are equal. The second axiom of the equational specification
(Fig. does not hold in this implementation. (The left
hand side gives a state with the right
hand side gives a state with
This can be remedied by modifying the parametricity
semantics to a parametric per semantics, where each type
carries its own notion of equality. 5 More formally, A "type"
in the new setting (called a per-type) is a pair
where X is a set and EX is a per over X representing the
notion of equality for X. All the above ideas can be modified
to work with per-types. (See Appendix B.)
The per semantics influences reasoning about programs
as follows. Suppose we obtain a package hhZ; \Delta Z
9Z: T (X; Z) as the meaning of a class. If p preserves some
per EZ in the sense that p T then we have
Thus, we are at liberty to make up any per EZ that is
preserved by p and use it as the equality relation for the
representation.
For example, for the Queue class of Fig. 5, the state set Z
consists of triples ha; f; ri where a: Int ! Int and f; r 2 Int .
We pick the equivalence relation EZ given by:
ha; f; ri EZ ha
- map a (f
to represent the intuition that only the portion of the array
between f +1 and r contains meaningful values. In verifying
the axioms of queues, we interpret =comm as the per for
5 It does not seem possible to obtain the information of this
semantics from the plain parametricity semantics because quantified
type operators do not map per's to per's in general.
inc.*
val.1
val.2
inc.*
inc.*

Figure

Trace set of a counter object
\Theta Z), viz., [EQ \Theta EZ ! EQ \Theta EZ ]. (EQ is some
per for Q respected by the other variables like g.) Here is the
verification of the problematic second axiom. The two sides
of the equation denote the respective state transformations:
It is clear that they are equivalent by the relation [EQ \Theta
3.2 Object-based semantics
The object-based semantics [49, 39] (see also [4]) treats objects
as state machines and describes them purely by their
observable behavior. The observable behavior is given in
terms of event traces whose structure is determined by the
type of the object. This is similar to how processes are
described in the semantics of CSP or CCS. Since no internal
states appear in the denotations, proving the equivalence
of two classes reduces to proving the equality of their trace
sets.
Before looking at formal definitions, we consider an example

Figure

6 depicts the trace set of a counter object
in its initial state. The events for this object are "inc. "
denoting a successful completion of the inc method, and
"val.i" denoting a completion of the val method with the
result i (an integer). The nodes can be thought of as states
and events as state transitions. Note that a val event does
not change the state whereas an inc event takes the object
to a state with a higher val value. For discussion purposes,
we can label each node with an integer (which might well
be the same integer given by val ). The trace set can then
be described mathematically by a recursive definition:
The parameter of the CNT function is the label of the state.
Note that these labels can be anything we make up, but it
often makes sense to use labels that correspond to states in
an implementation. For instance, here is another description
of the same trace set using negative integers for labels:
This description corresponds to the class Counter2. While
it is obvious that the two trace sets are the same, a formal
proof would use the simulation relation S defined in (9). We
can show by fixed point induction that
and it follows that
Note that in this description there is virtually no difference
between classes and instances. A class determines a
trace set which is then shared by all instances of the class.
The specification equations of classes can be directly verified
in the trace sets. For example, the equation x.inc;
g(x.val of the Counter class is verified by noting
that
for all states n.
The object-based semantics, described in [47, 39], makes
these ideas work for Idealized Algol. For simplicity, we consider
a version of Idealized Algol with "Syntactic Control of
Interference", where functions are only applied to arguments
that they do not interfere with.
We start with the notion of a coherent space [22], which
is a simple form of event structure [59]. A coherent space
is a pair A = (jAj; -A ) where A is a (countable) set and
-A is a reflexive-symmetric binary relation on jAj. The
elements of jAj are to be thought of as events for the objects
of a particular type. The relation -A , called the coherence
relation, states whether two events can possibly be observed
from the same object in the same state.
The free object space generated by A is a coherent space
A  is the set of sequences over jAj
("traces") and -A   is defined by
This states that, after carrying out a sequence of events
the two traces must have coherent events at
position i. If a then the same condition applies to
position then the two events lead to
distinct states and, so, there is no coherence condition on
future events.
An element of a coherent space A is a pairwise coherent
subset x ' jAj. So, the elements of object spaces denote
trace sets for objects. Functions appropriate for object
spaces are what are called regular maps
It turns out that they can be described more simply in
terms of linear maps F : A   ! B. We actually define
"multiple-argument linear maps" because they are needed
for semantics. A linear
jBj such that, whenever
(~s;
Every such linear map denotes a multiple-argument regular
Coherent spaces for the events of various Idealized Algol
types are shown in Figure 7. The trace sets for objects of
type ' are elements of [[']]   . Since we have a state-free description
of objects, there is virtually no difference between
jA1 \Theta A2

Figure

7: Coherent spaces of events for IA types
objects and classes. The only difference is that a class can
be used repeatedly to generate new instances. So, a trace of
a class is a sequence of object traces, one for each instance
generated. Therefore, we define
The meaning of a term x1 :
multiple-argument linear map
We regard a vector of traces ~s 2 j[[' 1 ]]j
a record j 2 \Pi x i
. So, the linear map [[M is a set
of pairs (j; a), each of which indicates that, to produce an
event a for the result, the term M carries out the event
traces on the objects for the free identifiers.
The interpretation of interference-controlled Algol terms
is as in [49]. The interpretation of class terms is as follows:
fields C x methods M init
The meaning of the class term says that the trace set of C
must have a trace s0s1 where s0 represents the effect of the
initialization command A. If the methods term M maps the
trace s1 2 j[[- ]]j   to a trace s 2 j[[']]j   , then s is a possible
trace for the new class. The meaning of new C P finds a
trace s supported by C such that P is ready to accept an
object with this trace. Of course, C supports many traces.
But, P will use at most one of these traces.
Theorem 2 The object-based model satisfies all the equivalences
and axioms of Sec. 2.1, adapted to a version of IA
with Syntactic Control of Interference.
4 Modularity issues
In this section, we briefly touch upon the higher-level modularity
issues relevant to object-oriented programming. Further
work is needed in understanding these issues.
4.1 Types and classes
In most object-oriented languages, the notion of types and
classes is fused into one. Such an arrangement is not feasible
in IA because classes are first-class values and their equality
is not decidable. For example, the classes (array c n)
and (array c 0 n 0 ) are equal only if n and n 0 are equal. Such
comparisons are neither feasible nor desirable. However,
a tighter integration of classes with types can be achieved
using opaque subtypes as in Modula-3, also called "partially
abstract" types [21]. For example, the counter class may be
defined as:
newtype counter !: finc: comm, val: exp[int]g
in
class counter .
A client program only knows that counter is some subtype
of the corresponding signature type and that Counter is of
type cls counter . The class Counter, on the other hand, is
inside the abstraction boundary of the abstract type counter,
and regards it as being equal to the signature type.
We can specify requirements for partially abstract types.
For example, the specification:
8x: counter.
states that every value of type counter - not just an instance
of some class - is monotonically increasing. All
reveal blocks of the type counter get a proof obligation to
demonstrate that their use of the type counter satisfies the
specification. For example, if we use reveal blocks to define
classes Counter and Counter2, we have the job of showing
that their instances are monotonically increasing. Note that
such partially abstract types correspond to what America [5]
calls "types."
4.2 Inheritance
is a typed lambda calculus with records, most
inheritance models in the literature can be adapted to it.
For illustration, we show the recursive record model [13, 15,
46]. A class that uses self-reference is defined to be of type
cls instead of cls ', so that the method suite is
parameterized by "self." We have a combinator
close: cls
close class ' fields c f methods fix f init skip
which converts a self-referential class c to a class whose
instances are ordinary objects.
Let c be of type cls (' ! '). To define a derived class of
is a record type extension,
we use a construction of the form:
class
fields c f; .
methods -self. (f self) with[-
init A
where with is a record-combination operator [16]. (The
with operator is qualified by the type - to indicate the
record fields that get updated. This is needed for coherence
of subtyping.)
As an example, suppose we define a variant of the Counter
class that provides a set method in a "protected" fashion:
type protected counter =
counter \Phi fset: val[int] ! commg
protected counter
in
class counter ! counter
fieldsVar[int] cnt
methods
-self.
We can then define a derived class that issues warnings
whenever the counter reaches a specified limit:
protected counter
in
Warn Counter
class counter ! counter
fields Counter f
methods
-self. (f self) with[set:.
print "Limit reached";
(f self).set kg
init skip
Note that both (close Counter) and (close Warn Counter)
are of type cls counter. Their instances satisfy the specification
of counter, including its history property. The set
method does not cause a problem because it is inaccessible
to clients.
The proof principle for self-referential classes is derived
from fixed-point induction:
(Inst c f: 8x: OE(x) =) OE(f(x)))
Inst (close c) x: OE(x)
For example, both
lim) satisfy:
Inst (close C) x.
8k: val[int]. 8p: exp[int] ! assert.
4.3 Dynamic Objects
Typical languages of Algol family provide dynamic storage
via Hoare's [26] concept of ``references'' (pointers). An
object created in dynamic storage is accessed through a
reference, which is then treated as a data value and becomes
storable in variables. Some of the modern languages, like
Modula-3, treat references implicitly (assuming that every
object is automatically a reference). But it seems preferable
to make references explicit because the reasoning principles
for them are much harder and not yet well-understood.
To provide dynamic storage in IA + , we stipulate that,
for every type ', we have a data type ref '. The operations
for references are roughly as follows:
The rule for newref is not sound in general. Since references
can be stored in variables and exported out of their scope,
they should not refer to any local variables that obey the
stack discipline. If and when the local variables are deallo-
cated, these references would become "dangling references".
A correct type rule for newref is given in Appendix A.
Our knowledge of semantics for dynamic storage is rather
incomplete. While some semantic models exist [55, 56], it
is not yet clear how to integrate them with the reasoning
principles presented here.
5 Conclusion
Reynolds's Idealized Algol is a quintessential foundational
system for Algol-like languages. By extending it with objects
and classes, we hope to provide a similar foundation
for object-oriented languages based on Algol. In this paper,
we have shown that the standard theory of Algol, including
its equational calculus, specification logic and the major
semantic models, extends to the object-oriented setting. In
fact, much of this has been already implicit in the Algol
theory but perhaps in a form accessible only to specialists.
Among the issues we leave open for future work are
a more thorough study of inheritance models, reasoning
principles for references, and investigation of call-by-value
Algol-like languages.

Acknowledgments

It is a pleasure to acknowledge Peter
O'Hearn's initial encouragement in the development of
this work as well as his continued feedback. Bob Tennent,
Hongseok Yang and the anonymous referees of FOOL 5
provided valuable observations that led to improvements in
the presentation. Thanks to Martin Abadi for explaining the
intricacies of per semantics. This research was supported
by the NSF grant CCR-96-33737.


Appendix


A Reflective type classes
In the type rules of section 2.1, the initialization command
of a class was restricted to only the local fields of the class.
While this restriction leads to clean reasoning principles:
the (fl) law and equations (2-6), it is too restrictive to be
practical. For instance, a counter class parameterized by
an initial value n does not type-check under this restriction
because its init command has free occurrences of n.
A reasonable relaxation of the restriction is to allow the
initialization command to read storage locations, but not to
write to them. This kind of restriction is also useful in other
contexts, e.g for defining "function procedures" that read
global variables but do not modify them [58, 56].
The use of dynamic storage involves a similar restriction.
A class used to instantiate a dynamic storage object should
not have any references to local store. We define a general
notion that is useful for formalizing such restrictions.
reflective type class is a set of type terms
T such that
1.
2.
3.
The terminology is motivated by the fact that these classes
can be interpreted in reflective subcategories of the semantic
category [48].
We define several reflective type classes based on the
following intuitions. Constant types involve values that are
state-independent; they neither read nor write storage loca-
tions. (Such values have been called by various qualifications
such as "applicative" [56], "pure" [37], and "chaste" [57]).
Dually, state-dependent types involve values that necessarily
depend on the state. Values of passive types only read
storage locations, but do not write to them (one of the senses
of "const" in C++). Values of dynamic types access only
dynamic storage via references.
We add three new type constructors Const, Pas and Dyn
which identify the values with these properties even if they
are of general types.
A value of type Const' is a '-typed value that has been built
using only constant-typed information from the outside. So
it can be regarded as a constant value.
We define the following classes as the least reflective
classes satisfying the respective conditions:
1. Constant types include val[ffi] and Const ' types.
2. State-dependent types include exp[ffi] and comm, and
are closed under Const, Pas and Dyn type constructors.
3. Passive types include val[ffi], exp[ffi], Const ' and Pas '
types.
4. Dynamic types include val[ffi]; Const ' and Dyn ' types.
said to be T -used in M if every free occurrence of x is
in a subterm of M with a T -type. (In particular, we say
"constantly used", "passively used", and "dynamically used"
for the three kinds of usages.)
The introduction rules for Const, Pas, and Dyn are as
follows:
is constantly-used in M and
there are no occurrences of ".
Const '
are passively used in M .
dynamically used in M .
The dereference operator (") is treated as if it were an
-used means that every identifier in \Gamma is
T -used. For the elimination of these type constructors, we
use the subtypings (for all types '):
Const ' !: Pas ' !: '
Const ' !: Dyn ' !: '
Note that any closed term can be given a type of the
Const '. For example, the counter class of Section 2
has the type Const (cls counter ).
Application to class definitions The type rule for classes
is now modified as follows:
fields C x methods M init
passively used in
This allows the free identifiers \Gamma to be used in A, but in a
read-only fashion. The parametricity interpretation of cls-
type must be modified to [[cls
Z]. The rest of the theory remains the same, except that
the equation (2) becomes conditional on non-interference:
c # a =) new c -x: a;
Application to references We use the following rule for
creating references:
The rule ensures that the class instantiated in the dynamic
store does not use any locations from the local store, so the
instance will not use them either. This avoids the "dangling
reference" problem.
B Semantics of specifications
In this section, we consider the issue of interpreting specifi-
cations. This raises two issues. First, the non-interference
formulas in specifications require a sophisticated functor category
interpretation [57, 41] whose relationship to the parametricity
interpretation is not yet well-understood. It is
however possible to interpret restricted versions of specifi-
cations, those in which 8-quantified identifiers are restricted
not to interfere with any other free identifiers. Note that
the queue specification in Fig. 3 is of this form. The second
issue, discussed in Section 3.1, is that the equality relation
of specifications must be general enough to be refined by
implementations.
To allow for equality relations to be refined in implemen-
tations, we define a parametric per semantics for IA + . The
basic ideas are from Bainbridge et al. [7]. (See also [8].) We
adapt them to a predicative polymorphic context. A per E
over a set X is a symmetric and transitive relation. (It differs
from an equivalence relation in that it need not be reflexive.)
The domain of E is defined by x 2 dom(E)
Note that E reduces to a (total) equivalence relation over
dom(E). The set of equivalence classes under E is denoted
Q(E). See [34, Sec. 5.6] for discussion of per's.
A "type" in the new setting (called a per-type) is a pair
is a set and EX is a per over X.
The per specifies the notion of "equality" for the type. A
is an ordinary relatin
(called a saturated
relation).
A "type operator" is a pair hTper ; T rel i of mappings for
per-types and saturated relations. The per-type operators
for products and function spaces are as follows:
R \Theta
Assume that S is a small collection of per-types. We are
interested in per-type operators over S. These operators
Inst C x: OE () 9hZ; hp; z0ii -

Figure

8: Interpretation of specifications
inherit product, sum and function space constructors from
the above notions. We define type quantifiers as follows:
ffl The per-type operator 8Z: T (X; Z) maps a per-type
X to the per-type h
The set consists of families indexed by Z 2 S. The
per equates two families p and p 0 if for all saturated
relations S: Z
Z 0 . The
relation part of the operator maps a saturated relation
ffl The per-type operator 9Z: T (X; Z) maps a per-type
X to the per-type h
given by
The relation part of the operator maps a saturated
relation R: X
Comparing this to the plain parametricity semantics of Section
3.1, we note that per's take the place of the identity
relations.
Theorem 5 Every type operator
types to per-types and saturated relations R
i to
saturated relations T
The proof is similar to that in [8].
The interpretation of IA + is exactly the same as in plain
parametricity semantics except that the type operators are
now understood to be per-type operators. The interpretation
of specifications is shown in Fig. 8. A judgment
of the form Q; j means that the formula OE with free
holds in the state set Q and environment j 2
dom([[\Gamma]](E Q )).



--R

An imperative object calculus.
A Theory of Objects.
A logic of object-oriented programs
Linearity, sharing and state.
Designing an object-oriented programming language with behavioural subtyping

Functorial polymorphism.

Refinement of concurrent object-oriented programs
Mathematical Foundations of Programming Semantics: Eleventh Annual Conference

Comparing object encodings.
A semantics of multiple inheritance.
FUDGETS: A graphical user interface in a lazy functional language.
A Denotational Semantics of Inheritance.
Inheritance is not subtyping.
An Algol-based simulation language
A calculus for concurrent objects.
An interpretation of typed OOP in a language with state.

On the relationship between classes
Proofs and Types.
Theoretical Aspects of Object-Oriented Programming
Abstract data types and software validation.
Data refinement refined.
Record handling.
An axiomatic approach to binary logical relations with applications to data refinement.
Reasoning and refinement in object-oriented specification languages
Modular specification and verification of object-oriented programs
A behavioral notion of subtyping.
Axiomatizing operational equivalence in the presence of side effects.
Towards fully abstract semantics for local variables.
An algebraic definition of simulation between programs.
Foundations of Programming Languages.
Abstract types have existential types.
On the Refinement Calculus.
Call by name
Syntactic control of interference revisited.
Objects, interference and Yoneda embedding.
Semantics of local variables.
Semantical analysis of specification logic


Simple type-theoretic foundations for object-oriented programming
A logic for parametric polymorphism.
Objects as closures: Abstract semantics of object-oriented languages
Global state considered unnecessary: Semantics of interference-free imperative programming
Passivity and independence.
Global state considered unnecessary: An introduction to object-based semantics
Syntactic control of interference.
The essence of Algol.
Idealized Algol and its specification logic.
Types, abstraction and parametric poly- morphism
Behavioral correctness of data representations.
Categorical models for local names.
Assignments for applicative languages.
Semantical analysis of specification logic.
Denotational semantics.
An introduction to event structures.
--TR
A semantics of multiple inheritance.
Structure and interpretation of computer programs
Communicating sequential processes
On understanding types, data abstraction, and polymorphism
Event structures
Abstract types have existential type
Objects as closures: abstract semantics of object-oriented languages
Communication and concurrency
Proofs and types
Inheritance in smalltalk-80: a denotational definition
Towards fully abstract semantics for local variables
A sound and complete axiomatization of operational equivalence of programs with memory
Semantical analysis of specification logic
Behavioural correctness of data representations
Inheritance is not subtyping
Call by name, assignment, and the lambda calculus
Theoretical aspects of object-oriented programming
Two semantic models of object-oriented languages
A behavioral notion of subtyping
Parametricity and local variables
Denotational semantics
An interpretation of typed OOP in a language
Positive subtyping
An imperative object calculus
ALGOL-like languages (v.2)
Assignments for applicative languages
On the relationship between classes, objects, and data abstraction
Semantics of dynamic variables in Algol-like languages
SIMULA: an ALGOL-based simulation language
Syntactic control of interference
A Theory of Objects
On the Refinement Calculus
Modular Specification and Verification of Object-Oriented Programs
Data Refinement Refined
Comparing Object Encodings
A Logic for Parametric Polymorphism
Reasoning and Refinement in Object-Oriented Specification Languages
An Imperative, First-Order Calculus with Object Extension
A Logic of Object-Oriented Programs
A Calculus for Concurrent Objects
An introduction to event structures
Designing an Object-Oriented Programming Language with Behavioural Subtyping
Abstraction
A denotational semantics of inheritance

--CTR
Bernhard Reus , Thomas Streicher, Semantics and logic of object calculi, Theoretical Computer Science, v.316 n.1-3, p.191-213, 28 May 2004
Uday S. Reddy , Hongseok Yang, Correctness of data representations involving heap data structures, Science of Computer Programming, v.50 n.1-3, p.129-160, March 2004
Bernhard Reus , Jan Schwinghammer, Denotational semantics for a program logic of objects, Mathematical Structures in Computer Science, v.16 n.2, p.313-358, April 2006
Matthew Parkinson , Gavin Bierman, Separation logic and abstraction, ACM SIGPLAN Notices, v.40 n.1, p.247-258, January 2005
Anindya Banerjee , David A. Naumann, Ownership confinement ensures representation independence for object-oriented programs, Journal of the ACM (JACM), v.52 n.6, p.894-960, November 2005
relational parametricity;semantics;algol-like languages;object-oriented programming;specification logic