COMPOUND MODULES AS GOALS INFORMATICA 3/1988 
UOK 681.3.06 PR0L0G:519.682 
Monika Kapus-Kolar 
IJS, Ljubljana 
Osnovna objektna interpretacija jezikov tipa Prolog je kreiranje 
in brisanje modulov. Nekateri jeziki te družine (npr. Delta Prolog) uvajajo 
vzporedno/zaporedno kompozicijo in eksplicitno komunikacijo, zaradi česar so 
primerni za specifikacijo komunikacijskih protokolov. Najvažnejša ideja 
pričujočega dela je ločitev pojma modula od pojma cilja, tako da lahko vsak 
modul sodeluje v več ciljih (sestavljenih modulih). Jezik Hornovih stavkov z 
vzporedno/zaporedno kompozicijo atomičnih dogodkovnih in nedogodkovnih ciljev 
smo dopolnili z novimi sintaktičnimi elementi, ki v luči nove izvedbene 
semantike omogočajo bolj jedrnato specifikacijo komunikacijskih protokolov, 
posebno tistih, pri katerih so potrebne številne operacije na posamezni 
zapleteni podatkovni strukturi. Jedrnatost dosežemo s temeljito izrabo 
možnosti, ki jih nudi struktura sestavijenih modulov, ki je ponavadi precej 
preprostejša kot sintaksa atomičnih modulov. 
The basic object paradigm of Prolog-type language 
modu les. Some languages of the farnily (e.g. De 
lel/3equential composition and explicit communic 
table for specification of communication protocol 
the paper is separation of the "module" concept f 
that a module may participate in several goal 
svntactic enhancements have been proposed for t 
with parallel/3equential composition of atomic 
which in the light of the new operational semant 
specification of protocols, particularlv those r 
on a complicated piece of data. The core idea 
exploitation of the structure of compound modules 
simple than the 3yntax of atomic modules. 
s is creation and deletion of 
Ita Prolog) introduce paral-
ation, what makes them sui-
s. The main contribution of 
rom the concept of "goal", so 
s (compound modules). Some 
he language of Horn clauses 
event and non-event goals, 
ics provide for more concise 
equiring multiple operations 
of the new language is full 
vjhich is usually much more 
1. Introduction 
The basic idea behind languages of the Prolog 
faniily is to find solutions to a problem (goal) 
by its reduction into more and more trivial 
subproblems (subgoals). 
A Prolog program, [4], is a set of universally 
quantified first order axioms (Horn clauses) of 
the form 
A:- Bi.Ba,...,Bo 
vhere the fl and the B's are atomic formulae, 
also called atomic goals. A is called the 
clause's head and the B's are called its body. 
The computation proceeds by selection of a goal 
Al frora the current conjunctive goal 
(Ai.Aa Am), which is then reduced with a 
selected clause 
A' :— Bt , B3, . . . ,Bi« 
where A and A' must be unifiable via the most 
common substitution 6. The reduction step 
transforms the current goal into 
(Al ,Ai_i,Bi,...,Bw,Ai-. ,A„)e. 
In the process of unification, some of the 
variables of the initial goal are assigned 
values, vjhich constitute • the output of the 
computation. The computation terminates suc-
cessfully, when the initial goal is reduced 
into an empty goal, but may terminate unsuc-
cessfully, if no further reduction is possible, 
or not terminate at ali. Several successful 
computations of a program may exist, resulting 
from various selections of clauses for reduc­
tion . 
Graphical representation of a Prolog program is 
an AND/OR tree with AlfD nodes mode 11 ing compo­
sition of goals into a clause body and OR nodes 
enumerating the suitable clauses for reduction 
of a particular goal. Several goals can be 
reduced in parallel (AND-parallelism) and seve­
ral alternative solutions searched for in pa­
rallel (OR-parallelism). True concurrency is 
allowed, if atomicity of reduction steps is 
preserved. 
The inherent AND-parallelism of Prolog programs 
makes them suitable for operational specifica-
tion of communication protocols. An AND subtree 
of the AND/OR tree mode Is a particular execu-
tion of a system, while the search of the 
entire AND/OR tree represervts verification of 
ali ' possible behaviours of the system. Note, 
that logic programming is also suitable for 
axiomatic specification and verification of 
communication protocols, but the paper does not 
deal with this aspect. 

The language has two major deficiencies: First, 
by introducing AND-parallelism, the execution 
order is controlled by the goal-subgoal rela-
tion only, ao it is difficult to deacribe 
3equential protocols. Second, communication 
between goals is implicit and asynchronous via 
coOTDon variables, vhile partners in communica­
tion protocols are usually loosely coupled (not 
sharing any variables). 
To solve the first problem, many Prolog-type 
languages (e.g. Delta-Prolog (DP) [6,7]. Con-
current Prolog (CP) [5], M-Prolog [9]) maJ<e 
distinction betveen the paral le 1 (!I) and the 
seguential (!) composition of goals. Declarati-
vely, the two composition operators are equiva-
lent to the AND-operntor, but serve to 3pecify 
the execution order in the špirit of CCS (11, 
CSP [2] or LOTOS [3]. 
In the literature, we meet two types of expli-
cit consnunication: communication on the level 
of variables and communication on the level of 
atomic goals. An example of the first type are 
the "read-only" variables in CP, modelling 
asynchronou3 broadcast. An e^ample of the 
second type are events in DP. Here, the wil-
lingness of a module to participate in an event 
of a particular type is expreased by a goal of 
a gpecial kind - an event goal, which is 
3uccessfully reduced in cooperation with some 
peer event goala of the (other) modules. The DP 
concept of events allow3 various cooperation 
schemes, differing in the number of participa-
ting modules, the degree of their 3ynchroniza-
tion and in side-effects of a particular event, 
while in CP, a single cooperation acheme is 
defined. Aiming tovards an event-order specifi-
cation language, the DP concept of events is 
adopted in the paper and extended. 
2. The Architectural Aopect of the Languasre 
An instantaneous representation of a system, 
described by a set of Horn clauses, is a tree -
the architectural tree. Nodes of the tree are 
hierarchical paral lel/seguential compositions 
(trees) of goals. The root represents the top-
level structure of the svstem, i.e. its static 
architectural components (the initial execution 
goal). Each atomic goal represents a declara-
tion of a particular module of the sy3tem. When 
an atomic goal ia reduced with a clause, the 
body of the clause is introduced in the tree as 
a descendant of the goal. A aubtree, attached 
to an atomic goal, represents dynamic architec-
ture of the module, declared by the goal. After 
a node has been succe3sfully executed (ali- its 
atomic goals reduced to TRUE), it is deleted 
from the tree. 
As the overall activity of a system is repre-
aented aa creation and deletion of modules, 
there is no evident distinction betveen a 
module, representing a guasi-static architectu­
ral component of the system, and a module, 
representing a procedure. Such semantic 
distinction belongs to a lower level of 
abstraction. The only feature that matters is 
the capability of the language to 3pecify 
loosely coupled modules. Modules are declared 
"loo3ely coupled" simply by Jceeping their va-
riable-sets disjoint. 
Atomic goals, which are event goals, do not 
generate subtrees, but are reduced in events. 
Looking at an event as a common action of 
several modules, it ia a free module, not 
embedded in the architectural tree, with its 
submodules residing in various nodes of the 
tree. According to the previous paragraph, it 
ia difficult to say which module does a parti­
cular event goal belong to, but it is no doubt 
that it belongs to a certain node. As events 
should serve for cooperation between loo3ely 
coupled modules, it is reasonable to declare 
that event goals, participating in a particular 
event, must not belong to the same node. 
The word "goal" 
architectural co 
tion of the curre 
at that point 
instantaneous pic 
atomic goals are 
They are basic 
U3ually combined 
rallel/sequential 
should not be used in the 
ntext - it denotes the inten-
nt architecture to change, but 
we are only interested in an 
ture of a 3y3tem. Therefore, 
rather called atomic modules. 
elements of nodes and are 
into compound moduleo by pa-
composition operators. 
Moduleo are further classified into expllclt 
and implicit ones. They can be best identified 
by observing a clause body (e.g. Fig.l): 
compound module: (AlBl(C. ID;;(EIF))) 
explicit modules: 
A, B, C, D, E. F 
(EIF) 
(Cl IDI I(EIF)) 
(AlBl (Cl IDI I(EIF))) 
implicit modules: 
(CIID), (DIKEIF)), (CIKEIF)) 
(AIB), (BI(ClID!I(EIF))) 
Fig.l: Explicit and implicit modules of a 
compound module. 
Atomic modules and bodies are exp 
Operands of paral lel and 3equenti 
operators are explicit modules 
subaet of modules with more than 
belonging to a parallel compositi 
is an implicit module and itsel 
composition of modules. Any prop 
of modules with more than one el 
ging to a seguential composition 
an implicit module and itself 
composition of modules. 
licit modules. 
al composition 
Any proper 
one element, 
on of modules, 
f a parallel 
er subsequence 
ement, belon-
of modules, is 
a seguential 
The above definition illustrates the module-
grouplng and raodule-orderlng role of the two 
composition operators. The parallel composition 
operator groups modules into seta and the 
sequential composition operator groups modules 
into 3equence3. Explicit modules are the actual 
and implicit modules the potential groups of 
modules. 
3. The Operatlonal Aapects of the Language 
3.1. Compound Modules as Goals 
If a module is declared to be a goal, it 
specifies a pending action. The goal becomes 
"executed", when the action is no longer pen­
ding. A node gains the right to be deleted from 
the architectural tree, after aH ita goals 
have been executed. 
In DP, only atomic modules are goala, every 
atomic module is a goal and the pending action 
of each goal is its reduction into TRUE. The 
main. contribution of the paper is the idea, 
that the concept of module should be fltrlctly 
oeparated from the concept of goal, so that a 
module might participate In several goals 
(compound modules). Note the importance of the 
word "participate" - a module itself ia not 

