GCL--THE GUARDED COMMAND LANGUAGE (VERSION 7):
Joseph Bergin
The course language is SIMILAR to this one, but not identical.
The programming language GCL is a Pascal-like language with guarded commands and parallel assignment. The language has tuples for encaplsuation and procedures for abstraction. It was developed from a language originally designed by Edsger Dijkstra.
Keywords
These words may not be redefined.
module private end const Boolean integer begin typedef array range
proc val ref return write read if fi do od true false forall llarof skip
Other symbols
. = := -- , ; ( ) [] [ ] -> #
< > <= >= & | ~ + - * / \ ..
Comments are introduced with the symbol -- and extend to the end of the line.
Identifiers
User defined identifiers consist of Letters, digits and underscore characters with the restriction that they must begin with a letter, they may not contain white space, and they may not contain sequences of more than one underscore.
Numbers
A number is a sequence of digits 0...9. It does not have a sign.
Programs
A program is a sequence of modules. Each module is a definition part followed by a block followed by a period.
<module> ->
module identifier
<definitionPart>
private
<block> .
The definition part of a module represents the interface that the module presents to other modules which follow in the sequence: its names are exported from the module.
A block consists of a definition part followed by a statement part:
<block> ->
<definitionPart>
begin
<statementPart>
end
The names introduced in the definition part of the block are local to that block. A block describes operations (computations) on named entities called objects. An object is either a constant, a variable, a tuple, or a function.
Declarations:
The definition part of a block is a sequence of definitions, each terminated by a semicolon.
<definitionPart> -> D1;D2;...Dn;
A constant definition introduces the name of a single integer or Boolean constant. For example:
const size = 100;
const done = false;
A variable definition introduces the names of variables of the same type; for example,
Boolean done,found;
integer x,y,z;
[integer, integer] pair;
The simple types of GCL are integer and Boolean. Integer represents a fixed range of the ordinary integer numbers (usually -32768...32767). The Boolean values are true and false. The words integer, Boolean, true, and false are keywords in the language, they are not names, and may not be redefined.
The variable definition
integer range [3..9] i,j ;
introduces range variables i and j that may take on integer values between 3 and 9 (inclusive). Range variables are compatible if they have compatible base types, here integer. Ranges are also automatically compatible with their base types. Nevertheless, a range variable should never obtain a value outside its allowable range. Range types with integer base types may be read and written. The basetype of a range can also be Boolean since Boolean values can be compared with the < operator. For example
Boolean range [false..true] bools;
Assume we have made the declarations:
const size = 100;
typedef integer range[1..size] subs;
Then the variable definition
integer array [subs] a,b;
introduces the names a and b as arrays of 100 integers each. The allowable subscripts of a and b are 1...100 in this case. Array elements may be of any type. The definitions
typedef integer range [1..5] one_five;
typedef integer range [1..10] one_ten;
Boolean array[one_ten][one_five] twodim
introduces an array of ten elements, each of which is an array of five Boolean values. Said another way, this is a two dimensional array of Booleans, with ten rows and five columns. Arrays may have any number of subscripts, but they may have only integers or Booleans for subscripts. Given the above declaration twodim[3] is an array of 5 Booleans and twodim[3][1] is the first element of twodim[3]. The name in brackets in an array declaration must, of course, be the name of a range type defined in a previous typedef.
The variable definition
[integer, boolean, integer] z;
introduces a tuple variable z with three components. Tuple variables are assignable. A value like [3, true, 5 + y] (assuming y has type integer) is a tuple value. You can extract the contents of a tuple variable using a "dot" notation. For example:
z.2
represents the contents of the second component of the tuple z. This may be assigned to as in:
z.2 := false;
A type definition looks like the keyword typedef followed by a type expression and then an identifier. For example
typedef integer size;
declares size to be a type identical to integer type. Similarly
typedef integer array[one_ten] element;
delcares the identifier element to be an array type with 10 integer cells. And
typedef [integer, integer] intpair;
delcares that intpair represents a tuple type with two integer components.
Note that, syntactically, a type definition looks like a variable declaration preceeded by typedef, except that only a single new name may be introduced. Thus
typedef integer size, style;
is illegal and does NOT define two new types, while
integer size, style;
is legal and defines two new variables.
Two type expressions represent the same type if they represent identical type structures. The names that may be given to types are a programmer convenience only. They do not create new types.
A procedure definition or declaration introduces the name, formal parameters and parameter passing mechanisms of a procedure, which may be called to produce an effect. A definition also gives the block that defines the procedure's action. for example
proc compute(val integer n; val Boolean greater; ref integer result)
begin
if greater -> result := n;
[] ~greater -> result := -n;
fi;
return;
end;
Several parameter declarations are separated by semicolons. Each parameter declaration may define several parameters as a variable declaration may define several variables. The parameters may be passed by value (val) or reference (ref). All names declared within a function (parameters and locals) must be distinct. Any type may be passed as a parameter, including arrays and tuples.
A procedure may be declared without being defined. A procedure declaration consists of its name, parameter definitions, and their passing mechanisms; for example
proc compute(val integer n; val Boolean greater; ref integer result);
A declared procedure must eventually be defined in the same block in which it was declared (and not within another block contained within that block). A previously declared procedure is defined by giving its name and block, without repeating its parameter definitions; for example,
proc fac(val integer n; ref integer result);
. . .
proc fac
begin
if n <= 1 -> result := 1;
[] n > 1 -> fac(n-1, result); result := n * result;
fi;
end;
It is an error to give more than one declaration of a procedure or more
than one definition of a
declared procedure.
Statements:
The statement part of a block is a sequence of statements followed by semicolons:
S1;S2;...Sn;
The empty statement is denoted by the keyword skip. It is a no-op. Nothing is done by skip.
The read statement inputs one or more integers and assigns them to variables; for example,
read i, a[i];
A write statement outputs on or more integers defined by expressions, and/or one or more string constants; for example,
write "The answer is: ", x, " and its size is: ", i;
The operands of a read statement must be of type integer or a range type with base type integer. The operands of a write statement may be integers, or ranges with integer base type, or they may be string constants. String constants are delimited by either double quote marks or by single quote marks (apostrophes). The left and right string delimiters must be of the same kind. A string delimited by double quotes may contain apostrophes and conversely. The quote marks surrounding a string are not output by the write statement. The following are legal strings
'These are the times'
"that try men's souls"
An assignment statement consists of a variable access list followed by an expression list; for example
n, m := n+1, n*m;
Each variable in the variable access list must be of the same type as the corresponding expression. All assignments are carried out in parallel.
Tuples and arrays may be assigned as well as subarrays. For example, using the declarations given above,
twodim[4] := twodim[1];
is legal, and copies the entire subarray twodim[1,1..5] into the subarray twodim[4,1..5]
The assignment statement is executed in the following way: First, the variable accessses are evaluated to obtain addresses. Second, the expressions are evaluated to obtain values. Third, the values are assigned to the addresses. Logically, no value may be assigned before all are evaluated. Note that
x, y := y, x;
is a valid way to write a value swap in gcl.
The name of the language comes from the form of the if and do statements.
The if statement takes the form
if B1 -> SP1 [] B2 -> SP2 [] ...[] Bn -> SPn fi where the Bs are Boolean expressions and the SPs are statement lists. For example,
if a < b -> min := a;
[] a >= b -> min := b;
fi;
This is equivalent to the C statement: if (a<b) min = a; else min = b;
The logical negation operator in GCL is the tilde, ~, so the above is equivalent to,
if a < b -> min := a;
[] ~(a < b) -> min := b;
fi;
The forms B -> SP are called guarded commands, where the Boolean expression B is the guard and SP is a statement part; for example, a < b -> min := a;
The execution of the if statement proceeds by determining if any of the guards is true. If any of them are true then one of the true guards will be chosen arbitrarily and the corresponding statement part will be executed. This will terminate the execution of the if and the computation will continue with any statement which follows. However, it is an error if none of the guards are true and the entire computation will be halted in an error state and a message is printed.
According to this rule the first example in this section is equivalent to the following (notice that both guards may be true simultaneously)
if a <= b -> min := a;
[] a >= b -> min := b;
fi;
A do statement also consists of guarded commands:
do B1 -> SP1 [] B2 -> SP2 [] ...[] Bn -> SPn od For example
do i <= size -> read A[i]; i := i+1; od;
If one or more of the guards is true then one of the true guards will be chosen arbitrarily and the corresponding statement part will be executed, after which the do statement will be re-executed. The do statement will terminate only when all guards are false.
A forall statement iterates over all values of a range variable.
integer range [1..10] x;
...
forall x -> write x; llarof;
The control variable (here x) must be a range variable. This statement executes its statement part once for each value of the range variable. It is not possible to iterate over a portion of the range. Instead use a do statement with an integer (or Boolean) control variable to achieve this.
The return statement consists of the keyword return. It is only legal within the block of a procedure. When executed the procedure immediately terminates. Every procedure has an implicit return statement as its last statement.
The procedure call statement consists of the name of the procedure to be called and argument expressions matching the parameters of the procedure. Ref parameters must be matched by variable access expressions. If a procedure has no parameters the empty parentheses are still present in the procedure call statement. An example of a call statement follows
compute ( x + 5, x <= y, result);
A procedure call activates the block of the corresponding procedure after matching the values of the value arguments with the names of the formal parameters and the addresses of the ref arguements with the names of the corresponding ref parameters.
Expressions:
The relational operators are =, #, <, <=, >, >=. Operators = and # apply to any type (including arrays and tuples). The last four apply only to integers and Booleans.
The arithmetic operators are +, -, *, /, \, with the last indicating the integer remainder. Operator - is also used as the unary negation op. Operator + may be used as a unary operator as well, though it has no effect.
The boolean operators are & | ~, indicating and, or and not respectively. These are always evaluated completely. Note that ~ is a unary prefix operator. The other two are binary infix operators.
All binary operators are left associative. The precedences of the operators fall into the classes below, in order of increasing precedence.
Primary operators & |,
Relational operators = # < <= > >=,
Adding operators + -,
Multiplying operators * / \,
Unary operators ~ - +
The grammar given at the end of the document reflects this precedence.
A GCL example.
-- Linear search
module search
private
const size = 10;
typedef integer range [1..size] sizer;
typedef integer array [sizer] elements;
sizer j;
elements A;
integer x;
[Boolean, integer] result;
proc search (val integer target; val elements B; ref [Boolean, integer] result)
integer m;
integer i;
Boolean found;
integer where;
begin
i:= 1;
m := size;
found := false;
do i <= m ->
if B[i] = target ->
found := true;
where := i;
i := m + 1;
[] B[i] # target ->
i := i+1;
fi;
od;
result = [found, where];
end;
begin
-- test search
forall j -> read A[j]; llarof;
read x;
do x#0 -> search(x,A, result);
if result.1 -> write x, ' can be found at ', result.2;
[] ~result.1 -> write x, ' not found';
fi;
read x;
od;
end.
In a program consisting of more than one module, the second and subsequent modules
may obtain
access to objects exported from earlier modules by preceding the name of the
object with the
name of the module; for example
module first const size = 100; proc search... begin ... end. ... module second begin ... first.size ... first.search... ... end.
The names declared within the module blocks are local to the modules and are not exported. Other modules have no access to them. If a name has been exported and not subsequently hidden by the redefinition of the same name in a new module, then access to the name may be obtained directly without prefixing it with the module name.
The blocks of the modules are executed in order of appearance in the program. Note that the statement part of a block may be empty.
Notes.
Capital letters and small letters are considered different.
Comments may be inserted into the source of a program by preceding them with the comment indicator , two adjacent dash characters, --. A comment extends to the end of the line.
Each declaration and each statement is terminated by a semicolon.
The skip statement may be used to simulate the effect of a Pascal if then statement (without an else part). The following are equivalent:
Pascal: if a < b then write a;
GCL if a < b -> write a; [] ~(a < b) -> skip; fi;
The following is almost certainly an error and is not equivalent to the above:
GCL if a < b -> write a; fi;
Procedure definitions may be nested. They define nested name scopes identical to Pascal. A name is visible in a block in which it is declared and in any blocks contained within it, but not to surrounding blocks.
While all names declared within a block must be distinct, it is possible, as in Pascal, to redeclare any name that was declared in a containing block. The new declaration is valid for the duration of the block in which it is declared. Outside the block the original declaration is valid. The scope of a name is the entire block in which it appears (not just from the point of declaration to the end).
Two variables that have the same structure are considered to have the same type for purposes of assignment. Arrays have the same structure if they have the same number of subscripts (dimensions), and in each corresponding dimension they have the same length. Finally, they must have the same ultimate component type.
The components of a tuple may be of any type, including other tuple types or array types. The types need names, however, to define the tuple.
All parameters are passed by value or by reference. Arrays and tuples are copied when used as value parameters as are all other types.
An EBNF grammar for GCL
<program> <module> {<module>}
<module> "module" "identifier" <definitionPart>
[ "private" <block> ] "."
<block> <definitionPart> "begin" <statementPart> "end"
<definitionPart> {<definition> ";"}
<definition> <constantDef> | <variableDef> | <procedureDef>
| <typedef> |<procedureDecl>
<constantDef> "const" <constantName> "=" <constant>
<variableDef> <type> <variableList>
<type> <typeSymbol> [ <arraytype> | <rangetype> ] | <tupletype>
<typeSymbol> "integer" | "Boolean" | "identifier"
<tupletype> "[" <typeSymbol> { "," <typeSymbol> } "]"
<arraytype> "array" "[" "identifier" "]"
{"[" "identifier" "]"}
<rangetype> "range" "[" <constant> ".." <constant> "]"
<variableList> "identifier" {"," "identifier"}
<typedef> "typedef" <type> "identifier"
<procedureDecl> "proc" "identifier" [<paramPart>]
<procedureDef> <procedureDecl> <block>
<paramPart> "(" [ <paramDef> { ";" <paramDef> } ] )"
<paramDef> ( "val" | "ref" ) <variableDef>
<statementPart> { <statement> ";"}
<statement> <emptyStatement> | <readStatement> | <writeStatement>
| <assignStatement> | <returnStatement> | <callStatement>
| <ifStatement> | <doStatement> | <forStatement>
<emptyStatement> "skip"
<readStatement> "read" <variableAccessList>
<variableAccessList> <variableAccess> {"," <variableAccess> }
<writeStatement> "write" <writeItem> {"," <writeItem> }
<writeItem> "stringconst" | <expression>
<expressionList> <expression> { "," <expression> }
<assignStatement> <variableAccessList> ":=" <expressionList>
<ifStatement> "if" <guardedCommandList> "fi"
<guardedCommandList> <guardedCommand> {"[]" <guardedCommand>}
<guardedCommand> <expression> "->" <statementPart>
<doStatement> "do" <guardedCommandList> "od"
<forStatement> "forall" <variableAccess> "->" <statementPart> "llarof"
<returnStatement> "return" <expression>
<callStatement> "identifier" ["." "identifier"] <argumentList>
<argumentList> "(" [ <expressionList> ] ")"
<expression> <relationalExpression> {<booleanOperator>
<relationalExpression> }
<booleanOperator> "&" | "|"
<relationalExpression> <simpleExpression> [<relationalOperator>
<simpleExpression>]
<relationalOperator> "<" | "=" | ">" | "<=" | ">=" | "#"
<simpleExpression> ( "+" | "-" ) <term> { <addingOperator> <term>} |
<term> { <addingOperator> <term>}
<term> <factor> {<multiplyOperator> <factor>}
<factor> <variableAccess> | "number" | <booleanConstant>
| "[" <expressionList> "]"
| "(" <expression> ")" | "~" <factor>
<addingOperator> "+" | "-"
<multiplyOperator> "*" | "/" | "\"
<constantName> "identifier"
<variableAccess> "identifier" <variableMore>
<variableMore> "" | "[" <expression> "]" <indexorcomp>
| "." <nextitem> <indexorcomp>
<nextitem> "number" | "identifier"
<indexorcomp> { "." "number" | "[" <expression> "]" }
<constant> <expression>
<booleanConstant> "true" | "false"
Notice that some constructs seemingly legal according to this grammar are actually illegal due to the semantics of GCL. The comment has not been included in the grammar (it is a Lexical consideration).