Thue (language)


Thue is an exotic programming language invented by John Colagioia in the early 2000s. It is a meta-language allowing the definition and recognition of type 0 languages in the Chomsky hierarchy . Thue is based on a non-deterministic rewriting system called semi-Thue grammar , the name of which is derived from Norwegian mathematician Axel Thue. Inspiration comes also from crane .

Production Rules

A Thue program begins with substitution rules of the form lhs :: = rhs

Successive rules can be added. The set of basic rules ends with a line containing an empty rule. The initial state is a series of symbols specified at the end of the program after the set of substitution rules.

Thue consumes the initial symbols and substitutes the results of the rules for each of the symbols of the initial state.

Thue ends when lhs can no longer be substituted using rules.

Syntax

  • :: = can be pronounced .
  • Lhs is “left part” ( l eft h and s ide ).
  • Rhs is “right part” ( r ight h and s ide ).
  • :: = can never be in the left part of a rule ( lhs ).
  • ::: is an input stream, substituted by what has been read.
  • ~ Is an output stream to display the text that follows it.

Call to Thue

The interpreter can be called with different options:

Option ‘d’ ( d ebug)
View status.
Option ‘l’ ( the EFT side)
Apply the left-to-right rules.
Option ‘r’ ( r ight side)
Apply the right-to-left rules.

Only the last option ‘l’ or ‘r’ is taken into account.

Examples of Programs

The traditional “Hello World! “In Thue:

A :: = ~ Hello World!
:: =
at

The following program increments a binary number entered as initial state, with the character “_”, here the number 1111111111:

1 _ :: = 1 ++
0 _ :: = 1
01 ++ :: = 10
11 ++ :: = 1 ++ 0
_0 :: = _
_1 ++ :: = 10
:: =
_1111111111_

The following program exposes the non-deterministic character of the Thue. The output of the program is a set of bits in an undefined order.

B :: = ~ 0
B :: = ~ 1
Ac :: = abc
:: =
ABC