Trep

Trep is a language created by User:TriMill based on binary tree rewriting.

Trep

Paradigm(s)	Declarative
Designed by	User:TriMill
Appeared in	2021
Computational class	Turing complete
Major implementations	In progress
File extension(s)	.trep

Syntax

statement   := pattern "=" pattern ";"
expression  := symbol | "(" expression expression ")"
pattern     := symbol | placeholder | "(" pattern pattern ")"
placeholder := /\$[^()=;$#\s]+/
symbol      := /[^()=;$#\s]+/

Whitespace is ignored, except where it is used to separate expressions in pairs. Line comments are written beginning with a #.

A Trep program is made up of a sequence of rewriting rules (statements) separated by semicolons, followed by a tree (an expression) to perform the replacements on. A statement is made up of two parts (the pattern and replacement) separated by an equals sign (=).

Expressions are one of the following:

• A pair (a b), where a and b are expressions.
• A symbol, the leaves of the tree, which can be any string of characters besides ( ) $ = ; and whitespace.
• A placeholder (only valid in patterns and replacements), which is a dollar sign $ followed by any characters allowed in symbols.

Placeholders cannot be repeated in the pattern, but can be in the replacement. Every placeholder used in the replacement must be present in the pattern. Placeholders in the pattern that are unused are named $_, $__, etc. by convention.

Here is an example program:

(a b) = (c (d d));
(c $x) = ($x q);
(c (a b))

Each pattern is checked in order to see if it matches the tree anywhere. If it does, the matching section of the tree will be replaced with the replacement expression and matching will restart from the first pattern. When no patterns match the tree, the program halts (and optionally outputs the final tree). Symbols only match if they are identical. Pairs only match if both of their elements match. Placeholders can match any expression.

When the above program is run: the following substitutions will be performed:

• Pattern 1 replaces (a b) with (c (d d)), the new tree is (c (c (d d)))
• Pattern 2 replaces (c (c (d d))) with ((c (d d)) q), the new tree is ((c (d d)) q)
• Pattern 2 replaces (c (d d)) with ((d d) q), the new tree is (((d d) q) q)
• No more patterns match, execution halts

Matching is always attempted outside-in (the whole tree is checked first, then its sub-trees are checked recursively), and the left side of a pair is checked before the right side. As an example, (a $_) = z; applied to (a (a b)) will match the entire tree, resulting in z.

Computational class

Trep is Turing-complete, since SKI combinator calculus can be trivially implemented as follows:

(I $x) = $x;
((K $x) $y) = $x;
(((S $x) $y) $z) = (($x $z) ($y $z));

Examples

In these examples, numbers are represented via the Peano axioms, so (succ 0) is 1, (succ (succ 0)) is 2, etc.

Boolean operations:

((and true) $x) = $x;
((and false) $_) = false;
((or true) $_) = true;
((or false) $x) = $x;
(not true) = false;
(not false) = true;
((xor false) $x) = $x;
((xor true) $x) = (not $x);

Addition and multiplication:

((+ $x) 0) = $x;
((+ $x) (succ $y)) = (succ ((+ $x) $y));
((* $x) 0) = 0;
((* $x) (succ $y)) = ((+ $y) ((* $x) $y));

Equality:

((eq 0) 0) = true;
((eq (succ $_)) 0) = false;
((eq 0) (succ $_)) = false;
((eq (succ $x)) (succ $y)) = ((eq $x) $y);

Using the above statements to check if 5 equals 3 + 2 (this should result in true):

((eq 
  (succ (succ (succ (succ (succ 0))))) ) 
  ((+ (succ (succ (succ 0)))) (succ (succ 0))) )

Truth machine (uncomment true and it loops forever, uncomment false and it halts):

true = true;
# true
# false

Implementations

In progress