Skip to content

old NDCA Specification

Jump to bottom
HactarCE edited this page May 1, 2020 · 1 revision

NDCell Automaton Language

Basic symbols/syntax

  • @ is used for directives
  • # is used for tags and state IDs
  • () groups an expression or calls a function
  • [] contains a comma-separated vector
  • {} contains a comma-separated list
  • "abc" and 'abc' are both strings
  • // begins a comment, which ends at the end of the line
  • /* begins a block comment, which ends at the next */

All whitespace is semantically equivalent to a single space .

Constants

The following names are reserved for predefined constants:

  • true = 1
  • false = 0
  • any = a state matcher which matches any state
  • N = [0, 1] ("north")
  • S = [0, -1] ("south")
  • E = [1, 0] ("east")
  • W = [-1, 0] ("west")
  • NE = [1, 1] ("northeast")
  • SE = [1, -1] ("southeast")
  • NW = [-1, 1] ("northwest")
  • SW = [-1, -1] ("southwest")
  • U = [0, 0, 1] ("up")
  • D = [0, 0, -1] ("down")

Types

NDCA is statically typed.

Types:

  • number (e.g. 10)
  • vector (e.g. [1, 2, 3])
  • state (e.g. #10)
  • tag (e.g. #tag_name)
  • tag value (e.g. #tag_name:10 or #tag_name:value_name)
  • pattern (e.g. napkin)
  • list
  • state matcher
  • pattern matcher

Common operations

All types support the following comparisons:

  • a == b
  • a != b

These always return 1 (true) if a and b are equal and 0 (false) if they are not. Two values can only be compared if they are the same type, or if one type can be automatically converted into the other.

Automatic type conversions

Numbers are automatically converted into vectors when used where a vector is expected. The resulting vector has the original numeric value along all axis. For example, converting 3 to a vector in a 2D automaton results in [3, 3].

Tags are automatically converted to state matchers when used where a state matcher is expected.

Numbers

All numbers are signed 32-bit integers.

Numbers support basic math operations:

  • Addition: a + b
  • Subtraction: a - b
  • Multiplication: a * b
  • Division: a / b (rounds down)
  • Modulo: a % b (always positive)
  • Exponentiation: a ** b
  • Negation: -a
  • Bitshift: a << b, a >> b
  • Bitwise AND: a & b
  • Bitwise OR: a | b
  • Bitwise XOR: a ^ b
  • Bitwise complement: ~a

Numbers can be compared:

  • a == b
  • a != b
  • a < b
  • a > b
  • a <= b
  • a >= b

There are three unary functions which operate on numbers:

  • Logical NOT: not(a)
    • equivalent to a == 0
  • Convert to boolean: bool(a)
    • equivalent to a != 0
  • Absolute value: abs(a)

To get the cell state with a given numeric ID, use the unary # operator:

  • #10
  • #(a) - use parentheses when value is stored in a variable

Vectors

All vectors have the same number of dimensions as the automaton. Unspecified vector components are initialized to zero.

Vectors support all of the same math operations as numbers, which operate elementwise. For example, [1, 2, 3] + [4, 4, -1] is [5, 6, 2].

Vectors support only two comparison operations:

  • a == b
  • a != b

Vectors support the same three unary functions as numbers:

  • Logiical NOT: not(a)
    • equivalent to a == 0
  • Convert to boolean: bool(a)
    • equivalent to a != 0
  • Absolute value: abs(a)
    • operates elementwise; returns a vector

Each component of a vector is a signed 32-bit integer and can be accessed individually using the name of the axis:

  • Vector component access: my_vector.X

Vector "swizzling" is supported. For example my_vector.XZY returns my_vector but with the Y and Z components swapped.

States

States can be constructed from a number using the # prefix. For example, #10 is the state with ID 10, and #(some_number) is the state with ID stored in the variable some_number. Note that when constructing a state from a number stored in a variable (e.g. #(some_variable)) or as a result from an expression (e.g. #(2 + 3)), parentheses are required.

States have tag attributes, which are numbers. To get the value of a tag, write the state followed by the tag. For example, state#tag_name returns the value of #tag_name on state.

When used with is or any of the set operators &, |, ^, or ~, a state automatically coerces to a state matcher that is true for its own state and false for all other states. For example, #10 | #15 matches only the state with ID 10 and the state with ID 15, and ~#10 matches any state with an ID other than 10.

Tags

Tags are identifiers with the # prefix (e.g. #tag_name). Tags are used in state definitions and as matchers.

A tag is a property of a state. For each tag (denoted #tag_name), every state has a numeric value. Unless otherwise specified, this numeric value is 0. When a state is defined, it can be given some other value.

Tag values

Tag values are tags followed by : and then either an identifier or a number (e.g. #tag_name:value_name or #tag_name:10). Tag values are used in state definitions and as matchers.

Each named tag value (denoted #tag_name:value_name) is automatically assigned a nonzero number that it is equivalent to; for example, if #some_tag:some_value is assigned the number 3, then #some_tag:some_value is equivalent to #some_tag:3.

Pattern

TODO

Lists

A list is defined using curly braces {}, with commas between elements. A trailing comma is allowed. For example, {1, 2, 3} is a list of the numbers 1, 2, and 3. A list must contain only one data type.

start..end constructs a list of numbers ranging from start to end, including both endpoints; for example, 1..5 is equivalent to [1, 2, 3, 4, 5]

A list's length is given by some_list.len.

A list can be indexed using a numeric index: some_list[10] or some_list[some_index]. The first element of a list has the index 0, and the last element has the index list.len - 1.

Lists can be concatenated using the .. operator (e.g. list1 .. list2).

TODO: list slicing using ranges? Pythonesque negative indices?

State matcher

When a state, tag, or tag value is used with is or any of the set operators &, |, ^, or ~, it is first converted to a state matcher according to the following rules.

  • #10 matches only the state with ID 10
  • #tag_name matches any state with a nonzero tag value for #tag_name
  • #tag_name:value matches any state with the tag value #tag_name:value

State matchers are primarily used in is expressions: state is state_matcher returns 1 (true) if state_matcher matches state and 0 (false) if it does not.

Pattern matcher

TODO

Variables

Variables can be created or modified using set var_name = expression. Variables can hold any value.

Control flow

There are several control flow constructs, modelled. <condition> stands for an expression which evaluates to a number, vector, or list; it is considered falsey if it is zero/empty and truthy if it is nonzero/nonempty.

  • if <condition> then ... end
  • if <condition> then ... else ... end
  • if <condition1> then ... else if <condition2> then ... end
  • if <condition1> then ... else if <condition2> then ... else ... end
  • while <condition> do ... end

TODO: iterators/for loops and switch statement

Directives

Directives must be top-level; i.e. they cannot appear nested inside of other directives or code blocks. Most directives take only a single value, but some have special syntax. Each directive can only appear at most once. @ndca and @name are required; all directives are optional. @author, @designer, and @year all default to "Unknown"; @description and @url default to an empty string; the default values for all other directives are shown below.

// Version of NDCA that this rule was written for
@ndca 0

// Name of automaton rule
@name "CA Name"

// Name of person who wrote this file
@author "Your Name"

// Name of person/people who first described this automaton
@designer "Name(s) of Designers"

// Year that this automaton was first described
@year "2020"

// Link to research paper, forum post, or wiki page describing this automaton
@url "https://www.example.com/"

// A multiline description of this automaton
@description "
A multiline description of this CA rule.

Blank lines are trimmed from the beginning and end of this description.
"

// Default pattern
// TODO: creator/description/year of default pattern?
@pattern r"!"

// Number of dimensions
@dim 2

// Neighborhood radius
@radius 1

// Cell states
@states { #dead, #alive }

// Transition function, terminated by keyword `end`
@transition
  remain
end

If @author is specified but not @designer, @designer will be the same as @author.

Two directives, @states and @transition, do not take a simple value. Both are described below.

State definitions

@states takes a list of state definitions. Each state definition consists of several state properties, separated by whitespace. If a state has no properties, _ must be used to express this.

State properties:

  • a state ID (e.g. #10), which forces the state ID
  • a tag (e.g. #tag_name), which is equivalent to #tag_name:1
  • a tag value (e.g. #tag_name:10 or #tag_value:value_name), which gives the state the given value for that tag.

Transition function

The transition function contains code that is executed to determine the next state of a given cell. Two special variables are accessible inside the transition function and cannot be modified:

  • this is the state of the center cell
  • napkin is the patten of cells in the surrounding region

TODO: allow napkin mask (i.e. neighborhood) to be modified

Style

Due to the decision-tree-like nature of many cellular automata, NDCA code may make quite heavy use of nesting. For this reason, NDCA files should be indented with 2 spaces per indent level.

Lines longer than 80 characters should be avoided, either by rewriting or by splitting one statement into multiple lines. Long lines are ok in a multiline string though.

The description should be wrapped to ~80 characters, and paragraphs should be separated by a blank line. In the future, basic markdown syntax may be supported.

If any state has multiple tags, then the members of @states should be split so that each state is specified on its own line.

Clone this wiki locally