CA-DSL: A DSL for designing and visualizing cellular automata

8.17.0.3

CA-DSL: A DSL for designing and visualizing cellular automata🔗ℹ

Jordan Zedeck <zedeck.j@northeastern.edu> Nate White <natewhite345@gmail.com>

Cellular Automata are a beautiful demonstration of how complexity can emerge from simple rules. This library helps visualize and explore them.

(require ca-dsl)

package: ca-dsl

1 Types🔗ℹ

1.1 Posn🔗ℹ

struct
(struct Posn (x y)
    #:transparent)
  x : Integer
  y : Integer

Represents a cell’s position on a 2D coordinate plane.

procedure
(posn-add posn1 posn2) → Posn
posn1 : Posn
posn2 : Posn

Component-wise addition of two positions.

procedure
(posn-scale n posn) → Posn
n : Integer
posn : Posn

Produces a new Posn by multiplying a scalar to a Posn’s coordinates.

1.2 States🔗ℹ

syntax
(define-states states-name : type (state-val ...))

A macro for defining enumerated states for cellular automata. This defines:

A type named type representing the union of all states
A list states-name containing all states
Individual bindings for each state-val

The library comes with a predefined state type:

type
AliveOrDead
value
alive : AliveOrDead
value
dead : AliveOrDead

A predefined state type representing the binary states commonly used in cellular automata like Conway’s Game of Life.

1.3 Core Types🔗ℹ

The library uses parametric types with a conventional meaning for the following type variables:

C: The type of cells (e.g., Posn for cartesian grids)
O: The type of offsets (e.g., Posn for cartesian neighborhoods)
S: The type of states (e.g., AliveOrDead)

type constructor
(StateMap C S)

Represents the construct which enumerates the cells and their current states.

type constructor
(Topology C O)

Represents transitions between cells using offsets. A function type (C O -> (Union C Void)) that takes a cell and an offset and returns either a new cell or void (for invalid transitions).

type constructor
(Neighborhood O)

Represents a set of offsets used for transition calculations.

type constructor
(Rule C O S)

A function type ((StateMap C S) (Topology C O) C -> S) that computes the new state for a cell based on the current state map, topology, and the cell itself.

type constructor
(ActiveFilter C)

A function type (C -> Boolean) that determines if a cell should be updated by the rule. Cells that don’t pass this filter keep their original state for the entire simulation.

type constructor
(ColorMap S)

A function type (S -> Color) that maps states to colors for visualization.

struct
(struct World C (state-map topology active-filter)
    #:transparent)
  state-map : (StateMap C S)
  topology : (Topology C O)
  active-filter : (ActiveFilter C)

A structure representing all characteristics of a simulated "World" in which a Rule can be applied.

type constructor
(Renderer C O S)

A function type ((World C O S) -> Image) that transforms a World into an Image for visualization.

1.4 Specialized Types🔗ℹ

The library provides specialized types for common cellular automata patterns:

type constructor
(2DWorld S)

type constructor
(2DRenderer S)

Specialized types for 2D worlds where cells and offsets are both represented by Posn.

type
LifelikeRule

type
LifelikeWorld

type
LifelikeRenderer

Specialized types for cellular automata similar to Conway’s Game of Life, using the binary AliveOrDead state on a 2D world.

2 Run🔗ℹ

procedure
(run world rule renderer) → (World C O S)
  world : (World C O S)
  rule : (Rule C O S)
  renderer : (Renderer C O S)

Main entry point to a program in this language. Opens a native window to visualize the cellular automata. This function takes a world, a rule for state transitions, and a renderer for visualization, then displays the cellular automata simulation in a window. When the simulation completes, it returns the final world state.

3 Rule🔗ℹ

This section documents the macros exported by the rule module, which allow for defining cellular automata rules in various formats.

syntax
(rule #:cell-type cell-type
      #:offset-type offset-type
      #:state-type state-type
      #:neighborhood neighborhood
      clause ...)

Creates a rule function for a cellular automaton. The resulting function has the type (StateMap cell-type state-type) (Topology cell-type offset-type) cell-type -> state-type, which computes the new state for a cell based on its neighborhood.

The parameters are:

#:cell-type - The type used to represent cells in the grid
#:offset-type - The type used to represent offsets within the neighborhood
#:state-type - The type used to represent cell states
#:neighborhood - An expression that evaluates to a Neighborhood of offsets
clause ... - One or more transition rules that determine state changes

In the general case, clause has the form (from-state -> to-state) condition ... where:

from-state is the initial state
to-state is the resulting state
condition ... are optional conditions that must be satisfied for the transition to occur

Also supported is chaining multiple state transitions controlled by the same condition using (state1->state2->state3 ...) condition ... as well as specifying any state using _.

Conditions can include:

count in state
- Tests if exactly count neighbors are in state
(count₁ count₂ ...) in state
- Tests if the number of neighbors in state matches any of the counts
all in state
- Tests if all neighbors are in state
some in state
- Tests if at least one neighbor is in state
Boolean operators to join anything above in order of highest to lowest precedence: not, and/nand, xor, or/nor, implies

syntax
(moore-rule #:state-type state-type
clause ...)

A convenience macro that expands to rule with Posn as both the cell and offset types, and uses a Moore neighborhood with radius 1. This is commonly used for 2D cellular automata like Conway’s Game of Life.

The parameters are:

#:state-type - The type used to represent cell states
clause ... - One or more transition rules as in rule

syntax
(lifelike [(born condition ...)]
[(survive condition ...)])

A specialized macro for creating rules similar to Conway’s Game of Life, using the AliveOrDead state type. It automatically creates a rule where:

Dead cells become alive if they satisfy the born conditions
Living cells stay alive if they satisfy the survive conditions
All other cells become or stay dead

This provides a concise way to define various "Life-like" cellular automata such as Conway’s Game of Life, HighLife, Day & Night, and others.

4 Renderer🔗ℹ

This section documents the functions and constants exported by the renderer module, which provides visualization capabilities for cellular automata.

procedure
(make-2d-renderer color-map
[ #:cell-width-px cell-width-px
#:origin-px origin-px])
→ (Renderer Posn O S)
  color-map : (ColorMap S)
  cell-width-px : Positive-Integer = 25
  origin-px : Posn = (Posn 0 0)

Creates a renderer function that can translate a world where cells are represented by Posns to a graphical representation.

The parameters are:

color-map - A function that maps states to colors for visualization
#:cell-width-px - The width of each cell in pixels (default: 25)
#:origin-px - The position of the top-left corner of the viewport in the world coordinate system (default: (0,0))

The returned function has type (World Posn O S) -> Image, which renders the current state of the world to an image.

The renderer:

Shows cells with states as colored squares based on the color-map
Shows cells not in the state map as gray squares with an "x"
Draws a grid of cell outlines in black
Crops the view to show only what fits within the window dimensions

5 Colormaps🔗ℹ

This section documents the functions and constants exported by the colormaps module, which provides color mapping capabilities for visualizing cellular automata states.

5.1 Predefined Colors🔗ℹ

value
BLACK : Color
value
WHITE : Color
value
RED : Color
value
GREEN : Color
value
BLUE : Color
value
YELLOW : Color
value
PURPLE : Color
value
PINK : Color
value
ORANGE : Color
value
GRAY : Color
value
TRANSPARENT : Color

Predefined color constants for use in colormaps and visualization.

value
COLOR_LIST : (Listof Color)

A list of predefined colors containing "WHITE, BLACK, RED, GREEN, BLUE, YELLOW, PURPLE, PINK, and ORANGE."

5.2 Colormap Functions🔗ℹ

procedure
(colormap-alive-or-dead state) → Color
state : AliveOrDead

A predefined colormap for AliveOrDead states. Maps 'alive to BLACK and 'dead to WHITE.

procedure
(make-default-colormap states) → (ColorMap S)
states : (Listof S)

Creates a colormap that assigns a distinct color to each state in the provided list. Deterministic and can support any number of arguments.

Raises an error if asked to map a state not in the original list.

procedure
(make-grayscale-colormap minimum maximum) → (ColorMap Integer)
minimum : Integer
maximum : Integer

Creates a colormap that maps integers to grayscale colors, linearly interpolating between black and white.

The parameters:

minimum - Maps to black (RGB: 0,0,0)
maximum - Maps to white (RGB: 255,255,255)

Values between minimum and maximum are mapped to proportional shades of gray. Values less than minimum are clamped to black, and values greater than maximum are clamped to white.

6 Neighborhoods🔗ℹ

This section documents the functions exported by the neighborhoods module, which provides predefined neighborhood patterns for cellular automata.

procedure
(moore-neighborhood-outline distance) → (Neighborhood Posn)
distance : Positive-Integer

Creates a set of positions that form the outline of a Moore neighborhood at the specified distance from the center.

The function returns a set containing positions that are exactly distance units away from the center (in a square pattern). This includes all positions along the perimeter of a square with side length 2 * distance + 1.

The parameter:

distance - The distance from the center to the outline positions

For example, (moore-neighborhood-outline 1) returns a set containing the 8 positions that are exactly 1 unit away from the center, which forms the standard Moore neighborhood used in cellular automata like Conway’s Game of Life.

procedure
(moore-neighborhood [distance]) → (Neighborhood Posn)
distance : Positive-Integer = 1

Creates a complete Moore neighborhood with the specified radius.

The function returns a set containing all positions within distance units from the center (in a square pattern, using the Chebyshev distance).

The parameter:

distance - The maximum distance from the center (default: 1)

For example:

(moore-neighborhood) returns the standard 8-cell Moore neighborhood
(moore-neighborhood 2) returns a 24-cell extended Moore neighborhood

The function works by unioning the outlines at each layer from 1 to distance.

7 Grid Utilities🔗ℹ

This library provides utilities for creating and manipulating grid-based cellular automata and other grid-based simulations.

procedure
(rect-custom width height state-fn) → hash?
  width : integer?
  height : integer?
  state-fn : (-> posn? any/c)

Creates a statemap over a rectangular region with cells initialized using the given function.

The function state-fn is called with each position in the rectangle to determine the state for that cell.

procedure
(rect-from width height state-generator) → hash?
  width : integer?
  height : integer?
  state-generator : (-> any/c)

Creates a statemap over a rectangular region with cells initialized using the given thunk.

The function state-generator is called for each cell to generate its state.

procedure
(rect-solid width height state) → hash?
  width : integer?
  height : integer?
  state : any/c

Creates a statemap of a rectangle composed of the given state.

All cells in the rectangle will have the same state value.

procedure
(overlay/statemaps topology
offset
statemap ...) → hash?
  topology : any/c
  offset : any/c
  statemap : hash?

Combines multiple statemaps by overlaying them at specified positions.

Arguments alternate between an absolute position and then a statemap to be placed with its lower left corner at that absolute position. Similar in functionality to overlay/xy in the htdp2/image library.

procedure
(biased-random-select weighted-sequence) → (-> any/c)
weighted-sequence : (listof (cons/c any/c exact-nonnegative-integer?))

Creates a function that returns random selections from a weighted list of values.

weighted-sequence is a list of pairs, where each pair consists of a value and its corresponding weight (a non-negative integer). The returned function will select values with probability proportional to their weights.

syntax
(path : type-id (x-expr y-expr) segment ...)

segment = (state-expr magnitude-expr direction state-expr ...)

direction = up
| down
| left
| right

Creates a statemap representing a path with the specified segments.

type-id - The type name for the states in the path
x-expr y-expr - The starting position of the path
state-expr - The state for the current segment
magnitude-expr - The length of the current segment
direction - The direction of the current segment (up, down, left, or right)

Multiple segments can be chained together to create complex paths.

(path : AliveOrDead (-2 3) ('dead 3 up 5 right 3 down 1 left))

8 Grid Topologies🔗ℹ

This library provides functions for creating and manipulating different grid topologies for cellular automata and other grid-based simulations.

procedure
(cartesian-topology pos offset) → posn?
pos : posn?
offset : posn?

A standard topology which adds Posns linearly.

Returns a new position that is the sum of the input position and offset.

procedure
(truncate-topology topology predicate)
→ (-> any/c any/c (or/c any/c void?))
topology : (-> any/c any/c (or/c any/c void?))
predicate : (-> any/c any/c any/c boolean?)

Restricts a Topology to produce additional Void returns if an input cell, offset, and the output of the original topology do not satisfy the provided predicate.

Returns a new topology function that respects the given predicate.

procedure
(modify-topology topology modifier ...)
→ (-> any/c any/c (or/c any/c void?))
topology : (-> any/c any/c (or/c any/c void?))
modifier : (-> any/c (or/c any/c void?))

Modifies a Topology with a series of "modifiers", which each take in a Cell and produce either a Void or a new Cell value, which are applied in sequence to outputs of a topology.

Returns a new topology function with the modifiers applied.

procedure
(make-finite-cartesian-topology max-x
max-y)
→ (-> posn? posn? (or/c posn? void?))
max-x : exact-positive-integer?
max-y : exact-positive-integer?

Creates a modified cartesian topology which is restricted by the given max-x and max-y values.

Outputs cells from the cartesian topology which have x values or y values with absolute values greater than the given max-x or max-y are turned to Void.

procedure
(in-cartesian-region point
max-point
[ #:origin origin]) → boolean?
  point : posn?
  max-point : posn?
  origin : posn? = (posn 0 0)

Returns if a point is in a region bounded by the origin and the provided max-point.

A point is in the region if its coordinates are both greater than or equal to the origin’s coordinates and less than or equal to the max-point’s coordinates.

procedure
(make-wrapping-cartesian-topology x-min
x-max
y-min
y-max)
→ (-> posn? posn? posn?)
  x-min : integer?
  x-max : integer?
  y-min : integer?
  y-max : integer?

Creates a modified cartesian topology in which Posns outputs are "wrapped" around at the given values.

In this topology, if a coordinate exceeds the maximum value, it wraps around to the minimum value, and vice versa.

procedure
(init-2d-world max-x
max-y
state-initializer) → any/c
  max-x : exact-positive-integer?
  max-y : exact-positive-integer?
  state-initializer : (-> posn? any/c)

Convenience function for creating 2D worlds with bounded cartesian topologies.

The state-initializer function is used to set the starting State of each Cell in the StateMap of the world.

syntax
(define-2d-world world : state-type
                #:state-map statemap-expr
                #:active-filter active-filter-expr
                #:topology topology-expr)

   statemap-expr : hash?
   active-filter-expr : (-> posn? boolean?)
   topology-expr : (-> posn? posn? (or/c posn? void?))

Defines a 2D world with the given parameters.

world - The identifier to bind the new world to
state-type - The type of state values in the world
statemap-expr - Expression producing the state map for the world
active-filter-expr - Optional expression producing an active filter function
topology-expr - Optional expression producing a topology function

The #:active-filter and #:topology parameters are optional.

1	Types
2	Run
3	Rule
4	Renderer
5	Colormaps
6	Neighborhoods
7	Grid Utilities
8	Grid Topologies