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:
- Requisite: download and install SWI-Prolog
- Download the gcl source files: gcl.tar.gz
- Uncompress the tar.gz file, move to gcl directory
and execute make:
gunzip gcl.tar.gz
tar -xvf gcl.tar
cd gcl
make |
- 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:
- 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.
- 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
|