DragonFly On-Line Manual Pages

Search: Section:  

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


2d-rewriter - a cellular automata simulator


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


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


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.


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.


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


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.


Igor Serikov <iserikov@acm.org> February 18, 2008

Search: Section: