Tag

Tag is an implementation of a variable Post tag system as a simple, but inscrutable, programming language by Mark C. Chu-Carroll.

Post tag systems

The Post tag machine is simple to the point of triviality. The system is a queue of characters (with one character designated as "Halt"), and a set of rules. Each rule has a different character that selects the rule, and a string of characters. Each step, the machine looks at the first character of the queue, and selects the rule associated with that character. If the character is "Halt", the system just stops, and whatever is left on the queue is the result of the computation. Otherwise, it appends the selected rule's string of characters to the end of the queue, and then removes a fixed number of characters from the front of the queue. The systems are called N-Tag systems where N is number of character dropped each step.

That's it. Look at the front of the queue, use it to pick a set of characters to append, and then remove and discard the first N characters from the queue.

For any N>=2, a Post N-tag system is Turing equivalent.

The Tag language

Tag is an implementation of a Post-tag system with a variable drop length: each rule specifies how many characters should be removed from the queue when that rule is selected.

The syntax is very simple: It's a list of rules. Each rule has the format:

     name ":" triggerchar numbertodrop "("characters to append")"

For example, addThreeAsOnB:B2(AAA) is a rule named addThreeAsOnB. It will run when the first character on the queue is B, and it will drop the first two characters from the queue, and append AAA.

For output, if the number to drop is followed by !, then it will print out the dropped characters except for the one that triggered the command.

Sample programs

The classic Hello World program:

     fillQueue:a2(pHpeplplpop pWpoprplpd#)
     printChar:p2!(#)

Simple conditional:

     ifA:A2(sss)
     ifB:B2(ss)
     ifS:s2(cd)
     ifC:c2(pA#)
     ifD:d2(pB#)
     print:p2!( )

What this does is: if the first character is an A, it inserts 3 ss; if it's B, it inserts two ss. On an s, it appends cd. A c causes it to print A and then halt; d causes it to print B and halt.

So suppose we started with AA on the queue. It would pick the rule ifA:, drop the two As, and the queue would be sss. Then it would pick rule s, which drops two, and appends cd - so the queue would be scd. It would run s again, which would append another cd, leaving dscd. The d appends pB#, so the queue becomes cdpB#; the c appends pA#, leaving pB#pA#. And then B gets printed, and the program halts.

Let's look at the other cases: BB on the queue. Rule B runs, leaving ss on the queue. s appends cd, leaving cd on the queue. The c appends pA# onto the queue, leaving the queue as pA#. So it prints A, and halts.

Add

Takes a list of digits terminated with an 'x', and outputs the sum of the digits in Unary format:

zero :01()
one  :11(p1)
two  :21(p1p1)
three:31(p1p1p1)
four :41(p1p1p1p1)
five :51(p1p1p1p1p1)
six  :61(p1p1p1p1p1p1)
seven:71(p1p1p1p1p1p1p1)
eight:81(p1p1p1p1p1p1p1p1)
nine :91(p1p1p1p1p1p1p1p1p1)
end  :x1(#)
print:p2!()

An initial queue of 52341x would produce the output 111111111111111

Factorial

Takes a digit (followed by !) and outputs the factorial, in unary.

one  :12(p1)
two  :22(p1p1)
three:32(2 2 2 )
four :42(3 3 3 3 )
five :52(4 4 4 4 4 )
six  :62(5 5 5 5 5 5 )
seven:72(6 6 6 6 6 6 6 )
eight:82(7 7 7 7 7 7 7 7 )
nine :92(8 8 8 8 8 8 8 8 8 )
print:p2!(#)'

See also

• Tag systems
• Bitwise Cyclic Tag

External resources

• The original presentation of Tag at the Good Math, Bad Math Blog, with links to a Haskell implementation(dead link).