**Table of Contents**

In this chapter, some of the new features of the XL programming
language will be shown. Most examples are to be understood as
excerpts of XL programmes, they are no stand-alone programmes.
Some of the examples are only valid within the
scope of a specific data model (Chapter 3, *Data Model Interface*),
namely the RGG data model which is contained in the RGG plugin
of the modelling software GroIMP, see
www.grogra.de.
In any case, in order to test the examples, it is easiest to use
GroIMP which provides an integrated compiler for the XL programming
language and a text editor with syntax highlighting. The GroIMP
distribution contains a set of demo projects which cover the examples
given here (PENDING).

This section gives examples for the
relational extensions. These are concerned with
relational data defined by the data model (Chapter 3, *Data Model Interface*):
*Rules*, enclosed in
*transformation blocks*, transform the data by
searching for their left hand side patterns
(*composite predicates*)
and replacing matches by their right hand side structures.
*Queries* are the building blocks for the left hand
side of rules, but can also be used outside of rules in order to query
the relational data source for occurrences of a pattern.
*Quasi-parallel assignments* perform modifications
of properties of the relational data source as if they were executed in
parallel. In conjunction with the application of rules in parallel, this
is an important feature for the modelling of processes running in parallel
as they occur, e.g., in nature.

The possibility of specifying *rules* is a main
feature of the XL programming language; it qualifies the XL programming
language as a language with support for rule-based programming.
This support will exemplified by means of the
famous snowflake curve (three Koch curves).
Its construction is as follows: Starting with
an equilateral triangle (consisting of three lines),
replace a line by four lines with certain angles inbetween,
see Figure 2.1, “Koch's construction step” and Figure 2.2, “Sequence of structures”.

In the sense of the rule-based paradigm, Koch's construction step is a rule. Roughly speaking, such a rule has a pattern on its left hand side and a replacement instruction on its right hand side. Thorough definitions and analyses of special kinds of rules have been made in the context of grammars; here, the reader is only referred to a special kind of grammars, namely the L-system formalism [ABOP].

The L-system formalism, combined with turtle geometry,
defines a symbolic notation that can be used, e.g., for the
specification of the snowflake example in a computer-readable form.
Namely, let the symbol `F`

represent a line segment
and `RU(a)`

a rotation of `a`

degrees, then the initial triangle can be specified as a sequence of
(parametrised) symbols:

F RU(120) F RU(120) F

This has to be interpreted in the context of turtle geometry, i.e., as a sequence of instructions to a drawing device which reads and performs instructions from left to right.

Now Koch's construction step can be specified as an L-system rule:

F ==> F RU(-60) F RU(120) F RU(-60) F

In other words, replace every occurence of the symbol `F`

in the instruction sequence by a subsequence consisting of some symbols
`F`

and `RU`

.

The XL programming language allows for an easy specification of rules of this and other kinds. In the context of GroIMP and the RGG data model as described above, the snowflake is programmed as follows:

[ Axiom ==> F(1) RU(120) F(1) RU(120) F(1); F(x) ==> F(x/3) RU(-60) F(x/3) RU(120) F(x/3) RU(-60) F(x/3); ]

This example makes use of the following features of the XL programming language:

Rules are indicated by arrows (

`==>`

in this case) and grouped within transformation blocks`[ ... ]`

. Transformation blocks are statements of the XL programming language and can be used like any other statement.The pattern of the left hand side may contain class names (

`Axiom`

) and*predicates*(`F(x)`

, a class name plus a parameter`x`

). The parameter`x`

stands for the length of the line segment, it will be set to the length of the currently found segment of class`F`

.The right hand side may contain a sequence of node expressions. In the example, all expressions are just constructor invocations, but without the keyword

`new`

. Thus, when the first rule is applied, new instances of the classes`F`

and`RU`

are created as if the expressions`new F(1)`

and`new RU(120)`

were evaluated.The structure actually is a graph of nodes.

`Axiom`

,`F`

,`RU`

are node classes, i.e., instances of these classes may be used as nodes in the graph. Initially, the graph contains a single node of class`Axiom`

, which corresponds to the start word of L-systems. Subsequently, the application of the two rules to the graph replaces nodes by sequences of nodes.The nodes of two textually consecutive node expressions are connected by an edge in the graph. Thus, the created nodes of classes

`F`

and`RU`

are connected linearly, forming a sequence similar to the sequence of symbols of L-systems. However, note that the structure could be a true graph of objects which may contain branchings and even cycles, whereas the L-system structure is just a linear sequence of plain symbols.The rule arrow

`==>`

indicates a rule with implicit*embedding*. In this simple example, this means that the first node of the right hand side receives the incoming edges of the matching node of the left hand side, and the last node of the right hand side receives the outgoing edges of the matching node. This effectively removes the matching node from the graph and inserts the sequence of new nodes at the location of the removed node.

The example so far is no complete programme of the XL programming language, it could be completed as follows:

import de.grogra.rgg.*; import de.grogra.lsystem.*; public class Koch extends RGG { public void derivation() [ Axiom ==> F(1) RU(120) F(1) RU(120) F(1); F(x) ==> F(x/3) RU(-60) F(x/3) RU(120) F(x/3) RU(-60) F(x/3); ] }

The XL programming language defines other kinds of rules. The rule
arrow `==>>`

indicates a rule without implicit
embedding, the rule arrow `::>`

indicates an
*execution rule* which executes the
statements of its right hand side for every match of the left hand side.

Rules are used to create and transform graphs. *Queries*
are used to query existing graphs for specific features. Their syntax is
exactly the same as for the left hand side of a rule, which can be seen
as a query for subgraphs that are to be replaced by the right hand side.
A query expression is a generator expression
(Section 2.2.4, “Generators, Aggregate Methods, and Filter Methods”),
it yields all possible matches in succession. As an example, consider the
query expression

(* F *)

The asterisked parentheses indicate a query expression, the contained
identifier `F`

specifies that the query yields
all nodes of class `F`

. Using the aggregate method
(Section 2.2.4, “Generators, Aggregate Methods, and Filter Methods”)
`count`

declared in
`de.grogra.xl.lang.Operators`

, the query could be
used to determine the number of instances of `F`

in the graph:

count((* F *))

With the help of the aggregate method `sum`

,
the total length of all instances of `F`

can be computed:

sum((* F *).length)

As a more complex example, consider the following:

sum((* d:Individual, ((d != c) && (distance(c, d) < 2)), d ( -(branch|successor)-> )* f:F, (isRelevant(f)) *).length);

Suppose a specific node `c`

is given, then
this expression
computes the length of all nodes `f`

of class
`F`

that are relevant according to some method
`isRelevant`

and that are descendants
(with respect to the edges `branch`

or
`successor`

) of a node
`d`

of class `Individual`

which lies within a distance of 2 from `c`

.

This example demonstrates some features of queries:

Query components can be labelled by local identifiers called

*term variables*, in this case`d`

and`f`

. During the process of matching, these variables are bound to the matches for the query components and can be used in the remaining part of the query.Queries may contain conditions enclosed in parentheses, in this case

`(d != c) && (distance(c, d) < 2)`

and`isRelevant(f)`

.Patterns for edges can be specified.

`-(branch|successor)->`

matches edges of type`branch`

or`successor`

which are traversed in forward direction.Transitive closures of binary relations, e.g. edge relations, can be used in queries. For example,

`(`

`edge`

`)*`

stands for all paths that can be built by traversingan arbitrary number of times.`edge`

For the XL programming language, rules are applied in parallel. To be more precise, they take effect as if they were executed in parallel. This holds at least for structural changes they apply to the graph. For example, the rule

a:A ==>> a A;

appends a new node of class `A`

to every existing node
`a`

of class `A`

.
Thus, the rule creates nodes which
match its own left hand side. However, because rules take effect as
if they were executed in parallel, the newly created nodes are not
visible for the matching process until the rule has been applied
completely to the whole graph, or, to be more precise, until
a *transformation boundary* has been passed.

Now consider the following example of an execution rule:

a:A b:A ::> b.x = a.x;

For every node `a`

of class `A`

having a successor `b`

of class
`A`

in the graph, the value of the variable
`a.x`

is forwarded to the variable `b.x`

.
This can be seen as the propagation of a value along a sequence
of nodes of class `A`

.

This rule contains an intricacy: It makes modifications to variables
`b.x`

which may happen to be the input variables
`a.x`

for later executions of the rule. For example,
suppose the graph consists of a sequence of nodes of class
`A`

, and suppose that the matches for the query
`a:A b:A`

are found from left to right. Then the
node `b`

of one match will be the node
`a`

of the following match. In this case, the value
of `x`

of the first node of the sequence propagates
through the whole sequence within just one application of the rule
to the graph. On the other hand, if the matches
are found from right to left, the value only propagates by one within
one application. This leads to indeterministic behaviour, because
the XL programming language does not specify conditions for the order
of matches.

This problem is solved by making use of
*quasi-parallel assignments*
(Section 15.2, “Quasi-Parallel Assignment Statements”). If the rule is changed to

a:A b:A ::> b[x] := a[x];

the assignments take effect as if they were executed in parallel, i.e., their modifications are not visible until a transformation boundary has been passed. In this case, it means that the propagation of values is by one within one application of the rule to the graph. This delayed effect of assignments is also useful for certain numerical computations where new values are computed based on the current ones. If the new values overwrote immediately the current ones, these computations would use partly the current values, partly the newly computed ones. Using quasi-parallel assignments, computations consistently use current values.

The example reveals the ingredients for quasi-parallel assignments:

Quasi-parallel assignment operators

`:= :+= :-= :*= :/= :&= :|= :^=`

Property variables (Section 7.1, “Property Variables”), indicated by their names enclosed in brackets.