Principles of Object-Oriented Software Development

[] readme course preface 1 2 3 4 5 6 7 8 9 10 11 12 appendix lectures resources

The language DLP

Apart from what may be considered the mainstream languages Smalltalk, Eiffel, C++ and Java, there are numerous other (experimental) languages incorporating the object paradigm in one way or another. See section classification and, for example, [Davison93] for an overview. Of particular interest is the combination of the logic programming paradigm with object orientation, of which the language DLP is an example.

DLP -- introduces logic into object orientation

DLP = LP + OO + $||$

Design principles -- support for knowledge-intensive applications

objects -- dynamic states
processes -- communication by rendezvous
distributed backtracking -- exhaustive search

slide: The language DLP

The DLP language combines logic programming (LP) with object orientation (OO) and parallelism (

||

). DLP is a (very) high-level language, meant to support the development of knowledge-intensive applications. In addition to the logic programming features, it provides objects (that may change their state dynamically), processes (such as active objects, that communicate by rendezvous), and it allows for distributed backtracking (to enable exhaustive search in a logic programming style). See [Eliens92] for a full treatment.

Terminology

Syntactically, DLP may be regarded as an extension of Prolog with constructs for parallel object-oriented programming. However, in addition to the familiar Prolog constructs it offers objects as well.

Objects -- a labeled set of clauses

DLP


  object name {
  var variables.
  
  constructor clauses
  method clauses
  }

slide: DLP -- terminology

An object definition or object in DLP is a (labeled) collection of (Prolog) clauses that define the methods supported by the object, and which in addition may contain non-logical variables that are private to each instance. An active object also contains one or more constructor clauses that defines the object's own activity. See slide dlp-term.

Expressions

The expressiveness of DLP is derived to a large extent from its heritage from Prolog. The basic syntactic units in Prolog are terms, which are either constants (such as characters, integers, strings, or the empty list

[ ]

), variables (which by convention start with a capital or underscore), or compound terms (which may be written as a function symbol with argument terms or as a list of the form

[ H | T ]

, where H stands for the head of the list and T for its tail). See slide dlp-expr.

Expressions -- terms

Prolog

constants -- a, "a string", [ ]
variables -- X,Y,Z
compound -- f(a,X), [ H | T ]

Unification -- bi-directional parameter passing

f(X,a) = f(b,Y) results in X = b and Y = a

slide: DLP -- expressions

Terms allow for what is called unification, which is an extended form of pattern matching. Unification results in binding variables to terms, in such a way that the two unified terms become syntactically equal. As an example, unifying f(X,a) with f(b,Y) results in binding X to a and Y to b. Unification is the primary mechanism of parameter passing in Prolog. It is essentially bi-directional and satisfies the one-assignment-only property, which means that evaluating a goal must result in a consistent binding, otherwise the goal fails.

Control

The computation mechanism employed by Prolog may be characterized as goal reduction with unification and backtracking. As an example, look at the Prolog program in slide dlp-control-1, consisting of a number of clauses and facts.

Prolog


  p(X,Y) :- r(Z), b(X). // clauses
  p(X,Y) :- q(Y), b(X).
  b(X) :- a(X).
  b(0).  // facts
  a(1).
  q(2).

Query


  ?- p(X,Y). // results in (X = 1,Y = 2)
              // and (X = 0, Y = 2)

slide: DLP -- control (1)

When we pose our query, it is first attempted to resolve the goal p(X,Y) with the first clause for p (which fails because r(Z) cannot be resolved). Then the second clause is tried, which leads to binding Y to 2 (since q(2) is a fact), and gives us two possible bindings for X, due to the facts a(1) and b(0). (Variables are local to clauses and will be renamed automatically to avoid clashes.) Hence, the evaluation of the goal p(X,Y) leads to two consistent bindings, that may successively be obtained by backtracking.

As an example of somewhat more realistic clauses, look at the list processing predicates member and append in slide dlp-control-2.

List processing -- backtracking


  member(X,[X|_]).
  member(X,[_|T]) :- member(X,T).
  
  append([],L,L).
  append([ H | T ],L,[ H | R ]):- append(T,L,R).

slide: DLP -- control (2)

Both predicates are specified in an inductive manner, taking care of all possible cases. For example, the first clause for member states as a fact that an element is contained in a list when it is the first element. The second clause prescribes the recursive application of member to the tail of the list if this is not the case. Similarly, the clauses for append distiguish between the case of appending a list to an empty list, and the case of appending a list to a non-empty list.

This manner of specification closely adheres to standard practice in mathematical logic and has proven to be a powerful means to develop knowledge-based systems (such as expert systems) that rely on logical reasoning.

Objects

The language DLP supports active objects with a state (expressed as the value of non-logical instance variables) and communication by rendezvous (which realizes message passing for active objects). See slide dlp-objects-1.

Additional statements

DLP

v := t -- to assign to non-logical variables
O = new(c(t)) -- to create an active instance of the object c
O!m(t) -- to call the method m(t) for the object O
accept(m1,...,m_n) -- to accept method requests

slide: DLP -- objects (1)

To support these features we need, in addition to terms and clauses, statements to assign terms to non-logical variables, a statement to create new active instances of an object (class), a statement to call a method for an object (which is essentially the invocation of a goal), and an accept statement that allows an active object to interrupt its own activity and accept the request to execute a method. When binding terms to logical variables or assigning terms to non-logical variables, simple rewriting rules are applied. Rewriting includes arithmetic simplification and string manipulation.

Computation model -- distributed logic

objects -- state + methods
processes -- to evaluate goals
communication -- backtrackable rendezvous

slide: DLP -- objects (2)

The computation model underlying DLP is a model that supports distributed logic, and may be seen as a combination of the models underlying logic programming and parallel object-oriented languages. See slide dlp-objects-2.

The DLP support system provides, in addition to a Prolog-like evaluation mechanism, support for objects (having a state, and methods defined by clauses), processes (to realize the object's own activity as well as to evaluate method calls or goals for the object), and a communication mechanism (that allows for a backtrackable rendezvous).

As an example of an object in DLP, look at the travel agency defined in slide dlp-objects-3, which has a non-logical instance variable cities (containing a number of destinations), a constructor travel (which defines the object's own activity) and two methods, reachable and add.

Object


  object travel {    travel  


  var cities = [amsterdam, paris, london].
  
  travel() :- accept( all ), travel().
  
  reachable(X) :- member(X, cities).
  add(X) :-
  	append( cities, [X], R), cities := R.
  }

Usage


   ?- O = new travel(), O!reachable(X), write(X).

slide: DLP -- objects (3)

The reachable method may be used to ask whether a particular destination exists or to ask for all possible destinations (which are actually obtained by backtracking). The add method may be used to add new destinations to the list of cities.

The travel constructor merely consists of a (tail-recursive) loop allowing to accept any request, one at a time. By specifying which requests may be accepted at a particular point in the lifetime of the object, the message interface of the object may be dynamically specified. In addition, an explicit accept statement is needed to guarantee mutual exclusion between method calls.

Inheritance

DLP supports static inheritance, by code sharing, as do Smalltalk, Eiffel, C++ and Java. For a discussion of dynamic inheritance, by delegation, see section prototypes. As an example of inheritance in DLP, look at the refinement of the travel object into a veritable agency. See slide dlp-inheritance.

Inheritance


  object agency : travel {    agency  


  agency() :- accept( any ), agency().
  book(X,Y) :-
  	reachable(X),
  	price(X,Y).
  price(amsterdam,5).
   ...
  }

slide: DLP -- inheritance

An agency offers the user, in addition to the functionality offered by travel, the opportunity to book for a particular destination and be informed of its price.

Inheritance in DLP conforms to the subsumption relation for logical theories, in that it extends the functionality of a given object in a strict manner. DLP allows for multiple inheritance and even checks for cycles to protect the user from repetitions or cycles in the inheritance chain.

Technology

Logic programming offers a wealth of techniques. In particular, the meta programming facilities (which are essentially based on the interpretation of programs as data) allow for very powerful programming techniques. See, for example, [Bratko].

Techniques -- logic

meta programming
active intelligent agents

slide: DLP -- technology

By virtue of being an extension of Prolog, DLP inherits these facilities. In addition, DLP provides the constructs necessary to define what may be called (active) intelligent agents, of which the functionality can be specified in a declarative, logic-based fashion. DLP, in other words, is an example of a fruitful combination of paradigms, merging logic with object orientation.

Summary

This section has presented an overview of the DLP language. It discussed the design principles underlying DLP and characterized its principal application area as the development of knowledge-based systems.

The language DLP

design principles -- logic
terminology -- distributed backtracking
syntax -- Prolog + additional statements
objects -- non-logical instance variables
inheritance -- static
techniques -- active intelligent agents

slide: DLP -- summary

It gave a brief characterization of Prolog, explained how DLP syntactically extends Prolog with constructs for parallel object-oriented programming, and characterized the computation model of DLP. Some examples were given to illustrate the definition of objects and the use of inheritance.

Knowledge-intensive applications will increasingly become part of mainstream IT. Distributed declarative languages and systems, of which DLP is just one example are likely to become the vehicle of choice for such applications.

A language such as DLP is particularly well suited for the realization of so-called agents, software processes that act as an intermediary between the end-user of a system and the system itself.

[] readme course preface 1 2 3 4 5 6 7 8 9 10 11 12 appendix lectures resources

eliens@cs.vu.nl

draft version 0.1 (15/7/2001)