Coordinating Rule-Based Software Processes with ESP Paolo Ciancarini Technical Report UBLCS-93-8 April 1993 Laboratory for Computer Science University of Bologna Piazza di Porta S. Donato, 540127 Bologna (Italy) The University of Bologna Laboratory for Computer Science Research Technical Reports are availablevia anonymous FTP from the area ftp.cs.unibo.it:/pub/TR/UBLCS in compressed PostScriptformat. Abstracts are available from the same host in the directory /pub/TR/UBLCS/ABSTRACTS inplain text format. All local authors can be reached via e-mail at the address last-name @cs.unibo.it. UBLCS Technical Report Series 92-1 Mapping Parallel Computations onto Distributed Systems in Paralex, by "O. Babao *glu, L. Alvisi, A.Amoroso and R. Davoli, January 1992. 92-2 Parallel Scientific Computing in Distributed Systems: The Paralex Approach, by L. Alvisi, A. Amoroso,"O. Babao *glu, A. Baronio, R. Davoli and L. A. Giachini, February 1992. 92-3 Run-time Support for Dynamic Load Balancing and Debugging in Paralex, by "O. Babao *glu, L. Alvisi,S. Amoroso, R. Davoli, L. A. Giachini, September 1992. 92-4 Paralex: An Environment for Parallel Programming in Distributed Systems, by "O. Babao *glu, L. Alvisi,S. Amoroso, R. Davoli, L. A. Giachini, October 1992. 93-1 Consistent Global States of Distributed Systems: Fundamental Concepts and Mechanism, by "O.Babao *glu and K. Marzullo, January 1993. 93-2 Understanding Non-Blocking Atomic Commitment, by "O. Babao *glu and S. Toueg, January 1993.93-3 Anchors and Paths in a Hypertext Publishing System, by C. Maioli and F. Vitali, February 1993. 93-4 A Formalization of Priority Inversion, by "O. Babao *glu, K. Marzullo and F. Schneider, March 1993.93-5 Some Modifications to the Dexter Model for the Formal Description of Hypertexts, by S. Lamberti, C. Maioli and F. Vitali, April 1993.93-6 Versioning Issues in a Collaborative Distributed Hypertext System, by C. Maioli, S. Sola and F. Vitali, April 1993.93-7 Distributed Programming with Logic Tuple Spaces, by P. Ciancarini, April 1993. 93-8 Coordinating Rule-Based Software Processes with ESP, by P. Ciancarini, April 1993.93-9 What is Logic Programming good for in Software Engineering?, by P. Ciancarini and G. Levi, April 1993. Coordinating Rule-Based Software Processes with ESP Paolo Ciancarini1 Technical Report UBLCS-93-8 April 1993 Abstract ESP is a language for modeling rule-based software processes that take place in a distributed softwaredevelopment environment. It is based on PoliS, an abstract coordination model that relies on Multiple Tuple Spaces, i.e., collections of tuples a la Linda. PoliS extends Linda aiming at the specificationand coordination of logically distributed systems. ESP (Extended Shared Prolog) combines the PoliS mechanisms to deal with concurrency and distribution, with the logic programming language Prolog,to deal with rules and deduction. Such a combination of a coordination model and a logic language provides a powerful framework in which experiments about rule-based software process programmingcan be performed and evaluated. 1. e-mail: cianca@cs.unibo.it 1 1 Introduction 1 Introduction The theme of software process modeling has been recently addressed by several specific conferences, see for instance [1,21,25]; for a survey, see [19]. This interest stems from the factthat activities involved in software development are so complicate, expensive and error-prone that it seems necessary to completely specify the development process, in order to gain controlof it and improve its quality. A software process program should formally define the activities that are carried out in the development of a software project, providing guidance to the agentsinvolved and controlling the overall evolution of the project status [33]. In this paper we devote our attention to the fact that a software process takes place necessarily within a software development environment. The environment supports and coordinates the interactions of the project members, allows the use of programming tools, and monitors the evolution of the project documents. We will show that the environment can be designed with the goal of explicitly modelingand coordinating the process itself. In fact, we suggest that a natural way to model a software process consists of introducing a suitable abstract machine defining the environment in which the software process is developed and a suitable programming language able to control the process evolution. Our guiding principle is that, in order to specify a software process, we must clarify the coordination model [13] that has to be used by all the agents, i.e., we must make explicit the communication mechanisms that are at the basis of the interaction protocols used by the participants of a software project. We identify the coordination model with theabstract architecture of the environment that supports the execution of the process itself. The main contribution of this paper is the definition of an abstract paradigm for modelingcoordination of activities that take place inside a software development environment. The paradigm is called PoliSpaces (or PoliS), because it is based on Multiple Tuple Spaces [23].PoliS allows a software process designer to model a software process that takes place inside a multi-user, distributed development environment. In modeling the activities that form the software process our approach is similar to that used in MARVEL [8,9] and Merlin [24,34]:each activity that takes place in the environment, as prescribed by the process, is governed by rules. With respect to these systems, we put emphasis on both the coordination mechanismsthat allow us to combine the rules that govern the software process, and on the declarative language that allows to express the rules themselves.Our proposal includes three steps. First, we define an abstract coordination model. A coordination model is a set of abstract mechanisms for expressing and controlling sets of sequential activities [13]. In our approach, each activity can be expressed in any sequential language; its interactions with respect to other activities is defined using the coordination model. Our coordination model - PoliS - is based on Multiple Tuple Spaces, i.e., collections of tuplesmanipulated with the operations offered by the Linda coordination language [22]. Second, in order to be able to express rule-based software processes, we use logic program-ming to take advantage of its inferential and relational capabilities. We introduced elsewhere the parallel logic language Shared Prolog [11], that combines Prolog with a Linda-like tuple space. Here, we use an extension of Shared Prolog that is better suited for distributed programming. In fact, Extended Shared Prolog (ESP for short) is a logic language that combines the features of PoliS for distributed programming with the declarative and inferential capabilities of Prolog.Finally, we show how ESP can been used to model a software process that takes place inside a distributed software development environment. The idea is that the software process is UBLCS-93-8 2 2 PoliS: A Model for Coordination explicitly defined by rules that form coordination protocols; these govern the activities inside a distributed environment. The rules specify goals, duties, and constraints that the agents involved in the software process have to fulfill. We suggest that it is the environment that imposes constraints and supports coordination protocols among the users, and that controlling the environment means governing the software process.The concepts of distributed development environment and rule-based software process as well as their interplay are naturally modeled in PoliS and easily implemented in ESP. In fact,we show how ESP can be used to design simple programming environments corresponding to simple software processes. The power of ESP can be tested using Oikos, a rule-based development environment able to execute software process models written in ESP [2,4]. Oikos offers a number of standard services giving some basic facilities, like access to databases and private workspaces, activationof shells, etc. The ESP language can be used to implement a desired software process. The paper is organized as follows: Section 2 introduces PoliS as a model for distributedprogramming. Section 3 describes Extended Shared Prolog, a programming notation based on PoliS. Section 4 shows how ESP can be used in the design of simple software developmentenvironments and processes. Section 5 summarizes the main design principles underlying Oikos. Finally, Section 6 contains some comparisons with related work. 2 PoliS: A Model for Coordination Intuitively, a multiuser software development environment can be seen like an abstract townwhere there are many places. Several agents are distributed in the places; they cooperate producing documents that either remain in the same place or are sent to another place. In the town many activities are performed simultaneously, mostly independently; however, all of them are ruled by laws and policies that are constraints that are either physical (e.g., the available resources, like space and time) or abstract (e.g., a set of laws that prohibit somebehavior). We suggest that a software process designer that has to set up a multiuser software development environment should design it as a polispace, i.e., as a distributed system that is acollection of named tuple spaces. The concepts of tuple and Tuple Space are borrowed from Linda; PoliS extends Linda allowing for a multiplicity of Tuple Spaces. More precisely, in PoliS three concepts are important: tuples, agents, and tuple spaces. 2.1 Tuples Tuples are sequences of variables and values. As in Linda, values depend on the chosen sequential programming language used for programming agents. However, in PoliS a numberof basic value types, as well as lists of these values, are allowed. Example: For instance, these are tuples: (do edit(program1)) ('Paolo', programmer, Program) (program1, [module1, module2, module3]) 2 UBLCS-93-8 3 2 PoliS: A Model for Coordination Some useful conventions: a tuple is always parenthesized; identifiers that are not quoted and begin with capital letters denote variables; other identifiers denote atoms; square brackets denote lists. Tuples denote themselves; they are simply data objects that exist in a tuple space, produced by an agent and possibly in the future consumed by an agent. The scope of variables inside tuples spans only for the tuple to which they belong. This means that each tuple insidea Tuple Space is completely independent from other tuples. Each tuple is produced by some agent in some tuple space, and it remains there untilsome agent consumes it. Access to a tuple is associative, i.e., it is done "by contents". The particular access mechanism chosen is a degree of freedom: e.g., PoliS can accommodate either a mechanism based on typed pattern matching, as in Linda, or a mechanism based on unification, as in a logic language. 2.2 Agents Abstractly, agents are execution threads, i.e., an agent is a process executing some program.As in Linda, an agent is represented by a so called active tuple. An important difference between Linda and PoliS is that in the latter an agent executes a program contained in a tuple of a special kind, called program-tuple. The program is written in a sequential programming language, enriched with a set of tuple space operations. 2.2.1 Tuple Space Operations An agent can use the following tuple space operations for interacting with the Tuple Space itlives in: ffl associative test of a tuple contained in the agent's Tuple Space; ffl associative consumption of a tuple from the agent's Tuple Space; ffl asynchronous creation of a Tuple Space or a tuple. Most of these operations are borrowed from Linda. There are two different "flavors" for the test and consumption operations-they can be either blocking or not-blocking-, and twonot blocking operators-one for the creation of a tuple, and one for the creation of a new tuple space.The blocking test operation in Linda is written read(Tuple schemata), the non-blocking test operation is written readp(Tuple schemata), the blocking consumption operation in is written in(Tuple schemata), and the non-blocking consumption operation is written inp(Tuple schemata). A T uple Schemata is a tuple containing formal arguments, i.e., wild cards that match any actual argument inside a tuple contained in the Tuple Space.Actually readp and inp are not considered part of the "standard" definition of Linda. We maintain them in PoliS, because agents need maximum generality in accessing tuple spaces,and the success/failure semantics of readp/inp will be useful when using logic-based control structures.An agent can output either a tuple or a Tuple Space (i.e., it creates a new tuple space). The former operation is written out(Tuple) in case of local writing, out(Tuple)@TupleSpace in case of outside writing; the latter one is written tsc(TupleSpace). The target of output operations is always a Tuple Space, specified using its name. If no name is specified, by default the Tuple Space of the agent is used. What happens if an outoperation targets an external Tuple Space that does not exists? PoliS is consistent with the Linda semantics: out is a non-blocking operation (i.e., the agent that issue it does not wait forany result or error code), that never fails. Communications among tuple spaces are supported UBLCS-93-8 4 2 PoliS: A Model for Coordination by a meta Tuple Space where undelivered tuples remains deposited; whenever a tuple space comes into existence, the undelivered tuples "pop up" in the tuple space. If an agent needs to be certain that a message has gone its way, it must explicitly use a protocol. For instance, it could send the message and an agent that sends back an acknowledgment.Finally, we note that an agent can test or consume tuples representing other agents. This is useful to build agents that schedule agents. Tuple spaces cannot be operands either fortesting or for consuming, because the obvious semantics for such operations (copy a whole tuple space, delete a whole tuple space) should necessarily manipulate the global state of a Tuple Space, in contrast with the asynchronous nature of its internal activities. 2.2.2 Program-tuples A Linda program can invoke arbitrary sequences of Tuple Space operations. PoliS agentsfollow instead a fixed protocol for invoking tuple operations. Syntactically, the program that an agent executes is written inside a program-tuple. (Heading : (Test; Consume; Loc Eval; Out)) The Heading is a Tuple Schemata. Test, Consume, and Out are sequences of tuple operations, whereas Loc Eval is a sequential computation that has no side effect in the Tuple Space to which the agent belongs. An agent is activated when the Tuple Space contains botha program-tuple and a normal tuple matching the heading in the program-tuple; the latter is consumed.The second component of a program-tuple is also called a pattern. Executing a pattern, an agent will do the following actions: ffl it reads something from its tuple space using any number of test operations; actuallythe test operation in PoliS has a broader semantics than read in Linda: a number of predefined tests on the Tuple Space are allowed, depending on the chosen type systemfor tuple arguments. Some useful predefined tests are: relational (binary) predicates, a var/1 predicate to check if an argument inside a tuple is a variable, and a thisplace/1 predicate returning the name of the tuple space in which an agent is located. ffl it deletes some tuples using any number of consumption operations. ffl it executes a "local evaluation" that has no effect on the Tuple Space insofar as nooperations on the Tuple Space itself are allowed; this local computation is expressed in a sequential programming language; ffl it outputs the results in a number of tuple spaces it "knows"; these outputs can consistof tuples or tuple spaces; ffl at the end of the sequence the agent "dies", terminating its thread of evaluation; however, we can specify an ever-lasting agent by inserting among its outputs the creation of a copyof itself. What is the computing model underlying the computation of an agent? The idea is that agents are stateless and reactive, i.e., they compute when a "molecule" of tuples can be built inside the Tuple Space. A molecule is composed of a program-tuple, a normal tuple matching the first component of a program-tuple, and all the tuples to be consumed as specified by theconsume section in the program-tuple. The agent "reacts" to its environment, "burning" the molecule, and creates new entities as specified in the create section. This semantics is studiedin [17]. UBLCS-93-8 5 2 PoliS: A Model for Coordination Example: An ever-lasting chemical reaction can be seen in this Tuple Space containing two table tennis players: f(a)(b)(ping) ((a) : (in(ping);out(pong);out(a))) ((b) : (in(pong);out(ping);out(b)))g Agent a begins building a molecule with tuple (ping); it consumes that tuple and producestuple (pong) and a copy of itself (a). Then it is the turn of agent b that reacts and consumes tuple (pong) producing tuple (ping) and a copy of itself (b), and so on, either forever oruntil something from outside comes to alter this "chemical solution". For instance, suppose that an external agent sends a new (ping) tuple in the above Tuple Space; as soon as the new tuple is noticed by agent a, the two agents are no longer serialized. 2 We remark that program-tuples are tuples, i.e., they can be freely added or removed from a Tuple Space, thus providing an indirect means of manipulating agents. Example (remote evaluation): If an agent a in tuple space source needs to be sure that some output reached a tuple space dest, it can use the following protocol: ((a): (out(msg)@dest; out(b)@dest; out((b):(read(msg); source.out(ack msg)))@dest)) i.e., the agent sends the message msg and a "representative" b, that in the destination Tuple Space tests for the presence of the message and sends back an ack message. 2 2.2.3 Non deterministic evaluation The agent semantics outlined above is very simple, because it can be defined as an inputoutput relationship independent from the global environment, i.e., the tuple space. An agent is "reactive", i.e., it reacts to its tuple space in the sense that the set of testing and consuming operations contained in its program can be thought of as a firing pattern that activates a computation (the loc(al) eval(uation)) that finally modifies the tuple space itself.Actually this semantics is even too simple, since we have problems in specifying some interesting situations. For instance, situations where it is impossible to give to an agent all theinput it needs at the start of its computation increase the verbosity of programs. Moreover, mutual exclusion relationships are very boring to specify, because they must be handled explicitly defining a "semaphore" tuple for each set of agents in mutual exclusion. We can define non deterministic agents simply by putting in the Tuple Space a set of program-tuples whose headings match. Example: The program-tuples describing the behavior of an agent a that can either edit, or compile, or execute a file, are the following: ((a) : (in(edit(File)); do edit(File, New); out(New)) ((a) : (in(compile(File)); do compile(File,Object); out(Object)) ((a) : (in(exec(File)); do exec(File,Results); out(Results)) 2 Such a set can be compared to the Hoare's CSP guarded command, or to an object definedby a set of methods, or to a logic predicate defined by a set of clauses. This is yet another UBLCS-93-8 6 2 PoliS: A Model for Coordination extension of PoliS with respect to Linda, that does not offer any non-deterministic operation. Non determinism is useful to specify complex tasks that are partitioned in several alternative subtasks. 2.3 Tuple Spaces A Tuple Space is a named multiset of passive or active tuples. Syntactically, we will write tuple spaces as sequences of tuples between curly brackets. Example: To describe a tuple space named workspace containing three tuples, we write what follows: workspacef (file,1) (file,2) (do edit,file,1) g 2 Another difference with respect to Linda is that in PoliS each Tuple Space has two attributes: a name, and a set of invariants. 2.3.1 Names of Tuple Spaces An important feature of PoliS tuple spaces is that they have a name. Agents can send tuplesoutside their own tuple space using the name of another tuple space. Tuple space names can be freely passed as arguments of tuples, so that it is possible to dynamically build complex communication flows. The name system of tuple spaces is a degree of freedom in PoliS, just like the choice of the sequential language for local computations, and the type system chosen for tuples. This means that PoliS does not offer any specific name system. A programming language based on PoliS has to choose its own name system for tuple spaces. If the names of the tuple spacesform a flat structure (e.g., they are pointers), all tuple spaces are independent and scoping rules are very simple: tuple space names form a global environment. If the names are structured,the tuple spaces are structured as well: e.g., if the names are paths in Unix-like style, the tuple spaces form a tree similar to the Unix file-system (this name system is used in Oikos; see 5). 2.3.2 Invariants Whereas agents are ephemeral and stateless, a Tuple Space can be seen as an object that is persistent and has a state [41]. A Tuple Space is not a passive entity, a mere repository of tuples or a channel for messages. There is a way of controlling the activities that take place inside a Tuple Space. In fact, for each Tuple Space we can define one or more invariants, i.e., constraintsthat must hold for all the Tuple Space life span. Whenever an invariant is violated, the Tuple Space stops all activities and terminates. A "tuple space garbage collector" could now claim all the resources allocated to the Tuple Space. Invariants are defined inside special program-tuples where the heading is substituted by the keyword invariant. (invariant : (Test; Loc Eval; Out)) The test section defines a condition on the Tuple Space that, when verified, terminates the Tuple Space itself. The Loc Eval and the Out sections can be used to compute andcommunicate any results to other tuple spaces. UBLCS-93-8 7 3 ESP: A Parallel Language that combines PoliS and Prolog Example: The following is an invariant: (invariant: (read(validated(design)); out(start(coding)@manager))) when tuple validated(design) is produced, the tuple space terminates, communicating tuple start(coding) to tuple space named manager. 2 The invariant concept is not present in Linda. In PoliS it is useful to specify the intendedsemantics of a Tuple Space: when the condition specified by the invariant is verified, a "result" has been obtained; it can then be passed to some other Tuple Space. 3 ESP: A Parallel Language that combines PoliS and Prolog PoliS could accommodate any sequential language for expressing local computations inside agents. For instance, C-Linda can be considered an instance of PoliS where the sequential language is C, tuples are built using the C data types and a unique tuple space is allowed. In Linda there are no constraints on the use of tuple operations (i.e., we can use in a program in, read, and out in any order). However, we note that any sequence of Linda operationscan be split in a number of subsequences such that each subsequence begins with read/in operations and terminates with out operations. In order to explore the effective usefulness of PoliS in the design of rule-based software processes and environments, we have introduced ESP, a programming language that combines PoliS with Prolog. ESP is actually an extension of the parallel logic language Shared Prolog [11], that is a logic language that uses the blackboard model [31] for organizing interprocesscommunication. With some approximations, Shared Prolog can be considered a member of the Linda family of physically distributed programming languages [22]. Shared Prolog gainsin expressive power with respect to Linda by exploiting unification and backtracking when an agent accesses the tuple space (Linda uses pattern matching, and no backtracking is allowed).ESP generalizes Shared Prolog with multiple tuple spaces. 3.1 Theories An ESP program is composed of a set of modules called theories. Each theory has the followingsyntactic structure: theory name(V 1; . . . ; V n):- % theory heading eval rule1# . . . #rulek % theory interface with P rolog program % theory implementation. A theory is a module identified by a name and zero or more arguments Vi that are logic variables that scope over the rules. The theory interface follows the keyword eval and itincludes a number of rules (also called "patterns"), separated by the symbol #; the theory implementation is the Prolog program that follows the keyword with (the reader not familiarwith Prolog will find a good introduction to it and its terminology in [37]). Example: The following is a theory that includes only one rule. It defines an agent that compiles a filewhen it finds in its tuple space the tuple compile(File); the result of the agent activation UBLCS-93-8 8 3 ESP: A Parallel Language that combines PoliS and Prolog is that either a success tuple is sent to blackboard test or, if the compilation fails, a failure message to blackboard user. theory compiler:- eval fcompile(File)g % consume ! call compiler(File), % P rolog goal fcompiled(File)@testg % Success Out fail freport error(File)@userg % F ailure Out with call compiler(File):- . . . % P rolog program % special predicate that invokes a compiler % it fails if compilation fails 2 An ESP theory including a set of rules is similar to a CSP guarded command: when one ofthe rules can fire, the agent executing the theory commits to that rule; if more than one rule can fire, one is chosen non deterministically. ESP rules are clauses that include: a T est section, that formally is a goal to be evaluated with respect the current contents of the Tuple Space; a Consume section, that describes a multiset of tuples to be consumed; a loc eval section, that is a Prolog goal to be evaluated with respect to the P rolog program; and finally some out operations. To make explicit the factthat they have side effects on the Tuple Space, consumption and creation operations are put between curly brackets.Test f Consume g ! Goal f Success Out g fail f Failure Out g The combination of Test and Consume sections is a guard: when such a guard is satisfied, i.e., if the test is satisfied and consume operations can be completed, the rule is fired, that means that the tuples to be consumed are really deleted and the Prolog goal is evaluated. To deal with the possibility of a failure of such a Prolog goal, creation operations are partitioned intwo sets separated by the keyword fail: if the goal evaluation succeeds the Success Out is produced, else the Failure Out is produced. Example: In the following rule, the first line is the Test section; the second line is the Consume section. This rule states: "if the Tuple Spaces contains tuple file(F) and does not contain tuple reserved(F, ), and tuple check out(P,F) can be found and deleted, then produce tuple reserved(F,by(P)) in this tuple space and tuple file(F) in the tuple space named bythe value bound to P". file(F), not reserved(F, ) fcheck out(P,F)g ! freserved(F,by(P)), file(F)@Pg 2 Communications with agents in other tuple spaces are denoted by simply adding theaddress of the destination tuple space to the tuple to send. If the destination tuple space has not yet been created, the tuple simply waits for such a creation; this consistently extends theLinda semantics of out operations to the PoliS framework. UBLCS-93-8 9 3 ESP: A Parallel Language that combines PoliS and Prolog Finally, a few remarks on the Prolog program that follows the keyword with. All Prolog built-ins can be used, except for predicates that alter the program, like assert and retract. This guarantees that agents are stateless, as required by PoliS semantics. Any state information must be stored in the tuple space. 3.2 Logic tuple spaces An ESP tuple space, also called a blackboard, is a named multiset of logic tuples; a logic tuple is simply a Prolog term.Blackboards can be dynamically created by agents simply using an activation goal of the form tsc(namefcontentsg). An activation goal specifies the name of the tuple space andpossibly its initial contents. Example: A goal that creates three tuple spaces; the tuple space bb of PM initially contains the tuple develop change and test(Unit). ?- ftsc(bb of CCB), tsc(bb of PMfdevelop change and test(Unit)g), tsc(bb of PT)g 2 In general, the execution of an ESP program builds a set of tuple spaces. The set grows when a tuple space is created, and shrinks when a tuple space terminates, i.e., when an invariant fires. Example: A goal that associates two invariants with the tuple space bb of PM. The tuple space terminatesitself when either the tuple end work(Id) or the tuple abort work(Id) it is found in its contents. ?- finvariant(end work(Id))@bb of PT, invariant(abort work(Id))@bb of PTg 2 3.3 Evaluation of logic agents An ESP Tuple Space can be seen as a programming construct that encapsulates a parallelevaluation of logic agents. Logic agents are represented by active tuples; a tuple is active if it matches the heading of a theory. An agent executes rules that read or delete tuples fromits tuple space; the result of the evaluation of a rule normally consists of the creation of some tuples in some tuple space.A notable feature of ESP is that control flow of test and consume operations is ruled by backtracking. Each test or consume operation either is successful or fails; a failure activates backtracking to the preceding operation. Example: Suppose we have the following subset of a Tuple Space: f. . . , deliver(Any), spec(1), spec(2), impl(2), . . . g UBLCS-93-8 10 3 ESP: A Parallel Language that combines PoliS and Prolog If an agent commits to the rule: spec(X), fdeliver(X), impl(X)g ! fmod(X)g then tuple deliver(X) is consumed with X = 2. The resulting tuple space subset is the following: f. . . , spec(1), spec(2), mod(2), . . . g 2 A formal semantics for this behavior is given in [11]. 3.4 ESP implementation ESP is a language that evolved as an extension of Shared Prolog. There are currently twodistributed implementations, one stand alone [12] and one based on Linda [18]. The first one is implemented part in C and part in Prolog. The C layer implements a socket-based Meta Tuple Space that supports a number of communication primitives usable by Prolog processes. Each Prolog process can handle either several blackboards or several agents. In the Linda based implementation, the Meta Tuple Space is a C-Linda program that (remotely) forks one "worker" for each new logical tuple space. Such a representative communicates via socketswith a Prolog process that handles one logic tuple space. For other details concerning the ESP implementation, see the references. 3.4.1 Interaction with the user ESP can be used for parallel programming just like Linda: a typical parallel application is a program that needs massive computation power to do a search inside a number of distributedknowledge bases. Linda is of course much more efficient, but ESP can be more easily used for symbolic applications. A good example is a program that coordinates several agentscooperating to solve a code according to the rules of Mastermind [14]. Our benchmarks show that the current ESP distributed implementation is at least as efficient as some parallel implementations of production systems [18]. However, the real use intended for ESP is in the design of programs that coordinate and interact with a number of users. For instance, we have developed a program that coordinates four players that intend to play bridge over a network. Each player is connected to a differentworkstation. The program distributes the cards to the players, handles each trick and keeps the score. Other programs in this class that have been developed are a simple distributed agenda to coordinate committee meetings, an e-mail system, and a financial simulation in which some users buy and sell stocks in a number of simulated stock markets. These distributed applications make large use of the interactive capabilities of Prolog: it is possible to launch, even remotely, special logic tuple spaces that directly communicate with a terminal. These are called shells; a user then can produce or consume tuples within the shell he is connected to.In principle, through his blackboard a user can access the whole universe of blackboards, sending message tuples or even active tuples that open new shells on these blackboards. Inpractice, his interaction with the blackboard system can be constrained by the rules that define the shell. Example:The following theory defines a shell that enables a user to put commands in a tuple space if the tuple space contains the tuple access granted(User) and the commands aresyntactically correct: UBLCS-93-8 11 4 Process Programming with ESP test compileedit oe \Gamma \Gamma \Gamma \Psi - l ll O/ OE o/AE O/OE o/AEO/OE o/AE Figure 1. A polispace coordinating a simple programming environment theory simple shell(User):- eval access granted(User) ! read command(Command) ftuple(Command), simple shell(User)g fail fsimple shell(User)g with read command(Command):- % check legality of Command; uses Prolog I/O predicates 2 This theory shows how user inputs can enter in a polispace. The I/O model used in ESP isbased on Prolog I/O built-in predicates. 4 Process Programming with ESP The activity of programming with a Linda-based logic language has been explored elsewhere [16,17,38]. In this section we will show how ESP can be used as a language for modeling simple software processes and the related development environments. 4.1 A Tiny Programming Environment A very simple software process takes place in a programming environment including an editorand a compiler. We specify a naive software development process that consists of editing a file, then compiling it as soon as the editing by a programmer is terminated. If the compilation gives no errors, the object program has to be invoked and executed using some test data. Fig.1 depicts such an environment as a polispace. In order to build the ESP program that implements such a polispace we need three theories:one for an editing agent, (actually a shell for a user), one for a compiler agent, and one for an executing agent. These theories use predicates that are called envelopes in [26], becausethey encapsulate external software tools. Envelopes are useful to introduce non-declarative UBLCS-93-8 12 4 Process Programming with ESP operators inside a declarative framework, because they are able to call standard Unix tools via some system predicates that return a logic result (i.e., either success or failure). theory editor(Editor, Tty):- eval thisplace(User) fdo edit(File)g ! call editor(Editor,Tty,File), fcompile(User,File)@compileg with call editor(E,T,F):- . . . % invoke envelope for editor E theory compiler:- eval fcompile(User,File)g ! call compiler(File), fcompiled(File)@testg fail fdo edit(File)@Userg with call compiler(File):- . . . % invoke envelope for cc % fails if compilations fails for errors theory tester(Datafile):- eval test data(Datafile) fcompiled(File)g ! do run(File,Datafile,Result), ftested(File,Result)g fail ftest error(File)g with do run(File,Datafile,Result) :- . . . % invoke Prolog-Unix envelope for object File This minimal programming environment enforces a simple edit-compile-test programming model. The user interacts only with his tuple space; actions in other tuple spaces arecoordinated by the ESP program. 4.2 A Multiuser Environment enforcing an Access Protocol A software project is composed of a set of modules developed by a team of programmers. A software process designer has to design a software development environment that enforcesthe following policy. The updated public version of the whole project is stored within a main database. Users can access the main database in read mode only. Coordination is based on a reserve/deposit access protocol for the main database which guarantees mutual exclusion and consistency: the main database always contains a consistent and updated version of the project. To modify the contents of a module, a user must reserve the module to gain writeaccess. Obviously, at any time a module can be reserved just once. A reserved module is copied into the user database, where the user can modify it at will. While a reserved moduleis being edited in a user database, other users can access in read mode the old public version UBLCS-93-8 13 4 Process Programming with ESP user1 dbuser2 db user3 db main database oe? ffi flffl fiffi flffl fi ffi flffl fi ffi flffl fiffi flffl fi#" ! #" ! #" ! ' & $ % Figure 2. A polispace coordinating a multiuser environment of the module stored in the main database. When the changes to the module are completed and tested, the user will deposit the new version back into the main database. The updatedversion is then readily accessible by all other users. A polispace realizing such an environment is showed in Fig.2. The code of the theory user db manager, that handles the user's requests in a user database, is the following: theory user db manager(Dbmain):- eval thisplace(Udb) fcheck in(File, Dbmain)g ! fcheck in(File,Udb)@Dbmaing # thisplace(Udb) fcheck out(File,Dbmain)g ! fcheck out(Udb,File)@Dbmaing Since a user can issue in his blackboard either a checkin or a checkout command, there is a rule for each command, that simply transmits a tuple to the main database blackboard.This tuple space contains two agents that guarantee the consistency of the main database: the checkin manager and the checkout manager, that execute the following theories: theory checkout manager:- eval file(F), not reserved(F, ) fcheck out(P,F)g % read request for file F by programmer P UBLCS-93-8 14 4 Process Programming with ESP ! freserved(F,by(P)), file(F)@Pg % request granted # not file(F) % file F does not exist fcheck out(P,F)g ! ferror(no file(F))@Pg % request not granted # reserved(F,by(OP)), P 6= OP % file F reserved by programmer OP fcheck out(P,F)g ! ferror(is locked(F,by(OP)))@Pg % request not granted The first rule reserves the requested file; the other rules handle different error situations. theory checkin manager:- eval not file(F) fcheck in(F,P)g % create request for file F by programmer P ! ffile(F)g, fcreated(F)@Pg % request granted # file(F), reserved(F,by(F,P)) fcheck in(F,P)g % modify request for file F by programmer P ! call file server(modify, F, P) fmodified(F)@Pg % request granted # file(F), not reserved(F) fcheck in(F,P)g % cannot create: a file F does exist ! ferror(file exists(F))@Pg % request not granted # file(F), reserved(F,by(F,OP)), P 6= OP fcheck in(F,P)g ! % cannot modify: file F is reserved ferror(is locked(F,by(OP)))@Pg % request not granted with call file server(modify, F, P):- . . . % asks file system to get new file F from P's workspace The first rule create a new file; the second rule modifies a file, invoking by an envelope an operating system service; the other rules handle different error situations. 4.3 A Software Process Program Fragment In October 1990, the organizers of the Sixth International Software Process Workshop suggested a software process problem to the workshop participants [27]. The problem specifies a process in natural language; it concerns the development, change, and testing of a defective softwaremodule. Such a process is decomposed in a number of phases: designing, coding, testing, and management of change. There is an authority, CCB, in charge of the project; there is aprogrammers' team PT coordinated by a project manager PM. UBLCS-93-8 15 4 Process Programming with ESP We show how a software process designer could model part of such a process in ESP. We start creating three blackboards: one for the CCB, one for the PM, and one for the PT. The following goal sets up the initial distributed environment in which the process will take place. ?- ftsc(bb of CCB), tsc(bb of PMfdevelop change and test(Unit)g), tsc(bb of PT)g For blackboard bb of PT, we specify the termination condition using the following invariants: ?- finvariant(end work(Id)@bb of PT),invariant(abort work(Id)@bb of PT)g This means that blackboard bb of PT will terminate its activities when either tuple end work(Id) or tuple abort work(Id) is found.The following ESP theory controls the overall process from the viewpoint of the project manager PM. theory develop change and test(Unit):- eval change(requirements(Unit),Id), fauthorization(Id)g ! fschedule and assign tasks(Unit),start work(Unit,Id)@bb of PTg # fsuccess(Id)g ! fend work(Id)@bb of PTg # fcancel change(Id)g ! fabort work(Id)@bb of PTg The theory develop change and test(Unit) includes three rules: the first one describes the activation of the process, that starts when the CCB issues the authorization tuple and the specification of the changes for the target unit. The project manager responds to this "stimulus" by starting the schedule and assign tasks phase, that is defined by anotherESP theory. The other two rules state the possible terminal conditions of the process. theory schedule and assign tasks(Unit):- eval fchange(requirements(Unit),Id), project plans(Plans)g ! update(Plans,NewPlans) fproject plans(NewPlans), mail(Assignments)@bb of PT, change(requirements(Unit),Id)@bb of PTg with update(Plans,NewPlans):- . . . % definition of the new scheduling of tasks. For brevity we do not give a complete process program. A detailed solution to this problemcan be found in [3]. UBLCS-93-8 16 4 Process Programming with ESP 4.4 Discussion The examples we have given in this section are admittedly not complex. Moreover, some of their features are also offered by some existing and well known tools. For instance, somethingsimilar to the first example is not difficult to do with the make tool or writing a script for a sophisticated editor like GNU Emacs, whereas the second example captures only the very basic mechanisms of a tool like SCCS. However, these examples show that in ESP distributed computations are very easy to deal with. For instance, it is easy to specify different allocation policies. In the first example the three agents editor, compiler, and tester can be integrated in a unique blackboard, tobe allocated on one workstation, or else they can be put in different blackboards, aiming at enforcing distribution and protection. Moreover, combining different software processes is also not difficult: the following goal sets up an environment that combines the program of the first example with the program of the second example: ?- ftsc(maindbfcheckin manager,checkout managerg), tsc(user1fuser db manager(maindb), editor(module1,tty1)g), tsc(user2fuser db manager(maindb), editor(module2,tty2)g), tsc(compilefcompilerg), tsc(testftester(data1),test data(data1) g)g. More important, we have chosen these examples in order to show that in ESP it is possible to program and control several levels of coordination: ffl the overall structure of the software development environment, defined as set of namedtuple spaces devoted to distinct activities; ffl the activities encompassing several tuple spaces, defined by the communication flows of tuples that are sent from a tuple space to another; ffl the coordination of agents inside a tuple space, defined by the multiset of tuples that are active in such a tuple space; ffl the concurrent interactions among different agents in the same tuple space, defined by the semantics of tuple operations; ffl the tasks that an agent can perform, defined by the rules of the theory that it executes; ffl the actions that an agent has to perform for each task on which it is activated, defined by the knowledge base of the theory that it executes. We believe that software process programming is a difficult and complex undertaking mainly because there are all these different coordination levels that have to be taken intoaccount and amalgamated in a harmonious assembly. Although ESP is based on a small number of language mechanisms, it can be used to program all the above levels of coordinationin a declarative way. In fact, ESP keeps from the logic programming paradigm the view of computation as proof search. Thus, we obtain for free a formal semantics for the local (i.e.,non related to the tuple space) evaluations of agents. Admittedly, ESP moves away from pure logic programming to rely on a different, more expressive framework. In fact, ESP enriches logic programming with a set of coordination mechanisms for agent and tuple space creation, and for inter-tuple space communications. Although ESP is a powerful and expressive language for programming coordination, thegoal of managing the definition and evolution of the software process would be impossible to attack without the support of a specialized environment. Apart from the definition andexecution of ESP programs, such an environment should allow the integration between a UBLCS-93-8 17 5 Oikos software process and the tools it needs, offering a repository of services that can be used as building blocks of complex software processes. Such an environment is Oikos. 5 Oikos Oikos is an experimental rule-based software development environment that supports processprograms written in ESP [2]. Oikos provides a number of predefined facilities to model rulebased software processes over a distributed system. The overall approach consists of offeringmechanisms that can be easily composed using ESP, which can be used to model different software processes. In Oikos a software process is an ESP program that coordinates a dynamic collection of agents cooperating in a distributed environment modeled as a hierarchy of blackboards. The hierarchy offers a natural way of structuring a software process; conceptually, it is similar to the contractual hierarchy in IStar [20], but in IStar the nodes of the tree are documents,whereas in Oikos they are tuple spaces. In fact, the blackboard hierarchy is used to reflect the decomposition of the software process in subprocesses, according to a top-down refinementstrategy. The hierarchy is not really constraining the communication flows among the participants of a software process, since blackboard names can be exchanged in tuples, and an agent can put tuples in any blackboard, provided that it knows the name of the destination. Therefore, highly dynamic communication patterns can be set up, even connecting blackboards at different levels of the hierarchy, if this is convenient.Here we give only a short description of the current system architecture; the interested reader will find more details in [2,5,4]. 5.1 Services in Oikos A key concept in Oikos is the service, that is is a predefined subsystem that accepts requestsfrom clients. Conceptually, a service offers access to shared resources according to a given set of rules. Shared resources include software products, tools, the process program itself, etc.Formally, each service is defined by an ESP program that specifies the protocol of interaction with the service itself, i.e., which tuples must be put into its blackboard to submit a request. There are a number of standard services, that in Oikos play the role that primitive operators and data types play in a programming language. We discuss here only two Oikos services: the database service DBS and the user interface service UIS.In order to store information on the documents of a software process, Oikos offers the service DBS that interfaces a database management system. Currently the DBS is Salad,a deductive database management system based on a logic language [15]. The DBS accepts scheme definition requests, queries, and transaction requests; it also enforces access rights. Oneof the first duties of the software process manager is to set up the project database by defining its scheme, describing properties and relations among the different kinds of documents. Oikos provides a few predefined schemes, for the reusable documents related to Oikos itself, e.g., those containing the service specifications and those related to the tools already available at start up.Documents are actually stored in files, and are manipulated in a blackboard only via their identifiers. When it is necessary to operate on a document with a tool, e.g., an editor, thedocument is retrived from the underlying file system. UBLCS-93-8 18 5 Oikos no pre layout quitopen bb of PM interface on: historyscript enterclearexpandprecond edit holdrefreshexpandblackboard Figure 3. The ESP user interface Users accesses Oikos through shells managed by the User Interface Service (UIS). The user can see the contents of its blackboard in a window; his action must comply the rules defined in the UIS specification. UIS is a service because several different shells can coexist. A shell offers a flexible way to monitor a software process, since the user can activate it on a blackboard, looking at the tuple flow, and even saving some tuples to record the evolution of the softwareprocess [30]. Fig.3 shows what the user sees when he is connected to the ESP programming environmentunder XWindows (the ESP programming environment is called EXPO [5]). Conceptually, the user opens a window through which he can see the contents of a blackboard, and also put andremove tuples in such a blackboard. In fig.3 the leftmost top window shows the current contents of the blackboard. A number of buttons allow the manipulation of the window. The leftmost bottom window is used to edit "shell patterns", i.e., rules that are inserted and evaluated "on the fly" when the user is interested in some events that happens in this blackboard, typically when some tuples appearor disappear. The rightmost top window shows the history of user actions. The rightmost bottom window shows the name of the blackboard, and three buttons used to manipulate thewindows. UBLCS-93-8 19 6 Comparison with related work ' & $ %EXPO ' & $ % ' & $ %#" ! '& $%ff\Omega \Phi \Psi ff\Omega \Phi \Psi ff\Omega \Phi \Psi #" ! ff\Omega \Phi \Psi fflffi fifl\Upsilon \Sigma \Xi \Pi & %' $ & %' $& %' $& %' $ ESP ESPESPESP Unix + TCP/IP+ XWindows Figure 4. The Oikos architecture 5.2 Oikos Implementation Oikos has been written mostly in ESP. Fig.4 shows the architecture of the Oikos prototype that has been implemented at the University of Pisa on top of a local network of Sun worksta-tions. ESP provides the basic mechanisms for physical distribution and dynamic activation of communicating processes.The three main layers of the Oikos architecture are shown in Fig.4: the EXPO programming environment, which is written in ESP and provides an XWindows-based user interface [5];a collection of separate processes, that implement a distributed ESP run-time system; the underlying operating system, that is Unix. The hierarchy of blackboards is represented by nested boxes. The processes in the second layer are depicted by circles: an ESP process is the local interpreter of the ESP language, and there are as many of them as machines in the network, eager to interpret pieces of the ESP program. For a detailed exposition see [12,5]. 6 Comparison with related work First we compare ESP with other coordination languages, then we compare it with otherrule-based process programming languages. UBLCS-93-8 20 6 Comparison with related work 6.1 Comparing ESP with other coordination languages ESP is a language that combines Linda-like coordination with Prolog-like computation. It is an extension of Prolog in the same sense that C-Linda is an extension of C. In compari-son to Linda, the main difference is that ESP is based on multiple tuple spaces. Moreover, it gains expressiveness thanks to the "magic" of logic programming. However, ESP is not a mere Prolog-Linda dialect, because of the structure of the clauses. Such a structure, i.e.,Test and Consume-Compute-Output makes ESP similar to parallel logic languages like Flat Concurrent Prolog and GHC [36]. The most important difference with respect to these languages is that ESP tuple spaces have a state that agents manipulate by adding and deletingtuples; FCP and GHC operate on shared streams in a monotonic way, i.e., they can only add new data. Moreover, ESP is a true extension of Prolog, whereas FCP and GHC have no sequential component. There are now other parallel logic languages that are based on a notion of logical tuple space. A programming notation similar to ESP is Swarm [35], a specification language based on UNITY that has been introduced for studying the programming logic underlying tuple space communications. ESP is more tightly related than Swarm to logic programming, and ithas many constructs for programming in the large, that are currently missing in Swarm. Linear Objects (LO) [7] is an object oriented language based on a concept of multiple tuple spacesthat communicate by broadcasting. Apart from this, there are many similarities between ESP and LO, and we are studying them in a unified semantic framework [6].With respect to other rule based programming languages, like for instance production systems like OPS5, ESP rules merge cleanly two basic evaluation mechanisms: forward and backward chaining. Backward chaining is used during the local computation of Prolog goals;a form of parallel forward chaining is used as basic mechanism for activating agents. A logic tuple space is also very similar to a blackboard [31], and in fact many ESP implementationissues can be discussed in the same way as for blackboard systems. A detailed discussion of ESP related implementation issues is contained in [12,18]. 6.2 Comparing ESP with other rule-based process programming languages A well known project that inspired Oikos is the rule-based software development environment MARVEL [8,9]. MARVEL follows an object oriented design paradigm, and relies upon a specialrule-based language derived from production systems for AI applications. A software process is specified by three sets of specifications: the project rule set describes the development process, the project type set specifies the project data, and the project tool set defines the interface with external tools. This is an example of a MARVEL rule [9]: compile[?f:CFILE]: : (?f.compile status = NotCompiled) COMPILER compile ?f.contents ?f.object code ?f.error msg '-g' (and (?f.compile status = Compiled) (?f.object time stamp = CurrentTime)); (?f.compile status = Error); MARVEL rules have a name and include three sections: a precondition, an activity part, and a postcondition. The precondition is a condition to be evaluated with respect to the currentstatus of the project database; if it is verified, the activity part is executed, that usually invokes UBLCS-93-8 21 6 Comparison with related work a tool. At the end of the tool activity the postcondition specifies the effects of the rule on the project database. Such a rule could easily translated in ESP as follows: fcompile(c file(File,notCompiled))g ! do compile('cc -g', File, Object code, Error msg), time(CurrentTime) fc file(File,compiled), object file(File, CurrentTime)g fail fc file(File,error)g with do compile(Compiler, File, Object code, Error msg):- . . . MARVEL puts emphasis on designing the interaction protocols used by a multiplicity of users that share a project database. In ESP more importance is put on the environment's architecture design, aiming at formalizing the coordination model underlying users' activities.A key issue in ESP is the use of the blackboard model in combination with logic programming. The blackboard model of problem solving is well known in Artificial Intelligence [31],whereas in software engineering it has been exploited only in a few projects. For instance, Agora [10] uses a blackboard architecture for interprocess communication among hetero-geneous software components. A more recent and relevant example is REBUS, where the blackboard is curiously called "whiteboard" [40]. REBUS is a process program written in APPL/A [39], an extension of Ada for software process modeling. The REBUS whiteboard isused through five ad hoc primitives that manipulate its contents. The whiteboard is used to coordinate the activities of a number of participants in the software process.In our experience, the combination of the blackboard model with logic programming provides a powerful rule-based framework to specify and prototype distributed softwaredevelopment environments and the related software processes. The use of logic programming techniques and tools in software engineering is slowly gaining popularity. For instance, the Darwin project [28,29] develops a Prolog-based framework to support rule-based software engineering environments, called law governed systems. In Darwin the law is an explicit statement of a rule that must be followed by agents in the environment. Environments written in ESP can be considered as law-governed systems whose laws are stated in a parallel language.The use of Prolog for software process programming was suggested for the first time in [32], but without introducing any concurrency mechanisms. A more successful project for a rule-based environment centered upon Prolog is Merlin [24,34]. Merlin can be used to model rule-based software processes using an extension of Prolog in which both forward chaining and backward chaining computations are possible. Merlin extends Prolog with a few imperative constructs, like for instance CALL, INSERT and REMOVE, that operate on clauses contained in the knowledge base. This is an example of a Merlin rule: IF document(module, Object Name, to be compiled) THEN CALL(compiler, Object Name, Compile Status), REMOVE(document(module, Object Name, to be compiled)), INSERT(document(module, Object Name, Compile Status)). Such a rule is easily translated in ESP as follows: fdocument(module, Object Name, to be compiled)g ! UBLCS-93-8 22 7 Conclusions do compile(compiler, Object Name, Compile Status) fdocument(module, Object Name, Compile Status)g More complex sequences including several INSERT and REMOVE commands in an arbitraryorder could be rephrased in ESP using chains of rules. Currently the Merlin project does not take into account concurrency and distribution issues.We believe that the PoliS coordination model would be a natural way to extend Merlin with features to deal with concurrency and parallelism. 7 Conclusions In this paper we have introduced PoliS, a coordination model useful for designing distributed systems. A programming notation based on a combination of PoliS with Prolog, ESP, hasbeen used as a language for software process modeling. ESP has been used in the design and implementation of Oikos, a rule-based software development environment that is distributedover a local network. The ESP programming environment has been operational for three years. It has been used to implement a few distributed multiuser applications, like a referee for coordinating fourbridge players, a financial simulation of stock exchanges, and a simple e-mail system. Some software processes have been simulated, but not fully enacted, like for instance the softwareprocess defined in section 4.3. Our future plans include: the development of a graphic specification language to help inthe development of software processes that can be successively modeled in ESP; the definition of planning tools for assisting users in the software process; the possibility of changing a software process program during its execution. Moreover, we feel that PoliS and the whole coordination framework based on Multiple Tuple Spaces deserve to be more deeply studied. For instance, we are developing a programming logic for PoliS, aimed at developing a specification language suitable for distributedapplications. Acknowledgments The contribution given by the referees' comments to the improvement of this paper is invaluable. The author is also very grateful to N.Carriero and D.Gelernter at Yale, for many discussions on Linda and PoliS, and to his PhD thesis supervisor, U.Montanari, for the suggestion of studying associative coordination mechanisms. Last but not least, theauthor thanks all the members of both the Shared Prolog and Oikos research groups in Pisa, especially V.Ambriola, A.Brogi, M.Danelutto, M.Gaspari, and C.Montangero.This work has been partially supported by C.N.R. Progetto Finalizzato Sistemi Informatici e Calcolo Parallelo, and by the Italian Ministry for University and Scientific Research (MURST). References [1] ACM AND IEEE. Proc. Int. Software Process Workshops (1984-93), ACM Press. [2] AMBRIOLA, V., CIANCARINI, P., AND MONTANGERO, C. Enacting software processes in Oikos. In Proc. ACM SIGSOFT Conf. on Software Development Environments (1990), vol. 15:6of ACM SIGSOFT Software Engineering Notes, pp. 12-23. UBLCS-93-8 23 REFERENCES [3] AMBRIOLA, V., JACCHERI, L., AND MONTANGERO, C. Software Process Specification in Oikos. Tech. rep., Oikos Project, Internal Report, University of Pisa, January 1991. [4] AMBRIOLA, V., AND MONTANGERO, C. Oikos at the age of three. In Software Process Tech-nology, EWSPT '92: Proc. 2nd European Ws on the Software Process Technology (Trondheim, Norway, September 1992), J.Derniame, Ed., vol. 635 of Lecture Notes in Computer Science,Springer-Verlag, Berlin, pp. 84-93. [5] AMBRIOLA, V., MONTANGERO, C., FLAGELLA, T., AND GASPARI, M. Expo: a framework foprocess centered environments. Tech. rep., CNR-Progetto Finalizzato Calcolo Parallelo e Sistemi Informatici, July 1992. [6] ANDREOLI, J., CIANCARINI, P., AND PARESCHI, R. Interaction Abstract Machines. In Trendsin Object-Based Concurrent Computing, G. Agha, P. Wegner, and A. Yonezawa, Eds. MIT Press, Cambridge, 1992, to appear. [7] ANDREOLI, J.-M., AND PARESCHI, R. Linear Objects: Logical Processes with Built-in Inheritance. New Generation Computing 9, 3-4 (1991), 445-473. [8] BARGHOUTI, N., AND KAISER, G. Modeling concurrency in rule-based development environments. IEEE Expert 5, 6 (December 1990), 15-27. [9] BARGHOUTI, N., AND KAISER, G. Scaling up rule-based software development environments. In Proc. 3rd European Software Eng. Conf (ESEC 91) (Milan, Italy, 1991), vol. 550 ofLecture Notes in Computer Science, pp. 380-395. [10] BISIANI, R., AND FORIN, A. Multilanguage Parallel Programming of Heterogeneous Ma-chines. IEEE Transactions on Computers 37, 8 (August 1988), 930-945. [11] BROGI, A., AND CIANCARINI, P. The concurrent language Shared Prolog. ACM Transactionson Programming Languages and Systems 13 , 1 (1991), 99-123. [12] BUCCI, A., CIANCARINI, P., AND MONTANGERO, C. Extended Shared Prolog: A multiple tuple spaces logic language. In Proc. 10th Japanese Logic Programming Conference (1991, toappear), Lecture Notes in Computer Science, Springer-Verlag, Berlin. [13] CARRIERO, N., AND GELERNTER, D. Coordination languages and their significance. Com-munications of the ACM 35 , 2 (February 1992), 97-107. [14] CASTAGNETTI, T., AND CIANCARINI, P. Static Analysis of a Parallel Logic Language Basedon the Blackboard Model. Journal of Parallel and Distributed Computing 13, 12 (December 1991), 412-423. [15] CHIMENTI, D., GAMBOA, R., KRISHNAMURTY, R., NAQVI, S., SHALOM, T., AND ZANIOLO, C. The LDL System Prototype. IEEE Transactions on Knowledge and Data Engineering 2, 1(March 1990), 76-90. [16] CIANCARINI, P. Blackboard programming in Shared Prolog. In Languages and Compilers forParallel Computing , D. Gelernter, A. Nicolau, and D. Padua, Eds. MIT Press, Cambridge,1990, pp. 170-185. [17] CIANCARINI, P. Parallel Logic Programming Using the Linda Model of Computation.In Research Directions in High-Level Parallel Programming Languages (Mont Saint-Michel, France, June 1991), J. Banatre and D. LeMetayer, Eds., vol. 574 of Lecture Notes in ComputerScience, Springer-Verlag, Berlin, pp. 110-125. [18] CIANCARINI, P. Parallel Programming with Logic Languages: a Survey. Computer Lan-guages 17 , 4 (1992), 213-240. [19] CURTIS, B., KELLNER, M., AND OVER, J. Process modeling. Communications of the ACM 35,9 (September 1992), 75-90. UBLCS-93-8 24 REFERENCES [20] DOWSON, M. Integrated project support with IStar. IEEE Software 4, 11 (November 1987), 6-15. [21] DOWSON, M., Ed. Proc. 1st Int. Conf. on the Software Process. IEEE Computer Society, Redondo Beach, CA, October 1991. [22] GELERNTER, D. Generative communication in Linda. ACM Transactions on ProgrammingLanguages and Systems 7, 1 (1985), 80-112. [23] GELERNTER, D. Multiple tuple spaces in Linda. In Proc. PARLE '89 (1989), E. Odijk, M. Rem, and J. Syre, Eds., vol. 365 of Lecture Notes in Computer Science, pp. 20-27. [24] HUENNEKENS, H., JUNKERMANN, G., PUESCHEL, B., SCHAEFER, W., AND VAGTS, J. A Steptowards Knowledge-based Software Process Modeling. In Proc. 1st Conf. on System Development Environments and Factories (London, 1990), Pitman. [25] J.DERNIAME, Ed. Proc. European Workshop on Software Process Technology, vol. 635 of LectureNotes in Computer Science . Springer-Verlag, Berlin, September 1992. [26] KAISER, G., KAPLAN, S., AND MICALLEF, J. Multiuser, distributed language based environ-ments. IEEE Software 4, 11 (1987), 58-67. [27] KELLNER, M., FEILER, P., FINKELSTEIN, A., KATAYAMA, T., OSTERWEIL, L., PENEDO, M., AND ROMBACH, D. Ispw-6 software process example. In Proc. 1st Int. Conf. on the SoftwareProcess (Redondo Beach, CA, October 1991), M. Dowson, Ed., IEEE Computer Society, pp. 176-186. [28] MINSKY, N. The imposition of protocols over open distributed systems. IEEE Transactionson Software Engineering 17, 2 (February 1991), 183-196. [29] MINSKY, N., AND ROZENSHTEIN, D. Configuration Management by Consensus: An Application of Law-Governed Systems. In Proc. 4th ACM SIGSOFT Symp. on Software Devel-opment Environments (December 1990), R. Taylor, Ed., vol. 15:6 of ACM SIGSOFT Software Engineering Notes, pp. 44-55. [30] MONTANGERO, C., AND SCARSELLI, F. Software Process Histories in Oikos. In Proc. AICANational Conf. (Siena, Italy, September 1991). [31] NII, H. Blackboard Systems: the Blackboard Model of Problem Solving and the Evolution of Blackboard Architectures. The AI Magazine (Summer 1986), 38-106. [32] OHKI, A., AND OCHIMIZU, K. Process Programming with Prolog. In Proc. ACM SoftwareProcess Workshop (1989), vol. 14:4 of ACM SIGSOFT Software Engineering Notes, pp. 118- 121. [33] OSTERWEIL, L. Software Processes are Software Too. In Proc. 9th Int. Conf. on SoftwareEngineering (1987), pp. 2-13. [34] PEUSCHEL, B., SCHAEFER, W., AND WOLF, S. A knowledge-based software developmentenvironment supporting cooperative work. Journal on Software Engineering and Knowledge Engineering 2, 1 (1992). [35] ROMAN, G., AND HC.CUNNINGHAM. Mixed Programming Metaphors in a Shared Datas-pace Model of Concurrency. IEEE Transactions on Software Engineering 16, 12 (December 1990), 1361-1373. [36] SHAPIRO, E. The Family of Concurrent Logic Languages. ACM Computing Surveys 21, 3 (September 1989). [37] STERLING, L., AND SHAPIRO, E. The Art of Prolog. MIT Press, Cambridge, 1986. [38] SUTCLIFFE, G., AND PINAKIS, J. Prolog-D-Linda. Tech. Rep. TR91/7, Dept. of CS, Univ. ofWestern Australia, Nedlands, Western Australia, 1992. UBLCS-93-8 25 REFERENCES [39] SUTTON, S., HEIMBIGNER, D., AND OSTERWEIL, L. Language Constructs for Managing Change in Process-Centered Environments. In Proc. 4th ACM SIGSOFT Symp. on Soft-ware Development Environments (Irvine, December 1990), R. Taylor, Ed., vol. 15:6 of ACMSIGSOFT Software Engineering Notes , pp. 206-217. [40] SUTTON, S., ZIV, H., HEIMBIGNER, D., YESSAYAN, H., MAYBEE, M., OSTERWEIL, L., AND SONG,X. Programming a Software Requirements-Specification Process. In Proc. 1st Int. Conf. on the Software Process (Redondo Beach, California, October 1991), Rocky Mountain Instituteof Software Engineering, IEEE Computer Society Press. (also as Arcadia Document UCI91-03). [41] WEGNER, P. Concepts and paradigms of object-oriented programming. ACM OOPSMessenger 1 , 1 (August 1990), 7-87. UBLCS-93-8 26