Permalink
Branch: master
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
86 lines (63 sloc) 2.7 KB
tag -- a Tag system processor
This program is a portable implementation of Emil Post's Tag systems [0].
Synopsis
tag [OPTIONS]... [FILE] [INPUT]
Description
Compile production rules of a Tag system given in FILE, run the system with given INPUT word, and print each step to standard output until the system halts.
The syntax of production rules is as follows; each line starts with a character ("head"), followed by one or more spaces, and ends with a possibly empty word ("tail"). No two different rules have the same head. Neither head nor tail can contain spaces. Empty lines and ones starting with spaces are ignored.
No spaces is allowed in any INPUT word.
The behavior of a Tag system is determined by a constant, positive integer D called the deletion number. D is 2 unless specified otherwise by -d option. At each step of production, the only state of a Tag system is its current word, say W. By default, the system halts if either (1) the length of W is less than D or (2) W's first character does not belong to the set of heads. However, if -e option is specified, it halts only if either W is empty or (2) holds. The rule which head matches with the leading character is applied; the updated word for next step is the concatenation of W and the tail of the matched rule, except its first D characters.
-d D
specify the deletion number D (default 2)
-e
halt only on the empty word regardless of the deletion number
-i, --indent
indent output, the depth of indentation is the deletion number multiplied by the step number
-m, -m LENGTH
exit if the length of the current word exceeds LENGTH (default 100)
-n, -n NUM
exit if the number of steps reaches NUM (default 100)
-q, --quiet
suppress output
-h, --help
display this help and exit
--version
output version information and exit
Exit status is 0 if it halts, 1 if it exits due to -m or -n option's effect, 2 otherwise.
Example
Production rules of a well-known 2-Tag system for Collatz (sub)sequences can be encoded in the following three lines:
a bc
b a
c aaa
Note that the leading spaces of the above rules are only for pretty formatting and must be avoided at a rule line. Supposing that the rule file is named collatz.txt in the current directory, invoking tag as follows computes the system starting from word "aaa":
$ tag collatz.txt aaa
aaa
abc
cbc
caaa
aaaaa
aaabc
abcbc
cbcbc
cbcaaa
caaaaaa
aaaaaaaa
aaaaaabc
aaaabcbc
aabcbcbc
bcbcbcbc
bcbcbca
bcbcaa
bcaaa
aaaa
aabc
bcbc
bca
aa
bc
a
Author
Takeshi Abe <tabe@fixedpoint.jp>
License
The MIT license
[0] https://en.wikipedia.org/wiki/Tag_system