I.Bider ilia@ibissoft.se

M.Khomyakov maxim@mag7.ulter.msk.su

Abstract. In traditional approaches to object-oriented programming, objects are "active", while relations between them are "passive". The activeness of an object reveals itself when the object invokes a method (function) as a reaction on a message from another object (or itself). While this model is suitable for some tasks, like arranging interactions between windows, widgets and the end-user in a typical GUI environment, it’s not appropriate for others. Business applications development is one of the examples. In this domain, relations between conceptual objects are at least as important as objects themselves and the more appropriate model for this field would be the one where relations are "active" while objects are "passive". A version of such a model is presented in the paper. The model considers a system as consisting of a set of objects, a code of laws, and a set of connectors, each connector hanging on a group of objects that must obey a certain law. Formal logical semantics of this model is presented as a way of analyzing the set of all possible trajectories of all possible systems. The analysis allows to differentiate valid trajectories from invalid ones. The procedural semantics is presented as a state machine that given an initial state, generates all possible trajectories that can be derived from this state. This generator can be considered as a model of a connectors scheduler that allows various degrees of parallelism, from sequential execution to the maxim possible parallelism. In conclusion, a programming language that could be appropriate for the proposed computer environment is discussed, and the problems of applying the model to the business domain are outlined.

Keywords: formal semantics, persistent action, law-based programming, business process, process management.

When first appeared, the computers were mainly used to complete computational tasks which had a great influence on the evolution of the discipline of programming in the future. The first program abstraction, black box, considered the program as a rigid computational device that having been supplied with a query, would compute the reply, and then stop. The stop was an essential feature of the program, and nonstop symbolized the erroneous behavior.

When nonstop and communication between different programs became a necessity, the problems where first practically solved on the level of operating systems. Later, these requirements lead to evolving the multi-component languages and environments. In AI, this lead to the collaborative agents’ abstraction while in programming - to the object-oriented programming languages, like, Smalltalk, C++, Java. However, the black box abstraction can still be traced in those new environments as individual components, i.e. objects, are often viewed as "black boxes".

Any traditional object-oriented system can be considered as consisting of objects and relations between them. Relations are usually "passive", while objects are "active. Objects possess both the structure and the ability to complete actions. Relations serve as a means of expressing the complex structure of objects, and as the channels for inter-objects communication. The objects interact with each other by exchanging messages, each message triggering the invocation of a method (function, etc.) in the receiver. Communication with the external world, e.g., end-users, external devices, is also defined in the form of messages that come from outside.

The above model is suitable for many computational and non-computational tasks. Arranging interactions between windows, widgets and the end-user in a GUI environment is a typical example were it works very well. In recent years, this model, without major modifications, started to be applied to the design of business applications where it doesn’t fit very well. All leading manuals on object-oriented analysis (see, for example, Rumbaugh et al., 1991, p.153; Coad and Yourdon, 1990, p. 61; Graham, 1995, p. 301) suggest searching for nouns when analyzing the business language of a particular domain. Nouns become objects, while verbs become methods inside those objects. The typical result of using the object-centered approach to the business application design is an employee object that has a method of calculating it’s own wages. This point of view is in apparent contradiction with common sense.

One difference between GUI and business environment is that the latter is driven by changes rather than by receiving external signals (messages). For example, a new purchase order may result from the number of goods in the stock falling below the minimal norm, i.e. the order is initiated by a change in one of the "business objects". Moreover, to calculate the right quantities of goods to order, the history of the stock changes is required, e.g., to know how fast the stock was falling. The result of the purchase process is also a change, the one that restores the normal level of the stock.

Another difference between business and technical domains is that in the business world relations are at least as important as objects themselves, and this tradition goes back to the ER model (Chen, 1976). From the business point of view, the calculation of wages is more natural to represent as a relation between the amount of money on the employee’s account and the time he/she worked for the company this month, rather than a method inside the employee class. (Obviously, this is not the only relation that affects the amount of money on the employee’s account.)

The third major feature of the business domain is that business processes are "human-assisted". The human beings need to have the flexibility not only to change the passive structure of business objects, but also the actions currently planned for them.

The limitations of the classical object-oriented approach are well known, see, for example, the extensive critique in (Kurki-Suonio and Mikkonen, 1999). So called generalized object models, which allow several objects to participate in the same action, where proposed in order to overcome those limitations, e.g., (Kilov and Ross, 1994), (Kurki-Suonio and Mikkonen, 1997). By now, the notion of generalized object model has already found its place in various object-oriented standards, see, for example, (Reference Model for Object Data Management, 1993).

