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);

do i<>5 cand b[i] >= b[p] -> p,i:=i,i+1
 | i<>5 cand b[i] <= b[p] -> i:=i+1
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.

  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
  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;
    do i<>N -> p,i   :=2*p,i+1
     | i<>N -> p,i,x :=2*p,i+1,x+p

    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:

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

5. News

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.

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.
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 "").
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