Sym
Sym is a small Esolang created by sugarfi. It is based around the idea of replacing symbols via rules. Every Sym program has two elements:
- An arbitrary set of symbols.
- A set of rules that apply to those symbols.
Symbols are described as single characters, and rules are described as a single character rule name followed by a dot followed by several symbols followed by the body, separated with an equals sign. In EBNF (using regex, ) this can be expressed as:
symbol ::= r"."
pattern ::= <symbol> | <symbol> "_" | <symbol> "..." | <symbol> "_" "..." | "(" <pattern ")"
call ::= r"." "." (<symbol> | <call>)+
rule ::= r"." "." <pattern>+ "=" (<pattern> | <symbol> | <call>)+
Note here the definition of call: a rule is invoked using its name and a dot. An example rule that replaces every a with a b might look like this:
r.a = b
Note also the definition of pattern above. Rules are pattern matched: a rule followed by an underscore denotes an unbound symbol: it will match any single symbol, and can be accessed in the rule body using its name. For example, if a rule's arguments contained a_, the matched symbol could be referenced as a+ in the body. As well, a symbol, unbound or otherwise, can be postfixed with a "..." to match a sequence of symbols. An unbound repeated symbol matches any sequence of symbols; a bound one matches any sequence of a particular symbol. For example, in the below f will match any number of as and replace them with a single 1, but replace any amount of any other symbol with 0:
f.a... = 1 f.a_... = 0
An unbound symbol that is repeated, ie. x_..., can be referenced in the rule body as only its name. For example, if a pattern x_... matched abc, we would use x_ to refer to that group of symbols in the ruby body. Normally an overbar would be used in place of an underscore, but in the interest of time I am formatting it as is. Finally, a pattern can be surrounded by parentheses to make it optional: the rule pattern a(b) would match a or ab. Rule patterns must be exhaustive; behavior is undefined and (hypothetically) implementation dependent if a pattern is passed to a rule that does not match.
Computational Class
Sym is Turing complete. This can be proved as follows:
Sym can be used to described a simple languages similar to [P\]. The language operates on an arbitrary tape of 0s and 1s with a third symbol t marking the position of the header. For example, the tape 00t11 signifies there are four elements, 0011, and the tape header is on the third one. This language has three instructions:
- r, which moves the tape header right. It wraps, so there is no need for an l.
- f, which flips the pointed-to symbol from a 0 to a 1 and from a 1 to a 0.
- i, which behaves like r if and only if the pointed-to symbol is 1. Otherwise it is a no-op.
These can be defined using the following rules:
r.(x_...)ty_z_ = z_y_tz_ r.x_...t = tx_... f.(x_...)t0(y_...) = x_t1y_ f.(x_...)ty_(z_...) = x_t0z_ i.(x_...)t1(y_...) = x_1ty_ i.x_... = x_
Then we chain these rules in reverse order to represent a proram, with the tape as an initial input: the program irif with an initial tape of 000 would be written as f.i.r.i.000. For the rest of this proof, the alternative syntax 000irif will be used.
Now that we have our language, it is trivial to implement a simple logic gate, in this case an and. We described the and as a function a such that:
a(1, 1) = 1 a(x, y) = 0
That can be represented as the program xy0iif, where x and y are the two arguments to a. Output is given in the third item on the tape, while the first two are undefined: thus, a(1, 1) would output ??1, and a(x, y) ??0, where ? is an undefined value. This and can be changed to a nand by altering the initial tape: xy1iif denotes a nand. Nand gates are universal, so instances of this program can be chained to perform any computation.