topical media & game development
object-oriented programming
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
E
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 ,
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
E
- 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.
(C) Æliens
04/09/2009
You may not copy or print any of this material without explicit permission of the author or the publisher.
In case of other copyright issues, contact the author.