From Esolang
Jump to navigation Jump to search

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


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.


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.


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


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


among many others. This is distinct from the statement


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

Rule statements

The rule statement


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


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


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


and the interpreter would output


See also

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