Source Code 1994 March/Source_Code_CD-ROM_Walnut_Creek_March_1994.iso/compsrcs/unix/volume26/celllr20/part03

Text File | 1993-04-02 | 81.3 KB | 2,648 lines

Newsgroups: comp.sources.unix
From: [e-mail] (J Dana Eckart)
Subject: v26i090: cellular-2.0 - a cellular automata language, Part03/03
Sender: [e-mail]
Approved: [e-mail]

Submitted-By: [e-mail] (J Dana Eckart)
Posting-Number: Volume 26, Issue 90
Archive-Name: cellular-2.0/part03

#! /bin/sh
# This is a shell archive.  Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file".  To overwrite existing
# files, type "sh file -c".  You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g..  If this archive is complete, you
# will see the following message at the end:
#        "End of archive 3 (of 3)."
# Contents:  compiler/semantic.c tutorial.tex
# Wrapped by [e-mail] on Sat Apr  3 01:27:39 1993
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f 'compiler/semantic.c' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'compiler/semantic.c'\"
else
echo shar: Extracting \"'compiler/semantic.c'\" \(50650 characters\)
sed "s/^X//" >'compiler/semantic.c' <<'END_OF_FILE'
X/* semantic.c
X   Copyright (C) 1992  J Dana Eckart
X
X   This program is free software; you can redistribute it and/or modify
X   it under the terms of the GNU General Public License as published by
X   the Free Software Foundation; either version 1, or (at your option)
X   any later version.
X
X   This program is distributed in the hope that it will be useful,
X   but WITHOUT ANY WARRANTY; without even the implied warranty of
X   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
X   GNU General Public License for more details.
X
X   You should have received a copy of the GNU General Public License
X   along with CELLULAR-2.0; see the file COPYING.  If not, write to the
X   Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
X*/
X
X/* This file contains the semantic routines (and their respective
X   support functions) for checking static semantics and generating
X   the intermediate representation (C code).
X
X   The names of variables are preceeded by an underscore ("_") in the C
X   code for the rule set of the cellular automata.  All other variables
X   generated by the compiler (and not appearing in the rule set of the
X   input) are NOT preceeded by a "_" (underscore); thus guaranteeing no
X   name conflicts (defines are given in capitals to prevent name conflicts).
X
X   NOTE: The comments given for semantic routines give the items that
X     the routine expects and leaves on the semantic stack.  In both
X     cases, the top of the stack is the leftmost item given.
X*/
X
X#include <stdio.h>
X#include <string.h>
X#include <limits.h>
X#include "boolean.h"
X#include "error.h"
X#include "semantic.h"
X#include "attribute.h"
X#include "symtable.h"
X#include "stack.h"
X
X/* The following declarations determine how many dimensions the cellular
X   universe can have and how many fields each cell is allowed.
X*/
X#include "size.h"
X
XFILE *file_h = NULL;        /* Denotes the C header output stream. */
XFILE *file_c = NULL;        /* Denotes the C code output stream. */
X
X#define MAX_STRING_LENGTH    256
X
boolean semantic_error = false;    /* Indicates if a semantic error has occured. */
X
X#define MAX_STACK_SIZE     25    /* Size of the semantic stack. */
X
stack_entry stack[MAX_STACK_SIZE];    /* The semantic stack. */
int top = -1;                /* Current top of semantic stack. */
X
X/* SUPPORT ROUTINE
X      ACTION - Increments top.  This provides checking so that pushes
X           onto the semantic stack are checked to insure that an
X           overflow does not occur.
X*/
void new_entry() {
X    if (top == MAX_STACK_SIZE - 1) {
X        fprintf(stderr, "INTERNAL ERROR: Semantic stack overflow.\n");
X        exit(1);
X    }
X    top++;
X}
X
X/************************************************************************/
X
X/* SUPPORT ROUTINE
X      ACTION - Prints an error message using the provided format
X           and input string, preceeded by the current line
X           number of the input stream.  A flag specifing that
X           a semantic error was encountered is also set to true.
X*/
void error(format, string) char *format, *string; {
X    semantic_error = true;
X    error_prefix();
X    fprintf(stderr, format, string);
X    fprintf(stderr, "\n");
X}
X
X/************************************************************************/
X
X/* Indentation to make the generated C code easier to read is
X   accomplished by using print_indent.  The amount of indentation
X   is kept in the "indentation" variable, whose value is updated
X   through use of the macros "indent" and "undent".
X*/
X
int indentation = 0;
X
X#define indent    indentation += 3
X#define undent    indentation -= 3
X
X/* SUPPORT ROUTINE
X      ACTION - Prints the current amount of indentation to the
X           specified file.
X*/
void print_indent() {
X    int i;
X    for (i = 0; i < indentation; i++) fprintf(file_c, " ");
X}
X
X/************************************************************************/
X
X/* SUPPORT ROUTINE
X      ACTION - Checks the top n entries (0 checks NO entries) on
X           top of the stack and returns true iff at least one
X           of them is a StackError entry.
X*/
boolean stack_error(n) int n; {
X    int i;
X    if (n-1 > top)
X        error("COMPILER ERROR -- too few entries on semantic stack\n",
X            (char*) NULL);
X    for (i = 0; i < n; i++)
X        if (stack[top-i].kind == StackError) return true;
X    return false;
X}
X
X/************************************************************************/
X
X/* A current count of the number of dimensions. */
int dimension_count = 0;
X
X/* Used to count the number of fields declared for the cells of the universe. */
int field_count;
X
X/* SUPPORT ROUTINE
X      ACTION - Enter the predefined identifiers "time" and "cell" into the
X           symbol table.
X*/
void decl_time_and_cell() {
X    attr_rec attribute;
X
X    /* Enter the predefined symbols "cell" and "time". */
X    attribute.assignable = true;
X    attribute.field_name = false;
X    attribute.structured = field_count > 1;
X    enterid("cell", attribute);
X
X    attribute.assignable = false;
X    attribute.field_name = false;
X    attribute.structured = false;
X    enterid("time", attribute);
X}
X
X/************************************************************************/
X
X/* SEMANTIC ROUTINE
X      EXPECTS - StackExpr
X      LEAVES  - n/a
X      ACTION  - Set the number of dimensions in the cellular automata
X        universe to that indicated by the top of the stack.
X*/
void set_dimensions() {
X    if (stack_error(1)) {
X        top--;
X        return;
X    }
X    else {
X        dimension_count = atoi(stack[top--].data.expr.addr);
X
X        /* Make sure not too many dimensions are used. */
X        if (dimension_count > MAX_SUPPORTED_DIMENSIONS)
X            error("Sorry, no more than %d dimensions are supported",
X                  (char*) MAX_SUPPORTED_DIMENSIONS);
X    }
X}
X
X/* Holds the field names given in the cell declaration, along with their
X   upper and lower bounds, in the order they were declared.
X*/
struct {
X    char *name;
X    long int lb, ub;
X} field_list[MAX_SUPPORTED_FIELDS];
X
X/* SEMANTIC ROUTINE
X      EXPECTS - n/a
X      LEAVES  - n/a
X      ACTION  - Start the cell type declaration.
X*/
void begin_decl_cells() {
X    field_count = 0;
X
X    /* Begin the cell type declaration. */
X    fprintf(file_c, "typedef struct {\n");
X    indent;
X}
X
X/* SEMANTIC ROUTINE
X      EXPECTS - n/a
X      LEAVES  - n/a
X      ACTION  - Writes code to declare the cell type of the cells which
X        make up the cellular automata universe.
X*/
void end_decl_cells() {
X    int i;
X
X    /* Finish the cell declaration. */
X    undent;
X    print_indent();
X    fprintf(file_c, "} cell_type;\n\n");
X
X    /* Make sure not too many fields are used. */
X    if (field_count > MAX_SUPPORTED_FIELDS)
X        error("Sorry, no more than %d fields are supported",
X              (char*) MAX_SUPPORTED_FIELDS);
X
X
X    /* Write the function definition for "neq". */
X    print_indent();
X    fprintf(file_c, "int neq(x,y) cell_type *x, *y; {\n");
X    indent;
X    print_indent();
X    fprintf(file_c, "return (");
X    for (i = 0; i < field_count; i++) {
X        fprintf(file_c, "(x->%s == y->%s)",
X            field_list[i].name, field_list[i].name);
X        if (i < field_count - 1)
X            fprintf(file_c, "||");
X    }
X    fprintf(file_c, ");\n");
X    undent;
X    print_indent();
X    fprintf(file_c, "}\n\n");
X
X    /* Write the function definition for "assign_cell". */
X    print_indent();
X    fprintf(file_c, "void assign_cell(x,y) cell_type *x, *y; {\n");
X    indent;
X    for (i = 0; i < field_count; i++) {
X        print_indent();
X        fprintf(file_c, "x->%s = y->%s;\n",
X            field_list[i].name, field_list[i].name);
X    }
X    undent;
X    print_indent();
X    fprintf(file_c, "}\n\n");
X}
X
X/************************************************************************/
X
X/* SEMANTIC ROUTINE
X      EXPECTS - StackRange, StackToken, ... StackToken, StackMark
X      LEAVES  - n/a
X      ACTION  - Take the list of field identifiers from the stack and
X        delcare them with the given range.  No code is generated.
X*/
void declare_fields() {
X    int mark;
X    range_entry range = stack[top--].data.range;
X
X    /* Go down to the mark. */
X        mark = top;
X    while (stack[mark].kind != StackMark) mark--;
X
X    /* Enter each of the fields into the symbol table. */
X    while (++mark <= top) {
X        char *token = stack[mark].data.token;
X
X        /* Enter into symbol table if necessary. */
X        if (!intable(token, FIELD)) {
X            attr_rec attribute;
X            attribute.assignable = true;
X            attribute.field_name = true;
X            attribute.structured = false;
X            enterid(token, attribute);
X
X            print_indent();
X            fprintf(file_c, "%s %s;\n", FIELD_TYPE, token);
X        }
X        else
X            error("Redeclaration of field, '%s'", token);
X
X        field_list[field_count].name = (char*) malloc(strlen(token) + 1);
X        strcpy(field_list[field_count].name, token);
X        field_list[field_count].lb = range.lower_bound;
X        field_list[field_count].ub = range.upper_bound;
X
X        field_count++;
X    }
X
X    /* Clean stuff off the stack. */
X    while (stack[top].kind != StackMark)
X        free(stack[top--].data.token);
X    top--;
X}
X
X/* SEMANTIC ROUTINE
X      EXPECTS - StackRange
X      LEAVES  - n/a
X      ACTION  - Generate a declaration for cells to be of a single field
X                with the given range.  No code is generated.
X*/
void declare_default_field() {
X    print_indent();
X    fprintf(file_c, "typedef %s cell_type;\n", FIELD_TYPE);
X
X    field_count = 1;
X
X    /* Build appropriate macros for "neq" and "assign_cell". */
X    fprintf(file_c, "#define neq(x,y) ((*(x))!=(*(y)))\n\n");
X    fprintf(file_c, "#define assign_cell(x,y) ((*(x))=(*(y)))\n\n");
X
X    top--;
X}
X
X/************************************************************************/
X
X/* SEMANTIC ROUTINE
X      EXPECTS - StackExpr, StackExpr
X      LEAVES  - StackRange
X      ACTION  - Convert the top two entries on the semantic stack into
X        a single range entry.
X*/
void make_range() {
X    if (stack_error(2)) {
X        if (stack[top].kind != StackError)
X            free(stack[top].data.expr.addr);
X        if (stack[top-1].kind != StackError)
X            free(stack[top-1].data.expr.addr);
X        top--;
X        stack[top].kind = StackError;
X        return;
X    }
X    else {
X        range_entry range;
X
X        /* Build the range entry. */
X        range.upper_bound = atoi(stack[top].data.expr.addr);
X        free(stack[top--].data.expr.addr);
X        range.lower_bound = atoi(stack[top].data.expr.addr);
X        free(stack[top--].data.expr.addr);
X
X        /* Warn if desired range is not supported. */
X        if (range.lower_bound < MAX_RANGE_LB ||
X            range.upper_bound > MAX_RANGE_UB) {
X            error_prefix();
X            fprintf(stderr, "Range [%d..%d] not supported (warning)\n",
X                range.lower_bound, range.upper_bound);
X        }
X
X        /* Push the range entry onto the stack. */
X        new_entry();
X        stack[top].kind = StackRange;
X        stack[top].data.range = range;
X    }
X}
X
X/************************************************************************/
X
X/* SUPPORT ROUTINE
X      ACTION  - Declare var_name as a variable of type.
X*/
void decl_variable(var_name, type) char *var_name, *type; {
X    attr_rec attribute;
X
X    /* Enter into symbol table. */
X    attribute.assignable = true;
X    attribute.field_name = false;
X    attribute.structured = (0 == strcmp(type, "cell_type"));
X    enterid(var_name, attribute);
X
X    /* Write code to declare the variable. */
X    fprintf(file_h, "%s _%s;\n", type, var_name);
X}
X
X/* SEMANTIC ROUTINE
X      EXPECTS - StackExpr_2, StackExpr_1
X      LEAVES  - StackExpr
X      ACTION  - Writes code to perform an assignment.  Implicit declarations
X            of variables are made, with the type of the variable being
X            determined by the first right hand side given.
X*/
void do_assign() {
X    if (stack_error(2)) {
X        if (stack[top].kind != StackError)
X            free(stack[top].data.expr.addr);
X        top--;
X        stack[top].kind = StackError;
X        return;
X    }
X    else {
X        char base_addr[MAX_STRING_LENGTH];
X        expr_entry expr_1, expr_2;
X        expr_2 = stack[top--].data.expr;
X        expr_1 = stack[top].data.expr;
X
X        /* Declare the variable if necessary. */
X        if (!intable(expr_1.addr, VARIABLE)) {
X
X            /* Put it in the symbol table. */
X            if (expr_2.unstructured)
X                decl_variable(expr_1.addr, FIELD_TYPE);
X            else
X                decl_variable(expr_1.addr, "cell_type");
X        }
X
X        /* Get the symbol table information for expr_1. */
X        stack[top].data.expr.unstructured =
X            !(get_attribute(expr_1.addr, VARIABLE)->structured);
X        expr_1 = stack[top].data.expr;
X
X        /* Check for a field of expr_1. */
X        if (expr_1.field) expr_1.unstructured = 1;
X
X        /* The variable "cell" is a special case. */
X        if (strcmp(expr_1.addr, "cell") == 0)
X            sprintf(base_addr, "(*_%s)", expr_1.addr);
X        else
X            sprintf(base_addr, "_%s", expr_1.addr);
X
X        print_indent();
X
X        if (expr_1.unstructured && expr_2.unstructured) {
X            fprintf(file_c, "(%s)", base_addr);
X            if (expr_1.field != (char*) NULL)
X                fprintf(file_c, ".%s", expr_1.field);
X            fprintf(file_c, " = %s;\n", expr_2.addr);
X        }
X        else if (!expr_1.unstructured && !expr_2.unstructured)
X            fprintf(file_c, "assign_cell(&(%s), &(%s));\n",
X                base_addr, expr_2.addr);
X        else
X{
printf("'%s' and '%s' are incompatible\n", expr_1.addr, expr_2.addr);
X            error("Incompatible assignment", (char*) NULL);
X}
X
X        free(expr_2.addr);
X    }
X}
X
X/* SEMANTIC ROUTINE
X      EXPECTS - StackExpr
X      LEAVES  - n/a
X      ACTION  - Removes the assignable which is on top of the semantic
X        stack, since it is no longer needed.  No code is written.
X*/
void end_assign() {
X    free(stack[top--].data.expr.addr);
X}
X
X/************************************************************************/
X
X/* SEMANTIC ROUTINE
X      EXPECTS - StackToken
X      LEAVES  - StackExpr
X      ACTION  - Converts the entry on top of the stack into an assignable
X        base entry.
X*/
void assignable_base() {
X    char *token = stack[top].data.token;
X
X    /* Convert StackToken entry into a StackExpr entry. */
X    stack[top].kind = StackExpr;
X    stack[top].data.expr.assignable = true;
X    stack[top].data.expr.unstructured = (field_count == 1);
X    stack[top].data.expr.field = (char*) NULL;
X    stack[top].data.expr.addr = token;
X
X    stack[top].data.expr.pre_declared = intable(token, VARIABLE);
X}
X
X/************************************************************************/
X
X/* SEMANTIC ROUTINE
X      EXPECTS - StackExpr
X      LEAVES  - n/a
X      ACTION  - Writes code to conditionally perform a block of statements.
X*/
void jump_if() {
X    if (stack_error(1)) {
X        top--;
X        return;
X    }
X    else {
X        print_indent();
X        fprintf(file_c, "if (%s) {\n", stack[top].data.expr.addr);
X        indent;
X        free(stack[top--].data.expr.addr);
X    }
X}
X
X/* SEMANTIC ROUTINE
X      EXPECTS - StackExpr
X      LEAVES  - n/a
X      ACTION  - Writes code to conditionally perform a block of statements
X        as an alternative to previous if's and elsif's.
X*/
void jump_elsif() {
X    if (stack_error(1)) {
X        top--;
X        return;
X    }
X    else {
X        undent;
X        print_indent();
X        fprintf(file_c,
X            "} else if (%s) {\n", stack[top].data.expr.addr);
X        indent;
X        free(stack[top--].data.expr.addr);
X    }
X}
X
X/* SEMANTIC ROUTINE
X      EXPECTS - n/a
X      LEAVES  - n/a
X      ACTION  - Writes code to unconditionally perform a block of
X        statements as an alternative to previous if's and elsif's.
X*/
void start_else() {
X    undent;
X    print_indent();
X    fprintf(file_c, "} else {\n");
X    indent;
X}
X
X/* SEMANTIC ROUTINE
X      EXPECTS - n/a
X      LEAVES  - n/a
X      ACTION  - Writes code to close off an if statement.
X*/
void end_if() {
X    undent;
X    print_indent();
X    fprintf(file_c, "}\n");
X}
X
X/************************************************************************/
X
X/* SEMANTIC ROUTINE
X      EXPECTS - n/a
X      LEAVES  - StackMark
X      ACTION  - Pushes the StackMark onto the semantic stack.
X*/
void push_mark() {
X    new_entry();
X    stack[top].kind = StackMark;
X}
X
X/* SEMANTIC ROUTINE
X      EXPECTS - n/a
X      LEAVES  - StackToken
X      ACTION  - Pushes a string the stack.
X*/
void push(string) char *string; {
X    new_entry();
X    stack[top].kind = StackToken;
X    stack[top].data.token = mymalloc((unsigned int) (strlen(string) + 1));
X    strcpy(stack[top].data.token, string);
X}
X
X/************************************************************************/
X
X/* SEMANTIC ROUTINE
X      EXPECTS - n/a
X      LEAVES  - StackExpr
X      ACTION  - Pushes a StackExpr onto the stack that represents the
X        value of the expression denoted by the literal.
X*/
void process_literal(literal) char *literal; {
X    expr_entry expr;
X    expr.assignable = false;
X    expr.unstructured = true;
X    expr.addr = mymalloc((unsigned int) (strlen(literal) + 1));
X    sprintf(expr.addr, "%s", literal);
X    new_entry();
X    stack[top].kind = StackExpr;
X    stack[top].data.expr = expr;
X}
X
X/************************************************************************/
X
X/* SEMANTIC ROUTINE
X      EXPECTS - StackExpr, StackToken
X      LEAVES  - StackExpr
X      ACTION  - Performs a simplified unary_op operation, building an
X        integer value without () or spaces.  This allows the
X        routine cell_reference to do an atoi call to get the
X        value of the integer and to compare it against the size
X        of the range for a dimension.
X*/
void mk_signed_int() {
X    stack_entry entry_1, entry_2;
X    entry_2 = stack[top--];
X    entry_1 = stack[top];
X    stack[top].kind = StackExpr;
X    stack[top].data.expr.assignable = false;
X    stack[top].data.expr.unstructured = false;
X    if (strcmp(entry_1.data.token, "-") == 0) {
X        stack[top].data.expr.addr =
X            mymalloc((unsigned int)
X                    (strlen(entry_2.data.token) + 2));
X        sprintf(stack[top].data.expr.addr,
X            "-%s", entry_2.data.expr.addr);
X        free(entry_2.data.expr.addr);
X    }
X    else {
X        stack[top].data.expr.addr = entry_2.data.expr.addr;
X    }
X    free(entry_1.data.token);
X}
X
X/************************************************************************/
X
X/* SEMANTIC ROUTINE
X      EXPECTS - StackToken
X      LEAVES  - StackExpr
X      ACTION  - Checks to insure that the token has been declared as
X        a variable.  If not an error is generated, if so then
X        the entry is converted into an expression.
X*/
void get_variable() {
X    char *string = stack[top].data.token;
X    if (!intable(string, VARIABLE)) {
X        error("Variable '%s' used before set", string);
X        free(stack[top].data.token);
X        stack[top].kind = StackError;
X    }
X    else {
X        attr_rec *attr = get_attribute(string, VARIABLE);
X        unsigned int size = strlen(string) + 2;
X
X        /* Do the conversion into an expression. */
X        stack[top].kind = StackExpr;
X        stack[top].data.expr.assignable = false;
X        stack[top].data.expr.unstructured = !attr->structured;
X
X        /* The variable "cell" is a special case. */
X        if (strcmp(string, "cell") == 0) size += 3;
X
X        stack[top].data.expr.addr = mymalloc(size);
X
X        /* The variable "cell" is a special case. */
X        if (strcmp(string, "cell") == 0)
X            sprintf(stack[top].data.expr.addr, "(*_%s)", string);
X        else
X            sprintf(stack[top].data.expr.addr, "_%s", string);
X
X        free(string);
X    }
X}
X
X/************************************************************************/
X
X/* SEMANTIC ROUTINE
X      EXPECTS - StackExpr, ..., StackExpr, StackMark
X      LEAVES  - StackExpr
X      ACTION  - The number of StackExpr before the StackMark must be
X        equal to the number of dimensions in the cellular
X        universe.  The relative indices (StackExpr's) into the
X        universe are converted into the proper C array reference
X        code which uses the current values of the dimension
X        indices and modular arithmetic to guarantee that the
X        references are legal.  References are made more efficient
X        by not doing any arithmetic if the relative index is 0.
X*/
void cell_reference() {
X    char *new_addr;
X    unsigned int size = strlen("cells[now]") + 1;
X    int mark = top;
X    int tmp_top;
X    int dim_count;
X
X    /* Determine the size of the array reference. */
X    dim_count = 0;
X    while (stack[mark].kind != StackMark) {
X        char sub_expr[MAX_STRING_LENGTH];
X        int index_value = atoi(stack[mark].data.expr.addr);
X        dim_count++;
X        if (0 == index_value)
X            sprintf(sub_expr, "[dim_%d]", dim_count);
X        else if (index_value > 0)
X            sprintf(sub_expr,
X                "[((x=dim_%d+%s)>=DIM_%d_SIZE?x-DIM_%d_SIZE:x)]",
X                dim_count,
X                stack[mark].data.expr.addr,
X                dim_count,
X                dim_count
X                );
X        else
X            sprintf(sub_expr,
X                "[((x=dim_%d%s)<0?x+DIM_%d_SIZE:x)]",
X                dim_count,
X                stack[mark].data.expr.addr,
X                dim_count
X                );
X        mark--;
X        size = size + strlen(sub_expr);
X    }
X
X    /* The number of dimensions used should match those declared. */
X    if (dimension_count != dim_count)
X        error("Incorrect number of dimensions in cell reference",
X              (char*) NULL);
X
X    /* Turn the StackMark entry into a StackExpr (the array reference). */
X    stack[mark].kind = StackExpr;
X    stack[mark].data.expr.assignable = false;
X    stack[mark].data.expr.unstructured = (field_count == 1);
X    new_addr = stack[mark].data.expr.addr = mymalloc(size);
X
X    /* Build the array reference. */
X    dim_count = 0;
X    tmp_top = mark + 1;
X    strcpy(new_addr, "cells[now]");
X    while (tmp_top <= top) {
X        char sub_expr[MAX_STRING_LENGTH];
X        long int index_value = atoi(stack[tmp_top].data.expr.addr);
X
X        dim_count++;
X
X        if (0 == index_value)
X            sprintf(sub_expr, "[dim_%d]", dim_count);
X        else if (index_value > 0)
X            sprintf(sub_expr,
X                "[((x=dim_%d+%s)>=DIM_%d_SIZE?x-DIM_%d_SIZE:x)]",
X                dim_count,
X                stack[tmp_top].data.expr.addr,
X                dim_count,
X                dim_count
X                );
X        else
X            sprintf(sub_expr,
X                "[((x=dim_%d%s)<0?x+DIM_%d_SIZE:x)]",
X                dim_count,
X                stack[tmp_top].data.expr.addr,
X                dim_count
X                );
X
X        free(stack[tmp_top].data.expr.addr);
X        strcat(new_addr, sub_expr);
X        tmp_top++;
X    }
X
X    /* Pop most of the semantic stack. */
X    top = mark;
X}
X
X/* SEMANTIC ROUTINE
X      EXPECTS - StackToken StackExpr
X      LEAVES  - StackExpr
X      ACTION  - The StackToken is used to create a field reference of
X        the StackExpr.
X*/
void field_reference() {
X    if (stack_error(2)) {
X        if (stack[top-1].kind != StackError)
X            free(stack[top-1].data.expr.addr);
X        top--;
X        stack[top].kind = StackError;
X        return;
X    }
X    else {
X        stack_entry field_entry, base_entry;
X
X        field_entry = stack[top--];
X        base_entry = stack[top];
X
X        if (!base_entry.data.expr.pre_declared &&
X            base_entry.data.expr.assignable) {
X            error("'%s' is not previously declared",
X                base_entry.data.expr.addr);
X            stack[top].kind = StackError;
X            return;
X        }
X
X        /* Make sure this is really a field. */
X        if (!intable(field_entry.data.token, FIELD))
X            error("'%s' is not a known field",
X                field_entry.data.token);
X
X        stack[top].kind = StackExpr;
X        stack[top].data.expr.assignable = base_entry.data.expr.assignable;
X        stack[top].data.expr.unstructured = true;
X
X        if (base_entry.data.expr.assignable)
X            stack[top].data.expr.field = field_entry.data.token;
X        else {
X            stack[top].data.expr.addr =
X                mymalloc((unsigned int)
X                    (strlen(base_entry.data.expr.addr) +
X                         strlen(field_entry.data.token) +
X                         strlen("(.)") + 1));
X            sprintf(stack[top].data.expr.addr, "(%s.%s)",
X                base_entry.data.expr.addr,
X                field_entry.data.token);
X            free(base_entry.data.expr.addr);
X            free(field_entry.data.token);
X        }
X    }
X}
X
X/************************************************************************/
X
X/* SEMANTIC ROUTINE
X      EXPECTS - StackExpr_1, StackToken, StackExpr_2
X      LEAVES  - StackExpr
X      ACTION  - Code for the indicated operation and operands is
X        produced and replaces the 3 items on top of the
X        stack.
X*/
void binary_op() {
X    if (stack_error(3)) {
X        if (stack[top].kind != StackError)
X            free(stack[top].data.expr.addr);
X        top -= 2;
X        stack[top].kind = StackError;
X        return;
X    }
X    else {
X        stack_entry entry_1, entry_2, entry_3;
X        entry_3 = stack[top--];
X        entry_2 = stack[top--];
X        entry_1 = stack[top];
X
X        /* Only fields can use (non)equality tests. */
X        if (!entry_1.data.expr.unstructured &&
X            !entry_3.data.expr.unstructured &&
X            !strcmp(entry_2.data.token, "=") &&
X            !strcmp(entry_2.data.token, "!="))
X            error("Comparisons of structured cells are limited to '=' and '!='",
X                (char*) NULL);
X        else if (entry_1.data.expr.unstructured !=
X                        entry_3.data.expr.unstructured)
X            error("Value types of operation, '%s', are incompatable",
X                entry_2.data.token);
X
X        stack[top].kind = StackExpr;
X        stack[top].data.expr.assignable = false;
X        stack[top].data.expr.unstructured =
X                        entry_1.data.expr.unstructured;
X
X        if (entry_1.data.expr.unstructured || field_count == 1) {
X            stack[top].data.expr.addr =
X                mymalloc((unsigned int)
X                    (strlen(entry_1.data.expr.addr) +
X                         strlen(entry_2.data.token) +
X                         strlen(entry_3.data.expr.addr) +
X                         strlen("(  )") + 1));
X            sprintf(stack[top].data.expr.addr, "(%s %s %s)",
X                entry_1.data.expr.addr,
X                entry_2.data.token,
X                entry_3.data.expr.addr);
X        }
X        else {
X            unsigned int size =
X                    strlen(entry_1.data.expr.addr) +
X                         strlen(entry_2.data.token) +
X                         strlen(entry_3.data.expr.addr) +
X                         strlen("neq(&(),&())") + 1;
X
X            if (strcmp(entry_2.data.token, "!=")) size++;
X
X            stack[top].data.expr.addr = mymalloc(size);
X
X            if (strcmp(entry_2.data.token, "!="))
X                sprintf(stack[top].data.expr.addr, "neq(&(%s),&(%s))",
X                    entry_1.data.expr.addr,
X                    entry_2.data.token,
X                    entry_3.data.expr.addr);
X            else
X                sprintf(stack[top].data.expr.addr, "!neq(&(%s),&(%s))",
X                    entry_1.data.expr.addr,
X                    entry_2.data.token,
X                    entry_3.data.expr.addr);
X        }
X
X        free(entry_1.data.expr.addr);
X        free(entry_2.data.token);
X        free(entry_3.data.expr.addr);
X    }
X}
X
X/* SEMANTIC ROUTINE
X      EXPECTS - StackExpr, StackToken
X      LEAVES  - StackExpr
X      ACTION  - The stack is rearranged to look like:
X           StackExpr_1, StackMark, StackToken
X        and a call made to endfuncall.
X*/
void unary_op() {
X    if (stack_error(2)) {
X        if (stack[top].kind != StackError)
X            free(stack[top].data.expr.addr);
X        top--;
X        stack[top].kind = StackError;
X        return;
X    }
X    else {
X        stack_entry entry_1, entry_2;
X        entry_2 = stack[top--];
X        entry_1 = stack[top];
X
X        /* Only fields can use unary operations. */
X        if (!entry_2.data.expr.unstructured)
X            error("Unary operations must operate on integer values",
X                (char*) NULL);
X
X        stack[top].kind = StackExpr;
X        stack[top].data.expr.assignable = false;
X        stack[top].data.expr.unstructured =
X                        entry_2.data.expr.unstructured;
X        stack[top].data.expr.addr =
X            mymalloc((unsigned int)
X                    (strlen(entry_1.data.token) +
X                         strlen(entry_2.data.expr.addr) +
X                         strlen("( )") + 1));
X        sprintf(stack[top].data.expr.addr, "(%s %s)",
X            entry_1.data.token,
X            entry_2.data.expr.addr);
X        free(entry_1.data.token);
X        free(entry_2.data.expr.addr);
X    }
X}
X
X/************************************************************************/
X
X/* SUPPORT ROUTINE
X      ACTION - Generates code to check that the read times are legal,
X           (i.e. greater than the current time).
X*/
void gen_check_time() {
X    print_indent();
X    fprintf(file_c, "if (next_time < _time) {\n");
X    indent;
X    print_indent();
X    fprintf(file_c,
X        "fprintf(stderr, \"%%s; time %%lu, entry %%lu: Must go forwards in time.\\n\", command, _time, entry);\n");
X    print_indent();
X    fprintf(file_c, "exit(1);\n");
X    undent;
X    print_indent();
X    fprintf(file_c, "}\n");
X}
X
X/* SUPPORT ROUTINE
X      ACTION - Generates code to give a read error message and quit, when
X           a index/value should have been read but wasn't.
X*/
void gen_read_error() {
X    indent;
X    print_indent();
X    fprintf(file_c, "fprintf(stderr, \"%%s; time %%lu, entry %%lu: read error\\n\", command, _time, entry);\n");
X    print_indent();
X    fprintf(file_c, "exit(1);\n");
X    undent;
X}
X
X/* SUPPORT ROUTINE
X      ACTION - Generates code to give a read error message and quit, when
X           the value read in was incorrect.
X*/
void gen_read_value_error(position) int position; {
X    indent;
X    print_indent();
X    if (position <= dimension_count)
X        fprintf(file_c, "fprintf(stderr, \"%%s; time %%lu, entry %%lu: value of index %d is out of range\\n\", command, _time, entry);\n",
X            position);
X    else
X        fprintf(file_c, "fprintf(stderr, \"%%s; time %%lu, entry %%lu: cell value is out of range\\n\", command, _time, entry);\n");
X    print_indent();
X    fprintf(file_c, "exit(1);\n");
X    undent;
X}
X
X/* SUPPORT ROUTINE
X      ACTION - Generates code to read the data from stdandard input
X           when the time has reached the time associated with
X           the next set of cell-value combinations to read.
X*/
void gen_read_loop() {
X    int i;
X
X    /* As long as the time of the automata is the time of the
X       data entries, keep looping to read all of the cell-value
X       data.
X    */
X    print_indent();
X    fprintf(file_c, "entry = 0;\n");
X    print_indent();
X    fprintf(file_c, "while (_time == next_time) {\n");
X    indent;
X
X    /* Generate code to read in the dimension values.  Because the
X       dimension variables are held in registers, the actually values
X       are read into temporary locations and the values then assigned
X       to the dimension variables.
X    */
X
X    /* Declare temporaries. */
X    for (i = 1; i <= dimension_count; i++) {
X        print_indent();
X        fprintf(file_c, "int temp_dim_%d;\n", i);
X    }
X
X    /* Read dimension values into temporaries. */
X    print_indent();
X    fprintf(file_c, "int scan_count;\n");
X    print_indent();
X    fprintf(file_c, "int count = scanf(\" [ %%d");
X    for (i = 1; i < dimension_count; i++)
X        fprintf(file_c, " , %%d");
X    fprintf(file_c, " \"");
X    for (i = 1; i <= dimension_count; i++)
X        fprintf(file_c, ", &temp_dim_%d", i);
X    fprintf(file_c, ");\n");
X
X    /* Assign temporaries to the dimension variables. */
X    for (i = 1; i <= dimension_count; i++) {
X        print_indent();
X        fprintf(file_c, "dim_%d = temp_dim_%d;\n", i, i);
X    }
X
X
X    /* Update the input entry count, for the printing of error messgaes. */
X    print_indent();
X    fprintf(file_c, "entry++;\n");
X
X    /* If no dimensions values read, then maybe this is a time. */
X    print_indent();
X    fprintf(file_c, "if (0 == count || EOF == count) {\n");
X    indent;
X    print_indent();
X    fprintf(file_c, "count = scanf(\" %%ld \", &next_time);\n");
X
X    /* If a time was read, make sure it was a legal time. */
X    print_indent();
X    fprintf(file_c, "if (1 == count) {\n");
X    indent;
X    gen_check_time();
X    undent;
X    print_indent();
X    fprintf(file_c, "}\n");
X
X    /* If this is the end of the input, then set next_time so that
X       no attempt is made to read from the input again.
X    */
X    print_indent();
X    fprintf(file_c, "else if (0 == count || EOF == count) {\n");
X    indent;
X    /* Make sure that only spaces, tabs and newlines are left; otherwise
X       indicate an error.
X    */
X    print_indent();
X    fprintf(file_c, "int c = getchar();\n");
X    print_indent();
X    fprintf(file_c, "while (c == '\\n' || c == '\\t' || c == ' ') c = getchar();\n");
X    print_indent();
X    fprintf(file_c, "if (c != EOF) {\n");
X    gen_read_error();
X    print_indent();
X    fprintf(file_c, "}\n");
X
X    print_indent();
X    fprintf(file_c, "next_time = -1;\n");
X
X    undent;
X    print_indent();
X    fprintf(file_c, "}\n");
X    print_indent();
X    fprintf(file_c, "break;\n");
X
X    undent;
X    print_indent();
X    fprintf(file_c, "}\n");
X
X    /* Generate code to check and see if only some of the cell
X       indices were read in.
X    */
X    print_indent();
X    fprintf(file_c, "else if (count != %d) {\n", dimension_count);
X    indent;
X    print_indent();
X    fprintf(file_c, "fprintf(stderr, \"%%s; time %%lu, entry %%lu: Incorrect number of dimensions referenced\\n\", command, _time, entry);\n");
X    print_indent();
X    fprintf(file_c, "exit(1);\n");
X    undent;
X    print_indent();
X    fprintf(file_c, "}\n");
X
X    /* Generate code to check the legality of the cell indices. */
X    for (i = 1; i <= dimension_count; i++) {
X        print_indent();
X        fprintf(file_c, "if (DIM_%d_SIZE-1 < dim_%d || dim_%d < 0) {\n",
X            i, i, i, i);
X        gen_read_value_error(i);
X        print_indent();
X        fprintf(file_c, "}\n");
X    }
X
X    print_indent();
X    fprintf(file_c, "scanf(\" ] = \");\n");
X
X    /* Find the location of the described cell. */
X    print_indent();
X    fprintf(file_c, "_cell = &cells[now]");
X    for (i = 1; i <= dimension_count; i++)
X        fprintf(file_c, "[dim_%d]", i, i);
X    fprintf(file_c, ";\n");
X
X    /* Write code to print the cell location just read in. */
X    print_indent();
X    fprintf(file_c,
X        "if (_time == next_report_time || _time == next_read_time)\n");
X    indent;
X    print_indent();
X#if COMBINED
X    fprintf(file_c, "if (output) ");
X#endif
X    fprintf(file_c, "printf(\"[%%d");
X    for (i = 2; i <= dimension_count; i++)
X        fprintf(file_c, ", %%d");
X    fprintf(file_c, "] = \"");
X    for (i = 1; i <= dimension_count; i++)
X        fprintf(file_c, ", dim_%d", i);
X    fprintf(file_c, ");\n", i);
X    undent;
X
X    /* Read, check and write out all of the fields. */
X    print_indent();
X    fprintf(file_c, "count = 0;\n");
X    for (i = 0; i < field_count; i++) {
X
X        /* Read and count the values. */
X        if (i > 0) {
X            print_indent();
X            fprintf(file_c, "scan_count = scanf(\" , %%d\", &read_value);\n");
X        }
X        else {
X            print_indent();
X            fprintf(file_c, "scan_count = scanf(\" %%d\", &read_value);\n");
X        }
X
X        /* Only do stuff with this value, if a value was read in. */
X        print_indent();
X        fprintf(file_c, "if (scan_count > 0) {\n");
X        indent;
X        print_indent();
X        fprintf(file_c, "count += scan_count;\n");
X
X        /* Make sure read values fall within the supported range. */
X        print_indent();
X        fprintf(file_c, "if (%d < read_value || read_value < %d) {\n",
X            MAX_RANGE_UB, MAX_RANGE_LB);
X        gen_read_value_error(dimension_count + 1);
X        print_indent();
X        fprintf(file_c, "}\n");
X
X        /* Assign read cell value to the cell.  Values are assumed
X           to be represented by char.
X        */
X        print_indent();
X        if (field_count > 1)
X            fprintf(file_c, "_cell->%s = read_value;\n",
X                field_list[i].name);
X        else
X            fprintf(file_c, "*_cell = read_value;\n");
X
X        /* Write out the value just read in. */
X        print_indent();
X        fprintf(file_c,
X            "if (_time == next_report_time || _time == next_read_time)\n");
X        indent;
X        print_indent();
X#if COMBINED
X        fprintf(file_c, "if (output) ");
X#endif
X        if (i > 0)
X            fprintf(file_c, "printf(\", %%d\", read_value);\n");
X        else
X            fprintf(file_c, "printf(\"%%d\", read_value);\n");
X        undent;
X
X        undent;
X        print_indent();
X        fprintf(file_c, "}\n");
X
X        /* If no value was read, then default value is zero. */
X        print_indent();
X        fprintf(file_c,
X            "else if (_time == next_report_time || _time == next_read_time) {\n");
X        indent;
X#if COMBINED
X        print_indent();
X        fprintf(file_c, "if (output) {\n");
X        indent;
X#endif
X        if (i > 0) {
X            print_indent();
X            fprintf(file_c, "printf(\", \");\n");
X        }
X        print_indent();
X        if (field_count > 1)
X            fprintf(file_c, "printf(\"%%d\", _cell->%s);\n",
X                field_list[i].name);
X        else
X            fprintf(file_c, "printf(\"%%d\", *_cell);\n");
X#if COMBINED
X        undent;
X        print_indent();
X        fprintf(file_c, "}\n");
X#endif
X        undent;
X        print_indent();
X        fprintf(file_c, "}\n");
X    }
X    print_indent();
X#if COMBINED
X    fprintf(file_c, "if (output) ");
X#endif
X    fprintf(file_c, "printf(\"\\n\");\n");
X
X    /* Check for too few cell values given. */
X    print_indent();
X    fprintf(file_c, "if (count < 1) {\n");
X    indent;
X    print_indent();
X    fprintf(file_c, "fprintf(stderr, \"%%s; time %%lu, entry %%lu: Too few cell value(s)\\n\", command, _time, entry);\n");
X    print_indent();
X    fprintf(file_c, "exit(1);\n");
X    undent;
X    print_indent();
X    fprintf(file_c, "}\n");
X
X    /* Check for too many cell values given. */
X    print_indent();
X    fprintf(file_c, "if (count > %d) {\n", field_count);
X    indent;
X    print_indent();
X    fprintf(file_c, "fprintf(stderr, \"%%s; time %%lu, entry %%lu: Too many cell value(s)\\n\", command, _time, entry);\n");
X    print_indent();
X    fprintf(file_c, "exit(1);\n");
X    undent;
X    print_indent();
X    fprintf(file_c, "}\n");
X
X#if COMBINED
X    print_indent();
X    fprintf(file_c, "if (!output) {\n");
X    indent;
X
X    if (field_count > 1) {
X        print_indent();
X        fprintf(file_c, "%s field_value;\n", FIELD_TYPE);
X        print_indent();
X        fprintf(file_c, "switch (field) {\n");
X        indent;
X        for (i = 0; i < field_count; i++) {
X            print_indent();
X            fprintf(file_c, "case %d: field_value = _cell->%s;\n",
X                i, field_list[i].name);
X        }
X        undent;
X        print_indent();
X        fprintf(file_c, "}\n");
X    }
X
X    print_indent();
X    fprintf(file_c, "set_cell_entry(dim_1, ");
X    if (dimension_count > 1)
X        fprintf(file_c, " dim_2, ");
X    else
X        fprintf(file_c, " 0, ");    /* Could be one dimensional. */
X    if (field_count > 1)
X        fprintf(file_c, "field_value);\n");
X    else
X        fprintf(file_c, "*_cell);\n");
X
X    undent;
X    print_indent();
X    fprintf(file_c, "}\n");
X#endif
X
X    /* Close of the loop for reading data. */
X    undent;
X    print_indent();
X    fprintf(file_c, "}\n");
X}
X
X/* SUPPORT ROUTINE
X      ACTION - Generates code to perform the looping over the cellular
X           universe for each time step, starting at 0.
X*/
void gen_begin_time_loop() {
X    print_indent();
X#if COMBINED
X    /* Begin a possibly infinite "time" loop. */
X    fprintf(file_c, "do {\n");
X#else
X    /* Begin an infinite "time" loop. */
X    fprintf(file_c, "while (1) {\n");
X#endif
X    indent;
X
X    /* Generate code to write out the time. */
X    print_indent();
X    fprintf(file_c, "if (_time == next_report_time || _time == next_read_time)\n");
X    indent;
X    print_indent();
X#if COMBINED
X    fprintf(file_c, "if (output) ");
X#endif
X    fprintf(file_c, "printf(\"%%lu\\n\", _time);\n");
X    undent;
X
X    gen_read_loop();
X}
X
X/* SUPPORT ROUTINE
X      ACTION - Generates code to perform the looping over the cellular
X           universe for each time step, starting at 0.
X*/
void gen_end_time_loop() {
X    /* Go to the next time step. */
X    print_indent();
X    fprintf(file_c, "_time++;\n");
X
X    /* Generate code to exchange the values for "next" and "now". */
X    print_indent();
X    fprintf(file_c, "next = !next;\n");
X    print_indent();
X    fprintf(file_c, "now = !now;\n");
X
X    /* Close off the infinite "time" loop. */
X    undent;
X    print_indent();
X#if COMBINED
X    fprintf(file_c, "} while (output);\n");
X#else
X    fprintf(file_c, "}\n");
X#endif
X}
X
X/* SUPPORT ROUTINE
X      ACTION - Generates code to initialize the cells of the cellular
X           universe to 0.
X*/
void gen_cell_init() {
X    int i, f;
X
X    /* Write code to initialize the cellular universe to contain 0's. */
X    for (i = 1; i <= dimension_count; i++) {
X        print_indent();
X        fprintf(file_c, "for(dim_%d=0;dim_%d<DIM_%d_SIZE;dim_%d++)\n",
X            i, i, i, i, i);
X    }
X    print_indent();
X    fprintf(file_c, "{\n");
X    indent;
X
X    /* The following code assumes that fields are stored as
X       unsigned char.
X    */
X    for (f = 0; f < field_count; f++) {
X        print_indent();
X        fprintf(file_c, "*(char*)((unsigned int)&cells[0]");
X        for (i = 1; i <= dimension_count; i++)
X            fprintf(file_c, "[dim_%d]", i, i);
X        fprintf(file_c, "+%d) = 0;\n", f);
X        print_indent();
X        fprintf(file_c, "*(char*)((unsigned int)&cells[1]");
X        for (i = 1; i <= dimension_count; i++)
X            fprintf(file_c, "[dim_%d]", i, i);
X        fprintf(file_c, "+%d) = 0;\n", f);
X    }
X
X    undent;
X    print_indent();
X    fprintf(file_c, "}\n");
X}
X
X/* SUPPORT ROUTINE
X      ACTION - Generates code for the variable declarations in the main
X           body of the program.
X*/
void gen_declarations() {
X    int i;
X
X    /* Declare (locally) the dimension variables. */
X    for (i = 1; i <= dimension_count; i++) {
X        print_indent();
X        fprintf(file_c, "register int dim_%d;\n", i);
X    }
X
X    /* The location of the current cell within the universe is
X       always contained in the variable "cell".
X    */
X    print_indent();
X    fprintf(file_c, "register cell_type *_cell = NULL;\n");
X
X    /* For counting lines of the input data to the cellular atuomata. */
X    print_indent();
X    fprintf(file_c, "unsigned long int entry = 1;\n");
X
X    /* Temporary variable used for reading in cell field values. */
X    print_indent();
X    fprintf(file_c, "int read_value;\n");
X}
X
X/* SUPPORT ROUTINE
X      ACTION - Generates code for the initialization in the main
X           body of the program.
X*/
void gen_initialize() {
X    int i;
X
X    /* Declare (locally) the dimension variables. */
X    for (i = 1; i <= dimension_count; i++) {
X        print_indent();
X        fprintf(file_c, "register int dim_%d;\n", i);
X    }
X
X    /* If no data is given, don't try to read from it ever again. */
X    print_indent();
X    fprintf(file_c, "int count = scanf(\" %%ld \", &next_time);\n");
X    print_indent();
X    fprintf(file_c, "if (0 == count || EOF == count) {\n");
X    indent;
X    /* Make sure that only spaces, tabs and newlines are left; otherwise
X       indicate an error.
X    */
X    print_indent();
X    fprintf(file_c, "int c = getchar();\n");
X    print_indent();
X    fprintf(file_c, "while (c == '\\n' || c == '\\t' || c == ' ') c = getchar();\n");
X
X    print_indent();
X    fprintf(file_c, "if (c != EOF) {\n");
X    indent;
X    print_indent();
X    fprintf(file_c, "fprintf(stderr, \"%%s: read error at beginning of input file\\n\", command);\n");
X    print_indent();
X    fprintf(file_c, "exit(1);\n");
X    undent;
X    print_indent();
X    fprintf(file_c, "}\n");
X
X    print_indent();
X    fprintf(file_c, "next_time = -1;\n");
X    undent;
X    print_indent();
X    fprintf(file_c, "} else\n");
X
X    /* Make sure that the time read in is okay. */
X    print_indent();
X    fprintf(file_c, "if (next_time < _time) {\n");
X    indent;
X    print_indent();
X    fprintf(file_c,
X        "fprintf(stderr, \"%%s: First time in input file must be >= 0\\n\", command);\n");
X    print_indent();
X    fprintf(file_c, "exit(1);\n");
X    undent;
X    print_indent();
X    fprintf(file_c, "}\n");
X
X    gen_cell_init();
X}
X
X/* SUPPORT ROUTINE
X      ACTION - Generates code to read the command line arguments.  These
X           consist of a time file and a set of upper bounds on each of
X           the dimensions (appearing in order).  The time file, if
X           given, is opened otherwise the time reporting step is set
X           to 1.  The upper bounds on the dimensions are set.
X*/
void gen_get_command_line() {
X
X    /* Get and set the upper bounds on the dimensions. */
X    print_indent();
X    fprintf(file_c, "if (argc != %d) {\n", 2);
X    indent;
X    print_indent();
X    fprintf(file_c, "fprintf(stderr, \"%%s: Incorrect number of command line arguments\\n\", argv[0]);\n");
X    print_indent();
X    fprintf(file_c, "exit(1);\n");
X    undent;
X    print_indent();
X    fprintf(file_c, "}\n");
X
X    /* Open the time file which specifies report times, if given. */
X    print_indent();
X    fprintf(file_c, "if (strcmp(argv[1], \"-\") != 0) {\n");
X    indent;
X    print_indent();
X    fprintf(file_c, "time_file = fopen(argv[1], \"r\");\n");
X    print_indent();
X    fprintf(file_c, "next_read_time = 0;\n");
X    print_indent();
X    fprintf(file_c, "get_report_time(time_file, &report_time_step, &next_read_time);\n");
X    undent;
X    print_indent();
X    fprintf(file_c, "}\n");
X}
X
X/* SUPPORT ROUTINE
X      ACTION - Generates code to read the report time file entries.
X*/
void gen_get_report_time() {
X    print_indent();
X    fprintf(file_c, "void get_report_time(file, time_step, read_time)\n");
X    print_indent();
X    fprintf(file_c, "FILE *file; unsigned long int *time_step; long int *read_time; {\n");
X    indent;
X
X    /* Get the next entry from the file. */
X    print_indent();
X    fprintf(file_c, "int c;\n");
X    print_indent();
X    fprintf(file_c, "*time_step = 0;\n");
X    print_indent();
X    fprintf(file_c, "while (*read_time >= 0)\n");
X    indent;
X    print_indent();
X    fprintf(file_c, "if (1 == fscanf(file, \" +%%u\", time_step));\n");
X    print_indent();
X    fprintf(file_c, "else if (1 == fscanf(file, \" %%ld\", read_time)) break;\n");
X    print_indent();
X    fprintf(file_c, "else if ((c = getc(file)) == '!') exit(0);\n");
X    print_indent();
X    fprintf(file_c, "else if (c == ' ' || c == '\\n');\n");
X    print_indent();
X    fprintf(file_c, "else *read_time = -1;\n");
X    undent;
X
X    undent;
X    print_indent();
X    fprintf(file_c, "}\n\n");
X}
X
X/* SUPPORT ROUTINE
X      ACTION - Generates code to read the report time file entries.
X*/
void gen_init_cells() {
X    print_indent();
X    fprintf(file_c, "void init_cells() {\n");
X    indent;
X
X    gen_initialize();
X
X    undent;
X    print_indent();
X    fprintf(file_c, "}\n\n");
X}
X
X/************************************************************************/
X
X/* SEMANTIC ROUTINE
X      EXPECTS - n/a
X      LEAVES  - n/a
X      ACTION  - Writes code to perform all the actions on the cellular
X        automata and its rules.  Including, but not limited to,
X        variable declarations, I/O, cell initialization.
X*/
void begin_rules() {
X    int i;
X
X    decl_time_and_cell();
X
X    /* Define the function for reading the report time file entries. */
X    gen_get_report_time();
X
X    /* Declare the cell universe. */
X    print_indent();
X    fprintf(file_c, "static cell_type cells[2]");
X    for (i = 0; i < dimension_count; i++)
X        fprintf(file_c, "[%d]", MAX_DIM_SIZE);
X    fprintf(file_c, ";\n\n");
X
X    /* Define the function for initializing the cell universe. */
X    gen_init_cells();
X
X    /* Start the "main" body of the program. */
X#if COMBINED
X    fprintf(file_c, "int cellang_main (output, field) int output, field; {\n");
X#else
X    fprintf(file_c, "int main (argc, argv) int argc; char *argv[]; {\n");
X#endif
X    indent;
X
X    gen_declarations();
X
X#if !COMBINED
X    gen_get_command_line();
X
X    print_indent();
X    fprintf(file_c, "command = argv[0];\n");
X
X    print_indent();
X    fprintf(file_c, "init_cells();\n");
X#endif
X
X    gen_begin_time_loop();
X
X    /* Generate code to step through the ranges of all indices. */
X    for (i = 1; i <= dimension_count; i++) {
X        print_indent();
X        fprintf(file_c, "for(dim_%d=0;dim_%d<DIM_%d_SIZE;dim_%d++)\n",
X            i, i, i, i, i);
X    }
X
X    /* Begin statements of for loop that range over dimensional ranges. */
X    print_indent();
X    fprintf(file_c, "{\n");
X    indent;
X
X    /* Generate code to read in the variables include file. */
X    fprintf(file_c, "#include \".cellang.h\"\n");
X
X    /* Declare temporary used for computing indices. */
X    print_indent();
X    fprintf(file_c, "register int x;\n");
X
X    /* Declare the variable that is the current "now" cell. */
X    print_indent();
X    fprintf(file_c, "cell_type now_cell;\n");
X
X    /* Generate code to set the location of the current "next" cell. */
X    print_indent();
X    fprintf(file_c, "_cell = &cells[next]");
X    for (i = 1; i <= dimension_count; i++)
X        fprintf(file_c, "[dim_%d]", i);
X    fprintf(file_c, ";\n");
X
X    /* Generate code to set the current values of "_cell" and "now_cell". */
X    print_indent();
X    fprintf(file_c, "assign_cell(&now_cell, &(cells[now]");
X    for (i = 1; i <= dimension_count; i++)
X        fprintf(file_c, "[dim_%d]", i);
X    fprintf(file_c, "));\n");
X
X    print_indent();
X    fprintf(file_c, "assign_cell(_cell, &now_cell);\n");
X}
X
X/* SEMANTIC ROUTINE
X      EXPECTS - n/a
X      LEAVES  - n/a
X      ACTION  - Writes code to end the grouping of cellular automata rules.
X*/
void end_rules() {
X    int i;
X
X    /* Generate code to "write out" the location and value of the "next"
X       cell value if it is different from the "now" value.
X    */
X    print_indent();
X    fprintf(file_c, "if ((neq(_cell, &now_cell) && 1 == report_time_step) || (report_time_step > 1 && (_time == next_report_time || _time == next_read_time))) {\n");
X    indent;
X#if COMBINED
X    print_indent();
X    fprintf(file_c, "if (!output) {\n");
X    indent;
X
X    if (field_count > 1) {
X        print_indent();
X        fprintf(file_c, "%s field_value;\n", FIELD_TYPE);
X        print_indent();
X        fprintf(file_c, "switch (field) {\n");
X        indent;
X        for (i = 0; i < field_count; i++) {
X            print_indent();
X            fprintf(file_c, "case %d: field_value = _cell->%s;\n",
X                i, field_list[i].name);
X        }
X        undent;
X        print_indent();
X        fprintf(file_c, "}\n");
X    }
X
X    print_indent();
X    fprintf(file_c, "set_cell_entry(dim_1, ");
X    if (dimension_count > 1)
X        fprintf(file_c, " dim_2, ");
X    else
X        fprintf(file_c, " 0, ");    /* Could be one dimensional. */
X    if (field_count > 1)
X        fprintf(file_c, "field_value);\n");
X    else
X        fprintf(file_c, "*_cell);\n");
X
X    undent;
X    print_indent();
X    fprintf(file_c, "} else {\n");
X    indent;
X#endif
X    print_indent();
X    fprintf(file_c, "printf(\"[%%d");
X    for (i = 2; i <= dimension_count; i++)
X        fprintf(file_c, ", %%d");
X    fprintf(file_c, "] = %%d");
X
X    for (i = 2; i <= field_count; i++)
X        fprintf(file_c, ", %%d");
X    fprintf(file_c, "\\n\"");
X
X    for (i = 1; i <= dimension_count; i++)
X        fprintf(file_c, ", dim_%d", i, i);
X
X    if (field_count > 1)
X        for (i = 0; i < field_count; i++)
X            fprintf(file_c, ", _cell->%s", field_list[i].name);
X    else
X        fprintf(file_c, ", *_cell");
X    fprintf(file_c, ");\n");
X
X    undent;
X    print_indent();
X    fprintf(file_c, "}\n");
X
X#if COMBINED
X    undent;
X    print_indent();
X    fprintf(file_c, "}\n");
X#endif
X
X    /* Close off for loops that range over dimensional ranges. */
X    undent;
X    print_indent();
X    fprintf(file_c, "}\n");
X
X    /* Update the time variables which determine when cell values
X       should be reported.
X    */
X    print_indent();
X    fprintf(file_c, "if (_time == next_read_time)\n");
X    indent;
X    print_indent();
X    fprintf(file_c, "get_report_time(time_file, &report_time_step, &next_read_time);\n");
X    undent;
X    print_indent();
X    fprintf(file_c, "if (report_time_step > 0 && _time >= next_report_time)\n");
X    indent;
X    print_indent();
X    fprintf(file_c, "next_report_time = _time + report_time_step;\n");
X    undent;
X
X    gen_end_time_loop();
X
X    /* Close off the "main" body. */
X    undent;
X    fprintf(file_c, "}\n");
X}
X
X/************************************************************************/
X
X/* SEMANTIC ROUTINE
X      EXPECTS - n/a
X      LEAVES  - n/a
X      ACTION  - Places the forward declarations for predefined symbols
X                into the symbol table.  This semantic routine is called
X        from main as opposed to being called from the grammar.
X*/
void start_up() {
X    int i;
X
X    /* Open the C files. */
X    file_h = fopen(".cellang.h", "w");
X    file_c = fopen(".cellang.c", "w");
X
X    /* Initialize the symbol table. */
X    initsymboltable();
X
X    /* Generate code to read in the standard include file(s). */
X    fprintf(file_c, "#include<stdio.h>\n");
X    fprintf(file_c, "#include<stdlib.h>\n");
X    fprintf(file_c, "#include<string.h>\n\n");
X
X#if COMBINED
X    /* Generate the external reference to use to cellviewer. */
X    fprintf(file_c, "extern set_cell_entry();\n\n");
X#endif
X
X    /* The declarations for now, next and time_file are given outside
X       the body of functions so that when the software is made such
X       the the viewer is COMBINED with the executable of a Cellang
X       program, these variables are visible and/or get initialized
X       only once.
X    */
X
X    /* command should be extern if COMBINED since it will be set
X       by the viewer software, otherwise it should be static.
X    */
X    print_indent();
X#if COMBINED
X    fprintf(file_c, "extern char *command;\n");
X#else
X    fprintf(file_c, "static char *command = NULL;\n");
X#endif
X
X    /* Write code to initialize the variable used for reading
X       the input to the cellular program.
X    */
X    print_indent();
X    fprintf(file_c, "static long int next_time;\n");
X
X    /* _time should NOT be static, since if COMBINED it will be used
X       by the viewer software.
X    */
X    print_indent();
X    fprintf(file_c, "unsigned long int _time = 0;\n");
X
X    /* Declare the time variables that determine when reports of
X       cell values should be made.
X    */
X    print_indent();
X    fprintf(file_c, "static unsigned long int report_time_step = 1;\n");
X    print_indent();
X    fprintf(file_c, "static unsigned long int next_report_time = 0;\n");
X    print_indent();
X    fprintf(file_c, "static long int next_read_time = -1;\n");
X
X    /* The first dimension of the cellular universe is used to
X       distinguish between current (now) cell values and those
X       values being computer for the next generation (next).
X       The two variables are also declared here.
X    */
X    print_indent();
X    fprintf(file_c, "static int now = 0;\n");
X    print_indent();
X    fprintf(file_c, "static int next = 1;\n\n");
X
X    /* time_file should NOT be static, since if COMBINED it will be used
X       by the viewer software.
X    */
X    print_indent();
X    fprintf(file_c, "FILE *time_file = NULL;\n\n");
X
X    for (i = 1; i <= MAX_SUPPORTED_DIMENSIONS; i++)
X        fprintf(file_c, "#define DIM_%d_SIZE  %d\n", i, MAX_DIM_SIZE);
X}
X
X
X/* SEMANTIC ROUTINE
X      EXPECTS - n/a
X      LEAVES  - n/a
X      ACTION  - Do some clean up actions.
X*/
void finish_up() {
X    /* Check to make sure that the semantic stack is empty. */
X    if (top != -1)
X        error("COMPILER ERROR -- %d entry(ies) left on the semantic stack",
X              (char*) top+1);
X
X    /* Flush and close the output files. */
X    fflush(file_h);
X    fclose(file_h);
X    fflush(file_c);
X    fclose(file_c);
X}
END_OF_FILE
if test 50650 -ne `wc -c <'compiler/semantic.c'`; then
    echo shar: \"'compiler/semantic.c'\" unpacked with wrong size!
