Oz - A Programming Language for Multi-Agent Systems
Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence. Distributed AI. Pages 404-408.
© 1993 International Joint Conferences on Artificial Intelligence
Abstract
Oz is an experimental higher-order concurrent. constraint programming system under development at DFKI. It combines ideas from logic and concurrent programming in a simple yet. expressive language . From logic programming Oz inherits logic variables and logic data structures, which provide for a programming style where partial information about the values of variables is imposed concurrently and incrementally. A novel feature of Oz is that it accommodat es higher-order programming without sacrificing that denotation and equality of variables are captured by first-order logic. Another new feature of Oz is constraint. communication, a new form of asynchronous communication exploiting logic variables. Constraint. communication avoids the problems of stream communication, the conventional communication mechanism employed in concurrent. logic programming . Constraint. communication can be seen as providing a minimal form of state fully compatible with logic data structures . Based on constraint. communication and higher-order programming, Oz readily supports a variety of object-oriented programming styles including multiple inheritance .
- Chen et a/., 1993)
- W . Chen, M. Kifer, and D. S. Warren . Hilog: A foundation for higher-order logic programming. Journal of Logic Programming, pages 187-230, 1993.
- Clark and Gregory, 1981) K .L. Clark and S. Gregory. A re- lational language for parallel programming. In Proc. of the A CM Conference on Functional Programming Languages and Computer Ar•chitecture, pages 171-178, 1981.
- Colmerauer and Benhamou , 1993) A. Colmerauer and F. Benhamou, editors . Constraint Logic Pmgramming: Se- lected Resear•ch. 1993. To appear.
- Colmerauer et al., 1983) A. Colmerauer, H . Kanoui, and M . Van Caneghem. Prolog , theoretical principles and current trends. Technology and Science of Informatics, 2(4):255-292, 1983.
- Goldberg et al., 1992) Y . Goldberg, W . Silverman, and E. Shapiro. Logic programs with inheritance. FGCS, pages 951-960, 1992 .
- Jaffar and Lassez, 1987) J. Jaffar and J .-L. Lassez . Con- straint logic programming . In Proceedings of the An- nual A CM Symposium 011 Principles of Programming Lan- guages, pages 111-119, 1987.
- [Janson and Haridi, 1991] S. Janson and S. Haridi. Pro- gramming paradigms of the Andorra kernel language. In Logic Programming, Pmceedings of the 1991 International Symposium, pages 167-186, 1991.
- [Kiczales eta/., 1991] G. Kiczales, J. des Rivieres, and D. Bobrow. The Art of the Metaobject Protocol. 1991.
- Kahn, 1989)
- K .M. Kahn . Objects: A fresh look. In Pro- ceedings of th e European Conference on Object Oriented Programming, pages 207-223, 1989.
- Maher, 1987)
- M. J . Maher. Logic semantics for a class of committed-choice programs . In Logic Programming, Proceeding.~ of tlw Fourth Int ernational Conference, pages 858-876, 1987.
- Milner, 1991)
- R. Milner. The polyadic 1r-calculus: A tuto- rial. ECS-LFCS Report Series 91-180, University of Edin- burgh, 1991.
- [Nadathur and Miller , 1988] G. Nadathur and D. Miller. An overview of .\Prolog. In Logic Programming: Proceedings of the Fifth International Conference and Symposium, Vol- ume 1, pages 810-827, 1988 .
- Saraswat and Rinard, 1990)
- V.A . Saraswat and M. Rinard . Concurrent constraint programming. In Proceedings of th e 7th Annual A CM Symposium on Principles of Program- ming Languages, pages 232-24.5, 1990.
- Shapiro and Takeuchi, 1983) E. Shapiro and A. Takeuchi. Object oriented programming in Concurrent Prolog. New Generation Computi ng, 1:24-48, 1983.
- Shapiro, 1989)
- E. Shapiro. The family of concurrent logic programming languages. A CM Computing Surveys, 21(3) :413-.5 10, 1989.
- Smolka and Treinen, 1992)
- G. Smolka and R . Treinen . Records for logic programming. In Proceedings of the 1992 Joint International Conference and Symposium on Logic Programming, pages 240-254,1992.
- [Smolka, 1993] G. Smolka. A calculus for higher-order con- current constraint programming. Research report, DFKI, 1993. Forthcoming.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
Oz is an attempt to create a high-level concurrent pro gramming language bringing together the merits of logic and object-oriented programming in a unified language.
Our natural starting point. was concurrent constraint programming [Saraswat. and Rinard, 1990], which .brings together ideas from constraint and concurrent logic pro gramming. Constraint logic programming [Jaffar and Lassez 1987 Colmerauer and Benhamou, 1993], on the one h~nd, o;iginated with Prolog II [Colmerauer ct a/., 1983] and was prompted by the need to integrate num bers and data structures in an operationally effir.ient., yet. lo~ically sound manner . Conc.urrent. logic program ming [Shapiro, 1989), on the other hand , originated with the Relational Language [Clark and Gregory, 1981] and was promoted by the Japanese Fifth Generation P~oject , where logic programming was conceived as the basic sys tem programming language and thus had to account for concurrency, synchronization and indeterminism. For this purpose, the conventional SLD-resolution scheme had to be replaced with a new computation model based on the notion of committed choice. At first, the new model developed as an ad hoc construction, but finally Maher [Maher , 1987] realized that commitment of agents can be captured logically as constraint entailment .. A major landmark in the new field of concurrent constramt programming is AKL [Janson and Haridi , 1991), the first implemented concurrent. constraint language accommo dating search and deep guards.
·This work has been supported hy the Bundesminister fiir Forschung und Technologie, contract ITW-!Jl05.
Saraswat.'s concurrent constraint model [Saraswat and Rinard, 1990] can accommodate object-oriented pro gramming along the lines of Shapiro's stream-base? model for Concurrent. Prolog [Shapiro and Takeuchi , 1983]. However, this model is intolerably low-level due to the clumsiness of stream communication and the lack of higher-order programming facilities. This becon:es fully apparent. when the model is extended to provide for inheritance [Goldberg et a/., 1992] .
Thus the two essential innovations Oz has to provide to be well-suited for object-oriented programming are better communication and a facility for higher-order pro gramming. Both innovations require stepping o~tside of established semant.ical foundations. The semantics of Oz is thus specified by a new mathematical m?del.' called the Oz Calculus whose technical set-up was mspued by the 7T-calculus [Milner, 1991], a recent foundationally moti vated model of concurrency.
The way Oz provides for higher-order programming is unique in that denotation and equality of variables ~re captured by first-order logic only. In fact, denotatiOn of variables and the facility for higher-order program ming are completely orthogonal concep~s in Oz. This !s in contrast to existing approaches to higher-order logic programming [Nadathur and Miller, 1988, Chen et a/., 1993].
Constraint communication is asynchronous and inde terministic. A communication event replaces two com plementary communication tokens with an equation link ing the partners of the communication. Constraint com munication introduces a minimal form of state that is fully compatible with logic data structures. Effi cient implementation of fair constraint communication is straightforward.
The paper is organized as follows. Tlw next. section out.Iines a simplified version of the Oz Calculus. Sec tion 3 shows how Oz accommodates records as a logic data structure. The remaining sections present .one pos sible style of concurrent object-oriented programming featuring multiple inheritance.
2 The Oz Calculus
The operational semantics of Oz is defined by a mathe matical model called the Oz Calculus [Smolka, 1993]. In this section we outline a simplified version sufficing for the purposes of this paper .
The basic notion of Oz is that of a computation space. A computation space consists of a number of agents con nected to a blackboard (see Fig. 1). Each agent reads the blackboard and reduces once the blackboard contains the information it is waiting for . The information on the blackboard increases monotonically. When an agent re duces, it may put new information on the blackboard and ereate new agents. Agents themselves may have one

or several local computation spaces. Hence the entire computation system is a tree-like structure of computa tion spaces {see Fig. 1) .
The agents of a computation spac.e are agents at the micro-level. They are used to program agents at the macro-level. One interesting form of macro-agents are the objects we will introduce in a later section of this paper .
Formally, a computation state is an expression ac cording to Fig. 2. (If ~ is a syntactic category, ~ de notes a possibly empty sequence ~ ... ~.) Constraints, abstractions and communication tokens reside on the blackboard. Applications and conditionals are agents. Composition and quantification are the glue assembling agents and blackboard items into a computation space. Quantification introduces local variables. Abstractions may be seen as procedure definitions and applications as procedure calls.
The clauses of a conditional are unordered. Their guards, i .e., rr in 3x(rr then r), constitute local com putation spaces. Note that any expression can be taken as a guard; one speaks of a flat guard if the guard is a constraint.
There are two variable binders: quantification 3xrr binds x with scope rr and abstraction x: fi/rr binds the variables in fj with scope rr. Free variables of an expres sion are defined accordingly.

Computation is defined as reduction (i .e., rewriting) of expressions. A reduction step is performed by ap plying a reduction rule to a subexpression satisfying the application conditions of the rule. There is no backtrack ing. Control is provided by the provision that reduction rules must not be applied to mute subexpressions, i.e., subexpressions that occur within bodies of clauses, else parts of conditionals, or bodies of abstractions. It is up to the implementation which non-mute subexpression is rewritten with which applicable rule .
Reduction "rr ---> r" is defined modulo structural con gruence "rr = r" of expressions, that is, satisfies the inference rule
Structural congruence is an abstract equality for compu tation states turning them from purely syntactic objects into semantical objects . Structural congruence provides for associativity and commutativity of composition, re naming of bound variables, quantifier mobility
3xrr 1\ T = 3:r:(rr 1\ r) if ;,; does not occur free in T ,
constraint simplification, and information propagation from global blackboards to local blackboards .
2.1 Constraints
Constraints (¢,1{! in Figure 2) are formulas of first-order predicate logic providing for data structures . Logical conjunction of constraints coincides with composition of expressions. Constraints express partial information about the values of variables. The semantics of con straints is defined logically by a first-order theory ~ and imposed with the congruence law
This law closes the blackboard under entailed constraints (since ~ I= <P --> 1{! iff ~ I= <P +-+ <P 1\ 1{! ) . The congruence law
imposes equalities on the blackboard t.o the rest of the computation space ((T[yjx] is obtained from (T by replac ing every free occurrence of x with y) . Equality of vari ables is strictly first-order : Two variables x, y are equal if the constraints on the blackboard entail x::: y, and differ ent if the constraints on the blackboard entail -,(x::: y). Of course, the information on the blackboard may be in sufficient. to determine whether two variables are equal or different. Moreover, an inr.onsist.ent. blackboard entails both x='=y and -,(x='=y) .
The Anullation Law
provides for the deletion of quantified constraints and abstractions not affecting visible variables.
2.2 Application
An application agent. xy waits until an abstraction for it.s link x appears on the blackboard and then reduces as follows :
Note that the blackboard y: z / (T 1\ x = y contains an ab straction for x due to the congruence laws stated above. Since the link x of an abstraction x : yj(T is a variable like any other, abstractions can easily express higher order procedures. Note that an abstraction x : y/(1' does not impose any constraints (e.g., e<JUalities) on its link X .
2.3 Constraint Communication
The semantics of the two communication tokens is de fined by the Communication Rule:
Application of this rule amounts to an indeterministic transition of the blackboard replacing t.wo complemen tary communication tokens with an equality constraint.. The Communication Rule is the only rule deleting items from t.he blackboard. Since agents read only constraints and abstractions, the information visible to agents nev ertheless increases monotonically.
2.4 Conditional
It. remains to explain the semantics of a conditional agent
The guards u; of the clauses are local computation spaces reducing concurrently. For the local r.omputa t.ions t.o be meaningful it is essential that information from global blackboards is visible on local blackboards.
This is achieved with t.he Propagation Law (recall that the clauses are unordered) :
if 11' is a constraint or abstraction and no variable in x appears free in 11'.
Read from left. to right, the law provides for copying in formation from global blackboards to local blackboards. Read from right t.o left., the law provides for deletion of local information that is present globally. An example verified by employing the Propagation Law in both di rections (as well as constraint simplification) is
The example assumes that the constraint theory entails that 1 and 2 are different .
Operationally, the constraint simplification and prop agation laws can be realized with a so-called relative sim plification procedure. Relative simplification for the con straint system underlying Oz is investigated in [Smolka and Treinen, 1992].
There are two distinguished forms a guard of a clause may eventually reduce to, called satisfied and failed. If a guard of a clause is satisfied, the conditional can reduce by committing t.o this clause:
if 3x ((T then r) w else I' - 3x ((11\T) if 3x (T = T. Reduction puts the guard on the global blackboard and releases the body of the clause.
A guard is failed if the constraints on its blackboard are unsatisfiable. If t.he guard of a clause is failed, the clause is simply discarded:
Thus a conditional may end up with no clauses at all, in which case it. reduces t.o it.s else part:
The reduction
is an example for t.he application of the first rule, and
is an example employing the other two reduction rules.
2.5 Logical Semantics
The subcalculus obtained by disallowing communication tokens and conditionals with more than one clause en joys a logical semantics by translating expressions into formulas of first-order predicate logic as follows ( compo sition is interpreted as conjunction, and quantification is interpreted as existential quantification) :
Under this translation, reduction is an equivalence trans formation, that is, if u--> Tor u = r, then .::l I= u ..... r. Moreover, negation can be expressed since --,(T is equiva lent to if (T then j_ else T.
2.6 Unique Names
A problem closely related to equality and of great impor tance for concurrent programming is the dynamic cre ation of new and unique names. Roughly, one would like a construct gensym(x) such that
is congruent to a constraint entailing --,( x :::: y). For this purpose we assume that there are infinitely many dis tinguished constant symbols called names such that the constraint theory .::l satisfies:
- .::l f= --,(a='= b) for every two distinct names a, b
- 2 . .::l I= S ..... S[ajb] for every logical sentence S and every two names a, b (S[a/b] is obtained from S by replacing every occurrence of b with a).
Now gensym(x) is modeled as a generalized quantification 3a(x:::: a), where the quantified name a is subject to a renaming. With that and the quantifier mobility stated above we in fact. obtain a constraint in which ;r: and y are different :
3 Records
The constraint system underlying Oz provides a domain that is closed under record construction [Smolka and Treinen, 1992]. We now outline its constraint theory as far as is needed for the rest of this paper. We will be very liberal as it comes to syntax. The reader may consult [Smolka and Treinen, 1992] for details.
Records are obtained with respect to an alphabet of constant symbols, called atoms, and denoted by a, b, /,g. Records are constructed and decomposed by constraints of the form
where f is the label, a1, ... , an are the field names, and x 1 , ... , Xn are the corresponding values of record x . The order of the fields a; : x; is not significant. The semantics of the above constraint is fixed by two axiom schemes
f(a:x) = f(a:y) ..... x = y f(a: x) = g(b: Y) --> j_ if f i= g or [a] i= [b]
where [a] is the set of elements of the sequence a.
Field selection x .y is a partial function on records de fined by the axiom schemes
J(a:xb:y) . b = y f(a: x) . b ='= y ___. _i if b ~ [a] .
The function label( x) is defined on records by the scheme
label(/(···)) ...:... f.
Finally, record adjunction "adjoinAt(x, y, z )" is defined by the schemes:
adjoinAt(f(a: x b: y) , b, z) ...:... f(a: x b: z) adjoinAt(f(a: x), b, z) ...:... f(a: x b: z) if b ~ [a] .
We write f(xl ... xn) as a short hand for /(1: 1:1 . . . n: xn) · Thus we obtain Prolog terms as a spe cial case of records.
4 Synchronous Communication
Constraint communication is asynchronous . The follow ing program shows how synchronous comunication can be expressed using constraint communication. Com putation only proceeds after communication has taken place (signaled by an acknowledgement) .
proc {Producer} exists Ack in item('.vellow brick' Ack 1) ! Channel if Ack = 1 then {Producer} fi end proc {Consumer} exists X Ack in item(X 1 Ack) ? Channel if Ack = 1 then { AddToRoad X} { CorJsumer} fi end
We have now switched to the concrete syntax of Oz: pred {x y} (Tend stands for x:yj(T 1\ 3a(x:a), {x Y} for xy, and juxtaposition for composition. Moreover, nesting is allowed and is eliminated by conjunction and quantification; e.g. item(X 1 Ack)? Channel expands to exists Y in Y=item(X 1 Ack) Y? Channel . Finally, the default. for a missing else part of a conditional is else true .
5 Objects
An object has a static aspect, its method table, and a dynamic aspect, its state. Methods are functions
method : state x message --> state.
A method table is a mapping from method names to methods, represented as a record whose field names act as method names. A message is a record, whose label is the name of the method and whose fields are arguments.
It. turns out that. we can represent an object 0 by the procedure that sends the message. This rep resentation gives a unique identity to the object since proc {x y} u end stands for x:yju 1\ 3a(x:a).
proc { 0 Message} if MetlwdName Method in MethodName={ label Message} Method=MethodTable.MethodName then exists State in State ? C fi end if { label State} =state then {Method State Message} ! C fi
Observe that nested application makes programs more concise: { Metlwd State Message} 1 C stands for
exists NState in {Method State Message NS'tate} NS'tate ! C
When a message is received by the object. 0, the method associated with the method name is retrieved using the method table of the object (i.e., late binding). Then the state of the object is replaced by the state obtained by applying the method.
The following procedure provides a generic scheme for creating objects from a method table and an initial mes sage.
proc {Create !Message MethodTahle 0} exists !Method C in !Method= MethodTahle.{Lal1el !Message} {!Method state(sel£:0) !Message} ! C proc { 0 Message} ... eud end
Observe that the notion of "self" is provided in a natu ral way by starting with the initial state state( self: 0) . Object initialization is provided by applying an initial message to that state. The resulting state is written on the blackboard. Now, the object is ready to receive messages . We abbreviate message sending of the form { 0 M} by 0 AM. Note that quantification of tlw com munication link C hides the state and provides for data encapsulation.
6 Methods
Assume that we want to model a counter as an object. First, we fix the methods to be stored in the method table. To initialize the counter we use the method
proc {Init InS X OutS'} if Y iu X= init( Y) then OutS' = { adjoinAt InS' val Y} fi end
Observe that Init will add the attribute val if it is not present in the state InS' (see the semantics of adjoinAt in Section 3). To ease the treatment of the state and to get a more elegant notation we abbreviate this abstraction by
I meth ((Init init( Y) )) val+-- Y end
Incrementing and retrieving is achieved by
proc {Inc InS' X OutS} if X= inc then OutS' = { adjoinAt InS val InS. val+ 1} fi end proc {Get InS X OutS'} if Yin X= get(Y) then OutS = InS' Y = InS'. val fi end
which is abbreviated to
meth ((Inc inc)) val +-- @val+ 1 end meth ((Get get ( Y) )) Y = @val end
MT = mt ( init:II1it inc:Inc get:Get) {Create i11it ( 0) MT Counter}
7 Inheritance
In our framework, inheritance amounts to using the method tables of other objects to build the method table of a new object . We modify the procedure Create to provide for inheritance.
proc {Create Ancestors !Message NewMetlwds 0} exists IMetlwdName !Method C AJJMetlwds Send in AllMetlwds = { AdjoinAJJ Ancestors New Methods} 0 = ohject(metlwds:AllMethods send:Send) proc { SelJ(l Message} ... end end
The procedure AdjoinAJJ (not. shown) adjoins the method tables of Ancestors and NewMethods from left to right : For any method name, the rightmost method definition is taken ( cf. adjoinAt in Section 3).
To make the methods of objects accessible, an ob ject is now represented as a record containing the meth ods and the send procedure. Therefore, message send ing changes slightly: Counter A inc stands now for {Counter .send inc} .
A counter that. is displayed in a window (the object VisibleOhject is defined in Section 9) and that can ad ditionally decrement. its value can be created by
meth ((Dec dec)) val +-- @val- 1 end DecCounter = {Create Counter! VisihleObjectlnil in it ( 0) mt ( dec:Dec)}
for which we introduce the following syntactic sugar.
create DecCounter from Counter VisihleObject with init meth dec val +-- @val - 1 end eud
8 Method Application
Some languages providing for inheritance support the concept of super to address methods overwritten due to the inheritance priority. Oz provides a more general scheme in that an object can apply to its state methods of any other object (regardless of inheritance) .
Assume an already defined object Rectangle. A square can inherit. from a rectangle but. needs for initialization only its length but not its width.
create Square from Rectangle with init(lO) meth init(X) (( (Rectangle.metlwds).init init(X X) )) end end
where the method expands to
proc {Init InS X OutS} if Y in X = ini t ( Y) then OutS = { Rectangle.metlwds.init InS init( Y Y)} fi end
Note that ((@self .methods m)) differs from @selr m in that the former tranforms the local state immediately, whereas other messages can be taken before the latter is eventually executed.
9 Meta Object Protocol
Now, we modify the object system such that the essen tials of object. creation and message sending can be in herited, providing the objec.t-syst.em with a meta object. protocol like in [Kiczales ct al., 1991] for CLOS. The new definition of Create uses the meta-method create to describe the object's behavior.
proc {Create Ancestors !Message New Methods 0} exists AJJMetlwds in AJJMethods = { AdjoinAJJ Ancestors NewMetlwds} {AJJMethods. create _ create(AllMetlwds !Message 0) -} end
The underscore "-" denotes an anonymous variable oc curring only once.
Like an organism, an object can inherit. the way it. and its heirs are created, and the basic structure how it communicates with its environment.
We can further modularize the object. protocol such that., e.g., each method call is performed by a call to the meta-method metlwdCall . Assume that the meta methods create and metlwdCall are defined in the object MetaObject. In this case, a VisiJ,leO/,ject that. sends a message containing its current. state to a Display whenever it executes a method, can be created as follows:
create VisibleObject from MetaO/,ject meth methodCall(InS Met}J Mess OutS) { Meth InS Mess OutS} Display A show( OutS) end end
Acknowledgements
We thank all members of the Programming Systems Lab at. DFKI for countless fruitful discussions on all kinds of subjects and objects; particularly many suggestions came from Michael Mehl and Ralf Scheidhauer.
@inproceedings{ijcai1993p57,
title = {Oz - A Programming Language for Multi-Agent Systems},
author = {Henz, Martin and Smolka, Gert and Würtz, Jörg},
booktitle = {Proceedings of the Thirteenth International Joint Conference on
Artificial Intelligence, {IJCAI-93}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Ruzena Bajcsy},
pages = {404--408},
year = {1993},
note = {Distributed AI},
url = {https://ijcai.org/proceedings/1993/57},
}
TY - CPAPER TI - Oz - A Programming Language for Multi-Agent Systems AU - Henz, Martin AU - Smolka, Gert AU - Würtz, Jörg T2 - Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence, IJCAI-93 PB - International Joint Conferences on Artificial Intelligence PY - 1993 SP - 404 EP - 408 UR - https://ijcai.org/proceedings/1993/57 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: