– sire verb. To create or bear.
The sire language is a simple imperative, block structured language with syntax similar to Pascal and features inspired from CSP [Hoare78] and Occam [Occam82]. It is indented to provide a platform on which to demonstrate a mechanism for dynamic process creation. It includes simple sequential constructs and features for message passing concurrency, but omits features such as user defined data types for simplicity. This document gives an informal description of the syntax and semantics.
Signed integers are the basic type in sire. They are represented either statically in values or dynamically in variables.
Value entities represent constant integer values. The declaration:
val c := 8;
sets the value of c to 8. c cannot then be the target of any assignment statement. All declarations must be terminated with a semicolon.
Integer valued numbers can be represented in binary, decimal and hex decimal forms by prefixing with 0b, nothing and 0x respectively. For example, a value can initialised with the different representations:
val a := 0b101111;
val b := 47;
val c := 0x2F;
The reserved symbols true and false represent the values 1 and 0 respectively.
Variables hold a value state which is changed by statements operating on this state. Variable instances are declared with the var keyword:
var a;
declares the variable a. Variable declarations are separated on new lines, for example:
var a;
var b[10];
declares a single a and an array b. The assignment statement is used to change the value of a variable:
a := 5
changes the value of a to 5. Any expression can appear on the right hand side of the assignment statement.
An array is created by suffixing a type with square brackets enclosing an expression specifying the length, for example:
var a[10];
declares a length 10 array of variables. The elements are accessed with the array subscript notation, for example, a[0] accesses the lowest element of a, legal accesses may be made up to a[9]. Currently, only one dimensional arrays are supported. Array references are also used for array slicing and formal parameters. For example, the declaration:
var b[];
declares b as an uninitialised array reference.
Array slicing is provided by the alias statement. This is a special type of assignment that assigns the value of a variable of type array reference to a valid position of the source array. For example, the statement:
b aliases a[4..]
causes b to reference the last half of a. Aliasing simply duplicates an offset array reference, no copying is involved.
The table below gives the arithmetic operators available with their type, associativity and precedence. Precedence 0 relates to the highest precedence.
| Symbol | Type | Associativity | Precedence | Meaning |
|---|---|---|---|---|
| - | unary | right | 1 | Negation |
| ~ | unary | right | 1 | Bitwise not |
| * | binary | left | 2 | Multiplication |
| / | binary | left | 2 | Division |
| + | binary | left | 3 | Addition |
| - | binary | left | 3 | Subtraction |
| rem | binary | left | 4 | Modulo |
| or | binary | left | 4 | Bitwise or |
| and | binary | left | 4 | Bitwise and |
| xor | binary | left | 4 | Bitwise xor |
| << | binary | left | 4 | Bitwise left shift |
| >> | binary | left | 4 | Bitwise right shift |
| lor | binary | left | 5 | Logical or |
| land | binary | left | 5 | Logical and |
| = | binary | none | 6 | Equal |
| ~= | binary | none | 6 | Not equal |
| < | binary | none | 6 | Less than |
| <= | binary | none | 6 | Less than or equal |
| > | binary | none | 6 | Greater than |
| >= | binary | none | 6 | Greater than or equal |
Processes and functions are composed of a set of block-structured statements. Statements can either be composed sequentially or in parallel. This is denoted by the use of the sequential separator ‘;‘, or the parallel separator ‘|‘. The block:
{ process1() ; process2() ; process3() }
is composed sequentially, so processes 1, 2 and 3 will be executed one after another. Execution of the block will complete when process3 has completed.
The while loop repetitively executes a body while a condition remains true. This is checked each time prior to the execution of the body. When it becomes false, the loop terminates. The following code demonstrates the use of a while loop, which implements an algorithm to calculate the factorial of a number n, n!:
var i;
var factorial;
{ i := 0
; factorial = 1
; while i < n do
{ factorial := factorial * i
; i := i + 1
}
}
The for loop repetitively executes a loop body based an index variable with pre and post conditions and an increment value. This allows a simple iteration to be clearly expressed. The following code again implements the factorial algorithm, but with a for loop:
var i;
var factorial;
{ factorial =: 1
; for i:=1 to n do
factorial := factorial * i
}
The if statement allows the conditional execution of statements. The condition is evaluated as an arithmetic expression and if non-zero then the then part is executed, otherwise the else part is. The else part is required to solve the dangling else problem. The following code implements a recursive factorial algorithm, demonstrating the use of an if statement:
func factorial(val n) is
if n = 0
then return 1
else return n * factorial(n-1)
The skip statement does nothing, but can be used to fill an empty if statement’s else.
In contrast, the block:
{ process1() | process2() | process3() }
is composed in parallel, so on entry to the block, two new threads are created for processes 2 and 3 and then execution of all three processes commences in parallel. Execution of the block will terminate only when the last process has completed.
A sire program consists of a set of processes and functions and possibly some global state. Processes and functions, both types of procedure, are a collection of one or more statements that perform some task. The structure of a sire program is as follows. Any value, variable or port global declarations are made at the beginning, before any process or function definitions. Processes and functions may then be defined in any order. A program must contain a process called main as execution will start at this point.
Processes do not return a value but have no such restrictions on side effects. A process is defined using the proc keyword, followed by the process name, formal parameters, local variable declarations and then the body. For example, the following process definition implements the bubble sort algorithm:
proc sort(var a[len]; val len) is
var i;
var j;
var tmp;
for i:=0 to len-1 do
for j:=0 to len-1 do
if a[j] > a[j+1]
then
{ tmp := a[j]
; a[j] := a[j+1]
; a[j+1] := tmp
}
else skip
A process is invoked by naming the process and specifying any input parameters:
sort(a, 10)
Functions are a special procedure type that do not cause any side effects and only return a value. A function causes a side effect if it also modifies some external state. This might include, for instance, changing the value of a global variable, or modifying the contents of a referenced array. To prevent this from happening, functions cannot write to global variables or referenced parameters, invoke processes or use input or output operators.
A function is defined in the same way as a process except with the func keyword, it must also complete with a return statement. The following function recursively calculates the n th Fibonacci number:
func fib(val n) is
if n > 1
then return fib(n-1) + fib(n-2)
else if n = 0 then return 0 else return 1
Functions can be called in the same way as processes or as part of an expression, as it is in the above example. The formal parameters of a function or process may only be of integer or integer array reference types.
There are only two levels of scoping for variables in sire: global, at the program level, and local, at the process/function level. Variable declarations may be made either globally or locally, but value declarations may only be made globally.
A process or function becomes visible only at the beginning of its definition. Hence, a procedure cannot be used before it is defined.
Recursion is permitted, but only for self-recursive procedures. Due to simple scoping for procedure names which would require the need for forward references, mutual-recursion is not supported.
For example, a complete example sorting program may be defined as:
val LEN := 10;
var a[LEN];
proc sort(var a[len], val len) is
var i;
var j;
var tmp;
for i:=0 step 1 until len-1 do
for j:=0 to len-1 do
if a[j] > a[j+1]
then
{ tmp := a[j]
; a[j] := a[j+1]
; a[j+1] := tmp
}
else skip
proc main() is
sort(a, LEN)
Process creation is the key feature of the sire language and is provided with the on statement. Semantically, on is exactly the same as a regular process call, except that the computation is performed remotely. It is synchronous in that it blocks the sending processes thread of execution until the new process has terminated; this behavior fits naturally with composing it in parallel with other tasks.
The transmission of a process to a remote processor for execution requires a closure of the process to be created. A closure is a data structure that contains the process’ instructions, and a representation of the functions lexical environment, that is the set of available variables and their values. sire processes may have formal parameters of type integer value or array reference, so these must be included as part of the closure. Referenced arrays are copied and replicated at the destination. On completion, any referenced arrays are sent back to reflect any changes that were made in the original copy. The statement:
var a[10];
on core[3] do sort(a, 10)
spawns the sort process on core 3. The core array is a system variable and is used to address the set of processing cores comprising the system. Because the on statement is synchronous, it is natural to to compose this in parallel with other statements. For example, the block:
var a[10];
var b[10];
{ on core[10] do sort(a, 10)
| sort(b, 10)
}
allows the thread to execute another sorting process whilst the spawned one is performed remotely.