object-oriented =
objects + classes + inheritance
data abstraction -- state accessible by operations
strong typing -- compile time checking
slide: Object-based versus object-oriented
In this section we will look at the arguments presented in [Wegner87]
in somewhat more detail.
Also, we will look at the viability of combining seemingly
disparate paradigms (such as the logic programming paradigm)
with the object-oriented language paradigm.
In the sections that follow, we will discuss some alternatives and extensions to
the object model.
\label{object-based}
How would you characterize Ada83? See [Barnes94].
Is Ada object-oriented?
And Modula-2?
See [Wirth83].
The answer is no and no.
And Ada9X and Modula-3?
See [Barnes94] and [Card89].
The answer is yes and yes.
In the past there has been some confusion
as to when to characterize a language as
{\em object-oriented}.
For example, [Booch86] characterizes Ada as
object-oriented and motivates this by saying that Ada
can be used as an implementation language in
an object-oriented approach to program development.
Clearly, Ada supports some notion of objects (which
are defined as packages).
However, although Ada supports objects and generic descriptions
of objects (by generic packages), it does not support
code sharing by inheritance.
In a later work, [Booch91] revises his original (faulty)
opinion, in response to
[Wegner87], who proposed considering inheritance
as an essential characteristic of object orientation.
Similarly, despite the support that Modula-2 offers
for defining (object-like) abstract data types,
consisting of
an interface specification and an implementation
(which may be hidden), Modula-2 does not support
the creation of derived (sub)types that share
the behavior of their base (super)type.
See also section [adt-modules].
Classes versus types
Another confusion that frequently arises
is due to the ill-defined relationship between
the notion of a class and the notion of a type.
The notion of types is already familiar
from procedural programming languages such as
Pascal and (in an ill-famed way) from C.
The type of variables and functions may be profitably
used to check for (syntactical) errors.
Strong static type checking may prevent errors
ranging from simple typos to using undefined
(or wrongly defined) functions.
The notion of a class originally has a more
operational meaning.
Operationally, a class is a template for object creation.
In other words, a class is a description of the collection
of its instances, that is the objects that are
created using the class description as a recipe.
Related to this notion of a class, inheritance was
originally defined as a means to share (parts of)
a description.
Sharing by (inheritance) derivation is, pragmatically,
very convenient.
It provides a more controlled way of code sharing
than, for example, the use of macros and file inclusion
(as were popular in the C community).
Since [Wegner87] published his original analysis
of the dimensions of object-oriented language design,
the phrase {\em object-oriented} has been commonly understood
as involving objects, classes and inheritance.
This is the traditional object model as embodied
by Smalltalk and, to a large extent, by Eiffel, C++ and Java.
However, unlike Smalltalk, both Eiffel and C++ have also been
strongly influenced by the abstract data type approach
to programming.
Consequently, in Eiffel and C++ classes have been identified
with types and derivation by inheritance with subtyping.
Unfortunately, derivation by inheritance need not necessarily
result
in the creation of proper subtypes,
that is classes whose instances conform to the behavior
specified by their base class.
In effect, derived classes may be only distantly related
to their base classes when inheritance is only
used as a code sharing device.
For example, a window manager class may inherit
from a list container class (an idiom used in Meyer, 1988).
Towards an orthogonal approach -- type extensions
According to [Wegner87], much of the confusion
around the various features of object-oriented
programming languages arises from the fact that
these features are largely interdependent,
as for instance the notion of object and class on
the one hand,
and the notion of class and inheritance on the other.
To resolve this confusion, [Wegner87] proposes
a more orthogonal approach to characterize the
various features of object-oriented languages,
according to dimensions that are to a large extent independent.
See slide [5-orthogonal].
Orthogonal approach
- objects -- modular computing agents
- types -- expression classification
- delegation -- resource sharing
- abstraction -- interface specification
slide: Orthogonal dimensions
The features that constitute an object-oriented
programming language in an orthogonal way are,
according to [Wegner87]: objects, types,
delegation and abstraction.
Objects
are in essence modular computing agents.
They correspond to the need for encapsulation in design,
that is the construction of modular units to
which a principle of locality applies (due to
combining data and operations).
Object-oriented languages may, however, differ in
the degree to which they support encapsulation.
For example, in a distributed environment a
high degree of encapsulation must be offered,
prohibiting attempts to alter global variables
(from within an object) or local instance
variables (from without).
Moreover, the runtime object support system must
allow for what may best be called remote method invocation.
As far as parallel activity is concerned, only a few languages provide
constructs to define concurrently active objects.
See section [Active] for a more detailed discussion.
Whether objects support reactiveness,
that is sufficient flexibility to respond safely
to a message, depends largely upon (program) design.
[Meyer88], for instance, advocates a {\em shopping list
approach} to designing the interface of an object,
to allow for a high degree of (temporal) independence
between method calls.
Types
may be understood as a mechanism for expression classification.
From this perspective, Smalltalk may be regarded
as having a dynamic typing system:
dynamic, in the sense that the inability to evaluate an expression
will lead to a runtime error.
The existence of types obviates the need to have classes,
since a type may be considered as a more abstract description of the
behavior of an object.
Furthermore, subclasses (as may be derived through inheritance)
are more safely defined as subtypes in a polymorphic
type system. See section [flavors].
At the opposite side of the type dimension we find the statically typed languages,
which allow us to determine the type of
the designation of a variable at compile-time.
In that case, the runtime support system need not carry any type information,
except a dispatch table to locate virtual functions.
Delegation
(in its most generic sense)
is a mechanism for resource sharing.
As has been shown in [Lieber], delegation subsumes inheritance,
since the resource sharing effected by inheritance may easily be mimicked
by delegating messages to the object's ancestors
by means of an appropriate dispatching mechanism.
In a narrower sense, delegation is usually understood as a more
dynamic mechanism that allows the redirection of control dynamically.
In addition, languages supporting dynamic delegation
(such as Self) do
not sacrifice dynamic self-reference.
This means that when the object executing
a method refers to itself, the actual context
will be the delegating object.
See section [prototypes] for a more detailed discussion.
In contrast, inheritance (as usually understood in the context of classes)
is a far more static mechanism.
Inheritance may be understood as (statically) copying the code
from an ancestor class to the inheriting class
(with perhaps some modifications),
whereas delegation is truly dynamic in that messages are dispatched
to objects that have a life-span independent of the dispatching object.
Abstraction
(although to some extent related to types)
is a mechanism that may be independently applied to provide
an interface specification for an object.
For example, in the presence of active objects
(that may execute in parallel)
we may need to be able to restrict dynamically the interface of an object as specified by its type
in order to maintain the object in a consistent state.
Also for purely sequential objects we may impose a particular protocol of interaction
(as may, for example, be expressed by a contract) to be able to
guarantee correct behavior.
Another important aspect of abstraction is protection.
Object-oriented languages may provide (at least) two kinds
of protection.
First, a language may have facilities to
protect the object from illegal access by a client (from without).
This is effected by annotations such as private and protected.
And secondly, a language may have facilities to protect the object
(as it were from within) from illegal access through delegation
(that is by instances of derived object classes).
Most languages support the first kind of protection.
Only few languages, among which are C++ and Java, support the second kind too.
The independence of abstraction and typing may further
be argued by pointing out that languages
supporting strong typing need not
enforce the use of abstract data types having a well-defined
behavior.
Multi-paradigm languages -- logic
Object-oriented programming has evolved as a new and
strong paradigm of programming.
Has it?
Of the languages mentioned, only Smalltalk
has what may be considered a radically new language design
(and to some extent also the language Self, that we will
discuss in the next section).
Most of the other languages, including Eiffel, C++
(and for that matter also CLOS and Oberon),
may be considered as object-oriented extensions of already
existing languages or, to put it more broadly, language
paradigms.
Most popular are, evidently, object-oriented extensions
based on procedural language paradigms,
closely followed by the (Lisp-based) extensions of the
functional language paradigm.
Less well-known are extensions based on the logic programming
paradigm, of which DLP is my favorite example.
In [Wegner92], it is argued that the logic programming
paradigm does not fit in with an object-oriented approach.
I strongly disagree with this position.
However, the arguments given in [Wegner92] to defend it
are worthwhile, in that they make explicit what desiderata
we may impose on object-oriented languages.
Remaining within the confines of a classical object model,
the basic ingredients for an object-oriented extension
of any language (paradigm) are:
objects, classes and inheritance.
Although the exact meaning of these notions is
open for discussion,
language designers seem to have no difficulty in
applying these concepts to extend (or design) a programming language.
Open systems
- reactive -- flexible (dynamic) choice of actions
- modular -- (static) scalability
Dimensions of modularity
- encapsulation boundary -- interface to client
- distribution boundary -- visibility from within objects
- concurrency boundary -- threads per object, synchronization
slide: Dimensions of modularity
According to [Wegner92],
the principal argument against combining logic programming
and object-oriented programming is that such a combination
does not support the development of open systems
without compromising the logical nature of logic programming.
Openness may be considered as one of the prime goals of
object orientation.
See slide [5-open].
A software system is said to be open
if its behavior can be easily modified and extended.
[Wegner92] distinguishes between two mechanisms to achieve
openness; dynamically through reactiveness,
and statically through modularity.
Reactiveness allows a program to choose dynamically between
potential actions.
For sequential object-oriented languages, late binding
(that is, the dispatching mechanism underlying virtual function calls)
is one of the mechanisms used to effect
the dynamic selection of alternatives.
Concurrent object-oriented languages usually offer an additional
construct, in the form of a guard
or accept statement, to determine dynamically which method call
to answer.
In both cases, the answer depends upon the nature of the object
and (especially in the latter case) the state of the object
(and its willingness to answer).
Openness through modularity means that a system can safely be extended by adding
(statically) new components.
The issue of openness in the latter sense is immediately related
to the notion of scalability,
that is the degree to which a particular component
can be safely embedded in a larger environment
and extended to include new functionality.
At first sight, classes and inheritance strongly contribute
to achieving such (static) openness.
However, there is more to modularity than the encapsulation
provided by classes only.
From a modeling perspective, encapsulation (as provided
by objects and classes) is the basic mechanism to define the
elements or entities of a model.
The declarative nature of an object-oriented approach
resides exactly in the opportunity to define such entities
and their relations through inheritance.
However, encapsulation (as typically understood in the
context of a classical object model) only provides
protection from illegal access from without.
As such, it is a one-sided boundary.
The other side, the extent to which the outside world
is visible for the object (from within),
may be called the distribution boundary.
Many languages, including Smalltalk and C++,
violate the distribution boundary by allowing
the use of (class-wide) global variables.
(See also section [meta].)
Evidently, this may lead to problems when objects reside on distinct
processors, as may be the case in distributed systems.
Typically, the message passing metaphor
(commonly used to characterize the interaction between objects)
contains the suggestion that objects may be physically
distributed (across a network of processors).
Also (because of the notion of encapsulation),
objects are often regarded as autonomous entities,
that in principle may have independent activity.
However, most of the languages mentioned do not (immediately)
fulfill the additional requirements needed for actual physical
distribution or parallel (multi-threaded) activity.
Object-oriented logic programming
Logic programming is often characterized as relational
programming, since it allows the exhaustive
exploration of a search space defined by logical relations
(for instance, by backtracking as in Prolog).
The advantage of logic programming, from a modeling point of view,
is that it allows us to specify in a logical manner
(that is by logical clauses) the relations between
the entities of a particular domain.
A number of efforts to combine logic programming with
object-oriented features have been undertaken,
among which is the development of the language Vulcan.
Vulcan is based on the Concurrent Prolog language
and relies on a way of implementing objects as
perpetual processes.
Without going into detail, the idea (originally proposed in
[ST83]) is that an object may be implemented as
a process defined by one or more (recursive) clauses.
An object may accept messages in the form of a predicate call.
The state of an object is maintained by parameters of the
predicate, which are (possibly modified by the method call)
passed to the recursive invocation of one of the clauses
defining the object.
To communicate, an object (defined as a process)
waits until a client asks for the execution of a method.
The clauses defining the object are then evaluated to
check which one is appropriate for that particular method call.
If there are multiple candidate clauses, one is selected and evaluated.
The other candidate clauses are discarded.
Since the clauses defining an object are recursive, after the evaluation
of a method the object is ready to accept another message.
The model of (object) interaction supported by Concurrent Prolog
requires fine-grained concurrency, which is possible
due to the side-effect free nature of logical clauses.
However, to restrict the number of processes created during the evaluation of a goal,
Concurrent Prolog enforces a committed choice between
candidate clauses, thus throwing away alternative solutions.
[Wegner92] observes, rightly I think,
that the notion of committed choice is in conflict
with the relational nature of logic programming.
Indeed, Concurrent Prolog absolves logical completeness
in the form of backtracking, to remain within the confines
of the process model adopted.
[Wegner92], however, goes a step further and states
that reactiveness and backtracking are irreconcilable features.
That these features may fruitfully be incorporated in a single
language framework is demonstrated by the language DLP.
However, to support backtracking and objects,
a more elaborate process model is needed than
the process model supported by Concurrent Prolog
(which in a way identifies an object with a process).
With such a model (sketched in appendix E),
there seems to be no reason to be against the marriage
of logic programming and object orientation.
Active objects -- synchronous Java/C++
When it comes to combining objects
(the building blocks in an object-oriented approach)
with processes (the building blocks in
parallel computing),
there are three approaches conceivable.
See slide [6-o-conc].
Object-based concurrency
- add processes -- synchronization
- multiple active objects -- rendezvous
- asynchronous communication -- message buffers
slide: Objects and concurrency
One can simply add processes as an additional data
type. Alternatively, one can introduce active objects,
having activity of their own,
or, one can employ asynchronous communication,
allowing the client and server object to proceed
independently.
Processes
The first, most straightforward approach,
is to simply add processes
as a primitive data type, allowing the
creation of independent threads of processing.
An example is Distributed Smalltalk (see Bennett, 1987).
Another example is Java, which provides support for
threads, synchronized methods and statements like wait
and notify to protect re-entrant concurrent methods.
The disadvantage of this approach,
however,
is that the programmer has full responsibility
for the most difficult part of parallel programming,
namely the synchronization between processes and the
avoidance of common errors
such as simultaneously assigning a value to a shared
variable.
Despite the fact that the literature, see [Andrews],
abounds with primitives supporting synchronization
(such as semaphores, conditional sections and monitors),
such an approach is error-prone and means a heavy burden on the
shoulders of the application developer.
Active objects
A second, and in my view preferable, approach
is to introduce explicitly a notion of active objects.
Within this approach, parallelism is introduced by having
multiple, simultaneously active objects.
An example of a language supporting active objects
is POOL, described in [Am87].
Communication between active objects occurs
by means of a (synchronous) rendezvous.
To engage in a rendezvous, however,
an active object must interrupt its
own activity by means of an (Ada-like) accept statement
(or answer statement as it is called in POOL),
indicating that the object is willing to answer a message.
The advantage of this approach is, clearly, that the encapsulation boundary
of the object (its message interface)
can conveniently be employed
as a monitor-like mechanism to enforce
mutual exclusion between method invocations.
Despite the elegance of this solution, however,
unifying objects and processes in active objects
is not without problems.
First, one has to decide whether to make
all objects active or allow both
passive and active objects.
Logically, passive objects may be regarded as active
objects that are eternally willing to answer every message listed
in the interface description of the object.
However, this generalization is not without
penalty in terms of runtime efficiency.
Secondly, a much more serious problem is that the
message-answering semantics of active objects
is distinctly different from the message-answering
semantics of passive objects with respect
to self-invocation.
Namely, to answer a message, an active object
must interrupt its own activity.
Yet, if an active object (in the middle of answering a message)
sends a message to itself, we have a situation of deadlock.
Direct self-invocation, of course, can be easily detected,
but indirect self-invocations require an analysis of the complete
method invocation graph, which is generally not feasible.
Asynchronous communication
Deadlock may come about by synchronous (indirect)
self-invocation.
An immediate solution to this problem is provided
by languages supporting asynchronous communication,
which provide message buffers allowing the caller
to proceed without waiting for an answer.
Asynchronous message passing, however,
radically deviates from the (synchronous) message passing
supported by the traditional (passive) object
model.
This has the following consequences.
First, for the programmer, it becomes impossible
to know when a message will be dealt with
and, consequently, when to expect an answer.
Secondly, for the language implementor,
allocating resources for storing
incoming messages and deciding when to deal
with messages waiting in a message buffer
becomes a responsibility for which it is hard to
find a general, yet efficient, solution.
Active objects with asynchronous message passing
constitute the so-called actor model,
which has
influenced several
language
designs. See [Agha].
Synchronous C++/Java
In [Petitpierre98],
an extension of C++ is proposed that supports active objects,
method calls by rendez vous and dynamic checks of synchronization
conditions.
The concurrency model supported by this language, which is called sC++,
closely resembles the models supported by CCS, CSP and Ada.
An example of the declaration of an active object in sC++
is given in slide [ex-active].
sC++
active class S {
public:
m () { ... }
private:
@S () { // pseudo-constructor
select {
01 -> m(); // external call
instructions ...
||
accept m; // accept internal method
instructions ...
||
waituntil (date); // time-out
instructions ...
||
default // default
instructions ...
}
}
};
slide: Synchronization conditions in sC++
The synchronization conditions for instances of the class
are specified in a select statement
contained in a constructor-like method, which
defines the active body of the object.
Synchronization may take place in either (external) calls to
another active object, internal methods that are
specified as acceptable, or time-out conditions.
When none of the synchronization conditions are met,
a default action may take place.
In addition to the synchronization conditions mentioned,
a when guard-statement may occur in any of the clauses
of select,
to specify conditions on the state of the object or
real-time constraints.
The sC++ language is implemented as an extension to the GNU C++ compiler.
The sC++ runtime environment offers the possibility
to validate a program by executing random walks,
which is a powerful way to check the various synchronization conditions.
The model of active objects supported by sC++
has also been realized as a Java library, see [Petitpierre99].
There is currently, however, no preprocessor or compiler
for Java supporting synchronous active objects.
As argumented in [Petitpierre98], one of the advantages of
synchronous active objects is that they allow us
to do away with event-loops and callbacks.
Another, perhaps more important, advantage is that the model
bears a close relationship with formal models of concurrency
as embodied by CCS and CSP,
which opens opportunities for the verification and validation
of concurrent object-oriented programs.
In conclusion, in my opinion, the active object model discussed
deserves to become a standard for both C++ and Java,
not because it unifies the concurrency model for these languages,
which is for example also done by JThreads++ described in [JThreads],
but because it offers a high level of abstraction suitable
for concurrent object-oriented software engineering.
(C) Æliens
04/09/2009
You may not copy or print any of this material without explicit permission of the author or the publisher.
In case of other copyright issues, contact the author.
