Paradigms of programming

\label{des/dig} \phrase{- Perhaps a difference is to be sought in the opposite direction: perhaps expression is more direct and immediate than representation. -} { Nelson Goodman, Languages of Art} The distributed logic programming language DLP that is introduced in this book is the result of combining notions of three distinct paradigms of computing: logic programming, object oriented programming and parallel/distributed programming. This chapter is intended to introduce these paradigms of programming independently. In particular, an extensive introduction to logic programming is given, treating the general concepts underlying logic based computation. Also, a detailed description is given of the popular logic programming language Prolog, with examples that illustrate the use of Prolog in typical search problems. \nop{ The major features of object oriented programming are introduced by discussing the developments that have contributed to the popularity of this paradigm. In addition, we will treat the notion of an object as a computational entity and the role of inheritance in specifying collections of objects in a structured way. } The major features of object oriented programming such as encapsulation and inheritance will be introduced. Design decisions with respect to these features will be discussed by comparing their support in some of the most well-known object oriented languages, such as Smalltalk and C++. We also will discuss the mechanism of inheritance from the perspective of polymorphic types and behavioral refinement. Finally, we will comment on the impact of object oriented technology on the various phases of the software life cycle. Further, an account is given of the three major computation paradigms underlying parallel/distributed programming: communicating sequential processes, object-based concurrency and concurrent logic programming. We will conclude this chapter by looking at these distinct paradigms from a software engineering perspective, in order to establish the benefits and shortcomings of these paradigms of programming with respect to the actual development of software. We will then raise the question what contribution a combination of these paradigms might make to the practice of programming.

Logic programming

The primary virtue of logic programming is its declarative semantics. A logic program can be read as a theory stating relations between entities in a particular domain. For a programmer, such an interpretation allows to separate the concerns for the logical structure of an algorithm from issues of control. The famous phrase [M] algorithm = logic + control of [Ko79] states this principle succinctly. The idea of using predicate logic as a programming language arose from research in automated theorem-proving in the early 70s and resulted in the language Prolog. The first implementation was by Roussel/Colmerauer. Soon afterwards, efficient implementations became available which demonstrated the fruitfulness of this idea, at least for the kind of problems to be found in academic settings. By now Prolog is a widely accepted programming tool which is applied in areas like databases, problem solving, natural language processing, compiler design and, not the least important, expert systems. According to [Bu83] Prolog has often been used to prototype small- to medium-scale expert systems in a business environment. As another indication of the potential of the paradigm, it may be mentioned that the Japanese Fifth Generation Computers project is based on logic programming. The logical language used in logic programming is called Horn clause logic, which is a subset of predicate logic that enables an efficient computational interpretation. C.f. [DoGa84]. \nop{ Polynomial time/pebblings. } In this section, which is necessarily of an introductory nature, we will explore the notion of a logic program and its mathematical, logical foundations enabling a declarative reading of a program. Complementary to the declarative interpretation we will define a procedural interpretation that allows logic programs to be used for computing.\ftn{ Readers not interested in the mathematical foundations of logic programming are advised to jump to section \ref{dig/prolog}. } We will then describe the language Prolog, including the so-called impure or extra-logical facilities that are in practice considered necessary for using Prolog in actual programming tasks. We will defer a discussion of the merits of Prolog from a software engineering perspective to section softw.

Declarative versus procedural semantics

Logic is an excellent vehicle for reasoning about the state of affairs in a particular world. The advantage of logic is that it offers a natural formalism to express the facts and rules that pertain to that world. We will explain how such facts and rules can be stated in a logic program. Our treatment is based on [Ll84]. \prologindex{declarative semantics} .so programs formulas .so models .so procedural

The logical variable

\prologindex{logical variable} Apart from being a means to establish the satisfiability of a goal, the power of logic programming lies in the way values are computed during an inference. The output of a goal with variables is a substitution binding these variables to terms. Terms are the elements of the universe a logic program deals with. As we have seen in section programs, defining logic programs, terms are either constants, variables or compound terms consisting of a function-symbol and zero or more argument-terms. We may use a logic program to define terms in a formal way. The program \oprog{terms}{

   constant(0) <-
   term(X) <- constant(X)
   term(s(X)) <- term(X)

} assumes a constant 0 and a one-argument function-symbol s and defines terms in accordance with the definition given earlier. The goal

<- term(X) has as solutions all the possible bindings of X to the terms contained in the set []

{ 0, s(0), s(s(0)),... } which represents the so-called Herbrand universe of the program terms. The possible output that may result from evaluating the goal

<- term(X) is given by the substitutions []

{X/0},

{X/s(0)},

{X/s(s(0))},... binding X to the elements of the Herbrand universe. The question that we will answer in this section is how we are able to find these substitutions.

Substitutions

\prologindex{substitutions} Recall that a substitution

%h is (represented by) a set of the form

{X1/t1,...,X_k/t_k} that binds each variable

X_i to a term

t_i, for

i=1,...,k. Applying a substitution

%h to a term is recursively defined by \hspace{0.7cm} \begin{tabular}{l l}

c %h = c & for a constant c, \\

X %h = t & for

%h = {...,X/t,...} and X otherwise, and \\

f(t1,...,t_n) %h = f(t1%h,...,t_n%h) & for a compound term

f(t1,...,t_n) \end{tabular} In other words, applying a substitution to a constant has no effect. Applying a substitution

%h to a variable X results in the term t when the binding X/t occurs in

%h. Applying a substitution

%h to a compound term

f(t1,...,t_n) results in the term

f(t1 %h,...,t_n %h) in which

%h is applied recursively to the argument terms

t1,...,t_n. As an example, applying the substitution

%h = {X/s(0)} gives [] $0%h = 0

, X %h = s(0)

, Y %h = Y

, and s(X)%h = s(s(0))

The application of a substitution is easily generalized to literals, by applying the substitution to each argument of the atom, and to conjunctions of literals, by applying the substitution to each literal. A substitution %h_2

is incompatible with a substitution %h_1

if there is a binding X/t1 in %h_1

and a binding X/t2 in %h_2

for which t1%h_2 != t2

. For %h_2

compatible with %h_1

, the composition %h_1 %h_2

of the substitutions %h_1 = {{X1/t1,...,X_n/t_n}}

and %h_2 = {{Y1/t1',...,Y_k/t_k'}}

is given by the set {{X1/t1%h_2,...,X_n/t_n%h_2,Y1/t1',...,

Y_k/t_k'}}

. If %h_2

is not compatible with %h_1

, we say that the composition %h_1 %h_2

does not exist. For an arbitrary term t it holds that $(t%h_1)%h_2 = t ( %h_1 %h_2 ). Moreover, it is easy to check that the composition of substitutions is associative, that is that $(%h_1 %h_2) %h_3 = %h_1 (%h_2 %h_3)

. As an example, consider the composition of %h_1 = {{ X/s(X1) }}

and %h_2 = {{ X1/s(X2) }}

which results in %h_1 %h_2 = {{X/s(s(X2)), X1/s(X2)}}

Unification

\prologindex{unification} Substitutions are the result of unifying two terms. A substitution %h

is a unifier of the terms t1 and t2 whenever t1%h = t2%h

, that is when the terms become equal after applying %h

. The most general unifier of two terms is the smallest substitution unifying the two terms. For example, the substitution %h = {{X/s(0)}}

is the most general unifier of the terms f(X,Y)

and f(s(0),Y)

. However, the substitution %h' = {{X/s(0), Y/0}}

is also a unifier, but clearly less general since it may be derived from %h

by adding the binding for Y. in other words, a substitution %h

is called the most general unifier of two terms, or mgu for short, if for each unifier %s

of these two terms there is a substitution %g

such that %s = %h %g

. A most general unifier can always be refined by another substitution to give an arbitrary unifier. Most general unifiers are not necessarily unique, but may be identified by renaming variables. We will describe a simple recursive algorithm to decide whether two terms are unifiable and to compute the most general unifier if it exists. To indicate that two terms are not unifiable we use the value fail. We now write the composition of substitutions %h_1

and %h_2

explicitly as %h_1 \c %h_2

and adopt the convention that %h_1 \c fail = fail

and fail \c %h_2 = fail

. Also when %h_2

is incompatible with %h_1

, because they disagree on the binding for a variable, we define the composition %h_1 %h_2 = fail

. We will use the constant %e

to denote the empty substitution, for which it holds that %h \c %e = %e \c %h = %h

for arbitrary %h

. The algorithm is given by the following recursive equations [D unify(c1,c2) = %e

if c1 = c2

, unify(X,t) = {{X/t}}

if X does not occur in t, unify(t,X) = unify(X,t)

if t is not a variable, unify(f(t1,...,t_n), f(t1',...,t_n')) = unify(t1,t1') \c ... \c unify(t_n,t_n')

, and unify(t1,t2) = fail

otherwise D] Unifying two constants results in the empty substitution whenever the constants are equal. In case one of the terms is a variable X, a substitution binding X to the other term is delivered, provided that X does not occur in that term. Unifying two compound terms is possible only when the two terms have the same function-symbol and the same number of arguments. The result is the composition of the substitutions resulting from the pairwise unification of the argument terms. This leads to failure whenever such unification proves to be impossible or an incompatibility arises. The unification function delivers fail when none of these cases apply. As examples consider [D unify(p(s(X),0), p(Y,Z)) = {{Y/s(X)}} \c {{Z/0}} = {{ Y/s(X), Z/0 }}

unify(p(s(X),0), p(Y,X)) = {{Y/s(X)}} \c {{X/0}} = {{ Y/s(0), X/0 }}

unify(p(s(X),0), p(Y,s(Z))) = {{Y/s(X)}} \c fail = fail

unify(p(s(X),0), p(Y,Y)) = {{Y/s(X)}} \c {{Y/0}} = fail

D] In the last example fail ~

results because an incompatibility arises between the substitutions resulting from unifying the argument terms, since they disagree on the binding of the variable Y.

The occur-check

\prologindex{occur check} In the unification algorithm, a binding results whenever we encounter a variable X and a term t, provided that X does not occur in t. In actual logic programming systems this so-called occur-check is often omitted for reasons of efficiency. This may lead to anomalous behavior, as exemplified by the goal <- X = s(X)

which succeeds, resulting in the binding {{X/s(X)}}

, although it clearly has no solution.

Compound terms

\prologindex{compound terms} In logic programming systems, unification provides a uniform mechanisms for parameter passing, data selection and data construction. Terms can be used to package data in a way resembling records. For instance, the fields on a chessboard can be denoted by the terms [] position(1,1)

, position(1,2)

,..., position(8,8)

naming the index in respectively the row and the column of the board. In a program the pattern of this structure can be used to select the wanted information, as illustrated in the clause that tests whether two positions occur on the same row. \oprog{row}{

   same_row(position(X,Y), position(X,Z)) <-

} When evaluating a goal {\em same_row} containing two positions, the information concerning the rows is selected and the implicit constraint that the rows are equal, since they are both referred to by the variable X, is enforced by the unification procedure.

The language Prolog

\label{dig/prolog} Prolog is the most widely used logic programming language that exists today. It implements a logic programming system as treated in the previous sections, but in addition contains a number of features that are convenient when programming actual systems. .so syntax lists bags arith cuts neg control meta dynamic $=

Examples

Concluding our discussion of Prolog, two examples will be given that will illustrate how to use Prolog for implementing search in a finite search space. The first example presents a solution to a problem in chess, the N-queens problem. Our solution is given for

N = 8, but may be easily generalized to other values of N. The second example illustrates depth-first search with a loop-check built-in to prevent non-termination. .so queens states

Object oriented programming

The contribution of object oriented programming to the practice of program develop\-ment lies in the facilities it offers to specify in a declarative way the structure of a program as a collection of related objects. An object oriented program reflects the conceptual structure of a problem domain by specifying the proper data types, and their relation by means of inheritance. Object oriented programming can best be regarded as a methodology, the essence of which is captured by the directive implied by the phrase object oriented modeling. \oopindex{modeling} Object oriented languages contribute to this methodology by providing the necessary technology. In this section, we will study the various mechanisms incorporated in object oriented programming languages and at the end we will come back to the more general issues that play a role in requirements analysis and the design of an object oriented system.\ftn{ See [Sau89] and [BPS89] for an overview and comparison of object oriented programming languages. } A succinct formulation of the basic ingredients of object oriented programming languages is given by the equation [M] OOP = encapsulation + inheritance These mechanisms, encapsulation by means of abstract data types and inheritance, allow to construct a declarative model of a given problem domain. When speaking of the declarative nature of object oriented programming, we do not intend to say that an object oriented program has a logical interpretation that is as strictly defined as the declarative interpretation of a logic program, but that in a rather loose sense an object oriented program may reflect part of the reality that it intends to model. The objects that we describe in an object oriented specification may thus partly correspond to entities in reality, although inevitably there will be objects for which such correspondence is not evident. These correspondences enhance our conceptual understanding of a program. \nop{ Evidently, this comes not for free, but is the result of careful design, that is a discipline rooted in the intention to specify an adequate model of the problem domain. }

History

\oopindex{history} Object oriented programming has its root in simulation. The first language supporting objects was Simula [DaNy66]. Simula has been primarily used to simulate complex dynamic systems. Since Simula supported co-routining, objects could coexist in a quasi-concurrent fashion, exchanging messages in order to direct the flow of control. The conception of computation as the exchange of messages between objects proved to be fruitful, as became apparent with the introduction of Smalltalk. Originally, Smalltalk was intended as a language for programming interactive graphic work-stations. This intention has been realized, to the extent that similar languages are used nowadays to implement menu-driven, window-based user interfaces. C.f. [LVC89], [Meyro86]. The introduction of Smalltalk meant both the introduction of a new language and the introduction of a radically different style of programming. Along with a new style came a new terminology, the now familiar terminology of objects, classes, methods, messages and inheritance.

Data abstraction

\oopindex{data abstraction} Why has the introduction of object oriented programming resulted in such a radical change of our conception of programming? Differently, phrased, what have been the developments that have led to the acceptance of object oriented programming as a new paradigm? These developments may be traced back to the introduction of structured programming in the 1970s. The advent of structured programming goes hand in hand with the dominance of what we may call the procedural style of programming. Developing a program by means of stepwise refinement was generally taken to consist of breaking up a problem into a number of abstract steps or procedures, that were then gradually refined by more detailed procedures. The effort went primarily into finding a proper algorithm and the procedures implementing it. The major disadvantage of the procedural approach was its inadequacy with respect to the representation of data as structured entities. The theory of abstract data types offered a correction to these shortcomings and may be regarded as the most important constituent of object oriented programming, since it provides a mathematically well-founded notion of encapsulation as a means to specify the behavior of an entity in an abstract way. An example of the abstract specification of a data type stack is given by the algebraic theory below. \oprog{stack}{ .so stackadt } The algebraic specification of a stack has three components: a signature component that declares the functions needed to create and manipulate a stack, a component that specifies the preconditions that must be met when calling these (partial) functions, and a component that specifies the semantic constraints characterizing the behavior of a stack by means of equational axioms. The preconditions for applying the functions pop and top state that the stack may not be empty, otherwise the result of the function will not be defined. The axioms fully describe the behavior of a stack. As an example, the composition of a pop and push operation, with push executed first, is evidently an identity operation for any conceivable stack. .so adt

Data hiding

\oopindex{hiding} An abstract data type specifies the behavior of a category of entities. Internal details of how such behavior is implemented remain hidden from the user of such entities. In this sense, the theory of abstract data types has certainly contributed to our awareness of the importance of data hiding. These developments have been taken up by programming language designers and have resulted in the introduction of modules and a distinction between specification and implementation parts. An example of a language supporting such features is Modula-2 [Wirth83]. The major disadvantage of modules, however, is that they do not constitute a type and may not be regarded as first class entities, however valuable they may be in providing a modularization mechanism. As argued in [St88] and [Meyer88], objects may be regarded as implementations of abstract data types, since they encapsulate data and behavior. Moreover, an interface may be specified that hides all internal details of an object and prevents unprotected access to its data. Not all object oriented languages, however, provide such a protection mechanism. Smalltalk [GR83], C++ [St86] and Eiffel [Meyer88] are languages that do provide such support.

Inheritance

\oopindex{inheritance} As a method of program development, the paradigm of data abstraction may be characterized as the activity of finding the right data types and specifying the appropriate behavior for these types. Abstract data types alone, turn out to be rather inflexible and inconvenient for specifying large programs in a structured way. C.f. [St88]. Inheritance allows such specifications to be related in the sense that they may be shared or organized in a specialization hierarchy. In the view of most, with the exception of [Booch86], inheritance is an integral part of the object oriented approach.

Encapsulation

\oopindex{encapsulation} The encapsulation mechanism offered by object oriented languages is embodied by the notion of an object. In most languages, objects are defined by a class declaration that characterizes the properties of the objects belonging to that class. In operational terms, a class may be regarded as a template for creating objects.

Objects

\oopindex{objects} may be thought of as structures that comprise both data and procedures that may operate on these data. Using Smalltalk terminology, we may write down the equation [M] object = data + methods The variables that refer to the data contained by an object are often called instance variables, since such variables are privately owned by each instance of a class.

Methods{\rm ,}

\oopindex{methods} in Smalltalk, have exclusive access to the instance variables of the object for which they are defined. The methods of an object are, no more and no less, priviliged procedures that may operate on the data of an object. In other words, methods provide a functional abstraction mechanism that allows the contents of an object to remain hidden. A pictorial representation of an object counter, containing an instance variable n, and supporting the methods initialize, increment and value is given below. .so instance

Messages

\oopindex{messages} A method is executed for an object in response to a message. For a message to be a legal method call, the method must be defined in the method interface of the object. Methods that are private to an object may not be called. \oopindex{method interface} Operationally, we may regard an object as encapsulating a state that is dependent on the values of the instance variables, and behavior that results from the functions embodied in the methods defined for the object. We may capture this operational view in the equation [M] object = state + behavior that closely corresponds to our previous characterization of an object as encapsulating data and methods. Computation in an object oriented system is sending messages. Sending a message to an object may result in a change of the state of the object and may possibly cause the object to send messages to other objects. We may remark, following [St88], that an object oriented language supports data abstraction to the extent that access to the state of an object is effectively forbidden, except for the methods defined for the object. To provide further protection, some languages allow to define an external method interface that states which methods are externally visible.

Responsibilities

\oopindex{responsibilities} In addition to the syntactic and operational characterization given of objects, we may characterize an object from the perspective of program development as an entity with certain responsibilities. From this perspective an object can be regarded as providing a service in response to a message. We will refer to the object sending a message to ask for a service as a client of the object that supplies the service. \oopindex{external interface} The external interface of an object, that comprises the methods visible to the clients of an object, may now be viewed as stating the responsibilities of an object, that is the services it is willing to supply. \oopindex{constructors} \oopindex{destructors} \oopindex{modifiers} \oopindex{selectors} \oopindex{iterators} As concerns the operations of an object (its responsibilities), a distinction can be made between methods to create and initialize an object (constructors), methods to dispose of an object (destructors), methods to change the state of an object (modifiers), methods to evaluate the current state (selectors) and methods to visit parts of the object (iterators). In a design, the description of an object will usually not contain a precise characterization of its constructor and destructor methods. However, when objects have activity of their own, the constructor characterizes this activity or may lay down the protocol for interaction with other objects. In these cases, the description of the constructor enhances a conceptual understanding of the functionality of the object.

Classes versus prototypes

\nop{ An object is an entity that comes into existence during an actual computation. } Object creation may be static, in which case all objects are created at the beginning of a computation, or dynamic. Dynamic object creation allows objects to come into existence at the moment that they are needed. The three languages mentioned, Smalltalk, C++ and Eiffel, all support dynamic object creation.

Types

\oopindex{types} An object is an instance of a class. A class acts as a template for creating objects. In a strictly typed language, where strictly typed means that each expression in the language may be assigned a type, the type of an object is determined by the class of which it is an instance. Dynamically, an object may be regarded, using the characterization given in the annotated reference manual for C++, as a region of storage, {\it the meaning of which is determined by the type of the expression used to access it}. See [ES90]. Static typing allows to resolve the well-typedness of a program at compile-time and enables to deal in an efficient way with method calls, provided that these are not overridden in an inheritance hierarchy. Smalltalk is an untyped language, that enforces no type checking. However, Smalltalk may be regarded as a dynamically typed language, since each computational entity created during the execution of a program is an object in the sense of being an instance of a class. Each object carries its own type information, telling to which class it belongs. When executing a method in response to a message, the object searches its method table, which is shared with the other instances of its class, for the appropriate procedure. When a method is not defined in the object's own method table, the method tables of the classes from which the object inherits are searched. The language C++, in contrast, is statically and strictly typed, although it allows for exceptions to the type scheme. Calling a method, which is called a member function in C++, amounts to calling an ordinary function since the existence of that function may be assessed at compile-time. However, for a function declared virtual, which allows such a function to be overridden by inheriting classes, the appropriate binding cannot be resolved statically but must be computed at run-time.

Classes and instances

\oopindex{class} \oopindex{instance} Classes are templates for creating objects as instances of a class. Being an instance of a class, an object embodies the functionality of that class as well as the functionality inherited from the classes of which the object's class is a subclass. In other words, in a class-based system, we have two relations that determine the behavior of an object, the instance relation, denoting that an object is an instance of a class, and the subclass relation, indicating that a class is a subclass of a class. We may capture these relations pictorially by the arrows \begin{center} .so rel \end{center} which must be read, respectively as, class C is a subclass of (the parent) class P, and object O is an instance of class C. \nop{ As an example, the picture below represents the case that we have an object i that is an instance of a class Integer, which is a subclass of the class Sortable. \begin{center} .so sort \end{center} } As an example, imagine the case that we have an object i that is an instance of a class Integer, which is a subclass of the class Sortable. Using inheritance allows to create an abstract superclass, such as the class Sortable, that contains the common properties of a number of subordinate classes. An example of such a property is the existence of the relation less-than by which instances of (subclasses of) Sortable may be compared and which can be used to define a generic sorting algorithm. As another subclass of Sortable, think of a class String that supports a lexicographical ordering among strings. \oopindex{object creation} Having classes as a means to create objects, it is rather natural to introduce a mechanism that allows all instances of a certain class to share class-wide resources. Smalltalk, for example, allows to declare so-called class variables and class methods that are, in opposition to the common instance variables and methods, shared by all objects of that class. Class-variables are in other words a kind of global variable, with access restricted to the instances of the class. \oopindex{class methods} Class-methods are procedures. These procedures are not allowed to access the instance variables defined for that class since these are private to each instance. Calling a class method is possible without creating an instance of the class. Class-methods are often used to create and initialize instances of a class. \oopindex{members} In C++, variable or function members may be declared static. Static members are shared by all instances of a class, similar to class variables and class methods in Smalltalk. Like class methods, static member functions are not allowed to access ordinary member variables.

Prototypes

\oopindex{prototypes} The disadvantage of making a distinction between the functionality of classes (supporting class variables and class methods) and objects (that are instances of classes, supporting instance variables and ordinary methods), is that programmers are faced with the complexity of making a design choice with respect to where functionality must be put. The choice between class methods or (object) methods will not always be evident. An alternative approach to creating objects is sketched in [US87], where prototypes are introduced as a unifying concept combining the functionality of classes and objects. Prototypes may be used as templates for creating objects, by cloning, and as computational entities that execute a method in response to a message. Cloning an object amounts to making a copy of an object, including its state at the moment the copy is made. \oopindex{object copying} An interesting variant of cloning is to allow for differential copying, in which the differences with respect to certain attributes of the cloned object can be stated when creating the copy. In effect, the newly created object then inherits the functionality of the object from which it is created, possibly overriding or adding behavior by its differential specification. See also [RC91]. \oopindex{delegation} As an alternative way to share behavior between objects, inheritance may be implemented as delegation to a designated parent object. Using delegation instead of subclassing or differential cloning to effect inheritance allows to build inheritance structures dynamically, during the computation. The advantage of using prototypes instead of classes to organize the conceptual structure of a program lies first of all in the simplicity that arises from the absence of classes. The primary relation supported by such an approach is the inherits relation, for which we have the choice to allow static inheritance by means of differential specifications or dynamic inheritance by making use of delegation. An additional advantage of discarding classes is that one-of-a-kind objects are naturally supported, since no extra class for such an object needs to be introduced. Another advantage, mentioned in [US87] is that the problem of whether to support metaclasses, and to what extent, does not occur.

Metaclasses

\oopindex{metaclasses} In a class-based approach objects are organized in taxonomies along the class abstraction. A class describes the semantics of a set of objects and acts as a mould from which to create instances. A class in itself is not an object but a syntactical construct used to describe objects. However, a number of class-based languages like Loops, Smalltalk, CommonLoops and Clos, allow a class to be characterized in a more abstract way by means of a metaclass. Metaclasses, in these languages, are used to implement the behavior of a class regarded as an object, behavior that is embodied in class variables and class methods. In addition, the implementation of a class by means of a metaclass allows the programmer to inspect the properties of a class dynamically. For instance a class may answer to a request whether it supports a particular method.\ftn{ Static members in C++ do not support such reflective capabilities, although library packages exist -- as for example the NIHCL-library [GOP90] -- that do provide such features for C++. } \oopindex{modeling} From the perspective of object oriented modeling, metaclasses provide the means to capture general properties of the system on a higher level, by defining the appropriate metaclass for a category of classes.

Three-level architecture

In Smalltalk and Loops, the dichotomy between classes and objects gives rise to a three-level architecture based on the distinction between objects, classes and metaclasses. The inheritance and instantiation structure of this architecture is pictured in the diagram below. .so three The diagram embodies two hierarchies, the hierarchy determined by the subclass relation (indicated by the solid arrows), and the hierarchy determined by the instance relation (indicated by the dotted arrows). The diagram contains three system-defined entities, namely Object, Class and MetaClass. Object is the root of the inheritance hierarchy, since every class (including metaclasses) must inherit the functionality of Object. Conversely, every ordinary class is an instance of MetaClass, or a subclass thereof. Metaclasses, such as Class and the user defined ListMetaClass, are instances of the system-defined entity MetaClass. MetaClass has a quite peculiar status in this diagram since (the appropriate arrow is omitted) it must be regarded as an instance of itself. The capability of creating instances ultimately comes from MetaClass. This capability is inherited by both the (system-defined) metaclass Class and all user defined metaclasses.\ftn{ In Smalltalk, the user is not allowed to define own metaclasses. In Smalltalk, to each class corresponds a metaclass that is hidden from the user. } In the diagram, the object level contains a single object b1 that is an instance of the class Book. Another user defined class is the class Point, which is an instance of Class and a subclass of the class Object. The architecture sketched by this diagram has a fixed number of levels, corresponding to the distinct notions of object, class and metaclass. The disadvantage of such an architecture from the point of view of object oriented modeling is that generalizations with respect to the functionality of the system may be taken only one level up above the class level. In principle, one would like to allow an arbitrary number of levels at which such generalizations are possible.

Reflective architecture

\oopindex{reflection} \nop{ The architecture sketched above has a fixed number of levels corresponding to the conceptually distinct notions of object, class and metaclass. } What we need is a view that unifies the notions of object, class and metaclass in a way that allows us to define metaclasses to an arbitrary level. In [Cointe87] a solution is given that unifies these concepts by taking a class as an object defined by a real class. The key to this solution is to provide a reflective definition of a class, as illustrated in the diagram below. \begin{center} .so reflect \end{center} This diagram pictures that Object is an instance of Class. Class, on the other hand, inherits its behavior from Object but is an instance of itself. \oopindex{postulates} The reflective model introduced in [Cointe87] is fully described by the following postulates:

An object encapsulates data and procedures.
Objects are activated by message passing. A message specifies what procedure to apply by providing a method selector and the appropriate arguments.
Every object belongs to a class that specifies the objects attributes (data) and behavior (methods or procedures). Objects are created as instances of a class.
A class is also an object, instantiated by another class, called its metaclass. Consequently, to each class is associated a metaclass that describes its behavior as an object.
A class can be defined as a subclass of one or many other class(es). The subclassing mechanism allows sharing of instance variables and methods, and is called inheritance. The class Object represents the most common behavior shared by all objects.
Instance variables of an object define a local environment. Class variables define a global environment shared by all the instances of a class. These class variables are defined at the metaclass level. It must hold that the class variable of an object is an instance variable of the objects class.

In other words, these postulates require that Object lies at the root of the inheritance hierarchy since every class is an object as well, and that Class lies at the root of the instantiation hierarchy as it provides the capability of creating new instances. Having Class at the root of the instantiation hierarchy entails a circular definition of Class, since Class must be its own instance. In order to act as an object, a class must have an attribute name that records the class name, an attribute supers that tells from which classes attributes and methods are inherited, an attribute iv that records the local variables of the instances of the class, and an attribute methods that contains the methods defined for objects of the class. In accordance with this discussion, we may instantiate the (metaclass) Class by the reflective pattern below. \yprog{Class}{

    name     supers            iv                           methods
  
   Class    (Object)     (name supers iv methods)     (new ...)

} Each class that displays such a reflective pattern may be regarded as a metaclass, since its instance variables reflect exactly the properties of a class. Minimally, a class must support the method new in order to create instances. In the picture below, this scheme is illustrated by using Class as a metaclass for a Point class, that has two points as actual (object) instances. $= \begin{center} .so reflexam \end{center} For each class the instance variables are given in brackets. The class Point is an ordinary instance of Class and need not contain the instance variables of Class. In contrast, a metaclass is created by inheriting from Class. It contains all the instance variables defined for Class. In addition, such a metaclass may contain the properties common to a category of classes. The architecture described allows to define an arbitrary number of metaclasses on top of an ordinary class. It is doubtful, however, whether the use of such a tower of metaclasses will often occur in practice. \nop{ A metaclass, created by inheriting from Class, would contain all the instance variables given for Class. In contrast, the class Point is an instance of Class and need not contain the instance variables of Class The instance variables for each class are given in brackets. }

Inheritance

\oopindex{inheritance} The popularity of the object oriented style of programming is to a large extent due to the possibility of sharing object (and class) specifications by means of inheritance. Objects in themselves provide the means to encapsulate the implementation of behavior and to regulate the interactions between objects by defining an external interface that establishes the responsibilities of the object. In addition to the clients that request a service of an object by invoking one of the methods listed in the external method interface, inheritance introduces a new category of clients that make use of the functionality of (classes of) objects by sharing functional resources of these objects, that is instance variables and methods. \oopindex{modeling} Inheritance may play a crucial role in object oriented modeling since it allows to factorize the properties common to a collection of classes in a common ancestor class. Because of this feature abstract classes may be specified to define the external interface of a collection of classes. The subclasses of an abstract class may then refine the definition provided by the abstract class by providing an implementation. From a software engineering perspective, inheritance promotes the reuse of software since when a class only captures part of the required functionality it may -- using inheritance -- easily be refined into a class that does capture all the functionality required.

Specialization hierarchies

\oopindex{specialization} In its most simple form, the inheritance mechanism provides a way of sharing common attributes, and thus allows to create a specialization hierarchy among a number of concepts. An example of such a specialization hierarchy is given in the tree below that depicts the relation between a variety of fruit. \begin{center} .so fruit \end{center} Since oranges are not the only fruit, we may encounter in this hierarchy a subtree that specifies some of the varieties of apples. As a common attribute of all the items in the tree we may think of the property of being edible. Specializations will occur with respect to the texture of their skin and the place of growth for example. The most common interpretation of this kind of taxonomies is given by a predicate logic rendering of the relations expressed by the specialization tree. The hierarchy depicted above, for example, states that all apples are (a kind of) fruit, or in a predicate logic formula:

\A x. apple(x) -> fruit(x). Semantically, each node in the tree corresponds to a set of individuals (elements of a domain of discourse). This set is exactly the set described by the information provided by that particular node. In a specialization tree, each descendant of a node provides more specific information and thus restricts the number of individuals to which the description applies. In other words, taken as sets of individuals, the relation

apple \< fruit holds.

Multiple inheritance

\oopindex{multiple inheritance} Instead of one ancestor, as in the specification hierarchy above, a concept may as well have multiple parents from which it inherits. For instance, if we have a concept edible then we may make apple inherit from edible to express that all apples are edible. As another example, if we have an object (type) machine with attributes age and fuel and an object type vehicle with attribute age and speed then we may create the object type car with attributes age, speed and fuel by inheriting from both machine and vehicle, as pictured below. \begin{center} .so car \end{center} The meaning of the concept car is the set of individuals that is both a machine and a vehicle, in other words the cross-section of the sets corresponding to machine and vehicle. See [Ca84].

Conformance

\oopindex{conformance} Ideally, the inheritance relation in object oriented programming languages conforms to the notion of refining a description of a concept by providing more information. In that case we have a substitution property that states when a concept conforms to another concept: \begin{quotation} (Substitution) {\em whenever we may use an instance of a concept we may also use an instance of a refinement of that concept.} \end{quotation} This holds also in the case of multiple inheritance. For instance, if I am asked for a vehicle then I may hand over my car. \oopindex{polymorphism} Technically, conformance may be checked by identifying concepts or classes with types. Regarding concepts as types, we speak of polymorphism since the inherited concepts may be taken to be subtypes of the original concept. \nop{ In practice this appears to be an unrealistic goal, since many applications of inheritance violate this principle of refinement. } However, conflict may arise when properties are inherited that contradict each other. A famous example, illustrating the possibility of ambiguity in property inheritance systems, is the so-called Nixon-diamond. \begin{center} .so nixon \end{center} The inheritance diamond above states that Nixon is both a Quaker and a Republican. Knowing that Quakers are notorious pacifists and Republicans equally notorious non-pacifists, the question arises whether Nixon is a pacifist or a non-pacifist. Notorious, no doubt. With regard to the diamond, evidently the logical theory expressed by the inheritance graph is clearly inconsistent. C.f. [To86]. If all the properties of the inherited concepts are preserved in the inheriting concept we say that the inheritance relation is monotonic. Otherwise, we say that the inheritance relation is non-monotonic. As observed in [WZ88], incremental system evolution often turns out to be non-monotonic, in practice. Non-monotonicity occurs when either exceptions or overridings are used to effect the desired behavior. In these cases we can no longer speak of behavioral refinement to characterize the inheritance relation employed.

Polymorphism

\oopindex{polymorphism} To decide on whether an object type conforms to another object type we need to have a notion of type and subtype, since then we may replace conforms to by being a subtype. \oopindex{subtyping} Pragmatically, we may regard a class inheriting from a class as a subtype of the type defined by the class, since the meaning of a class is operationally defined by the method lookup procedure employed by instances thereof. See [WZ88]. However, viewing classes as types is really overspecifying the notion of conformance and moreover such a view does not allow static type checking, since type errors are only dynamically detected as the result of a failing method lookup. \oopindex{dynamic method lookup} The procedure for dynamic method lookup (in the case of single inheritance) may be phrased recursively as follows. \yprog{lookup}{

  procedure lookup(method, class)
       if method = localmethod then do localaction
       elsif inheritedclass = nil then undefined
       else lookup(method, inheritedclass)

} Multiple inheritance gives rise to more complicated lookup algorithms. See [DH88]. With regard to polymorphism, whenever a method is defined for a superclass then no type error will occur when calling the method for an instance of a subclass since all methods of the superclass are inherited by the subclass. They may however be redefined, which involves the risk of specifying contradictory behavior that (intuitively) does not conform to the intended behavior of the inherited class. \oopindex{dynamic binding} \oopindex{virtual functions} The dynamic binding that occurs with virtual functions, for instance in C++, resembles the method lookup procedure sketched above. Conformance to a supertype however is statically checked in C++. Also, in C++ there are ways to use inheritance in a non-standard way, for instance to restrict the functionality of a class of objects. C.f. [HOB87]. A classical example of a nonstandard application of inheritance is to derive a stack from a double ended queue by disabling the ordinary deque operation (that delivers the first, that is oldest element of the queue). However, from the perspective of types, the relation [D]

DQueue <_{subtype} Stack holds, since a double ended queue may be regarded as inheriting all the behavior of a stack while adding a deque operation.

Objects as records

\oopindex{objects as records} In order to grasp the subtype relation between object classes we need to introduce a more formal notion of object types. To establish the type of an object, we may regard an object as a record containing attributes and functions that are accessible by labels. The notions employed here are due to [Ca84]. An example of a record with values is the record []

{ a = 1, b = true, c = "hello" } We will use type expressions of the form

e:%t to denote that the expression e is of type

%t. \oopindex{conformance} The conformance rule for arbitrary expressions may now be stated as follows. [D] $(Conformance) if e:%t' and %t' <= %t then e:%t

The rule expresses that an expression may always be regarded as being of an appropriate supertype. For simple attributes a, say of type integer or subranges thereof, this property is easy to establish. For instance, when a:[2..5]

then also a:[1..6]

, taking [i..j]

to be the interval ranging from i to j. The subtype relation for simple types corresponds to the subset relation with respect to the sets of individuals denoted by these types. However, for functions f:%s -> %t

, where %s

is the type of the domain and %t

the type of the range of f, it is much more difficult to establish whether a function f'

of type %s' -> %t'

conforms to (the type of) f. In [Ca84] the function conformance rule is given by [] $(Functions) if %s <= %s' and %t' <= %t then f':%s' -> %t' <= f:%s -> %t The difficulty of applying this rule is brought about by the contravariance between the domain types, namely

%s <= %s' whereas

f' <= f. We hope to give a more intuitive understanding of this rule in the next section by exploring the notion of behavioral refinement for functions. In order to define a subtype relation for objects we state the following conformance rule for records. [D $(Records) if %t_1' <= %t_1 and ... and %t_n' <= %t_n then

{{ a1:%t_1',...,a_{n+m}:%t_{n+m}' }} <= {{ a1:%t_1,...,a_n:%t_n }}

D] In other words, a record type is a subtype of another record type if for each of the field a_i:%t_i

(for i=1,...,n

) there is a corresponding field a_i:%t_i'

for which %t_i' <= %t_i

. The subtype may, however, contain additional fields. As an example, defining the record types [D vehicle = {{ age : integer, speed : integer }}

machine = {{ age : integer, fuel : string }}

D] we may establish that the record type car defined by [D car = {{ age : integer, speed : integer, fuel : string }}

D] is a subtype of both vehicle and machine. We now have a (syntactic) notion of types that enables us to decide whether an object (type) conforms to -- is a subtype of -- another object (type).\ftn{ \oopindex{object types} In this treatment, we have not paid any attention to the recursive structure of object types. For a treatment of these aspects see [CW85] and [CoHC90]. } In the next section we will provide a more intuitive notion of (behavioral) refinement based on the notion of subtype conformance introduced here. .so refinement

Object oriented analysis and design

\seindex{analysis} \seindex{software life-cycle} In the previous section we have given an inventory of the mechanisms provided by object oriented programming languages and we have indicated the possible use of these mechanisms in the enterprise of object oriented modeling. The question we wish to raise now is what influence object oriented technology may exert on the software life cycle and what issues play a role in object oriented analysis and design. \nop{ Traditionally, the software life cycle is subdivided in an analysis phase in which the requirements for a system are laid down, a design phase in which a conceptual architecture for a system meeting the requirements put forward in the analysis phase is proposed, an implementation phase in which the conceptual structure resulting from the design phase is embodied in actual software and an operational phase that includes installing and maintenance of the system. The transition from one phase to the next usually involves a significant effort of translating the results into the formalism appropriate to that phase. The use of object oriented techniques in the design and implementation phase has resulted in a shift of emphasis in favor of the design phase since the effort of implementing a system in an object oriented programming language on the basis of an object oriented design may be regarded as a process of refining the decisions laid down in the design. The use of object oriented techniques has thus effectively reduced the gap between the concept-oriented world of design and the technology-oriented world of implementation. C.f. [WWW90] and [Meyer88]. } \nop{ The central guideline in developing an object oriented program comes down to the advice to construct an (object oriented) model of the problem domain. Object oriented modeling is also the main activity in (an object oriented approach to) the rquirement analysis and the design of a system. }

Object oriented analysis

The main issue in the analysis phase is to extract the needs of the person or organization for which the software will be developed. Analysis is not so much concerned with the development of the system as with an adequate description of the problem domain, to enable the problem to be solved. A basic requirement to any analysis method is that it provides the means to handle the complexity of the underlying problem domain. In [CY90] some currently used analysis methods, such as functional decomposition, the data flow approach and semantic modeling are discussed and compared with object oriented analysis. Functional decomposition amounts to breaking up the problem into functional steps that have to be carried out to complete the task. The data flow approach primarily models the flow of information and the events that are of influence on this flow. Information (or semantic) modeling comes closest to an object oriented approach, since it models the objects occurring in the domain, their attributes and their relationships. \seindex{information modeling} Object oriented analysis may be regarded as extending the information modeling approach by providing the means to model not only the attributes but also the behavior of the entities occurring in the domain and by the use of inheritance to elucidate the conceptual relationships between these entities. Both the information modeling approach and the object oriented approach aim at modeling the problem domain, by identifying the objects that exist in that reality. \oopindex{object identification} \seindex{linguistic analysis} \seindex{requirements} As a possible method to identify the proper objects, [Booch86] and [WWW90] suggest a linguistic analysis of a (written down) natural language account of the requirements. As a first attempt, objects are suggested by thinking of objects that correspond to the nouns occurring in the document and of operations or methods to correspond with the verbs used. Clearly, such a method provides only a first step towards a model or a design. \oopindex{modeling} \seindex{modeling} \seindex{rapid prototyping} A major advantage of a modeling approach to analysis is that it facilitates the communication with domain experts, since these may be supposed to be well-acquainted with the objects that constitute the problem domain.\ftn{ In contrast, domain experts are usually not well-acquainted with the methods used in functional decomposition or the data flow approach, nor are they generally willing to acquire that expertise. } Another advantage of the modeling approach is that it allows for rapid prototyping. In particular in cases where there is a continual change of user requirements, prototyping may be helpful in establishing these requirements. \nop{ Evidently, communication with domain experts plays a crucial role in successfully completing the analysis phase. }

Object oriented design

\seindex{design} After completing the analysis phase, the next step is to design the system. Applying an object oriented approach, the transition between the analysis phase and the design phase may be rather smooth. The objects comprising the design may (to a certain extent) be thought of as refining the object identified during analysis. Similarly, when using an object oriented language, the objects actually implemented may be considered as a further refinement specifying the implementation details. In addition, however, to the object identified in the analysis phase, objects will play a role in the design for which no clearly identifiable counterpart exists in reality. As an example of such objects, think of the objects that are needed to develop a (graphical) user interface. Also, objects may be present that embody hypothetical entities of the domain. For instance, in a medical expert system objects may be used to define the reasoning capabilities of the experts in a domain-independent manner. These objects do not exist in reality, but are artefacts needed to explain the functional behavior of the entities involved. An example of a very elementary design method is the method introduced in [BC89]. \oopindex{CRC cards} \seindex{CRC cards} The authors propose the use of so-called CRC-cards. An example of such a card (approximately the size of a small postcard) is pictured below. \fboxClassname & Collaborators \\ Responsibilities & \vspace{3cm} \\ \hline \end{tabular} The abbreviation CRC stands for Class, Responsibility and Collaborators. One such card may be used to describe the responsibilities of a particular class (of objects) and to indicate what kind of object classes are needed to provide the services listed under the responsibilities of the (object) class. The design of a system consists of a collection of such cards, one for each class. The authors report that the use of these cards facilitates the design, in particular when working in groups; and, perhaps more importantly, that such a card design may be conveniently used to explain the design of a system to others. Using these cards, the dynamic operation of a system may be mimicked by selecting the appropriate card whenever a particular service is needed. Surprisingly simple, yet apparently quite effective. A similar method is proposed in [CY90]. As an example of the use of CRC-cards we will discuss the design of the classes underlying the user interface of Smalltalk programs. The approach taken by the designers of the Smalltalk system has become known as the MVC-paradigm. The basic postulate in this approach is that the classes describing the functionality that is needed to solve a problem must be separated from the classes that implement the interaction with the user. The class describing the problem related functionality is known as the model. Smalltalk provides a class Model that incorporates the methods needed to specify the other classes in an independent way. A CRC-card describing the class Model is pictured below. {\mbox{}\hspace{1cm}\begin{tabular}{|p{5cm}|p{4cm}|} \hline \fboxModel & \\ Maintain problem-related info.\nl Broadcast change information. & ... \\ \hline \end{tabular} A model class is defined as a subclass of Model. To enable the (graphic) display of a model, a view class must be associated with the model. To factor out the display, the model maintains a list of dependents of which the view object is a member. When the state of the model is changed, then the model notifies the objects in its list of dependents to allow these objects to update the information they have of the model. The functionality of a view class is rendered by the CRC-card depicted below. {\mbox{}\hspace{1cm}\begin{tabular}{|p{5cm}|p{4cm}|} \hline \fboxView & \\ Render the model.\nl Transform coordinates. & Controller \n Model \\ \hline \end{tabular} Apart from the possibility of displaying its state, a model may need input from the user. In the MVC-paradigm, obtaining user input is delegated to a so-called controller object. A controller object in its turn cooperates with both the model and the view. An additional function of a controller object is to distribute the control in response to the input from the user. The functionality of a controller is summarized in the CRC-card depicted below. {\mbox{}\hspace{1cm}\begin{tabular}{|p{5cm}|p{4cm}|} \hline \fboxController & \\ Interpret user input.\nl Distribute control. & View \n Model \\ \hline \end{tabular} A model may allow for a variety of views and a variety of ways to obtain user input. Hence, to each model may correspond a multiple of view--controller pairs. A design by CRC-cards may be regarded as a first attempt at modeling a real system. It presents, when properly documented, an overview of the design of the system that may be used to explain the decisions taken. However, it lacks the details needed to provide an adequate model that gives insight in the behavioral aspects of the system. \nop{ The example above shows that CRC-cards may be helpful in giving an outline of the design. However, as observed by the authors, an explanation needs to accompany such a design to make it understandable. }

Object oriented modeling

In an object oriented system, computation amounts to sending messages among objects. [Booch86] identifies the roles that objects may play in such a system. An object may be an actor that operates by sending requests to other objects but provides no services. An object may be a server that may be requested to perform some task. The most usual case, however, is that an object both suffers and requires actions. These objects, called agents in [Booch86], need as well as provide services. \id{ With regard to the distinctions made, we may want to phrase the design guideline {\it `minimize and localize dependencies among objects'} as a recommendation to maximize the number of actors and servers in a system, under the proviso that no more objects are introduced than necessary. } \oopindex{concurrency} An important advantage of an object oriented approach is that objects allow for a natural introduction of concurrency. A client of an object does not have to be aware of whether the object has activity of its own or is passive and only activated to respond to a message. In contrast, when applying a functional decomposition method to design a system the introduction of concurrency requires to reorganize the modular structure of the program, since modules there represent the major computation steps. The central guideline in developing an object oriented program comes down to the advice to construct an (object oriented) model of the problem domain. Object oriented modeling is hence the main activity in (an object oriented approach to) the requirement analysis and the design of a system.

Parallelism and distribution

\label{des/per/concept} One of the reasons for employing parallelism in a program is the need for efficiency. Preferably, the parallelism remains implicit, which means that the compiler takes care of how the concurrent execution of the program will take place. However, realizing implicit parallelism is in practice quite difficult and in most cases the programmer will have to indicate explicitly how to execute the program concurrently. Another, equally valid motivation for employing parallelism is that it better fits the conceptual structure of the problem to be solved. As an example, to synchronize the behavior of objects it may be worthwhile to allow objects to have activity of their own. C.f. [Pe89] and [Bro86]. \parindex{geographical distribution} As an additional aspect, the processes that are involved in a concurrent computation may be geographically distributed, either because they need resources residing on distant processors or to attain an increase in execution speed. See [CDJ84]. Programming languages that allow the computation to be spread over a number of distinct processors connected by a network are called {\em distributed programming languages}.

Computation models

\parindex{computation models} \disindex{computation models} When classifying distributed programming languages we can distinguish between three distinct underlying computation models. The most basic of these is that of communicating sequential processes, first presented in the influential paper of [Ho78]. Object-based concurrent languages may be regarded as extending this basic model, by generalizing communication and providing additional features for synchronization and protection. Finally, the model underlying concurrent logic programming languages is perhaps the most flexible of these, since it allows to mimick the two previous ones. The languages that we will refer to in this section are listed in the table below. .so tl Distributed programming languages may differ in what is employed as the unit of parallelism, the way they deal with communication and how partial failures are handled. In [Ba89] an overview is given of a number of distributed programming languages, discussing the choices made with regard to these dimensions.

Parallelism

\disindex{unit of parallelism} There seems to be abundant choice in what to take as the unit of parallelism, to name a few: processes (CSP), tasks (Ada), active objects (POOL), multi-threaded objects (Emerald), clauses (Concurrent Prolog and Parlog), or even statements (Occam). With respect to the granularity of computation, we encounter Concurrent Prolog and Parlog on the side of the spectrum of languages supporting small-grain parallelism and Ada or POOL on the other side, supporting large-grain parallelism. Large-grain parallelism means that, proportionally, the amount of computation significantly exceeds the time spent communicating with other processes. Another important issue is whether a language supports the allocation of processes to processors. Allocation is supported for instance by POOL and Occam.

Communication

\disindex{communication} Another decision that must be made concerns the way communication is dealt with. As alternatives we encounter data sharing and message passing. We mention Linda as an interesting example of data sharing.\ftn{ The apparent contradiction between distribution and data sharing is resolved by making a distinction between physical data sharing and logical data sharing. Obviously, we mean the latter here. Logical data sharing provides the programmer with the illusion of common data by hiding the physical distribution of the data. } Also Concurrent Prolog and Parlog, utilizing shared logical variables as the medium of communication, deserve to be classified among the distributed languages. Choosing for message passing we may employ point to point connections (CSP), channels (Occam, Delta Prolog) or broadcasting. Communication may to a certain extent be non-deterministic. For example, both the select statement of Ada and the guarded Horn clauses of Concurrent Prolog and Parlog result in a choice for a particular communication, ignoring alternatives.

Failures

\disindex{failures} \disindex{partial failure} As an additional feature, some of the languages mentioned in [Ba89] handle partial failure by offering exceptions, atomic sections or recovery mechanisms. Failure may be due to, for example, hardware errors or the violation of integrity constraints. We wish to remark that such failures are rather different from the failure encountered in a language such as Prolog. Failure in Prolog is one of the possible outcomes of a computation; it may even be used to generate all the solutions to a particular goal. \nop{

Computation models

\parindex{computation models} \disindex{computation models} When classifying the languages mentioned we can distinguish between three computation models underlying distributed programming. The most basic of these is that of communicating sequential processes, first presented in the influential paper [Ho78]. Object based concurrent languages may be regarded as extending this basic model, by generalizing communication and providing additional features for synchronization and protection. Finally, the model underlying concurrent logic programming languages is perhaps the most flexible of these, since it allows to mimick the two previous ones. }

Communicating sequential processes

\label{des/per:CSP} \parindex{sequential processes} The basic model of a distributed programming language is that of a group of sequential processes that run in parallel and communicate by message passing. By a sequential process we mean a process with a single thread of control. C.f. [We87].

Processes

\parindex{processes} The prime example of a language supporting communicating sequential processes is CSP. [Ho78]. In CSP we may create a fixed number of parallel processes by using a parallel operator. Each process consists of a name and a body, that is a sequence of statements. Communication between processes is achieved by using send and receive statements. As an example, consider the program [] [ p1 :: p2!3 || p2 :: p1?n ]

where process p1 is about to execute the statement p2!3

, sending the value 3 to process p2 and p2 is about to execute p1?n

, to receive a value from p1 that is assigned to the (integer) variable n. The proposal in [Ho78] also provides for pattern matching in communication. \parindex{guarded command} Also, a guarded command is offered, that allows to select a particular alternative dependent on the possibility of a communication. Due to its synchronous nature, communication in CSP is said to subsume synchronization mechanisms such as semaphores, events, conditional critical regions and monitors. C.f. [AS83].

Channels

\parindex{channels} Occam is a language that embodies a number of the features of CSP. [In84]. A noticeable difference with CSP is that communication statements do not address processes, but that instead communication takes place over channels. Occam is the machine language of the transputer. Transputers may be connected into a network. The language provides a mechanism for mapping symbolic channels to the actual hardware channels implementing the network. In contrast to CSP, Occam also provides facilities for mapping processes on processing units. \nop{ Despite the fact that Occam is a low level language, lacking data types, recursive procedures and modules, it is used in a number of applications. [Jo85]. } \parindex{efficiency} \parindex{grain of parallelism} Perhaps the major advantage of such a language is that it is efficiently implementable, giving the programmer full control over the hardware resources. C.f. [Ba89]. From the point of view of program design, however, the necessity of such control may be considered a disadvantage. From this perspective, languages with inherent parallelism seem more suitable. As alternatives to languages supporting the basic model we have: object oriented languages, that support concurrently executing active objects; functional languages, that allow parallel evaluation due to the absence of side-effects; and logic programming languages, that enable to work in parallel on parts of the and/or proof tree. \nop{ With the possible exception of the latter, these languages usually display a more fine grained parallelism. }

Object-based concurrency

\label{des/per:obj} \parindex{object based concurrency} Conceptually, objects are independent entities and the paradigm of method call by message passing allows in a natural way for concurrency. \nop{ The notion of an object based language covers a wide range of languages, including Ada, POOL, Emerald, Smalltalk and C++. An object may be characterized as an entity that has a collection of operations and a state that remembers the effect of operations.\ftn{ In accordance with the literature, we speak of object based languages and reserve the phrase object oriented language for the languages offering inheritance as an additional mechanism. See [We87] for a detailed discussion of the dimensions of object based language design. } C.f. [We87]. Apart from providing a construct to group operations, and a facility for defining an abstract interface to a collection of data, an object provides an additional protection mechanism since access and modification of the data it encapsulates is allowed only through the use of the operations defined for the object, the so-called methods. } However, even when considering method calls as (synchronous) message passing, object based languages may fit well in a sequential model of computation, assuming that an object is passive except when answering a method call. Extending the sequential object model to include parallelism may be achieved simply by allowing an object to be active on its own account, that is when not answering a message. As alternative ways to obtain parallelism, we mention the possibility to employ asynchronous communication as encountered in the Actor languages [He77], [Ag86]; or to add processes as an orthogonal concept to the language. A drawback of the last solution however is the need to provide extra facilities for synchronization and mutual exclusion. See also [GR88]. Active objects seem in this respect to be a much more natural solution, since such protection is already offered by the method interface, assuming that only one method is answered at a time. C.f. [Am89b].

Active objects

\parindex{active objects} The notion of active objects, that may be created dynamically, has been adopted by the language POOL. For a more extensive description of POOL see section \ref{impl/comp:lang}. Each object may have own activity, called the body of the object, that is started as soon as the object is created. The own activity of the object is interrupted to answer a method call when a so-called answer statement is encountered. The answer statement introduces a certain degree of non-determinism since, although a number of method calls may be considered acceptable, only one of these will be chosen. The communication model of method calls in POOL has been derived from the rendez-vous as encountered in Ada. See below. The rendez-vous, as an interaction between processes, has a two-way nature. It generalizes in this respect the primitives provided by for example CSP, that allow only one-directional point-to-point communication. In the terminology of POOL, the rendez-vous model is based on three concepts: a method declaration, which is like the declaration of a procedure having the right to access the private data of an object; a method call, which is like a procedure call but with an object as an additional parameter; and an answer statement, to interrupt the own activity of an object and to state the willingness to accept a particular method call.\ftn{ In the context of Ada one speaks of respectively an entry declaration, an entry call and an accept statement. } Answer statements allow to suspend the acceptance of a method call, dependent on the state of the object.\ftn{ Even stronger acceptance conditions may be imposed in Concurrent C that allows to inspect the actual parameters of a call to determine acceptance. }

The rendez-vous in Ada

\parindex{rendez-vous} We will explain the rendez-vous concept in somewhat more detail by looking at some simple Ada program fragments, taken from [Perrott87]. \parindex{Ada -- task} In Ada a process is called a task. As an example of the specification of a task, consider the declaration of a (single-element) buffer. \yprog{task}{

   task buffer is
     deposit( c : in character );
     remove( c : out character );
   end buffer

} The declaration specifies that a buffer allows two operations, namely an operation to deposit a character and an operation to remove a character. An implementation of the buffer is given by the following definition \yprog{body}{

   task body buffer is
       ch : character;
   begin
      loop
         accept deposit( c : in character)  do   ch := c   end
         accept remove( c : out character)  do   c := ch   end
      end loop
   end buffer

} The body of a buffer specifies the own activity of a buffer, which is given by the succession of two accept statements, to accept subsequently a deposit call and a remove call, repeated indefinitely. To illustrate the use of the buffer, we assume the existence of a producer task in which the statement buffer.deposit(c); for a character c, occurs and a consumer task in which a statement buffer.remove(c); occurs. The first rendez-vous then takes place between the producer and the buffer when the buffer accepts the call for deposit. After that, the buffer has no other choice then to accept a remove call, which must come from the consumer task. It is important to note that the rendez-vous in Ada is of a synchronous nature. Only when the remote procedure call is completed may both tasks resume their activity. From the implementation of the body of the buffer task, we can infer that the buffer actually is a one-element buffer. However, the implementation may be changed (without affecting the task specification) by using for example an array of characters. In that case we may wish to use a more sophisticated protocol for accepting a call, a protocol that allows to take into account the number of elements the buffer contains. Ada offers a so-called select statement and a construct enabling the conditional acceptance of a call by which such a protocol can be implemented. The non-determinism allowed by these constructs is local, since it is solely dependent on the internal state of the task.\ftn{ In constrast, CSP supports global non-determinism by enabling a programmer to impose conditions with respect to the environment of the process, for instance to check whether a communication event may occur. }

Multiple threads

\parindex{multiple threads} As another object-based distributed language, we wish to mention Emerald. Just as POOL, Emerald offers the possibility to create active objects dynamically. An important difference between POOL and Emerald however is that Emerald allows multiple threads of control: one object can be active answering a number of method calls. Moreover, the processes created for answering a method call run in parallel with the process executing the own activity of the object. A monitor construct is provided to enable synchronization and protection when accessing local data shared by processes active for the object.

Allocation

\disindex{allocation} Object-based concurrency is most suitable for large-grain parallelism. Large-grain parallelism results in processes of considerable size. To the extent that these processes may run independently, speed-up can be obtained by allocating these processes to distinct processors. The language POOL enables the programmer to locate a newly created object on a particular processor by so-called pragmas, listing the set of processors from which the system may choose. In addition to a facility for mapping objects and processes to processors, Emerald supports the migration of objects and processes by allowing them to move, or to be moved, from one processor to another.

Concurrent logic programming

\label{des/rel:CP} \parindex{concurrent logic programming} \disindex{concurrent logic programming} The model underlying concurrent logic programming forms a rather radical departure from the two previous models in that communication is essentially effected through shared logical variables. Parallelism is inherent in the computation model of logic programming languages, because of their declarative nature. \parindex{\em or} parallelism} \parindex{\em and} parallelism} Basically, two kinds of parallelism can be distinguished: and-parallelism that is due to the parallel evaluation of the atoms in a compound goal, and or-parallelism that arises from trying multiple clauses simultaneously for finding a solution to a goal atom. Although there are a number of attempts at implementing parallel Prolog this way, the two major representatives of concurrent logic programming, Concurrent Prolog and Parlog, have based their approach on the additional assumption of committed choice non-determinism and restricted unification.

Committed choice

\parindex{committed choice} \parindex{guarded Horn clauses} Unlimited or-parallelism, required to find all solutions to a goal, may result in an uncontrollable amount of processes. To restrict or-parallelism, guarded Horn clauses were introduced. A guarded Horn clause is a clause of the form [] A:- G1,...,G_n | B1,...,B_m.

where A is the head of the clause, G1,...,G_n

the guard goals and B1,...,B_m

the actual body of the clause. When a goal atom is evaluated, all clauses of which the head unifies with the atom are selected and the guards of these clauses are evaluated in parallel. The first clause of which the guard is evaluated successfully is committed to. The alternative solutions to the goal atom, embodied in the competing clauses, are thrown away. Since only one clause is chosen, backtracking over alternative solutions is impossible, once the commitment to that particular clause is made. What is allowed as a guard influences the expressiveness of the language in a significant degree, and for that matter the difficulty of implementing it. See [Sh89] for an extensive discussion of this topic.

Restricted unification

\parindex{restricted unification} Unrestricted and-parallelism, that is the parallel evaluation of the atoms in a compound goal, may result in incompatible bindings of the logical variables involved. To handle this problem, both Concurrent Prolog and Parlog require to indicate which atom acts as the producer of a binding to a variable and which atoms are merely consuming the binding. Concurrent Prolog uses annotations to indicate the variables that must be bound to a term to enable the evaluation of the atom in which they occur to proceed. Parlog, on the other hand, uses mode declarations, indicating the input/output behavior of the arguments of a predicate.

Objects

\disindex{objects in concurrent logic programming} Concurrent logic programming languages offer a very versatile mechanism for implementing distributed systems. C.f. [Sh89]. In particular these languages allow to implement active objects with state variables in a very elegant way. This is achieved by defining clauses for objects according to the scheme presented below. \oprog{object}{

   obj(State, [Message|Messages]) :-
  		\{\it handle\} Message,
  	        \{\it update\} State \{\it to \} State',
  		obj(State',Messages).

} An object is implemented as a tail-recursive process, that receives messages and updates its state if necessary. C.f. [ST83]. As an example, consider the clauses implementing a counter in Concurrent Prolog. \oprog{ctr}{

   ctr(N,[inc()|T]):- N1 = N + 1, ctr(N1,T).
   ctr(N,[value(N)|T]) :- ctr(N,T).

} The first argument of ctr represents the state of the object, that is passed as an argument to the recursive call, appropriately modified if necessary. The second argument represents the stream of incoming messages, with the tail unspecified to await later binding. Concurrent logic programming languages offer fine-grained parallelism. As an additional feature for dynamically mapping computations to processes [Sh84] proposes a turtle notation for executing Concurrent Prolog programs on a grid of processors. See also section \ref{des/ext/alloc}.

Extensions

The primary advantage of using a concurrent logic programming language for implementing distributed systems is the declarative nature of these languages, allowing a logical interpretation of a program. This property is preserved when implementing objects in the way shown. To overcome the syntactical complexity of this approach, two languages combining logic programming and object oriented programming have been proposed, Vulcan and Polka, that preserve the declarative semantics of their underlying logic programming languages.\ftn{ These languages will be discussed in section Vulcan. } The drawback of this approach, however, is that the restrictions imposed by the requirement of efficiency -- committed choice and restricted unification -- do not allow for the occurrence of backtracking.

Software engineering perspectives

\seindex{perspectives} Of the various phases of the software life cycle, the design phase is perhaps the most interesting one since it aims at reconciling the requirements resulting from the analysis phase and the restrictions that are a priori imposed on the implementation phase. On the one hand a design must specify the structure and functionality of a system in a conceptually clear way and on the other hand it must take into account the feasibility of an implementation. To conclude this introductory chapter, we will investigate what support the three paradigms just treated provide with respect to the design of a system, that is to which problems they promise a solution and which questions they leave unanswered.

Logic programming

\seindex{logic programming} The contribution of logic programming as a program design formalism lies primarily in its declarative nature. Designing a program in a logic programming formalism enables an easy transition to an actual implementation in a language such as Prolog. Prolog is a general purpose language based on first order logic with a simple semantics. It uses backward chaining inference as a computation mechanism. Due to its declarative semantics a Prolog program may be read as a logical theory concerning a particular domain. This aspect has contributed to the popularity of Prolog for AI-applications. It has been extensively used to implement expert systems. See [Bu83]. Further, it has been used to model British legislation, drug design and even systems programming. In addition, in [Webster] Prolog is characterized as a potentially powerful design representation tool, since it may be used to specify the functionality of systems in a concise and formally precise way.\ftn{ In a similar vein, constraint logic programming languages can be thought of as providing an even more powerful formalism, since these languages have knowledge of a particular (formal) domain built-in, which allows them to solve equations over these domains. } For the representation of knowledge, however, Prolog has a number of drawbacks. It lacks first of all facilities to modularize knowledge, that is to partition the knowledge in module-like entities. It lacks, secondly, a means to construct hierarchies of concepts in a structural way. A number of extensions have been proposed to deal with these deficiencies, extensions with hierarchical frame-based representations, with inheritance hierarchies and object oriented features. According to [Su85], none of these extensions have matured sufficiently to gain wide acceptance. Promising approaches seem to be those aiming at incorporating object oriented features in the logic programming paradigm, that allow to create logical theories dynamically as first-class entities.

Object oriented programming

\seindex{object oriented programming} Object oriented software technology has major impacts on the traditional software life cycle. One of these impacts is the shift of emphasis brought about in the relation between the design and the implementation phases of a software development project. The design phase has become increasingly important since the availability of object oriented programming languages allows to regard the implementation as a process of refining the decisions made in designing the system. The popularity of object oriented programming languages is partly due also to their successful use in prototyping systems of medium complexity. According to [Meyer88] the introduction of object oriented programming has meant the beginning of a revolution in the program development process, since these languages allow to design a system bottom-up, instead of in the traditional way, top-down. The end result of developing a system, bottom-up or top-down, is a set of classes that specifies abstractly the functionality of the corresponding objects by means of external method interfaces. After a while, designing a system comes down to selecting a number of already existing components and assembling them according to the requirements resulting from analysis. Although, undeniably, the object oriented approach promotes the reuse of software, there are many problems to be solved before this view becomes reality. See for example [Meyer90] and [BV90]. One of the major problems that we encounter here is the problem of granularity. In many cases, a class will be a too low-level entity to serve as the unit of reuse. A visual metaphor that illustrates this problem is given by the term ravioli-code to characterize a large collection of well-structured objects with highly complex interrelations. To overcome problems of granularity, one has to think in terms of application frameworks to capture the functionality of subsystems. Even then, the specification of a system in an object oriented programming language falls short of providing insight into the conceptual structure of the system, that is the design underlying the program.\ftn{ The plethora of constructs that may be encountered in actual object oriented programming languages makes this insight even more difficult. } Experience has shown that prototyping is advantageous in situations where the requirements are likely to change. To enhance the conceptual understanding of the system embodied by the prototype, the language in which the prototype is implemented needs to be of a sufficiently high level to allow the code to be read as a formal specification of the system. An object oriented approach is only fruitful then, if the objects implementing the system provide an abstract view that corresponds with the way we perceive the problem domain.

Parallel/distributed programming

\seindex{parallel/distributed programming} The choice for a parallel or distributed implementation may be motivated either by the application domain, in which concurrency is a natural phenomenon, or by efficiency considerations. From either perspective, designing a distributed system involves a partitioning of the system into separate components and an allocation of these components to (possibly distinct) processes. See [Shatz87]. In order to distribute the computation among a number of concurrently executing components, the design will have to indicate a partitioning of the functionality among a number of distinct logical modules. Further, the design must specify the synchronization and possibly the communication that occurs between these logical modules. Logical modules, in the sense used here, may be active objects, single-threaded processes or even multi-threaded processes. For the actual exploitation of parallelism, an allocation of these modular entities to processes must be given, taking into account possible precedence relations that may hinder the independent execution of these modules. Allocation may be done statically, before actually starting a system, or may be determined dynamically by an allocation algorithm that takes system parameters such as the workload and the availability of processors into account. Using a performance oriented cost function to determine an optimal allocation, further factors that may be taken into account are the amount of interprocessor communication and the total completion time. One of the principal difficulties in designing a distributed system is to ensure the correctness of the program. Verifying a distributed system is difficult because of the non-deterministic behavior of such a system, that results from the independence of the concurrently executing components. This non-determinism makes dynamic testing almost infeasible. First of all, it is hard to reproduce the state of the system that has resulted in an error. Secondly, since there is no global state there is no way to freeze the execution in order to inspect the states of the individual components. Before freezing takes effect, the relevant components may already have changed their local state. As a more fruitful approach, [Shatz87] recommend to employ static testing, an analysis that may be performed without executing the program. In a static test all syntactically specified control-flow paths must be considered. Analysis may then reveal the potential for deadlock, or the occurrence of particular communication events. Given the difficulty of applying a verification method to ordinary sequential languages, the difficulty of applying such a method to a distributed program will be clear.

Distibuted logic programming

\seindex{distributed logic programming} In the previous discussion we have indicated some of the problems that arise in designing a software system. Whatever formalism is used, the partitioning of a program into modules and the specification of the interaction between modules will always remain a non-trivial problem that can only be solved by creative thinking. Our effort of introducing a new language is not meant as a promise to make this task any easier but to provide the means to encode a solution in a high level formalism, including all relevant aspects of a system (including its physical distribution). Such a high level description promotes the conceptual understanding of the system specified and makes the task of verifying the program easier. In developing the language DLP, which will be the subject of the rest of this book, we have made choices to combine the paradigms introduced in this chapter. With this discussion we have made an attempt to motivate these decisions from a software engineering perspective.