fi
# end of 'compiler/semantic.c'
fi
if test -f 'tutorial.tex' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'tutorial.tex'\"
else
echo shar: Extracting \"'tutorial.tex'\" \(28266 characters\)
sed "s/^X//" >'tutorial.tex' <<'END_OF_FILE'
X%  tutorial.tex
X%  Copyright (C) 1992  J Dana Eckart
X%
X%  This program is free software; you can redistribute it and/or modify
X%  it under the terms of the GNU General Public License as published by
X%  the Free Software Foundation; either version 1, or (at your option)
X%  any later version.
X%
X%  This program is distributed in the hope that it will be useful,
X%  but WITHOUT ANY WARRANTY; without even the implied warranty of
X%  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
X%  GNU General Public License for more details.
X%
X%  You should have received a copy of the GNU General Public License
X%  along with CELLULAR-2.0; see the file COPYING.  If not, write to the
X%  Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
X
X\documentstyle[12pt]{article}
X
X% Setup the desired page style.
X\pagestyle{plain}
X\setlength{\textwidth}{6.5in}
X\setlength{\textheight}{9.15in}
X\setlength{\oddsidemargin}{0mm}
X\setlength{\evensidemargin}{0mm}
X\setlength{\topmargin}{-0.3in}
X\setlength{\headheight}{0mm}
X\setlength{\headsep}{0mm}
X
X\setlength{\columnsep}{5mm}
X
X% Setup the desired paragraph style.
X\setlength{\parindent}{0mm}
X\setlength{\parskip}{3mm}
X\begin{document}
X
X% A new command to define a constant tabbing distance for code examples.
X\newcommand{\tab}{\hspace{5mm}}
X
X\title{A {\em Cellular} Automata Simulation System:\\Version 2.0}
X\author{J Dana Eckart\\
X        Radford University}
X\date{}
X\maketitle
X
X\section{Introduction}
With the growing popularity of cellular automata in both recreation
X\cite{life}\cite{wireworld}\cite{fluids}\cite{crystals}
and the modeling of physical
systems\cite{toffoli}\cite{Wolf-Gladrow}\cite{Chen}\cite{Lavallee}\cite{Lim},
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 system consists of: a programming
language, {\em Cellang 2.0}\footnote{
X            Pronounced cell ' ang.
X        },
and associated compiler, {\tt cellc};
an ``abstract'' virtual machine\footnote{
X        The construction of an actual machine embodying the
X        pe--scam architecture is under development.\cite{pe-scam}
X    }
for execution, {\tt pe-scam}; and a viewer, {\tt cellview}.
Compiled {\em Cellang 2.0} 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 automaton program to the viewer.  This simple UNIX\footnote{
X                UNIX is a registered trademark of AT\&T.
X        }
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 2.0}
provides greater flexibility, particularly in the formation of
neighborhoods, than does {\em Cal} (part of the {\em Scamper}
system)\cite{Scamper}.  And although the {\em SLANG}\cite{SLANG} system
supports probablistic possibilities, {\em Cellang 2.0} is a far
simpler language for constructing deterministic cellular automata.
X
X\section{The Language}
X
Programs written in {\em Cellang 2.0} have two main components, a cell
description and a set of statements.  The cell description determines
how many dimensions there are, what field(s) each cell
contains, and the range of assignable values associated with each field.
Statements occur in only two varieties:
assignment and if.  The assignment
statement is unusual in that it provides conditional assignment;
the if statement is of a conventional nature.
X
There is only one primitive data type in {\em Cellang 2.0}, integer.
Variables are
declared by their first usage which is usually as the left hand side of an
assignment statement.  Conditional expressions follow the
rules of {\em C}\cite{harbison},
thus 0 values correspond to false and non--0 values indicate
true.  The arithmetic and logical operators available are: --, +, *, /,
X\% (remainder), ! (logical not), \& (logical and), $|$ (logical or),
X=, !=, $<=$ and $>=$.  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.
X
This version (2.0) is an incompatible upgrade to the previous
version (1.0).\cite{cellang 1.0}
The differences are primarily:
X\begin{itemize}
X
X\item
X{\em Cellang 2.0} does NOT permit the specification of dimension index ranges
X(whereas {\em Cellang 1.0} did);
X
X\item
X{\em Cellang 2.0} does NOT permit the use of dimension names to determine a
cell's exact location within the universe (as did {\em Cellang 1.0});
X
X\item
X{\em Cellang 2.0} DOES allow multiple fields to be associated with each cell
of the universe (unlike {\em Cellang 1.0} which had only one field per cell);
X
X\item
X{\em Cellang 2.0} REQUIRES a range of legal values be given for all cell fields
X(whereas this was optional in {\em Cellang 1.0}).
X
X\end{itemize}
X
X\begin{figure}[t]
X\begin{center}
X\begin{verbatim}
X2 dimensions of 0..1
X
sum := [0, 1] + [1, 1] + [1, 0] + [-1, 1] + [-1, 0] +
X       [-1, -1] + [0, -1] + [1, -1]
X
cell := 1 when (sum = 2 & cell = 1) | sum = 3
X     := 0 otherwise
X\end{verbatim}
X\end{center}
X\caption{The game of Life}
X\label{simple life}
X\end{figure}
X
The game of Life, popularized by Gardener\cite{life},
demonstrates many of the features of {\em Cellang 2.0}.
XFigure~\ref{simple life}
shows the this problem.  Note
that the universe of cells is 2--dimensional each having either a 0 or
X1 value.  Comments begin
with a sharp (\#) and continue to the end of that line.  The predefined variable
X{\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{
X                Relative indexing specifies a cell relative to the
X                current cell.  Thus the relative index ``[-1, 1]''
X                refers to the bordering northwest cell.
X        }
While relative indexing may seem cumbersome,
it provides great flexibility.  The only practical restriction on relative
indices is that they be integer constants.
X
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 topographical properties.
X
An additional predefined variable,
X{\tt time}, can only appear within expressions.
Thus a program can not change {\tt time}, but {\tt time} 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.  Figure~\ref{time dependent life} demonstrates this
possibility.  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 in situations where the physical system behaves
according to different rules/neighborhoods as it ages.
X
X\begin{figure}[t]
X\begin{center}
X\begin{verbatim}
X2 dimensions of 0..1
X
if time % 2 = 0 then
X   sum := [0, 1] + [1, 0] + [-1, 0] + [0, -1]
else
X   sum := [1, 1] + [-1, 1] + [-1, -1] + [1, -1]
end
X
cell := 1 when (sum = 2 | sum = 3) & cell = 1
X     := 1 when sum = 3 & cell = 0
X     := 0 otherwise
X\end{verbatim}
X\end{center}
X\caption{An alternate game of life with a time dependent (hybrid) neighborhood}
X\label{time dependent life}
X\end{figure}
X
X\begin{figure}[t]
X\begin{center}
X\begin{verbatim}
X2 dimensions of
X        x, y of 0..255
end
X
cell.x := ([1, 0].y + [0, 1].y + [-1, 0].y + [0, -1].y) % 256
X                when time % 2
X
cell.y := ([-1, 1].x + [1, 1].x + [-1, -1].x + [1, -1].x) % 256
X                when (time + 1) % 2
X\end{verbatim}
X\end{center}
X\caption{An example program with multi--field cells.}
X\label{multiple cell fields}
X\end{figure}
X
X{\em Cellang 2.0} programs may also contain more than a single field
per cell.  The program given in Figure~\ref{multiple cell fields} shows
a program with 3 fields per cell.
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.
X
XFinally, both the input and output of {\em Cellang 2.0} 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
XFigure~\ref{time blocks}.  It specifies that although
all the cells of the universe have a default value of 0 at time
X0, 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 2.0}
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 2.0} 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
thus retain their previous values.
X\begin{figure}[t]
X\begin{center}
X\begin{verbatim}
X                             0
X                             [3, 3] = 1
X                             100
X                             [24, 56] = 0
X                             [50, 50] = 5, 6
X                             [2, 32] = , , 3
X\end{verbatim}
X\end{center}
X\caption{An example input/output for a {\em Cellang 2.0} program}
X\label{time blocks}
X\end{figure}
X
X\section{The Viewer}
X
The viewer, which is used to examine the cell values in a graphic manner, is
independent of the {\em Cellang 2.0} language and compiler.  The input
to the viewer is identical in form to the output (and thus the input)
of {\em Cellang 2.0} programs.  The current viewer allows the viewing of
a single field along contiguous portions of any two dimensions.
The values can be displayed as either characters
X(via curses) or colored squares (via X--Windows).  A limited debugging
aid (available only with the X--Windows viewing option) also allows the numeric
values of a neighborhood of cells (as opposed
to the color associated with this value) to be viewed.
X
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 2.0} program, and it
is possible that programs of other sorts will be developed
to examine, gather and report statistics concerning the results of
X{\em Cellang 2.0} programs.  ``Valve'' filters
could be inserted between the output generated by a {\em Cellang 2.0}
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 2.0} programs are written
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 storage of all or part of the
produced cell values into a file.
X
X\begin{figure}[t]
X\begin{center}
X\begin{verbatim}
X                                     50
X                                     +1
X                                     100
X                                     500!
X\end{verbatim}
X\end{center}
X\caption{An example time file for reporting cell values}
X\label{report times}
X\end{figure}
X
X\section{Compiling \& Viewing}
X
Suppose the {\em Cellang 2.0} program for the game of Life that appears in
XFigure~\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 a.pe-scam}.
The object code is executed and displayed by the {\tt pe-scam}
abstract machine via:
X\begin{verbatim}
pe-scam -c a.pe-scam -r times -x11 -map life.colors < life.data
X\end{verbatim}
where {\tt life.data} is a data file containing the
initial configuration of live cells and
X{\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.
X
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 a time file 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.
X
Alternatively, {\tt pe-scam} can just output the cell values which can be
filtered and/or viewed with {\tt cellview}.  An example of this style of
use is:
X\begin{verbatim}
cat  life.data | pe-scam -r times -o |
X                         cellview -x11 -map life.colors -dim 0..63,0..63
X\end{verbatim}
Where the {\tt -o} option indicates that cell values be written to the
standard output.  The ``-c a.pe--scam'' has been left out, since the
the codefile is assumed to be ``a.pe-scam'' by default.
Note that now, however, the dimensions of the cell universe must be known.
By convention, {\tt pe-scam}'s cell universe begins numbering at 0 for
each dimension.  The size and number of dimensions is implementation
dependent (and can be configured at installation time in the current release
of the software).
X
X\begin{figure}[t]
X\begin{center}
X\setlength{\unitlength}{3pt}
X\begin{picture}(31, 31)(0, 0)
X\normalsize
X
X\put(0, 20){\framebox(10, 10){0}}
X\put(10, 20){\framebox(10, 10){1}}
X\put(10, 10){\framebox(10, 10){3}}
X\put(0, 10){\framebox(10, 10){2}}
X
X\put(11, 9){\dashbox(10, 10){}}
X\put(21, 9){\dashbox(10, 10){2}}
X\put(21, -1){\dashbox(10, 10){0}}
X\put(11, -1){\dashbox(10, 10){1}}
X
X\end{picture}
X\end{center}
X\caption{Margolus neighborhood}
X\label{Margolus neighborhood}
X\end{figure}
X
X\begin{figure}[t]
X\begin{center}
X\begin{verbatim}
X                             0 1 0 1 0 1 0 1 0 1
X                             2 3 2 3 2 3 2 3 2 3
X                             0 1 0 1 0 1 0 1 0 1
X                             2 3 2 3 2 3 2 3 2 3
X\end{verbatim}
X\end{center}
X\caption{The pattern of {\tt which} field values for the Margolus neighborhood}
X\label{which Margolus}
X\end{figure}
X
X\section{Advanced Examples}
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{
X        The program is modeled closely on the version
X        described by \cite{toffoli} on page 156.
X    }
while the hexagonal neighborhood is used to calculate distance.
X
X\begin{figure}[tbp]
X\begin{center}
X\footnotesize
X\begin{verbatim}
X2 dimensions of
X        which of 0..3
X        rand  of 0..1
X        gas   of 0..1
end
X
X# Calculate the shared random value in the block of 4 cells.
random := cell.rand + [1, 0].rand + [1, -1].rand + [0, -1].rand
X                when (cell.which = 0 & time%2 = 1) | (cell.which = 3 & time%2 = 0)
X
X       := [-1, 0].rand + cell.rand + [0, -1].rand + [-1, -1].rand
X                when (cell.which = 1 & time%2 = 1) | (cell.which = 2 & time%2 = 0)
X
X       := [-1, 1].rand + [0, 1].rand + cell.rand + [-1, 0].rand
X                when (cell.which = 3 & time%2 = 1) | (cell.which = 0 & time%2 = 0)
X
X       := [0, 1].rand + [1, 1].rand + [1, 0].rand + cell.rand
X                otherwise
X
X# Alternate between the overlapping 4 cell blocks
if time%2 = 1 then
X        if random%2 = 1 then
X                # Clockwise rotation
X                cell.gas := [0, -1].gas when cell.which = 0
X                         := [-1, 0].gas when cell.which = 1
X                         := [0, 1].gas when cell.which = 3
X                         := [1, 0].gas when cell.which = 2
X        else
X                # Counter-clockwise rotation
X                cell.gas := [1, 0].gas when cell.which = 0
X                         := [0, -1].gas when cell.which = 1
X                         := [-1, 0].gas when cell.which = 3
X                         := [0, 1].gas when cell.which = 2
X        end
else
X        if random%2 = 1 then
X                # Clockwise rotation
X                cell.gas := [0, -1].gas when cell.which = 3
X                         := [-1, 0].gas when cell.which = 2
X                         := [0, 1].gas when cell.which = 0
X                         := [1, 0].gas when cell.which = 1
X        else
X                # Counter-clockwise rotation
X                cell.gas := [1, 0].gas when cell.which = 3
X                         := [0, -1].gas when cell.which = 2
X                         := [-1, 0].gas when cell.which = 0
X                         := [0, 1].gas when cell.which = 1
X        end
end
X
X# Stir the random values, so that they keep changing.
cell.rand := ([1, 0].rand + [0, 1].rand + [-1, 0].rand + [0, -1].rand + cell.rand)%2
X\end{verbatim}
X\end{center}
X\caption{Gas diffusion using a Margolus neighborhood}
X\label{gas diffusion}
X\end{figure}
X
X\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
X(Margolus neighborhood) and having each block of cells randomly rotate their
gas particles either clockwise or
counter--clockwise.
X
To better understand the Margolus neighborhood, consider
XFigure~\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 2.0} 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 shown in Figure~\ref{which Margolus}.
X
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 2.0} program that implements gas diffusion is shown in
XFigure~\ref{gas diffusion}.
X
X\begin{figure}[tbp]
X\begin{center}
X\setlength{\unitlength}{4pt}
X\begin{picture}(80, 60)(0, 0)
X
X\multiput(10, 40)(20, 0){3}{\framebox(10, 20)
X    {\shortstack{\,n\vspace{1ex}\\
X            \, nw \  ne \vspace{6.2ex}\\
X            \, sw \ \, se \vspace{1ex}\\
X            s}}}
X\multiput(10, 20)(20, 0){3}{\framebox(10, 20)
X    {\shortstack{\,n\vspace{1ex}\\
X            \, nw \  ne \vspace{6.2ex}\\
X            \, sw \ \, se \vspace{1ex}\\
X            s}}}
X\multiput(10, 0)(20, 0){3}{\framebox(10, 20)
X    {\shortstack{\,n\vspace{1ex}\\
X            \, nw \  ne \vspace{6.2ex}\\
X            \, sw \ \, se \vspace{1ex}\\
X            s}}}
X
X\multiput(0, 30)(20, 0){4}{\framebox(10, 20)
X    {\shortstack{\,n\vspace{1ex}\\
X            \, nw \  ne \vspace{6.2ex}\\
X            \, sw \ \, se \vspace{1ex}\\
X            s}}}
X\multiput(0, 10)(20, 0){4}{\framebox(10, 20)
X    {\shortstack{\,n\vspace{1ex}\\
X            \, nw \  ne \vspace{6.2ex}\\
X            \, sw \ \, se \vspace{1ex}\\
X            s}}}
X
X\end{picture}
X\end{center}
X\caption{A portion of a ``squeezed'' hexagonal universe}
X\label{hexagons}
X\end{figure}
X
X\begin{figure}[tbp]
X\begin{center}
X\begin{verbatim}
X                             0 1 0 1 0 1 0 1 0 1
X                             1 0 1 0 1 0 1 0 1 0
X                             0 1 0 1 0 1 0 1 0 1
X                             1 0 1 0 1 0 1 0 1 0
X\end{verbatim}
X\end{center}
X\caption{The pattern of {\tt which} field values for the hexagonal neighborhood}
X\label{which hexagon}
X\end{figure}
X
X\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 2.0}.  Simply imagine taking a hexagon and squeezing in
at the sides, yielding 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 (north
east), se (south east), s (south), sw (south west) and nw (north west).
X
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{which hexagon} 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{
X    In order to more accurately display (in X--Windows) the height--
X    width ratio of the ``hexagons'', the option ``--s 5,3'' to
X    {\tt pe-scam}/{\tt cellview} makes the displayed cells 5 pixels
X    wide and 3 pixels high.
X}
X
X\begin{figure}[p]
X\begin{center}
X\begin{verbatim}
X#                          north
X#                          -----
X#                    nw  /       \  ne
X#                       /         \
X#                       \         /
X#                    sw  \       /  se
X#                          -----
X#                          south
X#
X2 dimensions of
X        which of 0..1
X        dist  of 0..255
end
X
X# Identification of the neighboring cells.
X#
if cell.which = 0 then
X        north := [0, 1]
X        ne    := [1, 0]
X        se    := [1, -1]
X        south := [0, -2]
X        sw    := [-1, -1]
X        nw    := [-1, 0]
else
X        north := [0, 2]
X        ne    := [1, 1]
X        se    := [1, 0]
X        south := [0, -1]
X        sw    := [-1, 0]
X        nw    := [-1, 1]
end
X
min_dist := 255
min_dist := north.dist when north.dist < min_dist & north.dist > 0
min_dist := ne.dist    when ne.dist    < min_dist & ne.dist    > 0
min_dist := se.dist    when se.dist    < min_dist & se.dist    > 0
min_dist := south.dist when south.dist < min_dist & south.dist > 0
min_dist := sw.dist    when sw.dist    < min_dist & sw.dist    > 0
min_dist := nw.dist    when nw.dist    < min_dist & nw.dist    > 0
X
cell.dist := min_dist + 4 when cell.dist = 0 & min_dist < 255
X\end{verbatim}
X\end{center}
X\caption{Calculating distance with hexagonal neighborhood}
X\label{dist}
X\end{figure}
X
X\section{How To Find Out More}
X
The entire {\em Cellular} system is available from the author.  Please
send requests to either:
X\begin{center}
J Dana Eckart\\
Box 6933\\
Computer Science Department\\
Radford University\\
Radford, VA \ 24142\\
X\ \\
or\\
X\ \\
[e-mail]\\
X\end{center}
X
X\begin{thebibliography}{99}
X
X\bibitem{Chen}
Chen, Shiyi, Hudong Chen and Gary D. Doolen,
X``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.
X
X\bibitem{wireworld}
Dewdney, A. K., ``The Cellular Automata Programs That Create Wireworld,
Rugworld and Other Diversions'',
X{\em Scientific American}, {\bf 262}:1 (January 1990), 146--149.
X
X\bibitem{crystals}
Dewdney, A. K., ``A Cellular Universe of Debris, Droplets, Defects and Demons'',
X{\em Scientific American}, {\bf 261}:2 (August 1989), 102--105.
X
X\bibitem{fluids}
Dewdney, A. K., ``The Hodgepodge Machine Makes Waves'',
X{\em Scientific American}, {\bf 259}:2 (August 1988), 104--107.
X
X\bibitem{pe-scam}
XEckart, J. Dana, ``A Parallel Extendible Scalable Cellular Automata Machine:
PE--SCAM'',
X{\em Proceedings of the ACM $20^{th}$ Annual Computer Science Conference},
March 3--5, 1992, 467--472.
X
X\bibitem{cellang 1.0}
XEckart, J. Dana, ``A {\em Cellular} Automata Simulation System'',
X{\em SIGPLAN Notices}, {\bf 26}:8 (August 1991), 80--85.
X
X\bibitem{life}
Gardner, Martin,
X``The Fantastic Combinations of John Conway's New Solitaire Game of `Life','',
X{\em Scientific American}, {\bf 223}:4 (April 1970), 120--123.
X
X\bibitem{harbison}
Harbison, Samuel P. and Guy L. Steele Jr., {\em C: A Reference Manual},
Prentice Hall, Englewood Cliffs, New Jersey, 1991.
X
X\bibitem{cellsim}
Langton, Chris and Dave Hiebeler, {\em Cellsim}, available by anonymous
ftp from isy.liu.se, Version 2.5.
X
X\bibitem{Lavallee}
Lavalle\`e, Paul, Jean Pierre Boon and Alain Noullez,
X``Lattice Boltzmann Equation for Laminar Boundary Flow'',
X{\em Complex Systems}, {\bf 3} (1989), 317--330.
X
X\bibitem{Lim}
Lim, Hwa A., ``Lattice Gas Automata of Fluid Dynamics for Unsteady Flow'',
X{\em Complex Systems}, {\bf 2} (1988), 45--58.
X
X\bibitem{Scamper}
Palmer, Ian J., {\em Scamper}, available by anonymous ftp from ftp.uu.net.
X
X\bibitem{SLANG}
Sieburg, Hans B. and Oliver K. Clay, ``The Cellular Device Machine Development
System for Modeling Biology on the Computer'', {\em Complex Systems},
X{\bf 5} (1991), 575--601.
X
X\bibitem{toffoli}
Toffoli, Tommaso and Norman Margolus,
X{\em Cellular Automata Machines: A New Environment for Modeling},
The MIT Press, Cambridge, Massachusetts, 1987.
X
X\bibitem{Wolf-Gladrow}
Wolf--Gladrow, D. A., R. Nasilowski and A. Vogeler,
X``Numerical Simulations of Fluid Dynamics with a Pair Interaction
Automaton in Two Dimensions'',
X{\em Complex Systems}, {\bf 5} (1991), 89--100.
X
X\end{thebibliography}
X
X\end{document}
END_OF_FILE
if test 28266 -ne `wc -c <'tutorial.tex'`; then
    echo shar: \"'tutorial.tex'\" unpacked with wrong size!
fi
# end of 'tutorial.tex'
fi
echo shar: End of archive 3 \(of 3\).
cp /dev/null ark3isdone
MISSING=""
for I in 1 2 3 ; do
    if test ! -f ark${I}isdone ; then
    MISSING="${MISSING} ${I}"
    fi
done
if test "${MISSING}" = "" ; then
    echo You have unpacked all 3 archives.
    rm -f ark[1-9]isdone
else
    echo You still need to unpack the following archives:
    echo "        " ${MISSING}
fi
##  End of shell archive.
exit 0