
© Jørgen SteensgaardMadsen, Copenhagen, 2006

Abstract data structures and control



The notion of a class originates from attempts to find language
expressions to support abstract data structures. A class is a means
to generate objects, each of which may have an internal state that can
be manipulated only through use of member functions. A class also has
a rôle similar to that of a type, since object instantiations may
appear like typed variable declarations and functions may return
(references to) objects of a specified class. A plethora of other
attributes are associated with the notion of a class.
The notion of a continuation of a function application is sometimes
described as `the rest of the program'. This is far too liberal in
our opinion, because its extent is essentially unlimited. It could as
well be `the rest of the current routine'. With a limit, it is
possible to associate a cleanup action when the limit is reached.
Researchers on the borderline between programming and formal logic
have pointed out a relation between the type of abstract data
structures and the logic of existence. Of two possible
characterisations of the existential quantifiers in an appropriate
logic, the more complex one corresponds best to the notion of a class
as a generator of objects.
Independently of the results on existence, we have previously argued
that the mechanisms of appropriate block structured languages, that
support definition of routines inside others and use of such as
arguments, need no extra mechanisms to support a useful notion of
abstract data structure. It was called a statementoriented
approach to data abstraction and later studies have revealed that
it is essentially identical to the simpler characterisation of the
existential quantifier.
The logic connection provides a nice way to explain our approach.
First we recall the usual definition of the existential quantifier in
terms of the universal
$x . F_{x} º Ø"x . ØF_{x}
A first step is to remove negation, for reasons that are irrelevant
here. Use of implication is more appropriate since it corresponds to
the operator of function types.
$x . F_{x} º ("x . F_{x} Þ false)Þ false
where the scope of a unversally bound variable, like x, is the
maximal expression to be recognised after the binding, i.e. it
includes the right hand side of the implication above.
Given an implication fÞy it is appropriate to
prescribe a corresponding type m(fÞy) as
m(f)®m(y), i.e.
m(fÞy) ~ m(f)®m(y)
Correspondingly, universal quantification matches abstraction over a
type, so
m($x . F_{x}) º m(("x . F_{x} Þ false)Þ false) ~ ([x]m(F_{x})®m(false))® m(false)
With m(false) ~ void we have that the
type of an abstract data structure might have the structure
([x]m(F_{x})®
void)®void
In words an abstract data structure is a routine with a routine as a
parameter. The parameter routine can be described as a continuation
that receives the access rights, with interface m(F_{x}), to
the abstract data structure.
The use of void is perhaps unpleasant. In a rather weak
higherorder logic one possible definition of the existential
quantifier is
$x . F_{x} º "w . ("x . F_{x} Þ w)Þ w
with a matching type
[w]([x]m(F_{x})® w)® w
Note that the given types cannot be expressed with the type system of
SML.
The statementoriented approach suggested the construction of routines
with descriptions as given by the function types above. The logic
connection was unknown to us at the time, and the suggestion was made
solely on grounds of feasibility and several experiences from using
the technique.
Existential quantification as defined above is known colloquially as
weak existence with strong existence as its obvious
counterpart. Both definitions allow the same fundamental inference
rule, but a strong existence may allow additional rules. Some find
such additional rules essential, but we have found no arguments for
them convincing.
A key point in our approach is explicit continuations, i.e. parts of
the program text that agrees with its syntactic composition. The
qualifier `explicit' is used to distinguish it from the possible use
of implicit continuations to explain the semantics of the programming
language. The latter are implicit, since they are not visible
(obviously because the notion of continuations need not be used to
describe the semantics).
We shall identify the scope of members of an object with the object's
explicit continuation. In outline the scope is the text that follows
the object instantiation in the innermost surrounding brace.
{ ...
myclass myobject();
... myobject.member1(); ...
}
We propose an analogy to control structures that makes a class into an
operation that can be called with an explicit continuation, e.g.
myclass myobject() { ... myobject.member1(); ... }
It is a simple, purely syntactic problem to identify the explicit
continuation when it is not enclosed in braces, so both forms is
allowed at the expense of error identification.
Obviously this presentation ignores important aspects of
objectorientedness, as for instance inheritance and subtyping. We do
not claim to have a replacement for classes and objects, only
something that is similar in certain respects, and on the other hand
comes with some nice additional properties that are unique.
Control operations with more than one explicit continuation are
useful. The simplest one is the ifthenelse operation with the true
and false branches considered as continuations. The set of members
associated with either of these two branches is empty, but useful
examples with nonempty and nonidentical sets exist. Also the
operation of a while statement has two continuations, the condition
and the iterand, with empty sets of members. But again it is only a
matter of imagination to find more interesting examples where some
explicit continuations get evaluated repeatedly: variations of
operations to build a sequence to be sorted and subsequently scanned.
Contents
File translated from
T_{E}X
by
T_{T}H,
version 3.33.
 On 18 Oct 2006, 16:47.

 