Footsteps

Footsteps is an esoteric programming language created by User:ais523 in 2017. The aim was to create a ZISC that, rather than being very low-level (and thus easy to implement in machine code), makes use of more advanced data structures (such as lists) in order to be able to make the language's rule even simpler. The language is something of a cross between SMITH, ResPlicate, and a tag system.

Syntax

A Footsteps program is a ragged array of commands (i.e. it's a number of lines, each of which contains some number of commands; the number of commands per line can vary, and having zero commands on a line is reasonable). The commands themselves each consist of a reference (which can be start or end), and a distance, a non-negative integer. Additionally, start 0 is considered to be undefined behaviour, and thus should typically be avoided.

In the "canonical" syntax, commands are written as reference distance, commands within a line are separated by commas, lines are separated by newlines. For example:

start 7, end 2

end 3, end 4, start 6
end 5

However, implementations are somewhat encouraged to use a convenient internal representation for programs (such as a list of list of integers) rather than working on this syntax directly, and to have a separate parser that just translates the canonical syntax into the internal representation; and programmers are encouraged to use the canonical syntax only for programs that might need to be run on multiple interpreters, and to freely make use of an implementation's internal representation as a syntax to write in directly.

Semantics

A Footsteps program runs each line in sequence from top to bottom. To run a line, each command on the line is run from left to right, and then the line is deleted from the program entirely. To run a command, one of the lines in the program is copied to the end of the program; the reference and distance specify where the line is copied from (e.g. end 0 means a distance of 0 from the end, i.e. the last line; end 1 would be the penultimate line; start 2 would be the third line). Lines that have already been executed (and thus deleted) aren't included in the count, e.g. start 2 copies the current third line of the program, not the third line of the original program.

There's no control flow of any sort; the only way to do loops is to keep copying lines forwards, and the only way to do conditionals is to write lines which will have a different effect based on the lines that are about to run or that have been recently added to the program.

Computational class

Footsteps was intended to be Turing complete, but this has not been proven (and may be fairly difficult to prove, or even incorrect). It seems plausible that certain subsets may also be Turing complete; the author suspects that if it is Turing complete, there will be no need to use both references (i.e. that it will be possible to write an interpreter for a Turing complete language using only a single reference).

Implementations

Python 2

    import sys
    
    class FootstepsPreprocessor:
      @staticmethod
      def process(program):
        output=[]
        for line in program:
          line = line.replace("start ","")
          line = line.replace("end ","~")
          line = line.split(",")
          line = map(eval, line)
          output.append(line)
        return output
    
    class FootstepsProgram:
        
      def __init__(self,prog):
        self.prog = prog
        for line in self.prog:
          if 0 in line:
            raise IndexError("start 0 is cheating")
        
      def update(self):
        for command in self.prog[0]:
          self.prog.append(self.prog[command])
        self.prog.pop(0)
        
      def run(self):
        while True:
          self.update()
          print "\033c"
          for line in self.prog:
            print line
          raw_input()
    
    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()
        import re
        listing = re.split('[\r\n]+',listing)
        if "start" in listing[0] or "end" in listing[0]:
          listing = FootstepsPreprocessor.process(listing)
        prog = FootstepsProgram(listing)
        finalprog = prog.run()
        for line in finalprog:
          print line

Python 3

• Terse Python3 implementation that halts on out-of-bounds line reference (which may change if it turns out to be a terrible idea).