%  tutorial.tex
%  Copyright (C) 1992, 1993, 1994  J Dana Eckart
%
%  This program is free software; you can redistribute it and/or modify
%  it under the terms of the GNU General Public License as published by
%  the Free Software Foundation; either version 1, or (at your option)
%  any later version.
%
%  This program is distributed in the hope that it will be useful,
%  but WITHOUT ANY WARRANTY; without even the implied warranty of
%  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
%  GNU General Public License for more details.
%
%  You should have received a copy of the GNU General Public License
%  along with CELLULAR; see the file COPYING.  If not, write to the 
%  Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

\documentstyle{article}

% Setup the desired page style.
\pagestyle{plain}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9.2in}
\setlength{\oddsidemargin}{0mm}
\setlength{\evensidemargin}{0mm}
\setlength{\topmargin}{-0.3in}
\setlength{\headheight}{0mm}
\setlength{\headsep}{0mm}

\setlength{\columnsep}{5mm}

\renewcommand{\topfraction}{1.0}
\renewcommand{\textfraction}{0.0}

% Setup the desired paragraph style.
\setlength{\parindent}{0mm}
\setlength{\parskip}{3mm}
\begin{document}

% A new command to define a constant tabbing distance for code examples.
\newcommand{\tab}{\hspace{5mm}}

\title{A {\em Cellular} Automata Simulation System}
\author{J Dana Eckart\\
	Computer Science Department\\
        Radford University\\
	Radford, VA \ 24142\\
	dana@rucs.faculty.cs.runet.edu\\
}
\date{7 April 1994}
\maketitle

\section{Introduction}
Cellular automata were first introduced by Stanislaw Ulam and John von
Neumann in the late 1940's.\cite{ulam}\cite{neumann}
A cellular automata consists of a possibly infinite, $n$--dimensional
lattice of cells.  Each cell has a state chosen from a finite alphabet.  
The state of all cells in the lattice are updated simultaneously and 
independent of one another in discrete time steps.  Cells update their values
by using a transition function.  The transition function takes as its input 
the current states of the local cell and some finite
collection of nearby cells that lie within some bounded distance, 
collectively known as a neighborhood.
With the growing popularity of cellular automata in both recreation
\cite{life}\cite{wireworld}\cite{fluids}\cite{crystals} 
and the modeling of physical 
systems\cite{toffoli}\cite{Chen}\cite{Lim}\cite{Boghosian}\cite{Teixeira},
the need for an easy-to-use system for cellular automata programming
is greater than ever.  {\em Cellular} is a system designed and implemented
by the author to meet these needs.

The {\em Cellular} system consists of: a programming
language, {\em Cellang},
and associated compiler, {\tt cellc};
an {\em a}bstract {\em v}irtual {\em c}ellular {\em a}utomata 
{\em m}achine\footnote{
		This gives the system the flexibility to be adapted
		to support a variety of platforms.
	}
for execution, {\tt avcam}; and a viewer, {\tt cellview}.
Compiled {\em Cellang} programs can be run
with input provided at any specified time during the execution.  The
results of an execution can either be viewed directly or output as
a stream of cell locations and values.  This stream of output
data can then be fed into {\tt cellview} for viewing, or it may
be passed through a filter that compiles statistics, massages the
data, or merely acts as a valve to control the flow of data from the
cellular automata program to the viewer.

This simple UNIX\footnote{
                UNIX is a registered trademark of AT\&T.
        }
toolkit view of the simulation process provides greater control
than systems which combine the language and viewer (i.e.
Cellsim\cite{cellsim} and CAM-6\cite{toffoli}).  {\em Cellang}
provides greater flexibility, particularly in the formation of
neighborhoods, than does {\em Cal} (part of the {\em Scamper} 
system)\cite{Scamper} and more safely than can be accomplished in
{\em Cellsim}\cite{cellsim}.  The use of a deterministic rule set
(as opposed to probablistic rules supported by the {\em SLANG}\cite{SLANG} 
system),
specified using an imperative programming paradigm allows {\em Cellang}
to be a small, simple, and easy to learn language.  Finally, {\em Cellang}
combines the classic cellular automata programming paradigm with that of
agents (as exemplified by the {\em Creatures}\cite{Creatures} system).  This
combination allows a richer solution space to many of the interesting
problems in modeling and simulation.

\section{Language Basics}
Programs written in {\em Cellang} have two main components, a cell
description and a set of statements.\footnote{
		The language assumes a uniform transition function over
		all the cells of the automata.
	}
The cell description determines
how many dimensions there are, what field(s) each cell
contains, and the range of values that can be associated with each field.  
Statements occur in three varieties: assignment, if and forall.  The assignment
statement is unusual in that it provides conditional assignment;
the if statement is of the conventional nature; and the forall causes
an index variable to iterate through a range of values.