necessarv a goal, but every module ahould be 
included into some goal, ofhervise it has no 
practical role in the sy3tem. 
Motivation for the new idea has been the fact 
that in most cases events aerve juat for 3ome 
kind of unification of modules, belonging to 
various nodea. From this aapect, event goala 
are just communicated pieces of data. Aasuming 
that there is a group (compoaition) of modulea, 
there might be aeveral nodes, each intereated 
in a particular subgroup of the group and 
villing to obaerve the whole subgroup in a 
single event. It is much more elegant to 
enumerate members of the group once and to 
declare that each subgroup of the group is an 
event goal, than to enumerate ali subgroups aa 
atomiC event goals. If a group of modules is a 
set (parallel composition), it might aerve as a 
data-baae (see aection 5 for the example in 
Fig.6); if it is a sequence {sequential compo­
sition) , it might serve for specification of a 
data-stream with multiple obaervers, each wai-
ting for a particular sub3equence. If the 
unifying event goals are parallel compoSitiona 
of modulea, the unification rule could be less 
strict (unification posaiblv preceded by permu-
tation of modulea) than for event goals, which 
are sequences. The fact ia, that seguences and 
aeta already exist in clause bodies, so why not 
to use them (aection 5). Similarly, if there 
has been a non-event goal (a procedure) execu-
ted, why should ita declaration part be dupli-
cated just to communicate ita exit resulta to 
an obaerver. 
The central operational concepts of our lan-
guage are reduction goala and event goals. The 
two naraes indicate that the concept of reduc­
tion has been separated from the concept of 
event - without thia step the realization of 
our ideas vrould not be possible. The role of 
reduction goals is tvofold: First, if they are 
atomic, they enforce execution of procedurea in 
the ordinary sense (like non-event goala in 
DP). Second, they control execution order by 
impoaing hierachical execution of goals: No 
goal can be executed, if some of its submodules 
are pending reduction goals, so that no event 
can occur on exit resulta of a procedure, until 
they are available. Becauae of the nature of 
the two roles, only explicit modules may be 
reduction goals, so that a reduction goal must 
be entirely contained in another reduction 
goal, or not at ali. 
Event goala aupport the idea of overlapping 
goala, as they may be explicit or implicit 
modulea and may partially ov"erlap. An event 
goal is executed by an event, where the parti-
cipating part of a node ia exactly the module, 
repreaenting the goal. Event goala impoae no 
particular execution order - a dangerous dimen-r 
aion of freedom, which ia partially compenaated 
with the execution-ordering role of reduction 
goals and composition operators. 
Depending on its reduction type (see section 
3.3.), execution of a reduction goal is inde-
pendent from events or a reduction goal is a 
submodule of an event goal and executed simul-
taneou3ly with the event goal. 
In DP, event goals never generate deacendants 
in the architectural tree, while event goals 
with atomic submodules, which are reduction 
goals, requiring the ordinary type of reduc­
tion, do. Nevertheless, when such an event goal 
gains permission for execution, ali auch reduc­
tion goala vrithin it have already been executed 
and their deacendants deleted from the tree. 
3.2. The Execution-ordering and the Selection 
Role of Composition Operatora 
The basic role of composition operators is 
their module-grouping and module-ordering role, 
but for ea3y specification of 3equential proto-
cols they must alao be assigned the execution-
orderlng role. To employ the full power of the 
two roles, it must be possible to use them 
independently, while in DP they are not separa­
ted. Therefore we define that the parallel and 
the sequential composition operator have no a 
priori execution-ordering role. 
When considering the execution-ordering role of 
composition operators, the distinction between 
compound modules, which are aets, and those, 
which are sequences, is irrelevant, because the 
attribute parallel/3equential, attached to com­
position operators, applies to another role. 
Therefore, ali compound modules vri 11 be treated 
as aequence3 of modules. 
A composition operator separates a sequence of 
modulea into the left and the right subse-
quence. A DP 3equential composition operator 
forces the goals from the left subsequence to 
be executed before' the goals from the right 
subsequence. But if a goal extends to the left 
and to the right 3ub3equence, which subseguence 
does it belong to? Another que3tion: Should the 
composition operator delay actions on the right 
3ub3equence until the reduction goals from the 
left 3ubsequence have been executed or until 
the event goals have been executed or, perhaps, 
just until aH goals from the left 3ub3equence 
have been created. The anaver depends on the 
nature of a particular application, but as 
default we propoae that creation of ali goala 
of a node ia an atomic action and that execu-
tion of a goal is treated as atomic in the 
sense that if a goal A must be executed before 
a goal B, then (at least virtually) the execu-
tion of the goal B may not even start before 
the execution of the goal B has been completed. 
The execution order is effected by reduction 
goals, implying that some goals must be execu-
ted before some others. Beside that, some 
reduction goals are executed 3imultaneously 
with an event goal, implying an OR composition 
of relations, specifying simultaneous execu-
tion. In addition, the language should facili-
tate specification of further relations of the 
"before" type. 
Such a specification should be concise, there­
fore we propose that goala are referred to 
3imply by their position in the node and that 
the composition operator, to which a particular 
"before" relation is attached, is carefully 
selected such that the goals of .the relation* 
are easily specified relatively to the position 
of the operator (section 5). 
The last requirement suggeats distribution of 
such relations ali over the node. Anyway, the 
execution order is determined by considering 
ali the relations simultaneou3ly (in DP, it is 
sufficient to conaider relations, implied by 
3equential composition operators, in a particu­
lar order). If a set of relations is in 
contradiction (i.e. (a<b) and (b<a)), they are 
ignored. With that rule, a programmer is free 
to 3pecify any relation, and if possible, it 
vri 1 1 be respected (e.g. Fig.2). 
In comparison to LOTOS, the language lacks tv^o 
important features: a construct for expressing 
intelligent selection (guarded commands) and . a 
construct for expressing disruption of proces-
ses. If guards are not located at the meta 
level (as, for example. in Tvro-level Prolog 
[8]), but at the obječt level, both problems 