We suggest another approach to the problems while remaining in the frame of the object-oriented paradigm. It consists in reversing the roles assigned to objects and relations. The relations become active, while objects become (relatively) passive. The distribution of roles becomes more even. The objects retain their complex structure (expressed by relations), but "lose" the ability to produce actions. Instead, this ability is handed over to the relations. Messaging disappears from the model while reaction on changes in the objects becomes the main means of communication. The connections with the external world is no longer based on messages received from outside. They are represented by relations that connect objects inside the system with the outside world, human beings becoming part of those "external" relations. From inside, the external relations behave non-deterministically, while their structural properties are the same as for the internal relations.

Note. On a very abstract level, our proposal of moving the weight from objects to relations resembles the main idea of category theory, see, for example (Barr and Wells, 1995).

The main topic of discussion in this paper is a precise semantics of a model with active relations. The experience of using this model for business software development, though slightly touched in sections 7, 9, is discussed elsewhere (Bider, 1997a, Bider and Khomyakov, 1997, 1998a, 1998b).

The need for formal semantics is well understood in the theory and practice of programming languages and systems. Currently, this is a topic of ongoing object-oriented standardization activities, see, for example (Kilov, 1993). Our model with active relations is aimed to express the laws of business reality and to help in building business applications, especially those that deal with process management, workflow, etc. These applications tend to become very complex in the end, even when the development starts on a small scale. The absence of a well-defined semantics may easily result in a system that does not fulfill the business requirements.

Conceptually, our approach to defining semantics is very close to the one outlined in (Kurki-Suonio and Mikkonen, 1999). Instead of trying to describe the behavior of any possible system with active relations, we concentrate on finding a practically interesting class of systems the semantics of which can be defined in a straightforward way. We also explore the closed system concept; i.e. the environment is included into the system specification, however incomplete it may be.

Our approach to formalization is similar to the one adopted in the field of logic programming (Lloyd, 1993), but only to some point: in our research, we are not interested in deductive reasoning, but in describing the behavior of dynamic systems. In our formalism, we use the notion of possible worlds that was developed in the field of modal logic starting with the works of Hintikka (Hintikka, 1962), and Kripke (Kripke, 1963). However, we don’t use this notion for speculation about different truth-values of a given formula in different worlds. We use it to formally differentiate valid worlds from invalid ones. Another difference is that we view a possible world not as a set of predicates that describes it, but as an infinite sequence of its states - the world’s history.

The paper has the following structure. In section 3, we give an informal description of the suggested model. In section 4, we present a formal logical semantics of it. In section 5, we discuss the model's procedural semantics without presenting the complete version of it. Section 6 is devoted to discussing a programming environment that would be suitable for our model. Section 7 discusses the issues of business process modeling from which the model with active relations originated. Section 8 reviews the related works. Section 9 contains a brief history of the project, and underlines the advantages of the model with active relations.

In this section, we will try to introduce all main notions of our model informally, i.e. using as little formal notation as possible. The discussion is not complete and sometimes is not precise, the goal is to offer a general view on our approach. Our aim is to give a definition of a valid world which we present as consisting of:

• a set of objects,
• a code of laws,
• a set of connectors, each connector hanging on a group of objects that must obey a certain law.

In a valid world all objects behave properly, i.e. their life is defined by the law imposed on them by a connector.

Our approach to describing the dynamic behavior is state oriented as defined, for example, in (Saaltink and Selic, 1997). We start with the set of objects O that are the main constituents of our world. An object may possess a complex structure the nature of which will be discussed later. For now, we will assume that there is a set S that lists all possible object states.

A function

st: O -> S

w: T -> ST

is called a world. The world determines the state w(t)(o) of any object o at any point of time t. For simplicity, we consider the discrete time axis with starting point, i.e., it consist of all nonnegative integers called time ticks. A moment of time t in which the value of function w changes is called an event.

We are interested in observing the collective behavior of a selected group of objects, where each object has its own role. Such group may be defined by an n-tuple of objects z = <o1,…, on> which we call an n-component system. The behavior of the system z in the world w can be described by the trace function trace_z,w(t) which for each t in T gives the states of all system components (objects). The important instance of a collective behavior is individual one when the system consists of only one object.

The laws are analogues to the predicates of logical programming. However, they differ from the latter in two important aspects:

• The truth values are defined on objects’ lifelines, not on the static states.
• If for some lifelines the law is not satisfied, it includes the action of how to restore it.

In a dynamic world, a system is exposed to external (for this system) disturbances that may change its state. If the law is broken it will take some time to restore it. Therefore, we can’t require the law to hold at each point. We need a more liberal definition of law preservation.

Figure 1. Behavior of the system <X,Y> under the law imposed by the connector C. Dashed intervals on time axis show moments when the law is broken.

system and see to it that the law is preserved.

We define the validness of the world with the help of Four Global Principles:

The world that satisfies the above principles can be generated by a machine in which a connector is regarded as a processing unit that monitors its operands. A connector

• awakes when one of its operands has been changed,
• checks by reading the condition part of the law whether it still holds,
• restores it when broken,
• falls asleep.

The machine has also a central unit that resolves conflicts when several connectors need access to the same objects. Thus interpreted, the connector behaves as an actor whose motive is a change in his environment and whose intention is to restore the law that has been entrusted to him. In other words, the connector aside from being an "active relationship" between its operands realizes the idea of "persistent action".

The connector machine gives the natural interpretation to the Four Global Principles defined above:

1. Causality. An event can happen only when some connector introduces changes in order to restore the law.
2. Inertness. The connector needs some time to compute and introduce changes. The constant h just expresses this fact.
3. Localism. The connector knows nothing about the objects beyond its operands, and thus, neither can change them nor use them in its work.
4. Limited lawlessness. In case when several connectors hang on common objects, it requires more time (than h) to restore the law. This principle guarantees that within time H any broken law will be restored.

To ensure that a valid world is computable, i.e. the connector machine can generate it, we need to introduce some constraints on any law that can be imposed in the world. The most important are the following two:

1. Quasi-idempotentness which requires that at any point of a system trace where the state is changed by the law’s action, the law holds. In other words, after the action is applied, the law is always restored. The connector entrusted with such a law doesn’t need to check the result of its work.
2. Fullness which requires that an action is defined for each point where the law doesn’t hold. This constraint guarantees that the machine won’t reach a dead-end.

Other constraints can be expressed as various symmetries. They ensure that any code of a law is a "finite text":

3. Fairness. Any law is symmetrical under a trace transformation based on an arbitrary object transformation. In other words, the law doesn’t differentiate any particular objects, only the behavior matters. There is no mention of concrete objects in the code of any law.
4. Liveliness. Any law is symmetrical under a transformation of traces based on an arbitrary mapping from time to time (not mandatory one to one) that preserves the sequence of events. In other words the length of the idle intervals is not taken into account, only the sequence of events matters. This constraint is directly connected with the principle of limited lawlessness. As the action can happen at any time within the interval H, there is no sense to take into account the length of time intervals, at least not with a precision that is less than H.
5. Limited (historic) memory. A part of the system trace that stretches up to the observation point t and covers the last k events is called a k-tail of this trace. Any law is symmetrical under a transformation of traces that preserves the l-tail, where l is a predefined constant. One of the consequences of this rule is that the law is not dependent on the future. The rule also manifests that there is no punishment for the old events of breaking the law if the subject behaved properly in the recent past. For l=1, the law looses its historic nature, and the connector becomes purely state-oriented.

Thus, there is only a finite set of all possible (factorized) l-tails that can be mentioned in a code of any law.

The universe described in the previous sections may be called quasi-deterministic. If the initial state is fixed, the difference between two worlds derived from it could be explained by different choices of what connector has been fired first in case of a conflict. Such determinism would be justified if when modeling the reality, we could have the exact knowledge of all laws that act in it. This is not true in practice where we always model only a part of the reality. To express this fact we exploit a notion of non-deterministic law. Its nature may be clarified by a so-called boundary connector, i.e. a connector part of which is outside the world being modeled. This part may include some operands (invisible inside our world) and/or some fragments of the law text. What we see inside is a projection of the connector from the bigger world on our world.

We differentiate two types of non-determinism: firing non-determinism, and action non-determinism. For a law with firing non-determinism, an action can be defined even for those points of a trace where the law holds. A connector that imposes such a law may be awoken even when none of its operands have been changed. This connector may, for example, be viewed as a projection of a connector with an additional operand that changes in the outer world, as illustrated on Fig. 2.

A law with action non-determinism can specify two different actions for the same point of a trace. A connector entrusted with such a law appears to be taking different courses of action in the same situation. This connector may, for example, be viewed as a projection of a connector with a more detailed text of the law, as illustrated on Fig.2. Those details actually determine what measures should be undertaken to restore the law.

A connector entrusted to guard a law over its operands is the main programming unit of our model. As such, it may be compared with a function in a traditional programming language, like C, or a method in an objet-oriented programming language, like Smalltalk, Java, or C++. The power of a programming language depends on the possibility of decomposing complex computations into simpler ones, including the recursive decomposition. In traditional languages, this power is obtained through (recursive) procedure calls, or function invocations. In object-oriented languages, the same is gained by one object sending a message to another one, or itself which may include direct or indirect recursion.

In our model, the connector guarding the law can’t directly invoke (or send a message to) another connector. The philosophy of decomposition in the model is completely different, and it corresponds to the nature of the programming units. The task of the connector is not to do calculations, but watch its operands and restore order in them. Decomposition for this goal may mean that the "main" law requires that there should always be connectors that guard some "local" laws between (part of) the main connector’s operands. If those connectors are absent, the main connector will add them. Then it is up to the local connectors to ensure that the local laws are satisfied. In case a local law is equal to the main one, we’ll get the recursive decomposition (see example in section 6).

A similar way of decomposition may be found in the programming language REFAL (Turchin, 1989). REFAL has a notion of working area where pure data can be mixed with calls to executable functions. If one function "wants" to invoke another one, it can place a call to the second function in the working area (instead of direct invoking the latter). This call is activated later when the processor of working area reaches it.

It’s worthwhile to mention that the above decomposition does not guarantee that the main law will be satisfied in the end. Changes introduced by other connectors can create a situation were all local laws of the given decomposition are never satisfied simultaneously. Decomposition guarantees only that if nothing else stays in the way, the main law will be satisfied in the end.

The goal with this section is to prove that our model has precise semantics, and thus it can serve as a sound basis for building software systems. The section consists of a number of definitions that follow the path: signature, interpretation, model. The definitions are built in the normal for logic programming way (as outlined in Lloyd,1993) with the reservation mentioned in section 2. When formally defining the notion of state, we use an approach similar to the one outlined in the club systems (Borshchev and Khomyakov, 1976).

Mostly, the text below just formalizes the notions that have already been discussed informally. However, two extensions are introduced in this section:

1. A connector, besides its operands, can have a number of constant parameters. In our model, those parameters serve as a way to introduce atomic (unstructured) data types.
2. A law may take into account not only the surface content of the objects it governs, but it can "see" the structure of their sub-objects up to a certain depth. A surface content consists of connectors included in the object while sub-objects are operands of those connectors.

The formal text does not follow exactly the line of thought presented under informal discussion. To make the text more readable, we tried when possible to use the terms informally explained in section 3. Another link to the informal discussion consists of the references to the global principles and law constraints in all places we consider relevant.

Let A be an alphabet that consists of:

Let:

then the expression c = p_v(z) is called a (well-formed) connector. Objects x1, ..., xn are called the operands of connector c; the set of all operands will be denoted as op(c).

Denote the set of all possible states with capacity b as UST_b (Universal set of States).

is called the guts of depth d of set s in state st. Apart from the objects from the original subset, the guts comprises all sub-objects that are directly, or indirectly included in one of the original objects. The depth of the inclusion is determined by constant d.

Definition. Let st be a state, s be a subset of objects from alive(st), and d be a positive integer. Then the restriction of function st on the subset gutsd-1(s, st,) is called the d-depth body of set s in state st, and is denoted as bodyd(s, st).

Note. The notion of d-depth body is introduced in order to restrict the visibility of the connector’s operands to a certain depth.

Consider a function that assigns a state to each time tick

Denote the set of objects whose states were changed during the event t as changed(w,t):

Let d, h be positive integers. A function w: T -> USTb is called a (well-formed) world with depth d, capacity b, and inertness h if for any event t there exists a connector c, such that:

The connector c is called the author of the event t. In the above, (a) formalizes the principle of inertness. (b-e) formalize the principle of localism, i.e., changes are localized to the d-depth bodies of the author’s operands. However, new objects may be born there.

The set of all possible worlds for a given alphabet A, depth d, capacity b, and inertness h is called the (A,d,b,h)-chaos language. Denote this set by UWd(A,b,h) (Universal set of Worlds).

The definitions in this subsection prepare a way to formally define the law properties: quasi-idempotentness, fullness, fairness, liveliness, and limited memory.

trajectory_d(z,w,r)(t) = body_d({x₁, ..., x_n}, w(t))

Let tr be a track, then denote:

1. its system as sys(tr),
2. its observation period as period(tr),
3. its ordered sequence of events as events(tr),
4. its trajectory as traj(tr)

Denote the set of all possible n-component tracks with depth d and length l in all possible worlds from UW_d as UTR_d,l,n (Universal set of Tracks).

Note. Reduction "truncates" the oldest event. This notion is used when formalizing the quasi-idempotentness property.

Note. Extension "adds" a new event. This notion is used when formalizing the fullness property.

Event-equivalent tracks share the same sequence of events.

m: O -> O

such that:

Object-equivalent tracks share the same object structure during the observation period.

Note. The notion of track equivalence is used to formalize the law symmetries, i.e., fairness, and liveliness.

Let l be a positive integer, then an l-interpretation I of an (A,d,b,h)-chaos language L consists of:

Otherwise we say that c is unsatisfied in world w at time t in interpretation I.

In this section we present an alternative approach to defining the semantics of valid worlds. This time it has the form of a formal procedure that given an initial state (at time 0) produces an H-valid world (chaos) in an l-interpretation I. We call such procedure a Chaos Generator (CG). An advantage of the procedural approach to defining semantics is twofold:

• It proves the existence theorem: a formal machine can generate a valid chaos.
• It also gives a clue to the structure of a software (hardware) implementation of our model.

Our Chaos Generator works in steps. At each step it produces an extension of the history generated at the previous step. Aside from the history produced so far, the state of the chaos generator is defined by 5-tuple GEN[i]:

where:

• SCON consists of connectors that are satisfied and do not need to do anything about their operands
• ECON consists of connectors such that:

1. their laws are nontrivial and their operands (more precisely their d-depth bodies) have been changed on one of the previous steps, or
2. their laws are with firing non-determinism, and they manifested the desire to change their operands without any internal reason.

• ACON consists of the connectors that have already got access to their operands and started their law enforcement work.

The idea of CG can be described as a connector’s circulation in nature, see Fig. 4.

By choosing different algorithms of transferring connectors from one set to another, we can model different ways of solving possible conflicts between connectors that hang on common objects. Three basic types of CG functioning are possible:

Initial state of CG is defined as:

where:

w[0] - the given initial state of the world;

TCON[w(0)] - the set of connectors with trivial laws (in the initial state of the world);

NTCON[w(0)] - the set of connectors with nontrivial laws (in the initial state of the world);

atime[0](c) = 0.

The Chaos Generator described above can be considered as a model of a connector’s scheduler. This model clarifies the relationship between h and H. The condition h*M <= H ensures the principle of limited lawlessness in the worst case: there exist M connectors, and all of them are linked to each other via common objects. Three different algorithms of activating connectors that were mentioned above can be used as a basis for implementing the connector scheduler in three different environments:

• Single-process environment,
• environment with a limited number of available processes - one per each active connector plus one for the scheduler,
• environment with unlimited number of available processes - one per each connector and one per each object.

This section discusses some topics that concern a CHAOS programming environment. The discussion touches such issues as elementary types and classes, communication with external world, and a suitable programming language for writing laws.

The model described in the previous sections consists of:

• objects,
• connectors, and
• constants.

Objects and connectors are the main elements of the model. They are the building blocks of complex structures. Constants are foreigners in this world since they are used to incorporate external data types. Constants may be of simple types, like integer, float, or string, or of some complex types, but even the latter are treated as unstructured entities (so called blobs).

Connectors express objects’ properties and relations. An unary connector expresses properties of its only operand with the help of the k constants (if any). If the connector’s law is trivial, it just assigns properties to the object. If the law is nontrivial, the connector forces the object’s structure and behavior to comply with those properties.

An n-ary connector expresses a relationship between its operands, where constants (if any) describe properties of this relationship. If the connector’s law is trivial it just expresses the (passive) relationship between the objects eventually assigning some properties to the relationship. If the law is nontrivial, the connector forces the objects’ structure and behavior to be in sync with each other and, possibly, with the properties of the relationship.

The notion of class is absent from our model. Objects are primary elements of it. A class may be represented as an unary connector that forces the object on which it hangs to have a predefined structure. Moreover, a class may be represented by a binary connector where one operand serves as a template of the structure that should be imposed on the other. The notion of class hierarchy may be represented as a chain of class connectors, where one hangs on the template of the next one in the chain adding additional elements to the previous template.

With our concept of class, an object can change its class during its lifetime. This happens when one class connector is substituted with another one. After that, it’s up to the second connector to rearrange the structure of the object so that it satisfies the requirements of the second class.

As several connectors can hang on the same object, several classes can be assigned to simulating multiple inheritance. It's up to class connectors to solve the inheritance conflicts in one way or another. If the connectors are defined in an incompatible way, hanging them on the same object can lead to the unstable behavior where one connector will always undo the changes done by the others.

Boundary connectors are the primary mechanism to model communication with the external world, e.g., people, or electronic devices. A boundary connector may be thought of as having a terminal where a human being can help the connector to do its job.

Let us assume that a connector’s law has action non-determinism. Then it is up to the connector to request the human assistance via the terminal when its operands have been changed, for example, by beeping, blinking, etc. After providing assistance, the human being may return to his other occupations, drinking coffee, for example, until the connector calls him again. Action non-determinism may vary from allowing any possible structural changes in the connector’s operands to a selection from a list of predefined choices (menu).

Now, let a connector’s law have firing non-determinism. Such connector can be represented as a big button that the user presses from time to time based on observations that lie beyond the boundaries of the computer system. Then it’s up to the connector to do the rest of the job.

All other situations of non-determinism may be considered as a combination of the two cases described above, see Fig.5.

A chaos runtime environment consists of a connector scheduler, and a connector executor. The connector scheduler decides when and which connectors should get access to their operands and start their law-enforcement work. The generation procedure described in section 5 outlines the main principles of the scheduler. The executor is a device that given the text of the law, changes the connector’s operands according to it. To facilitate the work of the executor we need a programming language for writing laws.

A law language should have two types of operations:

• The operations on constants (external data types), like arithmetic operations, string operations, etc.
• The operations on objects’ structures (internal data types), like add connector, delete connector, etc.

Different approaches to constructing a law language can be used. For example, it may be built as a relatively low-level language with basic operations, like add/delete connector. However, for dealing with complex structures, a pattern matching and transformation technique would be more appropriate. The sophisticated pattern matching technique has been developed in AI for LISP, PROLOG, and other AI languages. This technique could be used for creating a high-level chaos programming language.

Building a real law programming language lies beyond the scope of this work. To demonstrate the difference between normal and law programming we present two simple examples. One of them is written in a would-be low-level law programming language. It mimics C-syntax, and has loop operations, set operations, and simple pattern matching operations. The other one demonstrates recursive decomposition and is represented by a picture. This picture may be viewed as a prototype for a visual law programming language.

Those two examples are classical: a shallow mirror (corresponds to the shallow_copy function), and a deep mirror (corresponds to the deep_copy function). We use the word mirror instead of copy to stress that we deal with persistent actions rather than functions. Both examples belong to the root chaos as they don’t take into consideration any historic data, and don’t "see" the objects deeper than one level. Nevertheless, those examples demonstrate the basic principles of law programming.

Example 1. The shallow_mirror(o1,o2) law enforces object o2 to contain the same connectors as object o1 with one exception. If a connector c from o1 has o1 as one of its operands, connector c1 is included in o2 instead of c, where c1 is derived from c by substituting the operand o1 with o2.

Example 2. The deep_mirror(o1,o2, buffer) law enforces object o2 to contain images of objects and connectors from the body of object o1. The third operand is used as a buffer for recursive decomposition defined as follows:

1. For each object o´ found in the body of o1 (except o1 itself), there should be one and only one connector deep_mirror(o´, o´´, buffer´) in buffer. This connector links o´ to its image o´´ (o´´ should not be a sub-object of o1).
2. Buffer should not contain any other connectors than described in (a).
3. For any connector c from o1, o2 should contain its image c´. Connector c´ has the same law as c, and the same set of constants (if any), but it hangs on the images of the original connector’s operands. If one of the operands is o1 itself, then o2 is used as an operand for c´.
4. Object o2 should not contain any other connectors than described in (c).

This low is declared as:

Its functioning is specified by Fig. 6. The figure shows a configuration that should be built in buffer, and o2 based on what is inside o1. Double lines shows universal quantifies "for each connector in o1", "for each operand that is equal to o1", and "for each operand that is not equal to o1". In addition, the correctness of o2, and buffer is determined by the principle of minimalism, i.e. the configuration should be achieved with the minimal set of connectors. The principle will assure that there is only one image for each sub-object, even when several connectors hang on it. The punishment is also defined by the principle of minimalism: to restore the configuration with the minimum of operations add/delete connector. This will ensure that already existing images will still remain.

Note: The law described above won’t handle properly the situation when an object coincides with its own sub-object on the level deeper than one. It also won’t work if the number of sub-objects in o1 is greater than the capacity b. Then the law will delete the latest added connectors from o1, or signal an exception in some other way.

The notion of active relations originated from our work on object-oriented business process modeling. We have found that the objects representing business processes posses some interesting properties that require special consideration, e.g.:

• They are time-based. An event can be raised when a certain time condition is fulfilled without any external message being received.
• They are history-based. It’s not always possible to calculate the reaction on the event based only on the current state of the object..
• They are human assisted. None of business application possesses the whole knowledge of the application domain it works in. Thus it’s not always possible for an object to react on the event (or even raise it) without a human being’s help.
• Their actions may evolve in time. Reaction on an event may change not only passive elements of the object structure (data), but the actions currently residing in the object. This is particularly true for human-assisted actions. The assisting end-user may remove some actions inappropriate for the given object from its state and add new ones.

These properties make it not practical using the traditional object-oriented approach to represent business processes. Even the generalized model that allows several objects to participate in the action doesn’t help much. We believe that the model proposed in this paper is better equipped for dealing with the above properties, as it includes time, history, configuration changes etc. However, even this model is too low-level for practical purposes.

The need for higher-level model can be derived from the following conceptual understanding of a business process. A business process serves as a framework for activities that should lead to a well defined objective, e.g., closing a sale, getting money for an incoming order (after delivering the goods), etc. At any given moment of time, the process is characterized by its state that shows how far it is from the objective. The process is driven forward through a set of stipulated states until it reaches the final state. The final state shows that the process objective has been achieved, e.g., all money invoiced for the goods delivered have been received. The objective can be defined as a set of conditions that indicate when the state of the process is considered to be final, see Fig 7.

The process that is not in the final state, but has no activities planned for moving it to the next stipulated state is considered to be in an invalid state. Formal rules (a law) can be defined that specify what planned activities could be added to the process’ state to make it valid.

Business processes possess the following essential features:

1. A business process may stretch over a long period of time, some processes may take years to complete. During this time, the perception of how the final state of the process should look like may change. For example, one could expect that in the final state of the order process from Fig.7, the amounts invoiced and paid are equal to 208440.00. However, it may still happen that the customer changes his order by returning part of (or even all) the goods initially ordered, or/and adding new items to the list. As a result, the list may be completely changed or even become empty.
2. When planning new activities, it’s often enough to analyze the current state of the process without going into its history. For example, to complement the process’s state from Fig.7 with the plan on Fig. 8 (left), we don’t need to know that the delivery has been done in two steps, as shown on Fig. 8 (right). It’s enough to know that all goods ordered have been delivered, the fact that can be established from the current state. However, in case of some goods not reaching the customer, we need to analyze which shipping went wrong in order to recover the goods (meanwhile, new goods could be shipped to the customer). Thus, the history may become important when the process deviates from the standard pattern.
3. Many people may participate in the same process and they can belong to different departments. For example, in order processing represented on Fig.7-8, people from sales, shipping and accounting usually participate.
4. The same person normally participates in many business processes simultaneously. For example, shipping may consist of one person that ships all goods ordered via various sales representatives.
5. A business process may require human participation not only for executing particular activities, but also for making "arbitrary" changes in the process state (non-deterministic law). This concerns both the static part of the process state, and its dynamic part, i.e. plan. "Arbitrary" changes in the former may be necessary to reflect changes in the outer world, for example, when the customer rings and modifies the list of goods ordered (see 1 above). "Arbitrary" changes in the plan may be required to control the process that deviates from the standard pattern. For example, if goods that have been shipped disappear, then some actions should be planned to recover them (see 2 above).

The above listed features make it impossible to effectively control business processes without a supporting system. This is especially true in the business environment where a relatively small staff handles a large amount of processes (see 4 above). The supporting system should help in coordinating the work of many participants of a process (see 3 above), and controlling processes when it’s not feasible to have a project manager assigned to each process. The control should be flexible to achieve the highest degree of automatism when a process follows the standard pattern (autopilot), while allowing manual control when the process deviates from the standard.

To formalize the conceptual understanding presented above, we need to define a number of high-level notions, such as:

