
 2000, Joseph Bergin
GCL--THE GUARDED COMMAND LANGUAGE (VERSION 7): 

Joseph Bergin

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.  

Qualified Identifiers

Identifiers may be qualified with the name of a module.  A qualified identifier has the form

identifier.identifier

where the first identifier is the name of a module and the second is the name of something defined 
within that module at the global level.  

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 procedure.   Names defined within a block or module must be unique 
within that block or module.  They may, however, be redefined in blocks contained within that block
or module.  Note: A name declared in the exported part of a module may not be redefined in the 
private, global, part of that same module. 

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 identifiers, 
and may not be redefined.  Boolean type is not compatible in any way with integer type.  

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 
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; 
	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 bounds.  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> | <procDef> 
			| <typedef> |<procDecl>  
<constantDef>  	 "const" <constantName> "=" <constant> 
<variableDef>   	<type> <variableList>  
<type>		<typeSymbol> [ <arraytype> | <rangetype> ] | <tupletype> 
<typeSymbol>   	 "integer" | "Boolean"  | <qualifiedIdent>
<tupletype>		"[" <typeSymbol> { "," <typeSymbol> } "]" 
<arraytype>		"array" "[" <qualifiedIdent> "]" 
				{"[" <qualifiedIdent> "]"}
<rangetype>		"range" "[" <constant> ".." <constant>  "]"				
<variableList>	  "identifier" {"," "identifier"} 
<typedef>		"typedef" <type> "identifier" 
<procDecl> 	"proc" "identifier" [<paramPart>]
<procDef>  	<procDecl> <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>  
<callStatement>	<qualifiedIdent> <argumentList>  
<argumentList>		 "(" [ <expressionList>] ")" 
<ifStatement>       	"if" <guardedCommandList> "fi"  
<guardedCommandList> 	<guardedCommand> {"[]" <guardedCommand>}  
<guardedCommand>	<expression> "->" <statementPart>  
<doStatement>       	"do" <guardedCommandList> "od" 
<forStatement>	"forall" <variableAccess> "->" <statementPart> "llarof"
<returnStatement>	"return" 
<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" 
<qualifiedIdent>		"identifier" [ "." "identifier ]
<variableAccess>    	<qualifiedIdent> <variableMore>  
<variableMore>      		""  |  "[" <expression> "]"  <indexorcomp>
				 	| "." "number"  <indexorcomp>
<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).  
