Trml

Trml is a term-rewriting matrioshka language discovered by User:Orby in May of 2020.

Purpose

Trml is used to describe the syntax and semantics of term-rewriting languages. It provides a formal language in which a term-rewriting language can be described. Many esoteric programming languages may be described as term-rewriting languages, such as Underload, Unlambda, and Clementine.

Description

A Trml description is divided into statements. There are two types of statements. Term statements describe the structure of a term. Rule statements describe rewrite rules. Rule statements contain a colon to delineate between the pattern to be matched and the pattern to which it is rewritten. Term statements do not contain colons. Each statement is terminated by a semicolon. Term meta-variables are referenced by one or more characters contained within parentheses. All white space in a Trml description is ignored. Rewrite rules are applied from left to right and from first appearing to last appearing, deterministically.

Term statements

The following term statements declare the characters k and s as terms.

k;
s;

The following term statement uses the meta-variables (a) and (b) to state for all terms (a) and (b), `(a)(b) is also term.

`(a)(b);

Notice the character ` has no special meaning in Trml. We could use any character here, but we choose ` because it is commonly used for application. This means that the following strings are terms

`sk
``skk
`s`kk

among many others. This is distinct from the statement

`(a)(a)

which would require the term (a) to appear twice identically.

Rule statements

The rule statement

``k(a)(b):(a);

says to rewrite ``k followed by terms (a) and (b) to the term (a). For example, the expression ``ksk would be rewritten to s. This is how the K combinator works in SK calculus. We could express the S combinator of SK calculus as

```s(a)(b)(c):``(a)(c)`(b)(c);

In that case, the expression ```sskk would be rewritten to ``sk`kk. Notice we can distinguish between term statements and rule statements by the presence of a colon.

Complete example

The SK calculus could be described in Trml as

s;k;`(a)(b);``k(a)(b):(a);```s(a)(b)(c):``(a)(c)`(b)(c);

Matrioshka language

Trml is a matrioshka language. That is, it is possible to program in the object language described by a Trml definition. The use of the $ character denotes the end of the meta-description and the beginning of the object language program. We could express the SK calculus program ```skkk as

s;k;`(a)(b);``k(a)(b):(a);```s(a)(b)(c):``(a)(c)`(b)(c);$```skkk

and the interpreter would output

k

See also

• Thue is a matrioshka language that uses a non-deterministic string-rewriting paradigm.