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.
The following term statements declare the characters
s as terms.
The following term statement uses the meta-variables
(b) to state for all terms
`(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
`sk ``skk `s`kk
among many others. This is distinct from the statement
which would require the term
(a) to appear twice identically.
The rule statement
says to rewrite
``k followed by terms
(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.
The SK calculus could be described in Trml as
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
and the interpreter would output
- Thue is a matrioshka language that uses a non-deterministic string-rewriting paradigm.