© Jrgen Steensgaard-Madsen, 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 statement-oriented 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 . Fx "x . Fx
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 . Fx ("x . Fx 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 fy it is appropriate to prescribe a corresponding type m(fy) as m(f)m(y), i.e.
m(fy) ~ m(f)m(y)
Correspondingly, universal quantification matches abstraction over a type, so
m($x . Fx)  m(("x . Fx false) false) ~ ([x]m(Fx)m(false)) m(false)
With m(false) ~ void we have that the type of an abstract data structure might have the structure
([x]m(Fx) 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(Fx), to the abstract data structure.
The use of void is perhaps unpleasant. In a rather weak higher-order logic one possible definition of the existential quantifier is
$x . Fx "w . ("x . Fx w) w
with a matching type
[w]([x]m(Fx) w) w
Note that the given types cannot be expressed with the type system of SML.
The statement-oriented 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 object-orientedness, 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 if-then-else 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 non-empty and non-identical 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.


Demo language
Implementation tool

Interpreter construction

Deep- and surface structures
Design issues
Abstract type operatorss
Description of operator
Name introduction
Data abstraction and control

File translated from TEX by TTH, version 3.33.
On 18 Oct 2006, 16:47.
SourceForge.net Logo