The cells of the automata reside at the integer lattice points of an
$n$--dimensional Euclidean space.
Due to the limitation of finite memory, only
a finite number of cells can be declared.  To prevent the creation of a
discontinuous boundary at the edge of the space, the lattice of cells
folds back upon itself to form a closed surface.  Thus, for $n = 2$ the
universe would form a torus. 
The field values of cells neighboring the 
current cell may be accessed by placing their relative position within square
brackets ([ ]), followed by an optional dot (.) and field name.

There is only one primitive data type in {\em Cellang}:  integer. 
Variables are
declared by their first usage as the left hand side of an
assignment statement.  Conditional expressions follow the
rules of {\em C} \cite{harbison},
thus a 0 value corresponds to false and non-0 values indicate
true.  The arithmetic and logical operators available are: +, --, *, /,
\% (remainder), +\% (modulo addition), --\% (modulo subtraction), ! 
(logical not), \& (logical and), $|$ (logical or), =, !=, $<=$ and $>=$.  

\begin{figure}[t]
\begin{center}
\begin{verbatim}
             2 dimensions of 0..1

             sum := [0, 1] + [1, 1] + [1, 0] + [-1, 1] + [-1, 0] + 
                    [-1, -1] + [0, -1] + [1, -1]

             cell := 1 when (sum = 2 & cell = 1) | sum = 3
                  := 0 otherwise
\end{verbatim}
\end{center}
\caption{The game of Life}
\label{simple life}
\end{figure}

\begin{figure}[t]
\begin{center}
\begin{verbatim}
             2 dimensions of 0..1

             sum := 0
             forall i:2..4
                 forall i:-3..-1
                     sum := sum + [i, j] when i != 0 | j != 0
                 end
             end

             cell := 1 when (sum = 2 & cell = 1) | sum = 3
                  := 0 otherwise
\end{verbatim}
\end{center}
\caption{The game of Life with a large asymmetric neighborhood.}
\label{large asymmetric life}
\end{figure}

\begin{figure}[t]
\begin{center}
\begin{verbatim}
             2 dimensions of
                     x, y of 0..255
             end

             cell.x := ([1, 0].y + [0, 1].y + [-1, 0].y + [0, -1].y) % 256 
                             when time % 2

             cell.y := ([-1, 1].x + [1, 1].x + [-1, -1].x + [1, -1].x) % 256 
                             when (time + 1) % 2
\end{verbatim}
\end{center}
\caption{Multi-field cells with time dependent neighborhoods.}
\label{multi-field time life}
\end{figure}

The game of Life, created by Cambridge mathematician John Horton 
Conway and popularized by Martin Gardener\cite{life},
demonstrates many of the features of {\em Cellang}.  
Figure~\ref{simple life}
shows a {\em Cellang} program for this problem.  Note
that the universe of cells is 2--dimensional, each having either a 0 or
1 value.  Comments begin
with a sharp (\#) and continue to the end of that line.  The predefined variable
{\tt cell} is special as it refers to the current cell of the universe under 
consideration.
Assignment to the variable {\tt cell} is the only way in which the value 
of the current cell (or one of its fields)
can be altered.  Furthermore, the new value of {\tt cell} doesn't take effect
until the beginning of the next cycle.  Notice that the standard Moore 
neighborhood used by the
game of Life must be given by relative indexing.\footnote{
                Relative indexing specifies a cell relative to the
                current cell.  Thus the relative index ``[-1, 1]''
                refers to the bordering northwest cell.
        }
While relative indexing may seem cumbersome,
it provides great flexibility.  The only practical restriction on relative 
indices is that they be integer constants or {\tt forall} statement index
variables (discussed below).

Because there are no language specific limits on the size of relative indices,
it is possible to explore a wide range of neighborhoods.
Neighborhoods which use field values {\em n} cells away are possible 
for any value of integer value {\em n}.
In addition, there is no restriction that neighborhoods
be symmetrical or have any other special topological properties.
This is exemplified by the program in Figure~\ref{large asymmetric life}, which
uses {\tt forall} statements to successively reference the neighboring cells.
The single index variable takes on the successive values given in the range of
values specified after the colon (:).  The lower and upper bound of the
range must be integer constants.

The predefined variable,
{\tt time}, indicates the number of computational time steps that have been
executed thus far.  In order to prevent corruption of its value, {\tt time}
can only appear within expressions,
where it can be used to influence
computation.  The initial value of {\tt time} is 0 and it is incremented by 1 
each time all the cells of the universe have been updated.
This feature allows neighborhoods which
are time dependent.
Similarly it is also possible to have cell field values change
with dependence upon time.
The time dependent neighborhoods can be used to represent both
hybrid neighborhoods
or situations where the physical system behaves
according to different rules/neighborhoods as it ages.

{\em Cellang} programs may also contain more than a single field
per cell.  Figure~\ref{multi-field time life} shows a program with 
2 fields per cell which also uses a time dependent neighborhood.
Note that the dot notation familiar from many other languages for use
with records/structures is used here to determine which of several
cell fields is being denoted.  If, on the other hand, the field name is 
not present, then all fields of the cell are used in
assignment and for tests of equality and inequality.

Finally, both the input and output of {\em Cellang} programs
allow the user to manipulate cellular automata data in ways that many
systems do not permit.  Both input and output are of identical form,
thus allowing automata to be chained together.  Both
input and output are given as a sequence of time blocks.  A time block
begins with a time (a non-negative integer value) followed by zero or more
cell location and value pairs.  When multiple time blocks are given,
successive times must be strictly greater than all previous times.
An example set of time blocks for a 2--dimensional automata is given in
Figure~\ref{time blocks}.  It specifies that although
all the cells of the universe have a default value of 0 at time
0, the cell at absolute location 3, 3 will have a value of 1.  Furthermore,
it specifies that at the beginning of time 100 (before any cells have been
updated), the cell at absolute location 24, 56 has its first field set to 0,
the cell at absolute location 50, 50 has its first field set to 5 and it second
field set to 6, and the cell at location 2, 32 has its third field set to 3.
This cell value input process continues for
as many time blocks as are in the input.  The output of a {\em Cellang}
program has the same form and can thus appear as input to another
automata.  If each cell has several values which must be set, then the
multiple values are separated by commas and are assigned in the order in
which they were declared in the associated {\em Cellang} program.  When
only some of the possible field values are given, then the values
are assigned in order until no more are available, the unspecified cell fields 
retaining their previous values.
\begin{figure}[t]
\begin{center}
\begin{verbatim}
                                    0
                                    [3, 3] = 1
                                    100
                                    [24, 56] = 0
                                    [50, 50] = 5, 6
                                    [2, 32] = , , 3
\end{verbatim}
\end{center}
\caption{An example input/output for a {\em Cellang} program}
\label{time blocks}
\end{figure}

\section{The Viewer}

The viewer, which is used to examine the cell values in a graphic manner, is
independent of the {\em Cellang} language and compiler.  The input
to the viewer is identical in form to the output (and thus the input)
of {\em Cellang} programs.  The viewer allows the viewing of
a single field along contiguous portions of any two dimensions.
The values can be displayed as 
colored squares (via either X-Windows, the IRIS Graphics Library
library, or VGA under DOS).  A limited debugging
aid (available only with the X-Windows and IRIS Graphics Library viewing 
options) also allows the numeric 
values of a neighborhood of cells (as opposed
to the color associated with this value) to be viewed.

The idea of separating the language (and thus the cellular automata
simulator) and the viewer allows
greater flexibility both in the viewing of data and in the creation of
cellular automata.  There is no restriction that
the input to the viewer be generated by a {\em Cellang} program, and it
is possible that programs of other sorts will be developed
to examine, gather and report statistics concerning the results of
{\em Cellang} programs.  ``Valve'' filters
could be inserted between the output generated by a {\em Cellang}
program and the input to the viewer.  Such a valve program could allow
the presentation speed to be tailored to the researcher's needs.
Since the output of {\em Cellang} programs can be sent
to the standard output, it can be piped directly
into the viewer with no need for intermediate storage files.  The
use of a tpipe filter would enable all or part of the
produced cell values to be captured in a file during viewing.

\begin{figure}[t]
\begin{center}
\begin{verbatim}
                                          50
                                          +1
                                          100
                                          500!
\end{verbatim}
\end{center}
\caption{An example time file for reporting cell values}
\label{report times}
\end{figure}

\section{Compiling \& Viewing}

Suppose the {\em Cellang} program for the game of Life that appears in 
Figure~\ref{simple life} is in the file {\tt life}.
A compiled version of the code is obtained by doing {\tt cellc life}
which places the object code into a file called {\tt avcam.out}.
The object code is executed and displayed by the {\tt avcam} 
abstract machine via:
\begin{verbatim}
        avcam -c avcam.out -r times -x11 -map life.colors < life.data
\end{verbatim}
where {\tt life.data} is a data file containing the 
initial configuration of live cells and
{\tt life.colors}
contains a suitable color map.
An optional parameter, {\tt -f},
is used to indicate which field (starting from 1 for the first field) to 
use as the value to display for the cells.
The {\tt -r} option indicates a file which contains information about
which generations to report cell values for.  

If the {\tt -r} option is not given
then the cell values which have changed will be reported for each generation.
A sample time file appears in Figure~\ref{report times}.  A time file is a list
of time indications given one per line.  A number indicates a 
time when the values should be
reported, while a ``+'' entry causes these values to be produced at the 
indicated time intervals.  Finally a ``!'' entry determines the time at
which the last set of values should be produced and the simulation stops.
Note that time files need not contain a ``!'' entry.  In the example,
The first set of values (after time 0) is produced at time 50, then at each 
time thereafter until time 100 at which point no values are reported 
until time 500 and the simulation stops.

Alternatively, {\tt avcam} can just output the cell values which can be
filtered and/or viewed with {\tt cellview}.  An example of this style of
use is:
\begin{verbatim}
        cat  life.data | avcam -r times -o |
                                 cellview -x11 -map life.colors -dim 0..63,0..63
\end{verbatim}
Where the {\tt -o} option indicates that cell values be written to the
standard output (as opposed to being viewed directly by using one of the
{\tt -x11}, {\tt -iris}, or {\tt -vga} options).  The ``-c avcam.out'' has 
been left out, since the
the codefile is assumed to be ``avcam.out'' by default.
Note that now, however, the dimensions of the cell universe must be known.
By convention, the cell universe begins numbering at 0 for
each dimension.  The size and number of dimensions is implementation
dependent (and both can be configured at compile time in the current 
release of the software).

\section{Advanced Examples and Additional Language Features}
This section examines two example programs that demonstrate techniques for
generating the Margolus and hexagonal neighborhoods.  The Margolus
neighborhood will be used in the simulation of the diffusion of a 
gas,\footnote{
		The program is modeled closely on the version
		described by \cite{toffoli} on page 156.
	}
while the hexagonal neighborhood is used to implement a lattice gas automata.

\begin{figure}[t]
\hspace{1.08in}
\setlength{\unitlength}{3pt}
\begin{picture}(31, 31)(0, 0)
\normalsize

\put(0, 20){\framebox(10, 10){0}}
\put(10, 20){\framebox(10, 10){1}}
\put(10, 10){\framebox(10, 10){3}}
\put(0, 10){\framebox(10, 10){2}}

\put(11, 9){\dashbox(10, 10){}}
\put(21, 9){\dashbox(10, 10){2}}
\put(21, -1){\dashbox(10, 10){0}}
\put(11, -1){\dashbox(10, 10){1}}

\end{picture}
\vspace{-1.25in}
\begin{verbatim}
                                                       0 1 0 1 0 1 0 1 0 1
                                                       2 3 2 3 2 3 2 3 2 3
                                                       0 1 0 1 0 1 0 1 0 1
                                                       2 3 2 3 2 3 2 3 2 3
\end{verbatim}
\vspace{0.5in}
\caption{Margolus neighborhood and the pattern of {\tt which} field values}
\label{Margolus neighborhood}
\end{figure}

\begin{figure}[t]
\begin{center}
\begin{verbatim}
        2 dimensions of 
                which of 0..3
                rand  of 0..1
                gas   of 0..1
        end
        
        neighbor[] for this, cw, ccw, opp
        
                := cell, [1, 0], [0, -1], [1, -1]
                        when (cell.which=0 & time%2=1) | (cell.which=3 & time%2=0)
        
                := cell, [0, -1], [-1, 0], [-1, -1]
                        when (cell.which=1 & time%2=1) | (cell.which=2 & time%2=0)
        
                := cell, [-1, 0], [0, 1], [-1, 1]
                        when (cell.which=3 & time%2=1) | (cell.which=0 & time%2=0)
        
                := cell, [0, 1], [1, 0], [1, 1]
                        otherwise
        
        # Calculate the sum of the random fields in the neighborhood.
        #
        random := cell.rand + cw.rand + ccw.rand + opp.rand
        
        cell.gas := ccw.gas when random%2 = 1   # Clockwise rotation
                 := cw.gas otherwise            # Counter-clockwise rotation
        
        # Stir the random values using a von neumann neighborhood.
        #
        cell.rand := ([1, 0].rand + [0, 1].rand + [-1, 0].rand + [0, -1].rand
                        + cell.rand)%2
\end{verbatim}
\end{center}
\caption{Gas diffusion using a Margolus neighborhood}
\label{gas diffusion}
\end{figure}

\begin{figure}[t]
\hspace{0.35in}
\setlength{\unitlength}{3.15pt}
\begin{picture}(80, 60)(0, 0)

\multiput(10, 40)(20, 0){3}{\framebox(10, 20)
	{\shortstack{\,n\vspace{1ex}\\
			\, nw \  ne \vspace{5.6ex}\\
			\, sw \ \, se \vspace{1ex}\\
			s}}}
\multiput(10, 20)(20, 0){3}{\framebox(10, 20)
	{\shortstack{\,n\vspace{1ex}\\
			\, nw \  ne \vspace{5.6ex}\\
			\, sw \ \, se \vspace{1ex}\\
			s}}}
\multiput(10, 0)(20, 0){3}{\framebox(10, 20)
	{\shortstack{\,n\vspace{1ex}\\
			\, nw \  ne \vspace{5.6ex}\\
			\, sw \ \, se \vspace{1ex}\\
			s}}}

\multiput(0, 30)(20, 0){4}{\framebox(10, 20)
	{\shortstack{\,n\vspace{1ex}\\
			\, nw \  ne \vspace{5.6ex}\\
			\, sw \ \, se \vspace{1ex}\\
			s}}}
\multiput(0, 10)(20, 0){4}{\framebox(10, 20)
	{\shortstack{\,n\vspace{1ex}\\
			\, nw \  ne \vspace{5.6ex}\\
			\, sw \ \, se \vspace{1ex}\\
			s}}}

\end{picture}
\vspace{-2in}
\begin{verbatim}
                                                             1 0 1 0 1 0 1 0 1 0
                                                             0 1 0 1 0 1 0 1 0 1
                                                             1 0 1 0 1 0 1 0 1 0
                                                             0 1 0 1 0 1 0 1 0 1
                                                             1 0 1 0 1 0 1 0 1 0
                                                             0 1 0 1 0 1 0 1 0 1
\end{verbatim}
\vspace{1.0in}
\caption{A ``squeezed'' hexagonal section and the pattern of {\tt which} field values}
\label{hexagons}
\end{figure}

\begin{figure}[t]
\begin{center}
\begin{verbatim}
     2 dimensions of 
             which of 0..1

             # The presence (1) of a particle traveling in the given direction.
             particle[] for n, ne, se, s, sw, nw of 0..1
     end
           
     # Hexagonal neighborhood.
     #
     neighbor[] for 6
             := [0, 1], [1, 0], [1, -1], [0, -2], [-1, -1], [-1, 0] when cell.which
             := [0, 2], [1, 1], [1, 0], [0, -1], [-1, 0], [-1, 1] otherwise
           
     # Find out how many particles are incident on this cell.
     #
     count := 0
     forall i
             count := count + 1 when neighbor[i].particle[i+%3] > 0
     end
           
     if count % 2 = 1 then
             #
             # Simulate a collision by random rotation.
             #
             forall i
                     cell.particle[i+%1] := neighbor[i+%3].particle[i] when cell.random
                     cell.particle[i-%1] := neighbor[i+%3].particle[i] otherwise
             end
     else
             #
             # Particles travel through undisturbed.
             #
             forall i
                     cell.particle[i] := neighbor[i+%3].particle[i]
             end
     end
\end{verbatim}
\end{center}
\caption{Lattice gas automata using a hexagonal neighborhood}
\label{lga}
\end{figure}

\subsection{Margolus Neighborhood}
Gas diffusion can be simulated by implementing a random walk for each
particle/molecule of gas.
The random walk can be implemented by using non-overlapping
blocks of four cells (two on a side) which are offset at alternate times
(Margolus neighborhood) and having each block of cells randomly rotate their 
gas particles either clockwise or 
counter-clockwise.

To better understand the Margolus neighborhood, consider 
Figure~\ref{Margolus neighborhood}.  The four cell block with a solid
outline, and the other with the dashed outline, would be used at
alternate times.  At any particular time, however, the universe of cells 
is completely covered by a non-overlapping set of blocks.  To implement
a Margolus neighborhood in {\em Cellang} requires use of the {\tt
time} variable and some way of distinguishing between different blocks
of 4 cells.  The latter is accomplished by introducing a field, {\tt which},
that contains a value, 0 to 3, indicating the cells relative position in
the block.  A portion of the cell universe {\tt which} values
are also shown in Figure~\ref{Margolus neighborhood}.

Now that the four cell block can be identified, a random number, common
to each cell in the block, must be generated.  This is done by having
each cell maintain a two value (0 or 1) {\tt rand} field.  By using {\tt time}
and the value of {\tt which} a random number, ``shared'' by each cell of the
block, can be calculated.  This random number is used to determine whether
the particles of gas, denoted by the value of the {\tt gas} fields,
are rotated clockwise or counter-clockwise.
To maintain an ever changing {\tt rand} field
for each cell, a new value is calculated using the Von Neumann neighborhood.

The {\em Cellang} program that implements gas diffusion is shown in 
Figure~\ref{gas diffusion}.  Note the implicit declaration and use of the
array variable {\tt neighbor}.  The intent is for arrays to act solely
as an alias for a group of closely related variables.  The first
lexical occurrence of an array associates it with the variables for which
it forms an alias.  Thus, the variables may either be referenced individually
by using their names, or collectively by using the array.
Note too that no bounds are given for the array at its first point of lexical
usage (which will always be as the left hand side of an assignment) and that 
its size is inferred from the number of variable names given
for which it is to act as an alias.  The simplest way to assign initial
values to an array is by using an empty index ([ ]) and giving the proper
number of values, separated by commas, to assign to the corresponding array
elements.  If only one value is given, then all elements of the array are
assigned that value.\footnote{
		This is very useful when working with large arrays
		(e.g. {\tt array[] for 256 := 0}).
	}
In this program the elements of the array
were always referenced using their individual names.

\subsection{Hexagonal Neighborhood}
Hexagonal neighborhoods exhibit properties desirable in the simulation
of many physical systems.  Fortunately, they are quite easy to build
in {\em Cellang}.  Simply imagine taking a hexagon and squeezing in
at the sides, creating a two cell stack.  Doing this for the
entire cell universe is depicted in Figure~\ref{hexagons}.  The solid
lines show the boundary of the original hexagon.  The sides of the
hexagons have been labeled, clockwise from the top, n (north), 
ne (northeast), se (southeast), s (south), sw (southwest) and nw (northwest).

In order to have the cells act as sets of 2 block stacks, a {\tt which}
field with the value pattern depicted in Figure~\ref{hexagons} is
used.  The value 1 represents the top cell in a pair, while 0 denotes
the bottom cell.  Note that the top cell of a pair gets its s (south)
value by skipping over the bottom cell of the pair, likewise the bottom
cell skips over the top one for its n (north) value.  Thus each cell
pair agrees on the relative location of neighboring values.  Note that
this requires that initial (and subsequent) values for fields of cells
given as input must be coordinated with the assignment to the {\tt which}
fields, otherwise one or more cell pairs will have only one of the pair
getting the desired value.\footnote{
	In order to more accurately display (under X-Windows, IRIS Graphics
	Library, or using VGA under DOS) the height:width ratio of 
	the ``hexagons'', the option 
	``--s 5,3'' to {\tt avcam}/{\tt cellview} makes the displayed 
	cells 5 pixels wide and 3 pixels high.
}

The lattice gas automata program in Figure~\ref{lga} demonstrates several
additional features regarding arrays and {\tt forall} statements.  First,
array aliases can also appear as fields of cells (i.e. {\tt particle}).
The second is that the index variables of {\tt forall} statements can be
used to index the different elements of the array, and that the range of
an index variable used in this manner can be automatically inferred by its
use (inferred ranges always have a lower bound of zero).  Finally, the 
modulo arithmetic operations +\% and --\% can be used
in conjunction with index variables to perform both addition and subtraction
operations modulo the range of that index variable.

The {\tt forall} statement is the preferred mechanism for indexing all of the 
values of an array.\footnote{
	If only some values are desired, their individual names 
	or an absolute reference (e.g. {\tt array[3]}) should be used.
	Note that absolute references are based on a lower bound of zero (0).
	}
Only one index variable can be given in a {\tt forall}.  It can act as
an index into one or more arrays that appear in the statement(s) of
the body of the {\tt forall}.  An index variable can be indicated either simply
as a variable name or as the variable name followed by a colon (:) and a
range of values that the variable should have during consecutive iterations
through the loop.
When the range of values for an index variable has been specified by the
programmer, the size of the range must be equal to the number of elements for
any array for which it is used as an index.  Furthermore, the successive
values of the index correspond to the successive elements of the array it
indexes (beginning
with the first named variable given in its declaration) regardless of the
value of the bounds given for the range of the index variable.  In this way,
different ranges can be specified to best suit the needs of the programmer
for that particular loop. If no range was specified, then its lower bound
is taken as 0 and the size of the range is inferred from its use in the
statements contained in the loop body.

It is also necessary to provide a mechanism to
look at values in the array at some constant offset from the the current value
of the index.  This is accomplished by using the +\% and --\% indicators
which ``circular shift'' the array in the desired direction from position 
the current index value would otherwise indicate.  More formally, a circular
shift is an addition/subtraction modulo the size of the index variable range.
Thus if the range of the
index variable {\tt i} is {\tt 0..5} and the value is {\tt 4}, then the
result of {\tt i+\%3} is {\tt 1}.  The modulo operations are extremely
useful in combination with arrays. 

\begin{figure}[t]
\begin{center}
\begin{verbatim}
        2 dimensions of
                # A value of 1 indicates the presence of a bumper.
                bumper of 0..1
        agent of
                # Indicates the direction of travel for the agent.
                # (1 = north, 2 = east, 3 = south, 4 = west)
                direction of 1..4
        end

        # Count the number of agents associated with this cell.
        count := 0
        forall a:agent
                count := count + 1
                ball := a
        end

        # Only single agents do anything.
        if count = 1 then
                if cell.bumper then
                        # The agent has collided with a bumper and divides.
                        if ball.direction = 1 then
                             agent(2) -> [1, 0]
                             agent(4) -> [-1, 0]
                        elsif ball.direction = 2 then
                             agent(1) -> [0, 1]
                             agent(3) -> [0, -1]
                        elsif ball.direction = 3 then
                             agent(2) -> [1, 0]
                             agent(4) -> [-1, 0]
                        else
                             agent(1) -> [0, 1]
                             agent(3) -> [0, -1]
                        end
                else
                        # The agent continues to travel.
                        ball -> [0, 1]  when ball.direction = 1
                             -> [1, 0]  when ball.direction = 2
                             -> [0, -1] when ball.direction = 3
                             -> [-1, 0] when ball.direction = 4
                end
        end
\end{verbatim}
\end{center}
\caption{A ``pinball'' simulation using agents}
\label{pinball}
\end{figure}

\begin{figure}[t]
\begin{center}
\begin{verbatim}
                                    0
                                    [32, 20] = 1, 1
                                    [32, 40] = 1, 2
                                    [20, 32] = 1, 3
                                    [40, 32] = 1, 4
                                    [32, 32] =  , 2
                                    [10, 10] =  , 1, 3
\end{verbatim}
\end{center}
\caption{An example input/output for a {\em Cellang} program with agents}
\label{agent time blocks}
\end{figure}

\subsection{Agents}
Although it is possible to move a value group from one cell to another cell 
using classical cellular automata techniques, it is an error plagued process.
These techniques invariably consist of two phases, each of which occurs during
alternate time steps.  The first phase determines which cell to move to, while
the second phase actually performs the operation.  Not only is programming 
complicated by this process, but the basic movement algorithm lies buried
deep within the resulting code and is thus not easily accessible to the reader.
Agents allow movement to be specified more clearly, concisely, and easily
than is possible by using classical cellular automata techniques alone.  The
agents of {\em Cellang} are an adaptation of those found in the 
{\em Creatures}\cite{Creatures} system.

The program in Figure~\ref{pinball} shows a {\em Cellang} program for an
odd sort of pinball game.   The pinball game consists of balls and bumpers.
The balls move around in the cell universe and split into two balls whenever
they encounter a bumper.  Each ball in the simulation has its own direction
of travel, which it maintains until it encounters either a bumper or another
ball.  If two or more balls meet, they annihilate one another.  

Several of the language features already discussed support the use of agents.
The cell declaration can consist of two parts.  The first specifies {\tt bumper}
as a classic cellular automata field, while the second indicates that the field
{\tt direction} is a part of every agent.  A cell can have zero (0) or 
more agents associated with it at any time.  In addition, the {\tt forall}
statement supports the iteration through all of the agents associated with the
current cell by specifying {\tt agent} as the range of iteration.  The 
assignment statement can also be used in conjunction with agents.  In the case
of the pinball program, the first {\tt forall} statement is counting the
number of agents associated with this cell.  The implicitly declared variable
{\tt ball} is used to remember the value of one of the agents.  Assuming that
there is only one agent associated with the cell, {\tt ball} will be the
value of that agent.

By default, agents cease to exist (and thus to be associated with a given cell)
at the end of every time step.  In order to have agents reappear during the
next time step, they must be explicitly propagated by the use of an agent
statement.  The agent statement is conditional in the same manner as the
assignment statement, and indicates which cell (appearing on the right of
the {\tt ->}) the agent on the left should be associated with during
the next time step.  New agent values can be created 
(e.g. {\tt agent(1) -> [0, 1]}) or an existing value can
be reassociated (e.g. {\tt ball -> [0, 1] when ball.direction = 1}).
Thus to have two or more balls annihilate one
another upon colliding, simply do {\em not} recreate/reassociate them.

The input and output of agent field values is an extension of that for cell 
field values.  Figure~\ref{agent time blocks} shows a sample input time block 
for use with the pinball program.  Cell field values are always given first,
with any fields beyond that specifying zero (0) or more agents.  Thus
the first four cell locations have bumpers with a single agent at each of
those cells.  Agents are
specified in field groups, with all of the fields specified in the cell
declaration being used before another agent is created and associated with
the indicated cell.  As with cell field values, agent field values
can be skipped by simply giving the comma (,) with no value.  The next to the
last line of Figure~\ref{agent time blocks} specifies no change in the
{\tt bumper} field, but does place a single east bound agent.  Alternatively,
the last line shows no change in the {\tt bumper} field, but places two
agents at the cell, one traveling north and one going south.
Output of agents is done in a similar manner.
On output, however, only the agent field values of existing agents will be 
output.  Thus, when an agent is no longer associated with a cell {\em only} its 
absence from the output is an indicator of this change.

One final note concerning agents: programs should make no assumptions
concerning the order in which agents are associated with a cell.  Thus,
multiple {\tt forall} statements which iterate through the agents associated 
with a cell might present the agents in a different order for the same cell
during the same time step.  Likewise, the order in which agents and input
and output does not necessarily reflecting the ordering that may be seen
with a {\tt forall} statement.  

\section{Current Status and Availability}
The current implementation of the {\em Cellang} compiler, as a part of
the {\em Cellular} system, generates code for both uni-processor
and shared-memory multi-processor systems.
The entire system is written in C and the compiler produces C as an
intermediate code, making the system highly portable.

The {\em Cellular} system is designed to be compiled under both the UNIX
and DOS operating system and currently supports the viewing of automata using 
either X-Windows (UNIX), IRIS Graphics Library (UNIX), or VGA (DOS). 
Instructions on the where to get a copy of the system can be obtained
by contacting the author.

\begin{thebibliography}{99}

\bibitem{Boghosian}
Bohgosian, Bruce M., ``A Cellular Automata Simulation of Two-Phase Flow on
the CM-2 Connection Machine Computer'', {\em Proceedings of Supercomputing
'88, Volume II: Science and Applications}, IEEE Computer Science Press,
(1988), 34--44.

\bibitem{Chen}
Chen, Shiyi, Hudong Chen and Gary D. Doolen,
``How the Lattice Gas Model for the Navier-Stokes Equation Improves When
a New Speed is Added'', {\em Complex Systems}, {\bf 3} (1989), 243--251.

\bibitem{wireworld}
Dewdney, A. K., ``The Cellular Automata Programs That Create Wireworld,
Rugworld and Other Diversions'',
{\em Scientific American}, {\bf 262}:1 (January 1990), 146--149.

\bibitem{crystals}
Dewdney, A. K., ``A Cellular Universe of Debris, Droplets, Defects and Demons'',
{\em Scientific American}, {\bf 261}:2 (August 1989), 102--105.

\bibitem{fluids}
Dewdney, A. K., ``The Hodgepodge Machine Makes Waves'',
{\em Scientific American}, {\bf 259}:2 (August 1988), 104--107.

\bibitem{life}
Gardner, Martin,
``The Fantastic Combinations of John Conway's New Solitaire Game of `Life','',
{\em Scientific American}, {\bf 223}:4 (April 1970), 120--123.

\bibitem{harbison}
Harbison, Samuel P. and Guy L. Steele Jr., {\em C: A Reference Manual},
Prentice Hall, Englewood Cliffs, New Jersey, 1991.

\bibitem{cellsim}
Langton, Chris and Dave Hiebeler, {\em Cellsim}, available by anonymous
ftp from isy.liu.se, Version 2.5.

\bibitem{Lim}
Lim, Hwa A., ``Lattice Gas Automata of Fluid Dynamics for Unsteady Flow'',
{\em Complex Systems}, {\bf 2} (1988), 45--58.

\bibitem{neumann}
von Neumann, John, {\em Theory of Self--Reproducing Automata}, edited and
completed by A. Burks, University of Illinois Press, Champaign, IL (1966).

\bibitem{Scamper}
Palmer, Ian J., {\em Scamper}, available by anonymous ftp from ftp.uu.net.

\bibitem{SLANG}
Sieburg, Hans B. and Oliver K. Clay, ``The Cellular Device Machine Development
System for Modeling Biology on the Computer'', {\em Complex Systems},
{\bf 5} (1991), 575--601.

\bibitem{Creatures}
Stephenson, I., {\em Creature Processing: An Alternative Cellular Architecture},
Technical Report ASEG92.04, Department of Electronics, University of York.

\bibitem{Teixeira}
Teixeira, Christopher M.,
{\em Continuum Limit of Lattice Gas Fluid Dynamics}, PhD Thesis, M.I.T.
Department of Nuclear Engineering, Sep 1992.

\bibitem{toffoli}
Toffoli, Tommaso and Norman Margolus,
{\em Cellular Automata Machines: A New Environment for Modeling},
The MIT Press, Cambridge, Massachusetts, 1987.

\bibitem{ulam}
Ulam, Stanislaw, ``Random Processes and Transformations'', {\em Proceedings of
the International Congress on Mathematics}, 1950, Vol. 2 (1952), pp. 264--275.

\end{thebibliography}

\end{document}
