Tuesday

Tuesday is an esoteric programming language created by Tanner Swett in 2013. It is a matrioshka language inspired by Thue.

Language description

Parsing a Tuesday program consists of removing all lines whose first non-whitespace character is a number sign (#), followed by removing all whitespace characters, followed by parsing the result according to the following grammar:

<program> ::= {<statement> ";"} <expression>
<statement> ::= <expression> ":" <expression>
<expression> ::= { lowercase English letter | uppercase English letter | "(" <expression> ")" }

In the below, an *expression* is a (possibly empty) sequence of lowercase letters, uppercase letters, nonce symbols, and/or correctly matched parentheses.

Each statement represents a rewrite rule, meaning "replace (left hand side) with (right hand side)", where the left hand side is a pattern using uppercase letters as variables, and the right hand side is a template using the same uppercase letters to refer to whatever those letters matched on the left hand side.

Execution begins with replacing each uppercase letter in the expression at the end of the program (the current expression) with a new nonce symbol, distinct from all letters, parentheses, and previously introduced nonce symbols. Each occurrence of the same letter must be replaced with the same symbol; occurrences of different letters must be replaced with different symbols.

From then on, execution consists of repeatedly making an unspecified legal replacement until it is no longer possible to make a legal replacement. A legal replacement consists of replacing a substring of the current expression, the matched substring, with another substring, the replacement substring, such that:

• The replacement is done according to some rule.
• For each uppercase letter that occurs on the left hand side of the rule, that letter has an assignment, which is an expression that does not contain any uppercase letters. (Different occurrences of the same letter can't have different assignments.)
• The assignment of each uppercase letter that occurs on the right hand side of the rule, but not the left hand side of the rule, is a new nonce symbol (distinct from all letters, parentheses, and previously introduced nonce symbols). Different uppercase letters can't have the same nonce symbol as their assignment.
• The matched substring is equal to the result of replacing every uppercase letter in the left hand side of the rule with its assignment.
• The replacement substring is equal to the result of replacing every uppercase letter in the right hand side of the rule with its assignment.

Sample program

These rules ought to implement the SKI calculus, where the application of x to y is denoted by x(y), and the entire expression is surrounded with parentheses:

(s(X)(Y)(Z)R): (X(Z)(Y(Z))R);
(k(X)(Y)R): (XR);
(i(X)R): (XR);

Notice that the above shows that Tuesday is Turing complete.