DragonFly On-Line Manual Pages

2d-rewriter(l) l 2d-rewriter(l)

NAME
2d-rewriter - a cellular automata simulator

SYNOPSIS
2d-rewriter [-h]
2d-rewriter [-s] source_file

DESCRIPTION
-h Print a help message and quit.

-s Start in stepping mode - one pass at a step.

source_file contains declarations, rules, initial placement for objects,
etc.

COMMANDS
q quit application.

+ increase resolution 2 times, if possible. When resolution is above
16 every cell is marked by the orientation mark.

- decrease resolution 2 times, if possible.

up move window up (against the data field).

up move window down (against the data field).

left move window left (against the data field).

right
move window right (against the data field).

s enter stepping mode (one pass at a step).

r enter running mode.

2d-rewriter rings the bell twice when evaluation process stops, it is
when no rule can be applied at any position. Evaluation process might
never stop.

LANGUAGE
The input language consists of statements. There is no separator. End-of-
lines are treated as blanks (except for the cases when they terminate
comments). The grammar uses following meta-symbols:

? The preceding term can appear zero or one time.

* The preceding term can appear zero or more times.

+ The preceding term can appear one or more times.

*n The preceding term must appear exactly n times.

| Alternative.

() Grouping.

x Literal `x'.

All names consist of an underscore or an alphabetical character followed
by underscores, alphabetical characters or digits. Names are case-
sensitive. Any text between `#' and the end of line is treated as a
comment. The language has following the grammar:

program ::= statement*

statement ::= "use" file_path_as_double_quoted_string
| "dimensions" width_as_integer height_as_integer
| "object" object_name object_name
| "init" object_name x_as_integer y_as_integer
| "set" set_name "{" "(" object_name+ ")"+ "}"
| "set" set_name "{" object_name+ "}"
| "rule" "(" variable_definition+ ")"?
pattern_element*9 result

variable_definition := variable_name ":" set_name

pattern_element := object_name
| set_name ( "." position_as_integer )? ( "/" orientation )?
| variable_name ( "." position_as_integer )? ( "/" orientation )?
| "*" ( "/" orientation )?

result ::= object_name ( "/" orientation )?
| variable_name ( "." position_as_integer )? ( "/" orientation )?

orientation ::= "up"
| "right"
| "down"
| "left"

use Process a given file.

dimensions
Dimensions of the data field.

object Object declaration.

init Place the specified object on the data field at the start. `init'
statements must be located after `dimension' statement.

set Declaration of an object set. Every tuple in the set must contain
the same number of objects. There is a short form where every
tuple consists of just one object.

rule Matching rule definition. The following table shows
correspondence between positions of elements in a pattern and 2D
positions (relative to the orientation) that they will be applied
to:

up_left up up_right
left center right
down_left down down_right

Line breaks do not matter but I encourage to use them for
clarity. Every pattern is tried in 4 orientations obtained by
rotation. Rules will be tried in the order they are written.
Object orientation specifies the orientation of the object
against the pattern and is checked only when specified. If all
pattern elements match, the central object will be replaced by
`result'. Orientation of the `result' is specified against the
pattern orientation as well and would be defaulted to "up", if
omitted. Borders are immutable. As a result of matching process
every used variable will be set to a particlular tuple of the
set. `position' refers to a position in the tuple, omitting the
specification sets position to 0. For example, if there is a
variable defined as `X:aset' and there are pattern elements X.0
and X.1 then match would succeed if set `aset' contains a tuple
that has a matched object at position 0 and a matched object at
position 1. The same variable can be used to specify `result'.
For example, specification X.2 will refer to an object at
position 2 of the tuple that was found in the match. Using sets
allows to reduce the total number of patterns significantly. If
`result' refers to a variable it must be a variable that was
previously mentioned in some pattern element. This prevents well-
known "use of uninitialized variable" condition but does not
eliminate an ambiguity if there is more than one tuple allowed by
the match.

Objects `border' and `ground' must be specified. The first one will be
used for the borders and the second one for the empty space (for every
cell that does not have an object placed into it using `init'
statements).

2d-rewriter works by making passes through the data field. On every pass
a set of modifications is generated using the existing data. Then, these
modifications will be applied and a new pass will follow. This algorithm
eliminates dependency on the evaluation order.

EXAMPLES
See examples installed into into `examples' directory of your system. It
is something like /usr/local/share/examples/2d-rewtiter.

ALGORITHM
Current implementation uses OBJECT * POSITION -> TUPLE_IDs_BITMAP table
and bitmap AND operation to calculate a set of qualifying tuples for a
variable. If the set is empty, then match fails. To obtain an object for
`result' the program uses TUPLE_ID * POSITION -> OBJECT table.

AUTHORS
Igor Serikov <iserikov@acm.org>

February 18, 2008