• Process state that consists of a static and a dynamic part. The static part includes attributes, like to pay, invoiced, paid, etc. on Fig. 7, and links to other business objects, like customer, articles, etc. The static part can be modeled by connectors with trivial laws. The dynamic part consists of a list of planned activities, like invoicing in Fig. 8. A planned activity can be modeled by a connector of a special kind that automatically deletes itself after its law-enforcement function is fulfilled. Before disappearing it may add some other activities to the list.
• External time, and timers (alarm clocks) that may be modeled as boundary connectors.
• Chronicle that gives a written explanation to each event that happens (e.g., as shown on Fig. 8, right).

The task of formalizing these and other notions, and expressing them in the terms of the object-connectors model lies beyond the frame of this paper; this activity is planned for the near future. Our practical model that introduces and implements the notions needed for business-process modeling is described in (Bider and Khomyakov 1997, 1998a, 1998b ) and (Bider, 1997a, 1997b).

In the practical frame, our work is related to the research being done in the field of business process modeling, see, for example, (Deiters and Gruhn, 1998). In the theoretical domain there are a lot of fields that are related to our research, including AI, object-oriented programming, object-oriented databases, temporal databases, logical programming, etc. Some works from these fields have been referred to in the previous sections. To list all relevant literature would extend the reference list too much.

Many features of our model can be found in other research works, or are in the air. To compare our approach to those of others is beyond the frame of this paper, the exception is made for two areas discussed below. Generally speaking, the essence of our approach is not the features itself, rather the way we are trying to obtain them from a small amount of simple and clear-cut notions.

As far as the concept of law-based programming is concerned, there is an interesting research on the law-governed architecture done by N. H. Minsky (Minsky, 1996). Though the basic idea of using the concept of law for system definition and implementation is the same, the direction of its application is different. We apply the concept of law to describe local behavior, while in (Minsky, 1996) laws are used to describe global behavior.

As far as the system architecture is concerned, our approach is close to the agent-based systems (see, for example, review in Müller, 1996). The similarity is based on the fact that we describe the same kind of dynamic systems, i.e., systems that have both the reactive and proactive behavior. However, the approach to structural presentation of these systems in our formalism, i.e., active relations, differs from the one normally used in the agent-based systems.

The object-oriented model presented in this paper is the main result of our CHAOS research project started back in 1984, where CHAOS stands for Concurrent Human-Assisted Object Systems. The main goal was to develop a general approach to building so called human-assisted systems, as opposed to the traditional, human-assisting systems. The former works on its own appealing to the human help only when necessary. The latter represents the traditional view on the business system development; it is a human being who does the work, the system only helps him to perform certain functions.

Our theoretical model was first tested in practice in 1989-90 when we were developing an application for supporting sales and marketing activities of a trading company. The system was called DealDriver to highlight that it helps the workers to "drive" their deals from the beginning to the end that is receiving payment. Our objective was to develop a system able to assist the office workers in all aspects of their everyday work, including registering all activities performed, and helping to plan the new ones, see illustration on Fig. 7-8. For this project, we devised a practical model for representing business processes that may be regarded as a specialization of our formal model (Bider, 1997a). During the project we created home-made development tools that included Hi-base - an object-oriented historical database, and Navi - an object oriented user-interface system (Bider, 1997b). Hi-base is able to store all previous states of the objects and show them on demand. Navi allows the end-user to easily navigate along the links connecting various objects to each other at present and in the past.

The advantages of our approach when applied to business application development are outlined in (Bider 1997a), (Bider and Khomyakov, 1997, 1998a). In addition, using active relations has a number of strong points even when considered in general.

First, the model represents a method of distributed programming that as long as possible separates the programming from implementation issues. The whole system is expressed in terms of local laws, communication and execution control being automatically provided by the environment. Programming is concentrated on objects’ behavior, freeing the developer from message passing, synchronization, assigning the processing units to action execution, etc.

Third, it is based on a formal semantics that allows formal reasoning about the properties of the system, e.g., whether it reaches the stable state if left alone.

The general nature of the CHAOS model makes it useful in business application design as well as in designing more technical systems. Currently, the authors are engaged in a practical activity of developing software for managing user-interactions with a computer system based on the CHAOS model.

The work of the first author was partly supported by Stockholm foundation "TeknikBroStiftelsen". The authors would also like to thank PSMT and ASE reviewers for their comments on initial drafts of this work.