have a simple common 3olution - excluoivo 
compoaition oporatora. 
body: (a;{ULS<RS} 
bi(RS.A<URS.ULS> 
cl{LS.A<URS> 
d)#M; (event goal - true; 
reduction atate - no-reduction) # 
execution-ordering relations: 
1,composition operator: 
((a), (alb), (a;b;c), (alblcld)) < 
{(b), (C), (d); (bic), (c;d), (blc:d)) 
2.composition operator: 
<(c), (d)) < {(bic), (alblc), (bicid), 
(a,'blc;d)> 
3.composition operator: 
((a), (b), (c)> < ((d), (cld). (blcld), 
(a!b:c:d)) 
ignored relations: 
<(b)< >(a;b:c;d) , 
(c)<>(a;b:c), (c)<>(a:b:c:d), 
(d)<>(a;b:c), (d)<>(a:blc:d)> 
Fig.2; The execution-ordering role of 
compoaition operators. 
A compound module may be a 
exclu3ive composition of 
exclu3ive forms of the 
paral le 1 composition ope 
while their exclu3ive f 
respectively. Each module 
position of moduleg is att 
(drawn from the set of al 
representing the guard 
section 5 and Fig.3 for an 
non-exclu3ive or an 
modu les. The non-
sequential and the 
rator are I and I 1 , 
orms are / and //, 
of,an exclu3ive com-
ached a set of goals 
1 goals of the node) 
of the module (see 
example). 
body: (((a#M: (reduction state - pending; 
reduction type - weak-common)# 
lb#M: event goal - true* 
) 
I c 
ld#M: event goal - true* 
)((ll)M] 
// 
(e#M: (reduction state 
reduction type 
• pending; 
weak-common)# 
:f 
ig 
:h#M: 
) 
// 
(i#M: 
:j#M: 
) 
event goal - true* 
(reduction state - pending; 
reduction type - weeik-common) * 
event goal - true* 
)#M: reduction state - no-reduction; 
WM: event goal - true* 
scenario: 
execution of event goal 
(((a;b)lc:d)//(e;flg;h)//(i:j)) 
-> ((aibjicid) not ready for selection, 
(elfigih) and (ilj) ready for selection 
-> the node transformed into (elfigih) 
or into (ilj) 
-> execution of event goal (h) 
(or event goal (j)) 
Fig.3: An example of a guarded command. 
After the guard of a module has been executed. 
the next operation on the module may only be 
its selection for further execution or its 
deletion from the 3y3tem. Several roodules with 
executed guards may exi3t, but exactly one of 
them is selected non-deterministically and the 
entire exclu3ive composition of modulea repla-
ced by the selected module, which from that 
moment behaves like an ordinary. module. Because 
guards are regular processes of a 3ystem and 
one of the modules in exclusive composition 
disrupts the others, this is a model of process 
disruption, more general than the one of LOTOS. 
3.3. Ex«cution of Reduction Goala 
In DP, a reduction goal is executed either by 
the ordinary type of reduction (reduction of a 
goal into more and more trivial subgoals), or 
by partjcipation in an event as exactly the 
whole event goal. In our language, a reduction 
goal can also be executed in event, where it is 
just a submodule of the relevant event goal. 
Hence, according to this criterion, there are 
three types of reduction. 
1. On-the-apot reduction is the ordinary type 
of reducCion and could serve for specifying an 
internal process of a node. It may be non-
trlvlal or trivial. Reduction of an atomic 
module is non-trivial, as it potentially crea-
tes descendants in the architectural tree. 
Reduction of a compound module is trivial, as 
it is just an observation that ali the reduc­
tion goals within the module have been execu-
ted. 
2. Strong comnon reduction teOtes plače, when a 
module is a reduction goal and an event goal at 
the same time (the DP-type event goal). When 
the event goal is executed, the reduction goal 
is executed, too. The adjective "common" steams 
from the fact that the participants can execute 
the reduction as a coianon action, without any 
of them executing the reduction on the spot. 
Common reduction could serve for exchange of 
values of any origin. 
3. W«ak conison reduction is like strong common 
reduction, but the reduction goal may also be 
just a submodule of the relevant event goal. 
To . facilitate observation of final (exit) 
results of modules, we introduce a fourth type 
of reduction, which is a weak common reduction 
with some additional requirement3: 
4. Obaojrved reduction takes plače, when a 
reduction goal participates in an event, in 
of the participating event goals 
submodule, unifiable with the reduc-
That submodule must be an executed 
goal with reduction type "on-the-
must have been unified with such a 
goal in one of the previous events. In thia 
way, the node does not have to execute the 
reduction goal on the spot (that might be a 
difficult operation, if the event goal is 
atomic), but just gathers the necessarv results 
by observing someone, who has already executed 
a matching goal on the spot or has learned the 
results from another node. Observation of exit 
results is important from several aspect: 
First, it can strongly reduce the execution 
effort. Second, it can reduce non-determinism 
by forcing various nodes to accept the same 
solution to various incarnations of the same 
problem. Thlrd, it could serve to implement 
monitors of overall system activity. Fourth, 
the concept of exit results is another step 
towards LOTOS. 
On-the-spot reduction may be thought of as 
being executed in the node, containing the 
which one 
contains a 
tion goal. 
reduction 
spot" or 

reduction goal, observed reduction as executed 
in another node and common reduction as execu-
ted in the space between nodes. Observed and 
cominon reduction are treated as trivial, as 
they do not create deacendants. 
At the tirne of its creation, each module is 
assigned its reduction type and state. The 
possible reduction type3 are the four tvpes, 
declared above. The possible states are 
"executed", "pending" and "no-reduction". 
If a module is a reduction goal, its initial 
reduction state is "pending" and its initial 
reduction type may be any type. If a module is 
not a reduction goal, its initial reduction 
state is "no-reduction" and its reduction type 
is "weak-common". Vfhen a reduction goal is 
executed, its reduction state is set to 
"executed". 
If reduction type of a reduction goal is 
"strong-common", the module is an event goal by 
definition. If reduction type of a reduction 
goal is "observed" or "wea)<-common" and the 
module is not a submodule of any event goal, it 
is an event goal by definition. 
Implicit modules are never able to propagate 
exit results of an on-the-spot reduction. while 
explicit modules are alwaya able to do that. 
When created, reduction goals with the reduc­
tion type "on-the-spot" are assigned unigue 
reduction identifiers. Reduction identifiers of 
other modules are undefined, until they begin 
to propagate results of an on-the-spot reduc­
tion. In that čase, their reduction type and 
state are set to "on-the-spot" and "executed" 
and their reduction identifier is set to the 
identifier cf the reduction fhey propagate. 
Reduction identifiers have been introduced to 
distinguish among various incarnations of a 
procedure and to facilitate specification of 
events with a limited number of active roles, 
in which the participating event goals may 
enroll (aee section 5 for the example in 
Fig.7). 
Each atomic reduction goal with reduction type 
"on-the-spot" is attached a predefined or user-
vrritten procedure for unification with clauses' 
heads. Similarly, heads are attached procedures 
for unification with reduction goals. Such 
procedures may be treated as sets of con-
straints. A necessary condition for reduction 
of a reduction. goal with a particular clause 
is, that their proposed constraints can be 
satisfied simultaneously. The reduction is exe-
cuted exactly according to the constraints, 
proposed by the goal or the head. The default 
unification procedure is the most common sub-
stitution. 
3imultaneou3ly. The event is executed exactly 
according to the constraints, proposed by at 
least one participant. 
When a group of event goals is ready to execute 
a common event, the pending event is created in 
the sy3tem as a free module, vhich may (or may 
not) later be executed (deleted from the 
3ystem). Each of the participating event goals 
(according to its synchronization requirements) 
may be executed simultaneou3ly with the event 
or before the event, but never after the event. 
Event goals remain formal participants of an 
event, until the event has been executed, even 
if they have already been executed or even 
deleted from the system. If not forbidden by 
the exi3ting participants, new participants 
(sometimes even an unlimited number . of them) 
may join with tirne. In that čase, a partici­
pant, which has not requested an iinmediate 
execution, can not be executed while new parti­
cipants could potentially change its execution 
results (e.g. if they could assign some of its 
remaining variables). Regardless the type of 
the execution procedure, an event must manda-
tory execute aH reduction goals, that are 
aubmodules of the participating event goals, 
and must not introduce any new tight coupling 
of nodes. 
We propose to cla33ify requirement3, posed by 
execution procedures, into those considering 
1. the number of participants, ' 
2. timing relations (e.g. 3ynchronization, 
delay3), 
3. relation between the state of the partici­
pants before and after the event, and 
4. potential side-effects. 
The proposed defaults are: any non-zero number 
of participants, full •3ynchronization (ali 
event goals executed simultaneously with the 
event), no speci al side-effects and the third 
relation defined by the following unification 
procedure: 
The procedure first tries to malce the partici­
pating event goals unifiable via substitution. 
together with a legal distribution of roles. If 
it succeeds, the event goals are unified via 
substitution and their pending reductions . exe-
cuted. The exclusive • and the non-exclu3ive 
version of composition operators are treated as 
equivalent. 
To make the event goals unifiable via substitu­
tion, the procedure may apply to them the 
following transformations, which are not 
visible after the event: 
3.4. Executlon of Event Goals 
- permutation of modules in parallel composi­
tion. 
An event goal can execute, if it meets a group 
of suitable event goals. Execution must be fair 
in the sense that an event goal, which is ready 
to execute, must not wait indefinitely, if 
suitable groups keep occurring, and must be 
allowed to join a group, vhich is able to 
accept it. If there is more than one suitable 
group, the event goal selects between them non-
deterministically. While an event goal is wai-
ting for execution, its variables might be 
getting assigned by other goals, so its selec-
tivity improves with tirne. 
Each event goal is attached a predefined or 
user-written procedure for its execution. A 
nece3sary an sufficient condition for a group 
of event goals to realize an event is, that 
their proposed constraints can be satisfied 
- grouping of modules (creation of explicit 
modules for the t ime of the execution of the 
event). The new modules are neither reduction 
nor event goals and are unable to propagate 
results of an on-the-spot reduction. 
The first transformation type supports the idea 
of using parallel and sequential composition 
operators for data ordering and reflects the 
fact that modules in parallel composition are 
not ordered. The second transformation type 
facilitates structured observation of unstruc-
tured data. 
Usually, an event goal (EG) can be transformed 
in several way3 to meet the requirements. In 
that čase, the selection betveen the transfor-
mations is non-deterministic and the procedure 

acts as a generator of permutations of modules 
(e.g. Fig.4). 
l.EG: (A!IB) - ready to receive data into 
A and B 
2.EG: (a,'lb) - ready to send data-items a and b 
posgible tranaformations before unification and 
the resulting EG: 
l.EG 2.EG l.EG after unification 
A B 
1. (Al;B) (alIb) (alIb) 
2. (AlIB) (bila) (bila) 
3. (BI lA) (al!b) (b! I a) 
4. (BllA) (bila) (alIb) 
Fig.4: An event, whlch does not preserve 
the order- of data. 
When the event goals have been made unifiable 
via substitution, sets of correaponding modules 
can be identified (e.g. Fig.5). We are interea-
ted only in the explicit modules of the event 
goals (the event goals themselves are treated 
as explicit modules). 
l.EG: (al(biICIId)) 
2.EG: (al(XIIclId)) 
sets of corresponding modules: 
((a), (a)); {(b),(X)); ((C), (O); {(d) , (d) ) 
{(blIClId),(XIICIId)}; 
{(al(biICIId)).(al(XIIclId))> 
Fig.5: An example of sets of corresponding 
modules. 
differs from the default procedure for unifying 
atomic goals with clause heads only in the way 
of unifying variables, which remain unassigned 
in the event: The corresponding variables are 
not unified into a single variable, but retain 
their identities to prevent tight coupling of 
loo3ely coupled modules. 
The modules of the event goals, which have a 
corresponding module with the reduction type 
"on-the-3pot" and are able to propagate results 
of an "on-the-3pot" reduction. are aasigned 
this property. 
4. The Problem of Verlflcatlon 
The ease of verification of specifications in 
the new language depends on the nature of 
procedures for execution of goals. For the čase 
of the proposed default procedures we provide 
some basic guidelines, how clauses of the 
language could be converted into the farniliar 
and widely treated form with just atomic event 
and non-event goals, the classical parallel and 
sequential composition, guarded 3equences of 
goals and 3ynchronou3 events. which reguire 
just pure unification. 
The behaviour of a node can be represented as a 
set of possible execution seguences of "on-the-
spot" reduction goals and event goals. If a 
reduction goal is executed simultaneou3ly with 
an event goal, it is not represented separa-
tely. As goals are not executed more than once, 
the set is finite and so are the 3equences. 
Hence, they can be specified with the classical 
composition operators and guards. Each event 
goal is then replaced by an OR composition of 
ali its forms, that can be generated by grou-
ping and permutation of submodules. Changing 
any term into an atomic goal is juat a 3yntac-
tic operation, but an exotic component of the 
language stili remains, naniely the procedure 
for execution of event goals. 
A distribution of roles betveen the participa-
ting event goals is legal if the distribution 
of reduction type3, states and identifiers of 
the corresponding modules is legal for ali sets 
of corresponding modules. 
We define the procedure for checl<ing the 
distribution for a particular set of correspon­
ding modules from the point of one of the 
modules of the set. The distribution from the 
aspect of each module of the set must comply 
with the folloving rules: 
1. If the reduction type of a module is "no-
reduction", any distribution is legal from the 
point of the module. 
2. If the reduction type of a module is "on-
the-spot", the corresponding modules must not 
have thia property, unless they have the same 
reduction identifier. 
3. If the reduction state of a module is 
"pending", the reguired reduction must be tri-
vial. 
4. If tM reduction type of a module is 
"observed", there must exist a corresponding 
module with the reduction type "on-the-spot". 
5. If the reduction type of a module is 
"strong-common" and its reduction state is 
"pending", the module must be a whole partici-
pating event goal. 
If the distribution of roles is legal, the 
event goals are unified by a procedure, which 
The problematic part of the proposed default 
execution procedure is the role distribution 
chec)<ing part. It involves checking and setting 
of the three implicit variables, associated 
with each submodule of the participating event 
goals: the reduction type, state and identi­
fier. When changing an event goal into an 
atomic goal, its modular structure must be 
retained, 30 that every submodule can expli-
citly be attached the three reduction varia­
bles. As the values of the variables are passed 
betveen goals, every variable must have its 
input and its output copy. Analogou3ly, each 
atomic non-event goal must be attached a var­
iable for generation of its reduction identi­
fier. 
5. A Simple Form of the Language 
and Some Exainple8 
An elegant and detailed 3yntax for the language 
is beyond the scope of the paper. To be able to 
provide some example3. just a very simple form 
of the language is proposed informally. 
A specification is a set of Horn clauses with 
the following conventions: 
a) Ali composition operators (1, 11, /, //) 
should be used as infix operators. If ali types 
of composition operators are treated as one, a 
clause's body is a hierarchical sequence of 
modules. For each composition operator it is 
obvious, which is the 3equence, it helps to 
create. Each module of a seguence is explicitly 

or implicitly followed by its belonging compo-
aition operator. The presence of a composition 
operator may be implicit, if it belongs to the 
last module of a sequence and no coinment needa 
to be attached to it. If there is a comment, 
attached to a module. it may (from the aspect 
of the syntax) also be treated as attached to 
the belonging composition operator. 
In a comment. attached to a composition opera­
tor, various gub3equences of the body can be 
defined, relatively to the position of the 
operator, with the following 3yntax: 
B: the body. 
Mi the module, belonging to the composition 
operator. 
3: the 3equence, created by the composition 
operator. 
S(n)i n:(0),1.2..: S(0) -S. S(n+1) is the 
3equence, to which S(n) belongs as the right-
mo3t element of its left 3ubsequence. 
LS(n); the left 3ubsequence of the 3equence 
S{n). The left 3ubsequence of S is the subse-
quence to the left of the composition operator. 
RS(n): the right 3ubsequence pf the sequence 
S(n). The right subsequence of S is the subse-
quence to the right of- the composition opera­
tor. 
implicitlv in intersection with M. 
The non-predefined properties of modules are: 
to be a reduction goal, to be an event goal, 
the reduction type and, if the module is an 
event goal, the required number of participants 
of the event, in which it will be executed. 
d) Each composition operator may be follovad by 
a coniment <..>, enumerating some execution-
ordering relations in the form SKS2 (the goals 
of the set SI must be executed before the goals 
of the set S2) . AH specified sets of modules 
are implicitly in intersection with G. 
e) Each module in an exclusive composition may 
be folloved by a comment (.. ], 3pecifying its 
guard. Ali specified sets of modules are impli­
citlv in intersection with G. 
f) The defaults are those, proposed earlier in 
the paper, plus: 
- Modules are not event goals. 
- Atomic modules are reduction goals with 
reduction type "on-the-spot". 
- Compound modules are not reduction goals. 
- Execution-ordering relation of I and / opera-
tors: {A.RG.LS<URS}. 
- Execution-ordering relation of I! and // 
operators: {). 
- Guards : [A.RG. (IDM] , if the module is com­
pound, or [RG.M), if the module is atomic. 
(rmi)X: the gubsequence of 
ting with the n-th element 
m-th element of the seguenc 
denotes the size of a segue 
a sequence with a single el 
the first element of the 
element, and (mn)X denotes 
element. Sequences with a s 
is again a sequence vith a 
forbiddeh. 
a 3equence X, star-
and ending vith the 
e X. The constant s 
nce X. Note: If X is 
ement, (11)X denotes 
element, not the 
a 3ub3equence of the 
ingle element, which 
single element. are 
b) Sets of modules, referred to in comments, 
may be constructed by intersection (.), union 
(+) and differenc'e (\) from the following 
simple sets: 
X: the set of aH modules, belonging entirelv 
to a sequence X. 
WX; the module, which covers exactly the whole 
3equence X. 
UX: the set of aH modules, containing at least 
a part of a sequence X. 
E: the set of aH explicit modules of the body. 
I: the set of ali implicit modules of the body. 
A: the set of aH atomic modules of the body. 
C; the set of aH compound modules of the body. 
G; the set of aH modules of the body, which 
are goals. 
RS; the set of aH modules of the body, which 
are reduction goals. 
EG: the set of aH modules of the bodv, which 
are event goals. 
c) Each explicit module may be followed bv a 
comnient *...#, declaring the non-default pro­
perties of sets of its submodules and itself. 
If a propertv of a particular module is defined 
in a conment. attached to an explicit module, 
and again in a comment, attached to one of its 
explicit submodules, the first declaration is 
ignored. AH specified sets of modules are 
svstem:- sender11receiverl!Ireceiver2. 
sender:- ((waitlIlwait2)#A: (event goal - true; 
reduction state -
no-reduction; 
participants - 2)# 
;<EG.LS<EG.RS) 
(a(X):ib(Y):;c(Z) 
)#M: event goal - true# 
) . 
a(X) 
b(X) 
c(X) 
receiverl:- ((c(X);;a(Y) 
)#WM: event goal - true; 
A: reduction type - observed* 
: O 
waitl#M: (event-goal - true; 
reduction state -
no-reduction; 
participants - 2)# 
:(LS<RS> 
processl(X,Y) 
) . 
processl(X,Y):-
receiver2:- ((a(X):;b(Y) 
)#WM: (reduction tvpe -
strong-common; 
reduction state - pending); 
A; reduction type - observed* 
l(> 
wait2#M: (event goal - true; 
reduction state -
no-reduction; 
participants - 2)* 
;{LS<RS) 
proces32(X,Y,Z) 
) . 
proceŠ32(X,Y,Z) :-
Fig.6: Distribution of subsets. 
With these defaults, protocols can be specified 
entirelv in the classical stvle and (with a 
3lightly modified execution procedure for 

10 
events) the language used as a dialect for the 
event-ordering part of LOTOS. Next, we provide 
some motivation examples for the new features 
of the language. 
Exainple in Fig.6: A set of data-items is sent 
to a conmunity of modules, so that everv module 
receives exactly the items of ita personal 
interest in a single event. The sender produces 
data and waits for creation of the receivers. 
Whenever aH the data-items, interesting for a 
particular receiver, are generated, they are 
tranamitted and, because of the fairness requl-
rements, the receiver actually receives them. 
svstem:- activei:!active2;Ipassive. 
a(X) :-
i)(X) :- • 
activei:- (( a(X)#M: reduction type - observed# 
:la(Y) 
:;b(Z) 
)#WM: event goal - true# 
;{LS<RS> 
processl 
) . 
processl:-
active2:- (( a(X) 
lla(Y)#M: reduction type - obaerved* 
llb(Z)#M: reduction type - obaerved* 
)#WM: event goal - true# 
1{LS<RS) 
proce3s2 
) . 
to be sent, and to send the message. 
6. ConcluBlona 
The basic object paradigm of Prolog-type lan-
guagea is creation and deletion of modules. 
Some languages of the family (e.g. DP) intro-
duce paral lel/3equential composition and expli-
cit communication, what makes them suitable for 
specification of communication protocols. 
The main contribution of the paper is separa-
tion of the "module" concept from the concept 
of "goal", so that a module may participate in 
aeveral goals (compound modules). Some syntac-
tic enhancements have been proposed for the 
language of Horn clauaes with paral-
lel/3equential composition of atoraic event and 
non-event goals, which in the light of the new 
operational semantics provide for more concise 
specification of protocols, particularlv those 
requiring multiple operations on a complicated 
piece of data. The core idea of the new 
language is full exploitation of the structure 
of compound modules, which ia usuallv much more 
simple than the 3yntax of atomic modules. 
proce3s2:-. 
Three independent roles 
tora have been identif 
grouping and module-order 
tate apecification of set 
and subsequence3 of modul 
ordering role they facili 
the execution order of p 
selection role they facil 
guarded commands and proč 
of composition opera-
ied: In the module-
ing role they facili-
3, subsets, 3equences 
es. In the execution-
tate apecification of 
ending goals. In the 
itate apecification of 
ess disruption. 
passive:- (( a(X) 
i:a(Y) 
;!b(E) 
)*WM: event goal - true; 
A: reduction type - observed* 
I<LS<RS> 
process3 
) . 
proce333:-. 
Fig.7: Distribution of data from aeveral 
sources and the concept of roles. 
Example in Fig.7: A svnchronous evenf is speci-
fied, involving collection of data-itema from 
aeveral sources, tnerging of data into a com­
pound mesaage and its dissemination to ali 
modules of the svstem. activei and actlve2 wi11 
wait for each other to execute the firat event, 
but will not wait for the passive observer if 
its event goal ia created to late. If the event 
was asvnchronous, alloving an unlimited number 
of participants, the passive observer could 
receive the message regardleas of the execution 
speeda. There are three roles in the event (a, 
a and b), the first played by aotive2 and the 
others by activei. 
The concept of reduction has been separated 
from the concept of event by introducing inde­
pendent promotion of modules into reduction 
goals or into event goals. Reduction goals have 
as well been assigned the execution-ordering 
role. 
To indicate to which extent the execution of a 
reduction goal depends on execution of an event 
goal, four reduction tvpea have been introdu-
ced: on-the-apot reduction, atrong cotrmon 
reduction, weak common reduction and observed 
reduction. The most original one is the obaer­
ved reduction, which could aerve for apecifving 
observation of exit reaults, for apecifving 
eventa with a limited number of roles. for 
reduction of the computational effort, for 
reduction of non-determinism and for implemen-
tation of monitors of the overall svstem acti-
vitv. 
The paper indicates, hov the architectural and 
the behavioural aspect of a svstem can be 
unified into a aingle semantic model and effi-
cientlv apecified by a simple language. 
References 
aender:- (Address#M: event goal - true* 
;(LS<URS) 
message 
)#WM: event goal - true; 
A: reduction state - no-reduction#. 
Fig.8: Receving an address and sending a 
message to the address. 
The task in example from Fig.8 ia to receive 
the addreas, on which a particular message is 
[1] R.Milner: A Calculus of Communicating 
Svstems, Springer verlag, LNCS 92, Berlin 1980 
[2] C.A.R.Hoare: Communicating Sequential Pro-
cesaes, Communications .of the ACM, vol.21, 
no.8, 1978, pp.666-677 
[31 E.Brinksma: A Tutorial on LOTOS, in 
"Protocol Specification, Testing, and Verifica-
tion. V", M.Diaz ed., North-Holland 1986, PP. 
171-194 
[41 L.M.Pereira, F.C.N.Pereira, D.L.D. Warren: 
User'3 Guide to DECsvstem-lO PROLOG, Occasional 
Paper 15, Dept.of Al, Edinburg 1979 

1,1 
[5] E.Y.Shapiro: A Subset of Concurrent Prolog 
and Its Interpreter. ICOT TR-003 (1983) 
[8] A.Porto; 
Informatica. 
Two-level Prolog Departamento de 
Universidade Nova de Lisboa, 1985 
[6] L.Monteiro: A Proposal for Diatributed 
Programning in Logic, in "Implementations of 
Prolog", J.Campbell ed., Ellis Horvrood 1984 
[9] M-Prolog, Language Reference Manual, Insti­
tute for Co-ordination of Computer Technique3, 
Budapest, March 1983 
[7] L.M.Pereira, R.Nasr: Delta-Prolog: A 
Distributed Logic Prograniming Language, Depar­
tamento de Informatica, Universidade Nova de 
Lisboa, 1985 
CALL FOR PAPERS 
ISMM International Conference 
MINI AND MICROCOMPUTERS 
From Micros to Supercomputers 
December 14-16,1988 
Miami Beach, Florida 
ISIVIM 
3PONSOREDBY 
The International Society (or Mini artd Microcompulers (ISMM) 
Technfcal Commtttee on Computers 
SUPPORTEOBV 
Department of Electrical and Computer Engirtoering, Universitv of Miami. Coral Gables. Florida. U.S.A. 
Modcomp, an AEG Company, Fort Lauderdale, Flonda, U.S^. 
LOCA-nON 
Hotel HItton Fontainbkeau, Miami Beach, Florida, U.S.A. 
SCOPE 
Covers alt aspects of computer architecture, organization, and design, artificial intelligence. 5oftware systems, and computer applicalions. 
• Computer archttecture 
' Paraflel computers 
' Fautt-tolerarTtsystems 
• VLSIarx]chipd€«ign 
• RISC archrtecture 
• Expen3ystem3 
> Ccimputer applications 
' ParaltelarKj concurrent programming 
' Operatlng system$ and databases 
' Softwareengineering 
' Real-time8ystems 
• Artificial intelligence 
• Supercomputtng 
' Computer Vision 
• Rcbotics 
' Alprogrammingartdenvironment 
' Software aystems 
> Localareanetvvorks 
• Optimlzlngcompilors 
Threo tutoriaJs wll| be presented by teadtng experts In the fieid. Tentative topics are: Advanced Computer Archilecture, Parallel Computers and Artificial 
Intaltigenc«. 
SUBMtSSION OF PAPERS 
Flve copfes of a 400-word summary 
Notiflcation of authors 
Full papers In camera-ready form 
Confererx» 
JunelS. 1988 
July15.1988 
Oclober 1.1988 
December 14-16.1988 
Ali papers shall be reviewed for possible publication In or« o1 the ISMM journals: International Journal of Mini and Microcomputars, and Microcomputer 
Applications. 
IKTERNATX>NAL PROGRAM COMMrTTEE 
G. Rabbat, General Chairman 
B. Furht. Proorain Chairman 
P. Alpar 
M. Carapic 
R. BteianI 
E. Femandez 
0. Gulch 
M. Hamza 
C.C. Hsu 
T. lahlko 
U.S.A. 
U.SJV. 
U.S.A. 
U.SA 
U.SA 
U.S.A. 
U.S.A 
Canada 
R.O.C. 
Japan 
M. Kabuka 
P. Uu 
E. Luque 
N. Marovac 
G. Mastronardi 
J.D. Meng 
V. Mllullnovic 
D. Motdovan 
S.C. Moon 
B.N. Naumov 
U.S.A. 
U.S.A 
Spain 
U.S.A. 
ltaly 
U.S.A. 
U.S.A. 
U.S.A. 
Korea 
U.S.S.R. 
V. Oklobdzlja 
D. Pattovic 
A.M. Salem 
B. Soucek 
W.V. Subbara/o 
D. Tabak 
M. tapia 
J. Urtan 
F. Vaida 
P. Visuri 
M. Vuskovic 
U.S.A 
U.S.A. 
Egypl 
U.S.A. 
U.S.A. 
U.S.A. 
U.S.A. 
U.S.A. 
Hungary 
Rnland 
U.S.A. 
AODRESS 
For correeporKienco, submisslon of exterxtod summaries, and to be placed on the mailing list, write to: Or. B. Furhl, Director of Advanced Techr>olo9y. 
Modcomp, 1650 West McNab Road, P.O. Box 6099. Mali Stop 850, Ft. Uuderdale, FL 33340-6099, U.S.A. 
Please comptete and retum this form to: ISMM SecretaHat, P.O. Box 25, Calgary. Alberta, Canada T3A 2G1 
Ptease sand me Information corv»mlng: 
Q The Intemallonal Joomal of Mini and Microcomputers 
• Microcomputer Applications Journal 
O The International Jourr^ of Robotlcs and Aulomation 
Q Expen 5ystems, Los Angeles, December 1988 
Q Computer Appllcatioris in Design Simulation and Analy5is, Reno. Nevada, U.S.A.. FebruaTy 1988 
Q Reliabil)ty and Ouallty Control, Los Angeles, December 1988. 
O SefxJ me caJI for papers to conferences in the following areas: