Chapter 2. New Features of the XL Programming Language

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”.

Figure 2.1. Koch's construction step

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:

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:

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: