Eodermdrome

From Esolang

Eodermdrome is a graph-rewriting tarpit created in 2008 by User:ais523.

[edit] Syntax

An Eodermdrome program consists of a sequence of commands, separated by whitespace; each command consists of the following, separated by whitespace:

optionally, a set of 1 or more characters enclosed in parentheses (if a closing parenthesis is in that set, it must be the first character of that set); this is the input set of the command
a string of letters, representing a graph (see below); this is the match subgraph
optionally, a string of 1 or more characters enclosed in parentheses (the first character may be a closing parenthesis, but none of the others may be); this is the output string of the command
a string of letters, representing a graph (see below); this is the replacement subgraph

Graphs are written with a string of lowercase letters; each unique letter in the string represents a different node of the graph, and if the same letter is used more than once, it refers to the same node of the graph. There is an arc between any two letters which are consecutive in the string, but not otherwise. For instance, the string abcdae would map to the following graph:

c-d
| |
b-a-e

Comments can be included in the source file between commas, and are legal anywhere whitespace would be; also, any strings of whitespace that contain punctuation marks other than commas and parentheses are ignored along with the punctuation marks they contain (so abc. def is equivalent to abcdef).

[edit] Semantics

An Eodermdrome program works by repeatedly rewriting a graph, which represents the internal state of the program. At the start of any Eodermdrome program, the internal state is the graph corresponding to the string thequickbrownfoxjumpsoverthelazydog. Which letter is used for which node is immaterial between commands; it's the shape of the graph that matters, not the letters used to define it.

Execution of the program works by repeatedly running commands; the commands do not run in any particular order and can run any number of times. However, commands only run if all their prerequisites are met. If no command in the program has its prerequisites met, the program will exit; otherwise, an unspecified command whose prerequisites are met will be run (this means that an interpreter can always choose the first, or the last, or a random command, or use any other method to determine which command runs, if more than one can run).

If a command has an input set, it has a prerequisite that the next character to be read in from standard input must be a member of the set.

All commands also have a prerequisite based on their subgraphs and the internal state graph: the match subgraph must be a subgraph of the internal state graph (i.e. there is a 1-to-1 mapping of a subset of the internal state graph's nodes to the match subgraph's nodes, such that all arcs in the match subgraph also exist between the corresponding nodes in the internal state graph), and also all closed nodes in the match subgraph must have the same degree as the corresponding node in the internal state graph. A node in a match subgraph is open if the letter used to describe it in the match subgraph is also used to describe a node in the replacement subgraph, and closed otherwise; likewise, a node in a replacement subgraph is open if the letter used to describe it in the replacement subgraph is used to describe a node in the match subgraph, and closed otherwise.

When a command runs, it does the following, in order:

Removes a character from standard input, if it has an input set
Prints its output string to standard output, if it has one
Deletes all nodes from the internal state graph that correspond to closed nodes in the match subgraph, and all arcs connecting to them
Deletes all arcs in the internal state graph between two nodes that both correspond to open nodes in the match subgraph
Creates a node in the internal state graph corresponding to each closed node in the replacement subgraph
For each arc in the replacement subgraph, create an arc in the internal state graph corresponding to it (i.e. such that if two nodes are joined in the replacement subgraph, an arc is created between the two nodes in the internal state graph that correspond to them)