PJ's Computational Model

PJ's syntax and static semantics are defined through topological relations which have to hold between language elements. Language elements are either represented as closed contours (agents, rules, ports, primitive functions, constraints, constants, arrays, bags) or as (directed) lines (links, channels, call arrows). Since PJ's syntax is purely based on topological relationships its language elements can have any shape, size, color, etc. provided the required relationships are still holding. These graphical features are available for the programmer to use for application-specific purposes. PJ's dynamic (operational) semantics can be defined by graphical transformation rules. Figure 1 shows a simple PJ program for concatenating two lists.

A PJ computation can be considered as a network of concurrently executing agents asynchronously communicating over point-to-point directional channels. The behavior of an agent is defined by a collection of rules. Rules describe conditions (guards) under which their agent will read incoming messages from channels and may place new messages on channels for which it has tell rights. They also define how an agent replaces itself by a new subnetwork of messages, channels, and agents. Messages may be or may contain channels.

Preconditions of a rule are denoted by elements that are (transitively) connected to the ports of this rule and that are allocated outside of this rule. These elements are called askers

of this rule since they represent what is ``asked'' of the corresponding ports of the enclosing agent. A rule is indeterministically selected if the agent's arguments match the askers of several rules.

The body of a rule consists of all elements that are inside of this rule. They have to be (transitively) connected to either a port or asker of this rule. We call these elements tellers since they post (tell) new constraints on shared data structures. A so-called tell right is required for posting new constraints to non-local data structures. At most one tell right may exist for any data structure. Tell rights are first-class elements since they may be communicated over channels.

The execution of a PJ program (i.e. of the corresponding agents) can be specified with purely graphical transformation rules.

1. The elements connected to the ports of an agent (later on referred to as input data) must graphically match with the askers of an agent's rule. As result of a successful match every link of the askers is connected to the corresponding input data of the agent.

2. An agent replaces itself with the body of the selected rule. The askers, ports, and contour of the rule disappear. Only the input data of the agent, now connected to elements of the rule body, and all elements of the rule body remain.

3. A rule may assign a value to a channel if the rule has a channel as asker (this proves that it has the tell right to this channel). An assignment takes place by connecting the value and the head of the channel with a link. Eventually links will shrink to length zero joining the assigned or matched value and its recipient.

The selection of rules ---by matching their askers to input data of their agent--- takes place as long as runnable agents exist. A PJ program either terminates or suspends depending on the state of the agents.