EASY Meta-Programming with Rascal

To illustrate this process consider the workflow in Figure 1.11, “Workflow for analyzing mystery box”. First we have to extract the calls from the source code. Rascal is very good at this, but to simplify this example we assume that this call graph has already been extracted. Also keep in mind that a real call graph of a real application will contain thousands and thousands of calls. Drawing it in the way we do later on in Figure 1.12, “Graphical representation of the calls relation” makes no sense since we get a uniformly black picture due to all the call dependencies. After the extraction phase, we try to understand the extracted facts by writing queries to explore their properties. For instance, we may want to know how many calls there are, or how many procedures. We may also want to enrich these facts, for instance, by computing who calls who in more than one step. Finally, we produce a simple textual report giving answers to the questions we are interested in.

Figure 1.11. Workflow for analyzing mystery box

Now consider the call graph shown in Figure 1.12, “Graphical representation of the calls relation”. This section is intended to give you a first impression what can be done with Rascal. Please return to this example when you have digested the detailed description of Rascal in the section called “The Rascal Language” and the section called “Built-in Operators and Library Functions”.

Figure 1.12. Graphical representation of the calls relation

Rascal supports basic data types like integers and strings which are sufficient to formulate and answer the questions at hand. However, we can gain readability by introducing separately named types for the items we are describing. First, we introduce therefore a new type proc (an alias for strings) to denote procedures:

rascal> alias proc = str;
ok

Suppose that the following facts have been extracted from the source code and are represented by the relation Calls:

rascal> rel[proc, proc] Calls = 
   { <"a", "b">, <"b", "c">, <"b", "d">, <"d", "c">, 
     <"d","e">, <"f", "e">, <"f", "g">, <"g", "e">
   };
rel[proc,proc]: { <"a", "b">, <"b", "c">, <"b", "d">, 
                  <"d", "c">, <"d","e">, <"f", "e">, 
                  <"f", "g">, <"g", "e">}

This concludes the preparatory steps and now we move on to answer the questions.

A node d of a flow graph dominates a node n, if every path from the initial node of the flow graph to n goes through d [ASU86] (Section 10.4). Dominators play a role in the analysis of conditional statements and loops. The function dominators that computes the dominators for a given flow graph PRED and an entry node ROOT is defined as follows:

module demo::Dominators
import Set;
import Relation;
import Graph;

public rel[&T, set[&T]] dominators(rel[&T,&T] PRED, 
                                   &T ROOT)
{
  set[&T] VERTICES = carrier(PRED);
  return  { <V,  (VERTICES - {V, ROOT}) - 
                 reachX(PRED,{ROOT},{V})> 
            |  &T V <- VERTICES
          };
}

First, the auxiliary set VERTICES (all the statements) is computed. The relation DOMINATES consists of all pairs <S, {S1,...,Sn}> such that

First import the above module and consider the sample flow graph PRED:

rascal> import demo::Dominators;
ok

rascal> rel[int,int] PRED = {
<1,2>, <1,3>,
<2,3>,
<3,4>,
<4,3>,<4,5>, <4,6>,
<5,7>,
<6,7>,
<7,4>,<7,8>,
<8,9>,<8,10>,<8,3>,
<9,1>,
<10,7>
};

rel[int,int]: { <1,2>, <1,3>, ...

It is illustrated inFigure 1.14, “Flow graph”

Figure 1.14. Flow graph

The result of applying dominators to it is as follows:

rascal> dominators(PRED);
rel[int,int]: {<1, {2, 3, 4, 5, 6, 7, 8, 9, 10}>, 
<2, {}>, 
<3, {4, 5, 6, 7, 8, 9, 10}>, 
<4, {5, 6, 7, 8, 9, 10}>, 
<5, {}>, 
<6, {}>, 
<7, {8, 9, 10}>, 
<8, {9, 10}>, 
<9, {}>, 
<10, {}>}

The resulting dominator tree is shown in Figure 1.15, “Dominator tree”. The dominator tree has the initial node as root and each node d in the tree only dominates its descendants in the tree.

Figure 1.15. Dominator tree

We illustrate the calculation of reaching definitions using the example in Figure 1.16, “Flow graph for various dataflow problems” which was inspired by [ASU86] (Example 10.15).

Figure 1.16. Flow graph for various dataflow problems

We assume the following basic definitions to represent information about the program:

module demo::ReachingDefs

import Relation;
import Graph;
import IO;

public alias stat = int;
public alias var = str;
public alias def  = tuple[stat, var];
public alias use = tuple[stat,var];

public rel[stat,def] definition(rel[stat,var] DEFS){
  return {<S,<S,V>> | <stat S, var V> <- DEFS};
}

public rel[stat,def] use(rel[stat, var] USES){
  return {<S, <S, V>> | <stat S, var V> <- USES};
}

Let's use the following values to represent our example:

rascal> rel[stat,stat] PRED = { <1,2>, <2,3>, <3,4>, 
                                <4,5>, <5,6>, <5,7>, 
                                <6,7>, <7,4> };
rel[stat,stat]: { <1,2>, <2,3>, ...

rascal> rel[stat, var] DEFS = { <1, "i">, <2, "j">, 
                                <3, "a">, <4, "i">, 
                                <5, "j">, <6, "a">, 
                                <7, "i"> };
rel[stat,var]: { <1, "i">, <2, "j">, ...

rascal> rel[stat,var] USES = { <1, "m">, <2, "n">, 
                               <3, "u1">, <4, "i">, 
                               <5, "j">, <6, "u2">, 
                               <7, "u3"> };
rel[stat,var]: { <1, "m">, <2, "n">,...

For convenience, we have introduced above a notion def that describes that a certain statement defines some variable and we revamp the basic relations into a more convenient format using this new type and the auxiliary functions definition and use:

rascal> definition(DEFS);
rel[stat,def]: { <1, <1, "i">>, <2, <2, "j">>, 
                 <3, <3, "a">>, <4, <4, "i">>, 
                 <5, <5, "j">>, <6, <6, "a">>, 
                 <7, <7, "i">> }

rascal> use(USES);
rel[stat,def]: { <1, <1, "m">>, <2, <2, "n">>, 
                 <3, <3, "u1">>, <4, <4, "i">>, 
                 <5, <5, "j">>, <6, <6, "u2">>, 
                 <7, <7, "u3">> }

Now we are ready to define an important new relation KILL. KILL defines which variable definitions are undone (killed) at each statement and is defined by the following function kill:

// continuing module demo::ReachingDefs

public rel[stat,def] kill(rel[stat,var] DEFS) { 
  return {<S1, <S2, V>> | <stat S1, var V> <- DEFS, 
                          <stat S2, V> <- DEFS, 
                          S1 != S2};
}

In this definition, all variable definitions are compared with each other, and for each variable definition all other definitions of the same variable are placed in its kill set. In the example, KILL gets the value

rascal> kill(DEFS);
rel[stat,def]: 
{ <1, <4, "i">>, <1, <7, "i">>, <2, <5, "j">>, 
  <3, <6, "a">>, <4, <1, "i">>, <4, <7, "i">>, 
  <5, <2, "j">>, <6, <3, "a">>, <7, <1, "i">>, 
  <7, <4, "i">>
}

and, for instance, the definition of variable i in statement 1 kills the definitions of i in statements 4 and 7.

After these preparations, we are ready to formulate the reaching definitions problem in terms of two relations IN and OUT. IN captures all the variable definitions that are valid at the entry of each statement and OUT captures the definitions that are still valid after execution of each statement. Intuitively, for each statement S, IN[S] is equal to the union of the OUT of all the predecessors of S. OUT[S], on the other hand, is equal to the definitions generated by S to which we add IN[S] minus the definitions that are killed in S. Mathematically, the following set of equations captures this idea for each statement:

IN[S] = UNION_{P in predecessors of S} OUT[P]

OUT[S] = DEF[S] + (IN[S] - KILL[S])

This idea can be expressed in Rascal quite literally:

public rel[stat, def] reachingDefinitions(
                            rel[stat,var] DEFS, 
                            rel[stat,stat] PRED){
  set[stat] STATEMENT = carrier(PRED);
  rel[stat,def] DEF  = definition(DEFS);
  rel[stat,def] KILL = kill(DEFS);

  // The set of mutually recursive dataflow equations 
  // that has to be solved:
  
  rel[stat,def] IN = {};
  rel[stat,def] OUT = DEF;

  solve (IN, OUT) {
    IN  = {<S, D> | int S <- STATEMENT, 
                    stat P <- predecessors(PRED,S), 
                    def D <- OUT[P]};
    OUT = {<S, D> | int S <- STATEMENT, 
                    def D <- DEF[S] + (IN[S] - KILL[S])};
  };
  return IN;
}

First, the relations IN and OUT are declared and initialized. Next follows a solve statement that uses IN and OUT as variables and contains two equations that resemble the mathematical equations given above. Note the use of the library function predecessors to obtain the predecessors of a statement for a given control flow graph.

Figure 1.17. Reaching definitions for flow graph in Figure 1.16, “Flow graph for various dataflow problems”

For our running example (Figure 1.17, “Reaching definitions for flow graph in Figure 1.16, “Flow graph for various dataflow problems””) the results are as follows (see Figure 1.17, “Reaching definitions for flow graph in Figure 1.16, “Flow graph for various dataflow problems””). Relation IN has as value:

{ <2, <1, "i">>, <3, <2, "j">>, <3, <1, "i">>, 
  <4, <3, "a">>, <4, <2, "j">>, <4, <1, "i">>, 
  <4, <7, "i">>, <4, <5, "j">>, <4, <6, "a">>, 
  <5, <4, "i">>, <5, <3, "a">>, <5, <2, "j">>, 
  <5, <5, "j">>, <5, <6, "a">>, <6, <5, "j">>, 
  <6, <4, "i">>, <6, <3, "a">>, <6, <6, "a">>, 
  <7, <5, "j">>, <7, <4, "i">>, <7, <3, "a">>, 
  <7, <6, "a">>
}

If we consider statement 3, then the definitions of variables i and j from the preceding two statements are still valid. A more interesting case are the definitions that can reach statement 4:

Relation OUT has as value:

{ <1, <1, "i">>, <2, <2, "j">>, <2, <1, "i">>, 
  <3, <3, "a">>, <3, <2, "j">>, <3, <1, "i">>, 
  <4, <4, "i">>, <4, <3, "a">>, <4, <2, "j">>, 
  <4, <5, "j">>, <4, <6, "a">>, <5, <5, "j">>, 
  <5, <4, "i">>, <5, <3, "a">>, <5, <6, "a">>, 
  <6, <6, "a">>, <6, <5, "j">>, <6, <4, "i">>, 
  <7, <7, "i">>, <7, <5, "j">>, <7, <3, "a">>, 
  <7, <6, "a">>
}

Observe, again for statement 4, that all definitions of variable i are missing in OUT[4] since they are killed by the definition of i in statement 4 itself. Definitions for a and j are, however, contained in OUT[4]. The result of reaching definitions computation is illustrated in Figure 1.17, “Reaching definitions for flow graph in Figure 1.16, “Flow graph for various dataflow problems””. We will use the function reachingDefinitions later on in the section called “Program Slicing” when defining program slicing.

The live variables of a statement are those variables whose value will be used by the current statement or some successor of it. The mathematical formulation of this problem is as follows:

IN[S] =USE[S] + (OUT[S] - DEF[S])

OUT[S] = UNION_{S' in successors of S} IN[S']

The first equation says that a variable is live coming into a statement if either it is used before redefinition in that statement or it is live coming out of the statement and is not redefined in it. The second equation says that a variable is live coming out of a statement if and only if it is live coming into one of its successors.

This can be expressed in Rascal as follows:

public rel[stat,def] liveVariables(rel[stat, var] DEFS, 
                                   rel[stat, var] USES, 
                                   rel[stat,stat] PRED){
  set[stat] STATEMENT = carrier(PRED);
  rel[stat,def] DEF  = definition(DEFS);
  rel[stat,def] USE = use(USES);
 
  rel[stat,def] LIN = {};
  rel[stat,def] LOUT = DEF;

  solve(LIN, LOUT) {
    LIN  = { <S, D> | stat S <- STATEMENT,  
                      def D <- USE[S] + 
                               (LOUT[S] - (DEF[S]))};
    LOUT = { <S, D> | stat S <- STATEMENT,  
                      stat Succ <- successors(PRED,S), 
                      def D <- LIN[Succ] };
  }
  return LIN;
}

The results of live variable analysis for our running example are illustrated in Figure 1.18, “Live variables for flow graph in Figure 1.16, “Flow graph for various dataflow problems””.

Figure 1.18. Live variables for flow graph in Figure 1.16, “Flow graph for various dataflow problems”

Rascal is based on static typing, this means that as many errors and inconsistencies as possible are spotted before the program is executed. The types (to be explained in more detail later) are ordered in a so-called type lattice shown in Figure 1.19, “The Rascal Type Lattice”. The arrows describe a subtype-of relation between types. The type void is the smallest type and is included in all other types and the type value is the largest type that includes all other types. We also see that rel is a subtype of set and that each ADT is a subtype of node. A special role is played by the datatype Tree that is the generic type of syntax trees. Syntax trees for specific languages are all subtypes of Tree. As a result, syntax trees can be addressed at two levels: in a generic fashion as Tree and in a specific fashion as a more precisely typed syntax tree. Finally, each alias is structurally equivalent to one or more specific other types.

Figure 1.19. The Rascal Type Lattice

Void stands for nothing and is represented by the type void. It is a type without any values.

Value stands for all possible Rascal values and is represented by the type value. This type is a container for all other types and does not have any values itself.

The Booleans are represented by the type bool which has two values: true and false.

The integer values are represented by the type int and are written as usual, e.g., 0, 1, or 123. They can be arbitrarily large.

The real values are represented by the type real and are written as usual, e.g., 1.5, or 3.14e-123. They can have arbitrary size and precision.

The string values are represented by the type str and consist of character sequences surrounded by double quotes. e.g., "a" or "a\nlong\tstring".

String literals support so-called string interpolation: inside string constants text between angle brackets (< and >) is first executed and then replaced by its string value. Let's try this:

rascal> N = 13;
int : 13

rascal> "The value of N is <N>";
str: "The value of N is 13"

rascal> "The value of N*N is <N*N>";
str: "The value of N*N is 169"

rascal> "The value is <(N < 10) ? 10 : N*N>";
str: "The value of 169"

As you can see the string value of variables and expressions is interpolated in the result as expected. As we will see later on, various statements (if, for, while, do) also return a value and can be used in this way. In the interpolation variant of these statements the block or blocks that are part of the statement become arbitrary text (that may itself contain interpolations). Their forms are:

<if(Exp){> ... Text ... <}>
<if(Exp){> ... Text ... <} else {>  ... Text ... <}>
<for(Exp){>... Text ... <}>
<while(Exp){> ... Text ... <}>
<do {>... Text ... <} while (Exp)>

Here Text is arbitrary text that may itself contain again contain interpolations.

Let's apply this to some examples:

rascal> "N is <if(N < 10){> small <} else {> large <}>";
str: "N is large "

rascal> "N is <if(N < 10){> small <} else {> large (<N>)<}>";
str: "N is  large (13)"

rascal> "before <for(x<-[1..5]){>a <x> b <}>after";
str: "before a 1 b a 2 b a 3 b a 4 b a 5 b after"

String interpolation enables very flexible template-based text generation.

Location values are represented by the type loc and serve as text coordinates in a specific local or remote source file. It is very handy to associate a source code location which extracted facts.

Source locations have the following syntax:

|Uri|(O,L,<BL,BC>,<EL,EC>)

where:

URIs are explained in http://en.wikipedia.org/wiki/Uniform_Resource_Identifier. From their original definition in RFC3986 we cite the following useful overview of an URI:

         foo://example.com:8042/over/there?name=ferret#nose
         \_/   \______________/\_________/ \_________/ \__/
          |           |            |            |        |
       scheme     authority       path        query   fragment
          |   _____________________|__
         / \ /                        \
         urn:example:animal:ferret:nose

Locations should always be generated automatically but for the curious here is an example:

|file:///home/paulk/pico.trm|(0,1,<2,3>,<4,5>)

The elements of a location value can be accessed and modified using the standard mechanism of field selection and field assignment. The corresponding field names are:

A list is an ordered sequence of values and has the following properties:

Lists are represented by the type list[T], where T is an arbitrary type. Examples are list[int], list[tuple[int,int]] and list[list[str]]. Lists are denoted by a list of elements, separated by comma's and enclosed in bracket as in [E₁, E₂, ..., En], where the En (1 <= i<= n) are expressions that yield the desired element type. For example,

When variables of type list occur inside a list, their elements are automatically spliced into the surrounding list. This can be prevented by surrounding them with extra [ and ] brackets. Note that this approach is atypical: in Rascal splicing is implicit while in other languages it has to be indicated explicitly by the programmer.

rascal> L = [1, 2, 3];
list[int]: [1,2,3]

rascal> [10, L, 20];
list[int]: [10, 1, 2, 3, 20]

rascal> [10, [L], 20];
list[value]: [10, [1,2,3], 20]

For lists of integers, a special shorthand exists to describe ranges of integers:

A set is an unordered sequence of values and has the following properties:

Sets are represented by the type set[T], where T is an arbitrary type. Examples are set[int], set[tuple[int,int]] and set[set[str]]. Sets are denoted by a list of elements, separated by comma's and enclosed in braces as in {E₁, E₂, ..., En}, where the En (1 <= i<= n) are expressions that yield the desired element type. For example,

In a similar fashion as with lists, set variables are automatically spliced into a surrounding set. This can be prevented by surrounding them with extra { and } brackets.

rascal> S = {1, 2, 3};
set[int]: {1,2,3]}

rascal> {10, S, 20};
set[int]: {10, 1, 2, 3, 20]}

rascal> {10, {L}, 20};
set[value]: {10, {1,2,3}, 20}

A map is a set of key : value pairs and has the following properties:

Maps are represented by the type map[T1, T2], where T1 and T2 are arbitrary types. Examples are map[int,int], and map[str,int]. Maps are denoted by a list of pairs, separated by comma's and enclosed in parentheses as in (K₁: V₁, ..., K_n: V_n), where the Kn (1 <= i<= n) are expressions that yield the keys of the map and Vn (1 <= i<= n) are expressions that yield the values for each key. Maps resemble functions rather than relations in the sense that only a single value can be associated with each key. For example,

A tuple is a sequence of elements with the following properties:

Tuples are represented by the type tuple[T₁L1, T₂L2, ..., Tn L_n ], where T₁, T₂, ..., Tn are arbitrary types and L1, L₂, ..., L_n are optional labels. An example of a tuple type is tuple[str name, int freq]. Examples are:

The elements of a tuple can also be labelled and can then be accessed using the field selection operator (.). Fields can be changed (yielding a new tuple value) by a combination of field selection and assignment. For instance,

rascal> tuple[str first, str last, int age] P = <"Jo","Jones",35>;
tuple[str first, str last, int age] P = <"Jo", "Jones", 35>;

rascal> P.first;
str: "Jo"

rascal> P.first = "Bo";
tuple[str first,str last,int age]: <"Bo","Jones",35>

A relation is a set of elements with the following property:

Relations are thus nothing more than sets of tuples, but since they are used so often we provide a shorthand notation for them. Relations are represented by the type rel[T₁L1, T₂L2, ..., Tn L_n ], where T₁, T₂, ..., Tn are arbitrary types and L1, L₂, ..., L_n are optional labels. It is a shorthand for set[tuple[T₁L1 , T₂L2, ..., Tn L_n ]]. Examples are rel[int,str] and rel[int,set[str]]. An n-ary relations with m tuples is denoted by {<E₁₁, E₁₂, ..., E1n>,<E₂₁, E₂₂, ..., E2n>, ...,<E_m1, E_m2, ..., Emn>}, where the Eij are expressions that yield the desired element type. For example, {<1, "a">, <2, "b">, <3,"c">} is of type rel[int, str]. Examples are:

Everything can be expressed using the elementary types and values that are provided by Rascal. However, for the purpose of documentation and readability it is sometimes better to use a descriptive name as type indication, rather than an elementary type. The alias declaration

alias Name  = Type;

states that Name can be used everywhere instead of the already defined type Type. Both types are thus structurally equivalent. For instance,

alias ModuleId = str;
alias Frequency = int;

introduces two new type names ModuleId and Frequency, both an alias for the type str. The use of type aliases is a good way to document your intentions. Another example is an alias definition for a graph containing integer nodes:

alias IntGraph = rel[int,int];

Note that Rascal Standard Library provides a graph data type that is defined as follows:

alias Graph[&T] = rel[&T, &T];

In other words the standard graph datatype can be parameterized with any element type. See the section called “Graph” for details.

In ordinary programming languages record types or classes exist to introduce a new type name for a collection of related, named, values and to provide access to the elements of such a collection through their name. In Rascal, data declarations provide this facility. The type declaration

data Name = Alt1 | Alt1 | ...

introduces a new datatype Name and its alternative forms Alt₁, Alt₂, ... . The description of an alternative is identical in form to the type declaration of a function. For instance,

data Bool = 
     tt() | ff() | conj(Bool L, Bool R)  | disj(Bool L, Bool R);  

defines the datatype Bool that contains various constants (tt() and ff() and constructor functions conj and disj.

In addition to the types that we have already discussed, a type may also be a type parameter of the form

&Name

A type parameter may occur at every syntactic position where a type is required and turns an ordinary type into a parameterized type. Parameterized types are used to define polymorphic functions and data types, i.e., functions and data types that are applicable for more than one type. Type parameters are bound to an actual type when the function or data type is applied and further uses of the type parameter are consistently replaced by the actual type.

The following syntactic positions are binding occurrences for type parameters:

All other occurrences of type parameters are using occurrences. The following rules apply:

As a final refinement, constraints can be imposed on the actual types to which a type parameter may be bound. This is expressed by a subtype constraint of the form:

&Name <: Type

which expresses that actual types bound to Name should be a subtype of Type. More on subtyping in the section called “Typing”.

Let's consider a small example of the use of function parameters in a function declaration, we refer to the section called “Function Declaration” for a full description of function declarations. The following function swap returns a tuple in which its arguments are swapped and can be applied to arbitrary values in a type safe manner:

rascal> tuple[&B, &A] swap(&A a, &B b) { return <b, a>; }
ok

rascal> swap(1,2);
tuple[int,int]: <2,1>

rascal> swap("abc", 3);
tuple[int,str]: <3, "abc">

Observe that the type parameters that are used in the return type should be defined in the declarations of the formal parameter of the function.

An alias definition may also be parameterized. So we can generalize graphs as follows:

rascal> alias Graph[&Node] = rel[&Node, &Node];
ok

rascal> Graph[int] GI = {<1,2>, <3,4>, <4,1>};
Graph[int] :  {<1,2>, <3,4>, <4,1>}

rascal> Graph[str] GS = {<"a", "b">, <"c","d">, <"d", "a">};
Graph[str] : {<"a", "b">, <"c","d">, <"d", "a">}

The type parameters that are used in the type in the right part of the alias declaration should be defined in the left part of the alias definition.

Usually one declares functions that have arguments that have a type that corresponds to one of the many forms of values in Rascal. In exceptional circumstances it is desirable to define functions that have a type itself as argument. The prototypical example is a parse function: how to write a type safe parse function that expresses the type of the result we expect? Suppose we want to parse a language that has the non-terminals EXP, STAT and PROGRAM. A first, naive, solution introduces a parse function for each non-terminal:

EXP parseEXP(str s){ ... }
STAT parsePROGRAM(str s) { ... }
PROGRAM parsePROGRAM(str s) { ... }

Unfortunately this solution does not scale well to large languages with many non-terminals and it breaks down completely when we do not know the non-terminals before hand.

To solve this problem in a more general manner something special has to be done. Types are not values and without an additional mechanism they cannot be passed as arguments to functions. To achieve this effect we introduce reified types that are denoted by the type type. Now we can write:

&T parse(type[&T] start, str s) { ... }

and use the parse by giving it a type as argument:

parse(#EXP, "1+3");

In other words, reified types make it possible to use vaues as types.

A Rascal program consists of a number of modules that may import each other.

A module declaration has the following form:

module Name
Imports;
Declaration1;
...
Declarationn;

and consists of a Name and zero or more imports of other modules, seethe section called “Import”, and declarations for

The module name Name will be used when the current module is imported in another module. A module is usually a qualified name of the form:

Name1::Name2:: ... ::Namen

which corresponds to a path relative to the root of the current workspace.

The constituents of a module are also shown in Figure 1.20, “Constituents of a Module”. The less familiar features are shown in a separate color.

The entities that are visible inside a module are

The only entities that are visible outside the module, are the public entities declared in the module itself. If different imported modules declare the same visible name, it can be disambiguated by explicitly qualifying it with its module name:

Module::Name

Figure 1.20. Constituents of a Module

An import has the form:

import QualifiedName;

and has as effect that all public entities declared in module QualifiedName are made available to the importing module. Circular imports are allowed. Two kinds of imported modules are supported:

In the former case, all publicly visible entities in the imported module become available in the importing module. In the latter case, all non-terminals (symbols in SDF parlance) that are declared in L become available as types in the importing module. In addition, concrete syntax patterns and parse functions can be used for any non-terminal that is defined in L.

Import is non-transitive, i.e., the visible entities from an imported module are not re-exported by the importing module.

A function declaration has the form

Type Name(Type1 Var1, ..., Typen Varn) Statement

Here Type is the result type of the function and this should be equal to the type of the result of Statement (using the return statement, see the section called “Return Statement”). Each Typei Vari represents a typed formal parameter of the function. The formal parameters may be used in Statement and get their value when function Name is invoked. Example:

rascal> rel[int, int] invert(rel[int,int] R){
            return {<Y, X> | <int X, int Y> <- R }
        }
ok

rascal> invert({<1,10>, <2,20>});
rel[int,int] : {<10,1>, <20,2>}

Variable argument lists.  A function may have a variable list of arguments, this has the form:

Type Name(ordinary parameters, Type Var...) Statement

The last parameter of a function may be followed by ... and this has as effect that all remaining actual parameters that occur in a call to this function are collected as list value of the last formal parameter. Inside the function body, the type of this parameter will therefore be list[Type].

Exceptions.  The exceptions that can be thrown by a function can be (optionally) declared as follows:

Type Name(Type1 Var1, ..., Typen Varn) 
     throws Exception1, Exception2, ... 

See the section called “Try Catch Statement” and the section called “Throw Statement” for details.

Parameterized types in function declaration.  The types that occur in function declarations may also contain type variables that are written as &TypeVar. In this way functions can be defined for arbitrary types. In the following example, we declare an inversion function that is applicable to any binary relation. :

rascal> rel[&T2, &T1] invert2(rel[&T1,&T2] R){  
            return {<Y, X> | <&T1 X, &T2 Y> <- R };
        }
ok

rascal> invert2({<1,10>, <2,20>});
rel[int,int] : {<10,1>, <20,2>}

rascal> invert2({<"mon", 1>, <"tue", 2>});
rel[int,str] : {<1, "mon">, <2, "tue">}

Here we declare a function that can be used to swap the elements of pairs of arbitrary types:

rascal> tuple[&T2, &T1] swap(&T1 A, &T2 B) { return <B, A>;;}
ok

rascal> swap(<1, 2>);
tuple[int,int] : <2,1>

rascal> swap(<"wed", 3>);
tuple[int,str] : <3, "wed">

A variable declaration has the form

Type Var = Exp

where Type is a type, Var is a variable name, and Exp is an expression that should have type Type. The effect is that the value of expression Exp is assigned to Var and can be used later on as Var's value. The following rules apply:

As a convenience, also declarations without an initialization expression are permitted inside functions (but not at the module level) and have the form

Type Var 

and only introduce the variable Var. When a variable is declared, it has as scope the nearest enclosing block, see the section called “Block Statement”.

Rascal provides local type inference, which allows the implicit declaration of variables that are used locally in functions. The following rules apply:

Examples.

rascal> int max = 100;
int: 100

rascal> min = 0;
int : 0

rascal> day = {<"mon", 1>, <"tue", 2>, <"wed",3>, 
              <"thu", 4>, <"fri", 5>, <"sat",6>, <"sun",7>}
rel[str,int]: {<"mon", 1>, <"tue", 2>, <"wed",3>, 
               <"thu", 4>, <"fri", 5>, <"sat",6>, <"sun",7>}

Tags are intended to add meta data to a Rascal program and allow to influence the execution of the Rascal program, for instance, by adding memoization hints or database mappings for relations.

All declarations in a Rascal program may contain (in fixed positions depending on the declaration type) one or more declaration tags (tag). A tag is defined by declaring its name, the declaration type to which it can be attached, and the name and type of the annotation. The declaration type all, makes the declaration tag applicable for all possible declaration types. All declaration tags have the generic format @Name{ ... }, with arbitrary text between the brackets that is further constrained by the declared type. Here is an example of a license tag:

tag str license on module;

This will allow to write things like:

@license{This module is distributed under the BSD license}
module Booleans
...

Other examples of declaration tags are:

tag str todo on all             %% todo note for all types
tag void deprecated on function %% marks a deprecated function
tag int memo on function        %% bounded memoization of 
                                %% function calls
tag str doc on all              %% documentation string

Here is an example of a documentation string as used in the Rascal standard library:

@doc{Maximum of a set: max}
public &T max(set[&T] R)
{
  &T result = arb(R);
  for(&T E : R){
    result = max(result, E);
  }
  return result;
}

Although user-defined tags are not yet available, the following tags are currently provided:

tag str doc on function         %% documentation string
tag str javaClass on function   %% implementation class of library 
                                %% function
tag void reflective on function %% library function with access to 
                                %% interpreter state
tag str javaImports on function %% imports needed by a Rascal 
                                %% function with Java body
tag str deprecated on function  %% deprecated function

An annotation may be associated with any node value. Annotations are intended to attach application data to values, like adding position information or control flow information to source code or adding visualization information to a relation. An annotation has a name and the type of its value is explicitly declared. Any value of any named type can be annotated and the type of these annotations can be declared precisely.

For instance, we can add to certain syntactic constructs of programs (e.g., EXPRESSION) an annotation with name posinfo that contains location information:

anno loc EXPRESSION @ posinfo;

or location information could be added for all syntax trees:

anno loc Tree @ posinfo;

We can add to the graph datatype introduced earlier, the annotation with name LayoutStrategy that defines which graph layout algorithm to apply to a particular graph, e.g.,

data LayoutStrategy = dot() | tree() | force() | 
                      hierarchy() | fisheye();

anno LayoutStrategy Graph @ strategy;

The following constructs are provided for handling annotations:

Functions are the workhorses of Rascal. They can have any value as parameter or result and are explicitly called by the user. Also, functions are declared inside modules and their visibility can be controlled.

Rewrite rules, on the other hand, operate only on nodes and abstract datatypes (ADTs), they are implicitly applied when a new value (we refer to this as the subject value) is constructed. The scope of rewrite rules is the whole Rascal program. Rewrite rules are applied to the subject value in a bottom-up fashion. As a result, the subject value may be changed. This process is repeated as long as there are rules that can be applied to the current subject value. Technically, this is called innermost rewriting. When done, the result of rewriting the original subject value is used instead of that original value.

Rules have the general form:

rule Name PatternWithAction

where Name is the name of the rule and PatternWithAction is the body of the rule consisting of a pattern and an associated action, see the section called “PatternWithAction” for a detailed description.

Here is an example for a user-defined type Booleans:

rascal>
data Bool = btrue;
data Bool = bfalse;
data Bool = band(Bool left, Bool right);
data Bool = bor(Bool left, Bool right);  

rule a1 band(btrue, Bool B)    => B;
rule a2 band(bfalse, Bool B)   => bfalse;
ok

rascal> band(band(btrue,btrue),band(btrue, bfalse));
Bool: bfalse

During execution of rules the following applies:

You may wonder why we write btrue and bfalse instead of true and false. The explanation is that the latter are reserved words that cannot be used as ordinary names. Reserved words can, however, be used as ordinary names by escaping them; this is done by prefixing them with a backslash (\), e.g. \true and \false.

The non-Boolean operators are summarized in Table 1.2, “Non-Boolean Operators”. All operators are highly overloaded and we refer to the section called “Built-in Operators and Library Functions” for a description of their meaning for each specific type. The following rules apply:

Most of these operators are described in detail in the section called “Built-in Operators and Library Functions” for specific types. Here we describe the remaining generic operators.

Field Selection and Field Assignment.  Field selection and field assignment apply to all values that have named components like tuples and relations with named elements, data types, and locations. Field selection returns the value of the named component and Field assignment returns a new value in which the named component has been replaced by a new value. We illustrate this for tuples:

rascal> tuple[int key, str val] T = <1, "abc">;
tuple[int, str] : <1, "abc">

rascal> T.val;
str : "abc"

rascal> T[val = "def"];
tuple[int, str] : <1, "def">

rascal> T;
tuple[int, str] : <1, "abc">

Observe that field assignment creates a new value with an updated field. The old value remains unchanged as can be seen from the unchanged value of T in the above example. Inthe section called “Assignment Statement” we explain how to change a field of variable value.

Field projection.  Field projection applies to tuples and relations and may contain element names or integer constants that refer to elements in the order in which they occur in the original value (counting from 0). A field projection returns a new value that consists of the selected elements. Suppose we have a relation with traffic information that records the name of the day, the day number, and the length of the traffic jams at that day.

rascal> rel[str day, int daynum, int length] Traffic = 
        {<"mon", 1, 100>, <"tue", 2, 150>, <"wed", 3, 125>, 
         <"thur", 4, 110>, <"fri", 5, 90>};
rel[str, int, int]: {<"thur",4,110>,<"tue",2,150>,<"wed",3,125>,
         <"fri",5,90>,<"mon",1,100>}

rascal> Traffic<length,daynum>;
rel[int, int]: {<110,4>,<150,2>,<90,5>,<100,1>,<125,3>}

rascal> Traffic<2,day>;
rel[int, str]: {<125,"wed">,<110,"thur">,<100,"mon">,<90,"fri">,
                <150,"tue">}

Field projection thus selects parts from a larger value that has a fixed number of parts. The selection is based on position and not on value and can be used to completely reorder or remove the parts of a larger value.

Subscription.  Subscription selects values with a given computed index from a larger value that has a variable number of elements. For lists and tuples a single integer expression is allowed as index and the returned value is the element with that index (counting from 0). For maps, the index type should correspond to the key type of the map and the value associated with the index is returned. For relations, more than one index expression is allowed and as value a new, reduced, relation is returned with all elements that contained the index values at the corresponding tuples positions (but these values are removed, hence a reduced relation). Some examples illustrate this:

rascal> L = [10, 20, 30];
list[int] : [10,20,30]

rascal> L[1];
int : 20

rascal> T = <"mon", 1>;
tuple[str,int] : <"mon", 1>;

rascal> T[0];
str : "mon"

rascal> colors = ("hearts":"red", "clover":"black", 
                  "trumps":"black", "clubs":"red");
map[str,str] : ("hearts":"red", "clover":"black", 
                "trumps":"black", "clubs":"red")

rascal> colors["trumps"];
str: "black"

rascal> colors[0];
Static Error: -:1,0: Expected str, but got int

rascal> colors["square"];
Uncaught Rascal Exception: -:1,0: NoSuchKey("square")

rascal> rel[str country, int year, int amount] GDP =
           {<"US", 2008, 14264600>, <"EU", 2008, 18394115>,
            <"Japan", 2008, 4923761>, <"US", 2007, 13811200>, 
            <"EU", 2007, 13811200>, <"Japan", 2007, 4376705>};
rel[str,int,int] : 
           {<"US", 2008, 14264600>, <"EU", 2008, 18394115>, 
            <"Japan", 2008, 4923761>, <"US", 2007, 13811200>, 
            <"EU", 2007, 13811200>, <"Japan", 2007, 4376705>}

rascal> GDP["Japan"];
rel[int,int] : {<2008, 4923761>, <2007, 4376705>}

rascal> GDP["Japan", 2008];
set[int] : {4923761}

Other Non-Boolean Operator Expressions.  The other non-Boolean operator expressions are explained in more detail for each datatype, see the section called “Built-in Operators and Library Functions”.

The Boolean operators are summarized in Table 1.3, “Boolean Operators”. All operators are highly overloaded and we refer to the section called “Built-in Operators and Library Functions” for a description of their meaning for each specific type. The Boolean operators have short-circuit semantics. Most operator are self-explanatory except the match (:=) and no match (!:=) operators that are also the main reason to treat Boolean operator expressions separately. Although we describe patterns in full detail in the section called “Patterns”, a preview is useful here. A pattern can

Match Operator.  The match operator

Pat := Exp

is evaluated as follows:

This looks and is nice and dandy, so why all this fuss about Boolean operators? The catch is that--as we will see in detail in the section called “Patterns”--a match need not be unique. This means that there may be more than one way of matching the subject value resulting in different variable bindings. A quick example. Consider the following match of a list

[1, list[int] L, 2, list[int] M] := [1,2,3,2,4]

By definition list[int] L and list[int] M match list elements that are part of the enclosing list in which they occur. If they should match a nested list each should be enclosed in list brackets.

There are two solutions for the above match:

Depending on the context, only the first solution of a match expression is used, respectively all solutions are used. If a match expression occurs in a larger Boolean expression, a subsequent subexpression may yield false and -- depending on the actual operator -- evaluation backtracks to a previously evaluated match operator to try a next solution. Let's illustrate this by extending the above example:

[1, list[int] L, 2, list[int] M] := [1,2,3,2,4] && size(L) > 0

where we are looking for a solution in which L has a non-empty list as value. Evaluation proceeds as follows:

This behaviour is applicable in the context of all Rascal constructs where a pattern match determines the flow of control of the program, in particular:

Patterns come in three flavours:

/\brascal\b/i

/^.*?<word:\w+><rest:.*$>/m

/<x:[a-z]+>---<x>/

/<x><n>/

/abc3/

/a{<n>}/

/<x:a{<n>}>/

Patterns can be used in various contexts, but a common context is a PatternWithAction, which in its turn, may be used in a switch statement, visit expression or rewrite rule.

A PatternWithAction can have one of the following two forms:

In switch statements, only the form Pat : Statement is allowed. When the subject matches Pat, the Statement is executed and the execution of the switch statement is complete. However, when a fail statement is executed in Statement all its side effects are undone and further alternatives of Pat are tried. If no alternatives remain, PatternWithAction as a whole fails and subsequent cases of the switch statement are tried. Also see the section called “Switch Statement”.

In visit expressions, the form Pat => Exp describes subtree replacement: the current subtree of the subject of the visit expression is replaced by the value of Exp. The form Pat : Statement is as described for switch statements, with the addition that execution of an insert statement will replace the current subtree. After both succes or failure of the PatternWithAction, the traversal of the subject continues. Also see the section called “Visit Expression”.

In rewrite rules, both forms are allowed. The form Pat => Exp behaves as described for visit expressions. The form Pat : Statement is as described for switch statement. If the PatternWithAction fails another rule will be tried. Also see the section called “Rewrite Rule Declaration”.

Comprehensions provide a concise notation to conditionally generate new values. We will use the familiar notation for list comprehension

[Exp1, ..., Expn | Gen1, ..., Genm]

to denote the construction of a list consisting of the successive values of the contributing expressions Exp1, ..., Expn. The value of the resulting list is determined by Exp1, ..., Expn and the generators Gen₁ ,..., Genm. Exp₁, ..., Expn are computed for all possible combinations of values produced by the generators. Each generator may introduce new variables that can be used in subsequent generators as well as in the expressions. A generator can use the variables introduced by preceding generators. Generators may enumerate all the values in a subject value.

Generators may also perform an arbitrary test. When the test fails, execution continues with the preceding generator (if any).

In addition to list comprehensions, Rascal also supports set comprehension

{Exp1, ..., Expn | Gen1, ..., Genm}

that also serve as relation comprehension in the case that Exp is of a tuple type.

Finally, map comprehensions are written as:

(Exp1 : Exp2 | Gen1, ..., Genm)

Since the entries in a map require both a key and a value for each entry, always two expressions are needed in this case.

Pat <- Exp

rascal> {X | int X <- {1, 2, 3, 4, 5}, X >= 3};
set[int] : {3,4,5}

rascal> {<X, Y> | int X <- {1, 2, 3}, int Y : {2, 3, 4}, X >= Y};
rel[int,int] : {<2, 2>, <3, 2>, <3, 3>}

rascal> {<Y, X> | <int X, int Y> <- {<1,10>, <2,20>}};
rel[int,int] : {<10,1>, <20,2>}

rascal> {X, X * X | int X <- {1, 2, 3, 4, 5}, X >= 3};
set[int] : {3,4,5,9,16,25}

Visiting the nodes in a tree is a very common task in the EASY domain. In many cases (but certainly not all) the tree is a syntax tree of some source code file and the nodes correspond to expressions or statements. Computing metrics or refactoring are examples of tasks that require a tree visit. In object-oriented programming, the visitor pattern is in common use for this. There are three frequently occurring scenarios:

The visit expression in Rascal can accommodate all these (and more) use cases and has the form:

Strategy visit ( Exp ) {
case PatternWithAction1;
case PatternWithAction2;
...
default: ...
}

Given a subject term (the current value of Exp) and a list of cases (consisting of PatternWithActions, see the section called “PatternWithAction”) it traverses the term. Depending on the precise actions it may perform replacement (mimicking a transformer), update local variables (mimicking an accumulator) or a combination of these two (accumulating transformer). If any of the actions contains an insert statement, the value of the visit expression is a new value that is obtained by successive insertions in the subject term by executing one or more cases. Otherwise, the original value of the subject term is returned.

The visit expression is optionally preceded by one of the following strategy indications that determine the traversal order of the subject:

The execution of the cases has the following effect:

The precise behaviour of the visit expression depends on the type of the subject:

one ( Exp1 , Exp2 , ... , Expn )

The one expression yields true when one combination of values of Exp_i is true.

all ( Exp1 , Exp2 , ... , Expn ) 

The all expression yields true when all combinations of values of Exp_i are true.

Several forms of statements produce a value and can be used as expression. This is further explained in the sections for the relevant statements, see the section called “If Statement”, the section called “While Statement”, the section called “Do Statement”, and the section called “For Statement”.

A block consists of a sequence of statements separated by semi-colons:

{ Statement1 ... Statementn }

Since a block is itself a statement, it may be used in all places where a statement is required. A block also introduces a new scope and variables that are declared in the block are local to that block. The value produced by a block is the value produced by its last statement.

The purpose of an assignment is to assign a new value to a simple variable or to an element of a more complex data structure. The most general form of an assignment statement is

Assignable AssignmentOp Exp

where AssignmentOp may be =, +=, -=, *=, /=, or ?=. Here = is the ordinary assignment operators and the other forms can be derived from it according to Table 1.5, “Assignment Operators”.

An assignable is either a single variable, (the base variable), optionally followed by subscriptions or field selections. The assignment statement always results in assigning a completely new value to the base variable. We distinguish the following forms of assignment:

Here are some examples:

rascal> N = 3;
int : 3

rascal> N;
int : 3

rascal> L = [10,20,30];
list[int] : [10,20,30]

rascal> P = L;
list[int] : [10,20,30]

rascal> L[1] = 200;
list[int] : [10,200,30]

rascal> P;  // Value of P is unchanged!
list[int] : [10,20,30]

rascal> M = ("abc": 1, "def" : 2);
map[str,int] : ("abc": 1, "def" : 2)

rascal> M["def"] = 3;
map[str,int] : ("abc": 1, "def" : 3)

rascal> T = <1, "abc", true>;
tuple[int,str,bool] : <1, "abc", true>

rascal> T[1] = "def";
tuple[int,str,bool] : <1, "def", true>

rascal> data FREQ = wf(str word, int freq);
ok

rascal> W = wf("rascal", 1000);
FREQ : wf("rascal", 1000)

rascal> W.freq = 100000;
FREQ : wf("rascal",100000)

rascal> <A, B, C> = <"abc", 2.5, [1,2,3]>;
tuple[str,real,list[int]] : <"abc", 2.5, [1,2,3]>

rascal> A;
str : "abc"

rascal> B;
real : 2.5

rascal> C;
list[int] : [1,2,3]

rascal> T = ("a" : 1);
map[str, int]: ("a":1)

rascal> T["b"] ? 1 += 5;
map[str, int]: ("b":6,"a":1)

rascal> anno str FREQ@color;
ok

rascal> W @ color = "red";
FREQ: wf("rascal",100000)[@color="red"]

rascal> wf(S, I) = W;
ok

rascal> S;
str : "rascal"

rascal> I;
int : 100000

The if-statement comes in an if-then and an if-then-else variant:

if ( Bool ) Statement

if ( Bool ) Statement1 else Statement2

In both cases the test Bool is evaluated and its outcome determines the statement to be executed. Recall from the section called “Boolean Operator Expressions” that boolean expression maybe multi-valued. In this case only the first true value (if any) is used. The value of an if-then statement is always void. The value of an if-then-else statement is the value of the statement executed in the then or else branch.

A switch statement is similar to a switch statement in C or Java and has the form:

switch ( Exp ) {
case PatternWithAction1;
case PatternWithAction2;
...
default: ...
}

The value of the expression Exp is the subject term that will be matched by the successive PatternWithActions (see the section called “PatternWithAction”) in the switch statement. The switch statement provides only matching at the top level of the subject term and does not traverse it. The type of the pattern in each case must be identical to the type of the subject term (or be a supertype of it). If no case matches, the switch acts as a dummy statement. There is no fall through from one case to the next.

The while-statement has the form:

while ( Bool ) Statement

The test Bool is evaluated repeatedly and Statement is executed when the test is true. Execution ends the first time that the test yields false. The test Bool is executed from scratch in each repetition and only the first true value (if any) is used.

By default, the value of a while statement is the empty list. In general, the value of a while statement consists of all values contributed by append statements that are executed during the repeated execution of its body Statement.

The do-while-statement has the form:

do Statement while ( Bool ) 

Statement is executed repeatedly, as long as the test Bool yields true. The test Bool is executed from scratch in each repetition and only the first true value (if any) is used.

By default, the value of a do statement is the empty list. In general, the value of a do statement consists of all values contributed by append statements that are executed during the repeated execution of its body Statement.

The for-statement has the form:

for ( Exp1 , Exp2 , ... , Expn ) Statement

It executes Statement for all possible combinations of values of the expressions Exp_i. Note that if one of the expressions is a boolean expression, we do try all its possible values.

By default, the value of a for statement is the empty list. In general, the value of a for statement consists of all values contributed by append statements that are executed during the repeated execution of its body Statement.

A return statement has either the form

return;

or

return Exp;

both end the execution of the current function. The first form applies to functions with void as return type. The second form applies to non-void functions and returns the value of Exp as result of the function. The following rules apply:

An append statement may only occur in the body of a while, do or for statement. It has the form

append Exp;

and appends the value of Exp to the resulting list value of the loop construct in which it occurs.

An insert statement has the form

insert Exp;

and replaces the value of the current subject (see below) by the value of Exp. An insert statement may only occur in the action part of a PatternWithAction (see the section called “PatternWithAction”), more precisely in

The following rule applies:

A fail statement has the form

fail;

and may only occur in the action of PatternWithAction (see the section called “PatternWithAction”). The fail statement forces the failure of that action. Any bindings caused by the pattern or side-effects caused by the action are undone.

A try catch statement has the form

try
   Statement1;
catch PatternWithAction1;
catch PatternWithAction2;
...
catch: Statement2;
finally: Statement3;

and has as purpose to catch any exceptions that are raised during the execution of Statement₁. These exceptions may caused by:

Note that all elements of the try catch statement are optional but that at least one has to be present. Their meaning is as follows:

A throw statement has the form

throw Exp;

and causes the immediate abortion of the execution of the current function with Exp's value as exception value. The exception can be caught by a try catch statement (the section called “Try Catch Statement”) in the current function or in one of its callers. If the exception is not caught, the execution of the Rascal program is terminated. The following rules apply:

An assert statement may occur everywhere where a declaration is allowed. It has two forms:

assert Exp1

and

assert Exp1 : Exp2

where Exp₁ is a boolean-value expression and Exp₂ is a string-valued expression that serves as a identifying message for this assertion. When Exp₁ evaluates to false, an AssertionFailed exception is thrown.

Example:

rascal> assert 1==2 : "is never true";
Uncaught Rascal Exception: -:1,0: AssertionFailed("is never true")

rascal> int div(int x, int y) {
  assert y != 0 : "y must be non-zero";
  return x / y;
}
int (int, int): int div(int, int);

rascal> div(4,0);
Uncaught Rascal Exception: -:2,2: AssertionFailed("y must be non-zero")
    :1,0: div

A test statement forms the basis for Rascal's unit-testing framework and may occur everywhere where a declaration is allowed. It has two forms:

test Exp1

and

test Exp1 : Exp2

where Exp₁ is a boolean-value expression and Exp₂ is a string-valued expression that serves as a identifying message for this test.

During normal execution tests are ignored and the test statement has no affect. When the script is executed as a test suite all tests in the current module and all its imported modules are executed and a summary of succeeded/failed tests is shown to the user.

rascal>test 1==2;      
ok
rascal>:test           
failed  : test 1==2
ok

	The test is ignored during standard execution.
	There are two ways to execute as test suite. By executing the :test directive of the Rascal shell (shown here) or by setting the option rascal.options.testsuite (not yet implemented).

Rascal provides a solve statement for performing arbitrary fixed-point computations. This means, repeating a certain computation as long as it causes changes. This can, for instance, be used for the solution of sets of simultaneous linear equations but has much wider applicability. The format is:

solve(Var1, Var2, ..., Varn)
  Statement

The solve statement consists of the variables for which a fixed point will be computed and a statement. Optionally, an expression directly following the list of variables gives an upper bound on the number of iterations. The format then becomes:

solve(Var1, Var2, ..., Varn; Exp)
  Statement

Statement can use and modify the listed variables Vari. The statement is executed, assigning new values to the variables Vari, and this is repeated as long as the value of any of the variables was changed compared to the previous repetition. Note that this computation will only terminate if the variables range over a so-called bounded monotonic lattice, in which values can only become larger until a fixed upperbound or become smaller until a fixed lower bound.

Let's consider transitive closure as an example (transitive closure is already available as built-in operator, we use it here just as a simple illustration). Transitive closure of a relation is usually defined as:

R+ = R + (R o R) + (R o R o R) + ...

In other words, it is the union of succesive compositions of the relation R with itself. This can be expressed as follows:

rascal> rel[int,int] R = {<1,2>, <2,3>, <3,4>};
rel[int,int] : {<1,2>, <2,3>, <3,4>}
rascal> solve (T) {
          T = T + (T o R);
        }
rel[int,int] : {<1,2>, <1,3>,<1,4>,<2,3>,<2,4>,<3,4>}