Thue resources

2003-08-08
[ EN | FR ]

Introduction

Thue is an esoteric language invented by John Colagiola in 2000. The Thue web pages tend to grow scarce these days, so I've included copies of material initially found on the web before it disappeared.

Description

Here is a short description of the language. Refer to the Thue reference manual in the original distribution for more details.

A Thue program consists of two parts: the rule base and the initial data. The rule base is a list of rules expressed in the form:

<left-hand-side>::=<right-hand-side>

where the left hand side (LHS) and right hand side (RHS) are strings of characters. The line

::=

separates the rule base from the initial data; The initial data is the string of characters resulting from the concatenation of all subsequent lines, omitting the <newline> characters.

Thue works by repeatedly picking at random a rule whose LHS string is contained in the current data, and replacing the LHS by the RHS. The program stops when no rule can match.

Input/output

Input/output is allowed by the following primitives:

Rules of the form:

<left-hand-side>::=~<output-string>

(i.e. rules whose RHS begin with a ~) allow output: when triggered, the LHS is deleted from the data, and the output string is printed (nothing gets inserted in the data).
A rule of the form:

<left-hand-side>::=:::

(i.e. rules whose RHS equals :::) are the input primitives: when triggered, the LHS is replaced with an input line (less its terminating <newline>).

Newlines

The Thue reference manual is not very clear about newlines in input/output. Existing Thue interpreters tend to output a newline after each output rule is triggered. However this prevents writing Thue programs which need a finer control on the output (like self-reproducing programs that output exactly their own code).

I propose a variant of Thue where:

Rules of the form:

<left-hand-side>::=~<output-string>

where the output-string is a non empty string of characters, output that string of characters when triggered, with no pending newline.
rules of the form:

<left-hand-side>::=~

(i.e. whose RHS equals the string ~), when triggered, outputs a single newline.

With this convention, nice programs like quines and 99 bottles of beer can be written.

Download

Original resources

thue.zip (27 kb), the original thue distribution;
catseyes.zip (36 kb), the page salvaged from the seemingly defunct cat's eyes technologies (http://www.catseye.mb.ca/esoteric/thue/).

Homemade

All programs below assume the output variant described above.

beer.t, implementation of 99 bottles of beer;
quine.t, a self-reproducing program;
fibo.t, a program printing fibonacci numbers in decimal;
fibnth.t, a program printing the nth fibonacci number;
thue.pl, a limited Thue interpreter in perl (does only implement random rule order);
thue.c, the original Thue interpreter modified for the output variant;
thue2sed.sed, a Thue to sed compiler, written in sed (does not implement the non-deterministic rule order);
thuemisc.zip, an archive of all homemade files above.