Antigram

Antigram

Paradigm(s)	String-rewriting
Designed by	User:Quintopia
Appeared in	2020
Computational class	Unknown
Reference implementation	None
Influenced by	Thue,2C
File extension(s)	.ant

Antigram is an esoteric programming language created by User:Quintopia in 2020. It was mainly designed because there had not yet been a language on this wiki named "Antigram," and that was a surprise and a shame. The design principle is that it should resemble particle annihilation in a supercollider and that effects produced by annihilation should be nonlocal and hard to describe. In this way, it becomes difficult to prove the language is Turing complete, even as it would seem to have the power to be.

Semantics

The state of a running Antigram program is a finite unbounded-length string of symbols. Implementations may define what alphabet these symbols may be drawn from, though some subset of Unicode characters would seem to be the most useful. The program listing defines the initial state of this string as well as a production string. The production string must contain every symbol that appears in the initial state string, though it may contain others.

To run the program, an interpreter will repeatedly perform the following steps until there are no adjacent pairs of identical symbols in the state string:

1. Locate in the state string the first match of the pattern ABBC, where A, B, and C each match a single symbol
2. Delete the symbols that matched BB from the state string
3. Locate the first occurrence of the symbol matching A in the production string
4. Append all symbols that appear before the matched symbol in the production string to the state string
5. Locate the last occurrence of the symbol matching C in the production string
6. Prepend all symbols that appear after the matched symbol in the production string to the state string

Syntax

May be defined however an implementer wishes.

Example

Let the symbols be the characters a, b, and c.

Production string: babbccac
Initial state string: bbbbb

The execution unfolds thusly:

                        bbbbb                       The first pair is preceded by b, thus appending nothing, and succeeded by b, thus prepending ccac
                    ccacbbb                         The first pair is preceded by c, thus appending babb, and succeeded by b, thus prepending ccac
                ccacccacbbabb                       The first pair is preceded by a, thus appending b, and succeeded by c, thus prepending nothing
                ccacacbbabbb                        The first pair is preceded by c, thus appending babb, and succeeded by a, thus prepending c
               cccacacabbbbabb                      The first pair is preceded by c, thus appending babb, and succeeded by a, thus prepending c
              ccacacabbbbabbbabb                    The first pair is preceded by a, thus appending b, and succeeded by b, thus prepending ccac
          ccacccacacabbabbbabbb                     The first pair is preceded by a, thus appending b, and succeeded by c, thus prepending nothing
          ccacacacabbabbbabbbb                      The first pair is preceded by a, thus appending b, and succeeded by a, thus prepending c
         cccacacacaabbbabbbbb                       You get the idea
        ccacacacaabbbabbbbbbabb
    ccacccacacacbbbabbbbbbabbbabb
    ccacacacacbbbabbbbbbabbbabbb
ccacccacacacacbabbbbbbabbbabbbbabb
ccacacacacacbabbbbbbabbbabbbbabbb                   And so on. This sequence appears to grow forever, adding a growing string of "ca" near the front, 
                                                    while adding runs of "b" of varying and unpredictable length separated by "a" at the end. 

Optional Output Semantics

Implementers may define a subset of symbols that, when a pair of any of those symbols is deleted from the state string, a single copy of that symbol is output.

Open Questions

• Is Antigram Turing complete? (Guess: yes)
• If so, what is the minimum number of symbols needed to achieve TCness? (The lower bound is 3 as 2 can be shown to be incapable of growing without bound.)

Implementations

Python 2

This does not use the output extension. Syntax is: first line of program is production string, second line is initial state. No unicode support.

   import re
   import sys
   
   class Halt(Exception):
     def __init__(self,state):
       self.state = state
       
   class AntigramProgram:
       
     def __init__(self,prog):
       self.productions = prog[0]
       self.state = prog[1]
       
     def update(self):
       matches = re.search(r"(.)(.)\2(.)",self.state)
       if not matches:
         raise Halt(self.state)
       pre = matches.group(1)
       post = matches.group(3)
       self.state = self.state[:matches.start(2)]+self.state[matches.start(3):]
       self.state += self.productions[:self.productions.index(pre)]
       self.state = self.productions[len(self.productions)-self.productions[::-1].index(post):] + self.state
       raw_input(self.state)
       
     def run(self):
       while True:
         self.update()
   
   if __name__=="__main__":
     if len(sys.argv)<2:
       print "No filename to execute."
     else:
       try: 
         openfile = open(sys.argv[1], "r")
       except IOError: 
         print("File '"+sys.argv[1]+"' not found.")
         sys.exit(1)
       else: 
         listing = openfile.read()
         openfile.close()
       listing = re.split('[\r\n]+',listing)
       prog = AntigramProgram(listing)
       finalstate = prog.run()
       print finalstate