GCL 2.2

A small interpreter for Dijkstra's Guarded Command Language

Pedro Cabalar
Dept. of Computer Science, Univ. of Corunna, Spain

Introduction  |  Download and install  |  Usage  |  Examples |  News

1. Introduction

GCL is a small interpreter for Dijkstra's Guarded Command Language [Dijkstra'76] written in SWI-Prolog. The interpreter allows executing a simple program in GCL allowing different execution modes. As an example of program, consider the computation of the position p of the maximum element in an array:
// p returns the position of the maximum value in b
b[0:5]:integer = (4,9,2,9,1,3);

i,p:=0,0;
do i<>5 cand b[i] >= b[p] -> p,i:=i,i+1
 | i<>5 cand b[i] <= b[p] -> i:=i+1
od
All nondeclared variables (like i and p, in the example) are assumed to be integer.

Some syntactic restrictions which will be probably removed in the future:
  • no multi-dimensional arrays
  • assertions are not allowed yet

2. Download and install

GCL is written in SWI-Prolog , and requires the installation of this Prolog distribution. Besides, the parser is an external C program (written for gcc compiler). The parser was generated with bison and flex: these tools are not required, but source files are also provided so you can see the grammar or in case you want to make changes.

Installation:
  1. Requisite: download and install SWI-Prolog
  2. Download the gcl source files: gcl.tar.gz
  3. Uncompress the tar.gz file, move to gcl directory and execute make:
    gunzip gcl.tar.gz
    tar -xvf gcl.tar
    cd gcl
    make
  4. This must create two executable files gcl and gcl2pl that you must locate in some directory in your PATH (for instance, /usr/local/bin). You can also keep the Prolog source file gcl.pl if you want to execute queries from the Prolog prompt.

3. Usage

gcl [options] <filename>
  -t  print whole trajectory after each execution
  -a  show all nondeterministic solutions
  -s  perform a single (random) execution step by step showing
      current line and resulting state (disabled by -a or -t)
  -q  quiet: supresses information header and messages


There exist two main execution modes:
  1. Background execution:

    $ gcl -q max.gcl
    p=3, i=6, b=[4,9,2,9,1,3]

    where the final state is shown after the program has completely finished its execution. It can be combined with option -t to show the whole execution trajectory (note: -t does not inspect the internal code of a function call yet):

    $ gcl -q -t max.gcl
    p=undef, i=undef, b=[4,9,2,9,1,3]
    p=0, i=0, b=[4,9,2,9,1,3]
    p=0, i=1, b=[4,9,2,9,1,3]
    p=1, i=2, b=[4,9,2,9,1,3]
    p=1, i=3, b=[4,9,2,9,1,3]
    p=3, i=4, b=[4,9,2,9,1,3]
    p=3, i=5, b=[4,9,2,9,1,3]
    p=3, i=6, b=[4,9,2,9,1,3]

    Note that the sequence of states is computed first and printed after the complete execution, rather than at each execution step. When the program has a non-deterministic choice, a random branch is executed. One more possibility is selecting option -a, that prints all non-deterministic possibilities:

    $ gcl -q -a max.gcl
    Solution 1:
    p=3, i=6, b=[4,9,2,9,1,3]

    Solution 2:
    p=1, i=6, b=[4,9,2,9,1,3]

    Solution 3:
    p=3, i=6, b=[4,9,2,9,1,3]

    Solution 4:
    p=1, i=6, b=[4,9,2,9,1,3]

    Note that solutions are shown depending on the possible execution traces and not on the sequence of states (this explains why some solutions may appear twice or more). Option -a can be further combined with -t to see the trajectories of each solution. Displaying all the non-deterministic solutions may easily blow up exponentially. For instance, the program  powerset.gcl

    const N=5;
    p,i,x:=1,0,0;
    do i<>N -> p,i   :=2*p,i+1
     | i<>N -> p,i,x :=2*p,i+1,x+p
    od

    makes a binary choice in each loop iteration, that decides whether we should add 2i to x or not. Using gcl -a powerset.gcl will generate 2N possible solutions with all possible values x=0,...,2N-1, in the example from 0 to 31.

  2. Step by step execution:
    $ gcl -q -s max.gcl
    1: p=undef, i=undef, b=[4,9,2,9,1,3]
    |: <enter>
    3: p=0, i=0, b=[4,9,2,9,1,3]
    |: <enter>
    5: p=0, i=1, b=[4,9,2,9,1,3]
    |: <enter>
    4: p=1, i=2, b=[4,9,2,9,1,3]
    |: <enter>
    5: p=1, i=3, b=[4,9,2,9,1,3]
    |: <enter>
    5: p=1, i=4, b=[4,9,2,9,1,3]
    |: <enter>
    5: p=1, i=5, b=[4,9,2,9,1,3]
    |: <enter>
    5: p=1, i=6, b=[4,9,2,9,1,3]
    |: <enter>

    This option cannot be combined with -a or -t. It allows executing the program step by step (in fact, only assignments are taken into account), showing current state and text line in the source file. For a better understanding when using this option, it is recommendable to locate each assignment in a different text line.

4. Examples

This is a small list of example source files:

abs.gcl
Absolute value as a function
add1.gcl
Non-deterministically adds one to each position of an array or sets it to zero
buble.gcl
Bubble search
common.gcl
Computes the number of common elements in two ordered arrays
division.gcl
Compute quotient and remainder for an integer division
euclid.gcl
Euclid's algorithm (using modulo)
euclid2.gcl
Euclid's algorithm (using subtraction)
fact.gcl
Factorial as a recursive function
max.gcl
Search the position of the maximum element
moveZeros.gcl
Move all zeros to the rightmost positions
mult.gcl
Performs the multiplication of 2 numbers, using binary operations
plateau.gcl
Length of the maximal sequence (plateau) of repeated values inside an ordered array
random.gcl
Get a random number between 0 and N
shiftright.gcl
shiftright-b.gcl
Circular shift right for an array of integers. Two options.
sum.gcl
Add all the numbers in an array
welfare.gcl
Find the positions of the lowest element that occurs in 3 ordered arrays (without repetitions)

5. News

14/2/2017
New version 2.2 and new web page (14 years later!). New features
  • Functions
  • Constant declarations

Many thanks to David Topham for pushing these new topics and testing the interpreter.

1/12/2003
New version 1.2:
  • Parsing is not done inside Prolog any more: the parser is now implemented as an external program in C language. This program is a preprocessor that transforms the .gcl source file into an intermediate file containing Prolog terms which can be directly handled by the interpreter. As a result, parsing is much faster and some syntax errors are now notified. The only problem is that the Windows version is not available yet.
17/12/2002
New version 1.1 available, with the following changes:
  • bug in array initialization fixed
  • new type char defined and handled as a subset of integer [0,255] but displayed as a character. Similarly, arrays of char can be initialized and are also displayed  as character strings (delimited by "").
17/12/2002
Program gcl has been locally installed in alba and deza




[Dijkstra76] Edsger W. Dijsktra, A discipline of Programming, Prentice-Hall series in Automatic Computation, Englewood Cliffs, N.J., 1976.

Maintained by Pedro Cabalar. 14/2/2017