My first working implementation of Life on a Turing Machine

life.es6

// A prelude of handy items

const I = _ => _;

const aKindOf = clazz => x => x instanceof clazz;

// preallocation and copy would be way faster
const flatMap = (arr, lambda) => {
  const inLen = arr.length;
  const mapped = new Array(inLen);

  let outLen = 0;

  arr.forEach((e, i) => {
    const these = lambda(e);

    mapped[i] = these;
    outLen = outLen + these.length;
  });

  const out = new Array(outLen);

  let outIndex = 0;
  for (const these of mapped) {
    for (const e of these) {
      out[outIndex++] = e;
    }
  }

  return out;
};

const gensym = (()=> {
  let n = 1;

  return (prefix = 'G') => `${prefix}-${n++}`;
})();

const times = n =>
  Array.from({ length: n }, (_, i) => i);

const get = property => object => object[property];

const range = n => Array.from({ length: n}, (_, i) => i);

const chunksOf = (chunkSize, array) =>
  Array(Math.ceil(array.length/chunkSize)).fill().map((_,i) => array.slice(i*chunkSize,i*chunkSize+chunkSize));

class Konst {
  constructor(name) {
    this.name = name;
  }
  toString() { return this.name; }
}

const deepishEqual = (a, b) => {
  if (typeof a !== typeof b) {
    return false;
  } else if (typeof a === 'string') {
    return a === b;
  } else if (typeof a === 'number') {
    return a === b;
  } else if (typeof a === 'object') {
    const aEntries = Object.entries(a);
    const bKeys = Object.keys(b);

    if (aEntries.length !== bKeys.length) {
      return false;
    } else {
      for (const [key, aValue] of aEntries) {
        const bValue = b[key];
        if (!deepishEqual(aValue, bValue)) {
          return false;
        }
      }
      return true;
    }
  } else {
    return a === b;
  }
}

class PseudoMap {
  constructor () {
    this.mappings = [];
    this.size = 0;
  }

  set (key, value) {
    const pair = this.mappings.find( ({ key: _key }) => deepishEqual(key, _key));

    if (pair == null) {
      this.mappings.push({ key, value });
      this.size += 1;
    } else {
      pair.value = value;
    }
  }

  get (key) {
    const pair = this.mappings.find( ({ key: _key }) => deepishEqual(key, _key));

    if (pair != null) {
      return pair.value;
    }
  }

  has (key) {
    const pair = this.mappings.find( ({ key: _key }) => deepishEqual(key, _key));

    return (pair != null);
  }

  keys () {
    return this.mappings.map(get('key'));
  }

  values () {
    return this.mappings.map(get('value'));
  }
}

class PseudoSet {
  constructor (contents = []) {
    this.contents = contents;
  }

  add (element) {
    const _element = this.contents.find(_element => deepishEqual(element, _element));

    if (_element == null) {
      this.contents.push(element);
    }
    return element;
  }

  has (element) {
    const _element = this.contents.find(_element => deepishEqual(element, _element));

    return _element != null;
  }

  map (fn) {
    return this.contents.map(fn);
  }

  filter (fn) {
    return this.contents.filter(fn);
  }

  // really should write an iterator and support Array.from()
  toArray () {
    return this.contents.slice(0);
  }
}

// a pretty printer for descriptons

function pd (title, description) {
  const HALT = 0, LEFT = 2, RIGHT = 3;

  if (description != null) {
    console.log(title);
  } else {
    description = title;
  }
  description.forEach(
    d => {
      const butLast = d.slice(0, d.length-1);
      const last = d[d.length-1];

      if (butLast[2] === HALT) butLast[2] = 'HALT';

      const butLastStrings = butLast.map(x=>x.toString());
      const lastString = last === RIGHT ? 'RIGHT' : (last === LEFT ? 'LEFT' : last);

      const strings = butLastStrings.concat([lastString]);

      console.log(strings.join(', '));
    }
  );
}

// inject the pretty printer into the tool chain

const pdc = (title) => ({ description }) => {
  pd(title, description);
  return { description };
}

// inject some stats into the tool chain
const stats = (title) => ({ description }) => {
  const instructions = description.length;

  const stateSet = new Set();
  for (const [state1, _, state2] of description) {
    stateSet.add(state1);
    stateSet.add(state2);
  }
  const states = stateSet.size;

  console.log({ title, states, instructions });

  return { description };
}

// a pretty printer for tapes

const ppt = (trim = true) =>
  trim
  ? () => ({
      after: tape => {
        let last = tape.length - 1;

        while (last >= 0 && tape[last] === 0) --last;

        return tape.slice(0, last + 1).join(' | ');
      }
    })
  : () => ({
      after: tape => tape.join(' | ')
    });

// flip out and give up
const error = (...args) => {
  console.log(...args);
  throw 1;
}

// The Turing Machine. This particular machine stretches infintely in one direction,
// can handle arbitrary marks on the tape, and allows for multiple 'instructions'
// to be associated with one line in the description, e.g.
//
// ['start', 0, HALT, Move(RIGHT), Move(DOWN)]

const tsMachine = (() => {
  const HALT = 'HALT';
  const LEFT = 'LEFT';
  const RIGHT = 'RIGHT';

  function Write (mark) {
    if (this == null) {
      return new Write(mark);
    }
    if (mark == null || mark === '') {
      console.log('missing mark');
      throw 1;
    }
    this.mark = mark;
  }

  Write.prototype.toString = function () { return `Write(${this.mark})`; };

  function Move (direction) {
    if (this == null) {
      return new Move(direction);
    }
    this.direction = direction;
  }

  Move.prototype.toString = function () { return `Move(${this.direction})`; };

  function turingScript({ description: _description, tape: _tape }) {
    const tape = Array.from(_tape);

    const description = _description.reduce(
      (acc, [currentState, match, nextState, ...actions]) => {
        const rules = acc[currentState] || (acc[currentState] = {});
        rules[match] = [nextState, ...actions];
        return acc;
      },
      {}
    )

    let tapeIndex = 0;
    let currentState = _description[0][0];

    while (true) {
      if (tapeIndex < 0) {
        console.log('moved off the left edge of the world');
        console.log({ tapeIndex, currentState, currentMark, tape: tape.join(' ') });
        return tape;
      }

      const currentMark = tape[tapeIndex];

      const rules = description[currentState];

      const rule = rules && rules[currentMark];

      if (rule == null) {
        if (currentState !== HALT) {
          console.log({ tapeIndex, currentState, currentMark, tape: tape.join(' ') });
        }
        return tape;
      }

      const [nextState, ...actions] = rule;

      for (const action of actions) {
        if (action instanceof Move) {
          const direction = action.direction;

          if (direction === LEFT) {
            --tapeIndex;
            if (tapeIndex < 0) {
              console.log('moved off the left edge of the world');
              console.log({ tapeIndex, currentState, currentMark, tape: tape.join(' ') });
              return tape;
            }
          } else if (direction === RIGHT) {
            ++tapeIndex;
            if (tape[tapeIndex] == null) tape[tapeIndex] = 0;
          } else {
            error(`Don't know how to move  ${direction}'`);
          }
        } else if (action instanceof Write) {
          tape[tapeIndex] = action.mark;
        } else {
          error(`Don't know how to execute action ${action}'`)
        }
      }

      currentState = nextState;
    }
  }

  return Object.assign(
    ({ description, tape = [] }) => turingScript({ description, tape }),
    { constants: { LEFT, RIGHT, HALT, Move, Write } }
  );
})();

// framework for compiling more expressive instruction sets to the basic TM

const compile = (...compilers) =>
  compilers.slice(0, compilers.length - 1).reverse().reduce(
    (machine, compiler) => {
      let { constants } = machine;

      const compiledMachine = ({ description: _description, tape: _tape }) => {
        const parameters = Object.assign({ description: _description, tape: _tape }, constants);
        const { description = _description, tape = _tape, after = I,  } = compiler(parameters);

        return after(machine({ description, tape }));
      }

      if (compiler.constants != null) {
        constants = Object.assign({}, constants, compiler.constants);
      }

      return Object.assign(compiledMachine, { constants });
    },
    compilers[compilers.length - 1]
  );

// annotate tape cells, useful for emulating multiple tape heads
const annotations = (() => {

  const Nothing = new Konst('∅');
  const Something = new Konst('+');
  const Anything = new Konst('*');

  function Annotated (annotation, mark = Anything)  {
    if (this == null) {
      return new Annotated (annotation, mark);
    }
    Object.assign(this, { annotation, mark });
  }

  Annotated.prototype.toString = function () {
    if ('' + this.annotation === '[object Object]') {
      error('annotation is not printable', this);
    }

    return `${this.annotation}::${this.mark}`;
  }

  function Unannotated (mark )  {
    if (this == null) {
      return new Unannotated(mark);
    }
    Object.assign(this, { mark });
  }

  Unannotated.prototype.toString = function () {
    return `∅::${this.mark}`;
  }

  function Annotate (annotation) {
    if (this == null) {
      return new Annotate(annotation);
    }
    this.annotation = annotation;
  }

  Annotate.prototype.toString = function () {
    return `${this.annotation}::*`;
  }

  function Deannotate () {
    if (this == null) {
      return new Deannotate();
    }
  }

  Deannotate.prototype.toString = function () {
    return `::*`;
  }

  function Not(...marks) {
    if (this == null) {
      return new Not(...marks);
    }
    this.marks = marks;
  }

  Not.prototype.toString = function () {
    return `![${this.marks.join(', ')}]`;
  }

  function Any(...marks) {
    if (this == null) {
      return new Any(...marks);
    }
    this.marks = marks;
  }

  Any.prototype.toString = function () {
    return `[${this.marks.join(', ')}]`;
  }

  const isSomething = input => input === Something;
  const isAnything = input => input === Anything;
  const isNothing = input => input === Nothing;
  const isNot = input => input instanceof Not
  const isAny = input => input instanceof Any
  const isConcrete = input => input != null && input !== Something && input !== Anything && !isNot(input) && !isAny(input);
  const isnt = input => input == null;

  const splitMatch = input => {
    if (input instanceof Unannotated) {
      const { mark } = input;

      return { annotation: Nothing, mark };
    } else if (input instanceof Annotated || input.annotation != null || input.mark != null) {
      const { annotation, mark } = input;

      return { annotation, mark };
    } else if (input === Nothing) {
      return { annotation: Anything, mark: 0 };
    } else if (input === Something) {
      return { annotation: Anything, mark: Something };
    } else if (input === Anything) {
      return { annotation: Anything, mark: Anything };
    } else {
      return { annotation: Anything, mark: input };
    }
  }

  const split = input => {
    if (input instanceof Unannotated) {
      const { mark } = input;

      return { annotation: Nothing, mark };
    } else if (input instanceof Annotated || input.annotation != null || input.mark != null) {
      const { annotation, mark } = input;

      return { annotation, mark };
    } else if (input === Nothing) {
      return { mark: 0 };
    } else if (input === Something) {
      return { annotation: Anything, mark: Something };
    } else if (input === Anything) {
      return { annotation: Anything, mark: Anything };
    } else {
      return { mark: input };
    }
  }

  const compiler = ({ description: _description, tape, Write }) => {
    function isVarableWrite (instruction) {
      if (instruction instanceof Write) {
        const { annotation, mark } = split(instruction.mark);

        return typeof annotation === 'object'
                 && (annotation instanceof Something || annotation instanceof Anything) ||
               typeof mark === 'object'
                 && (mark instanceof Something || mark instanceof Anything)
        return false;
      }
    }

    // extract annotate and deannotate states so that they are always
    // the first instruction in a sequence
    function extractAnnotateDeannotateWrite ([currentState, match, nextState, first, ...rest]) {
      const unsplit = [first];
      let instruction;

      while (instruction = rest.shift()) {
        if (instruction instanceof Annotate  || instruction instanceof Deannotate || isVarableWrite(instruction)) {
          // TODO: not writes that are constant!
          const bridgeState = gensym('bridge');

          return [[currentState, match, bridgeState, ...unsplit]].concat(
            extractAnnotateDeannotateWrite([bridgeState, Anything, nextState, instruction, ...rest])
          );
        } else {
          unsplit.push(instruction);
        }
      }
      return [[currentState, match, nextState, ...unsplit]];
    }

    // gather a vocabulary of annotations and marks
    let annotations = new PseudoSet();
    let anythings = new PseudoSet([0]);

    const scan = input => {
      if (input instanceof Annotated || input.annotation != null || input.mark != null) {
        const { annotation, mark } = input;

        if (isConcrete(annotation)) {
          annotations.add(annotation);
        }
        if (isConcrete(mark)) {
          anythings.add(mark);
        }
      } else if (isConcrete(input)) {
        anythings.add(input);
      }
    }

    for (const [currentState, match, nextState, ...instructions] of _description) {
      scan(match);

      for (const instruction of instructions) {
        if (instruction instanceof Write) {
          scan(instruction.mark);
        } else if (instruction instanceof Annotate) {
          annotations.add(instruction.annotation);
        }
      }
    }

    for (const cell of tape) {
      scan(cell);
    }

    const somethings = anythings.filter(_ => _ != 0);

    // console.log({ annotations, somethings, anythings })

    // first, split annotate, deannotate, and variable writes

    const splitDescription = flatMap(_description, extractAnnotateDeannotateWrite);

    const annotationsToSymbols = new PseudoMap();

    const markFor = (something) => {
      if (something instanceof Annotated) {
        let mark = annotationsToSymbols.get(something);

        if (mark == null) {
          mark = gensym(something.toString());
          annotationsToSymbols.set(something, mark);
        }

        return mark;
      } else {
        return something;
      }
    }

    const instructionFor = (something) => {
      if (something instanceof Write) {
        return Write(markFor(something.mark))
      } else {
        return something;
      }
    }

    const description = flatMap(splitDescription, ([currentState, match, nextState, ...instructions]) => {
      let flavours;

      const { annotation, mark } = splitMatch(match);

      let validAnnotations;
      let validMarks;

      if (isNothing(annotation)) {
        validAnnotations = [Nothing];
      } else if (isConcrete(annotation)) {
        validAnnotations = [annotation];
      } else if (isSomething(annotation)) {
        validAnnotations = annnotations.toArray();
      } else if (isnt(annotation) || isAnything(annotation)) {
        validAnnotations = [Nothing].concat(annotations.toArray());
      }

      if (isnt(mark)) {
        error('Must have a mark or use Something or Anything', match);
      } else if (isConcrete(mark)) {
        validMarks = [mark];
      } else if (isSomething(mark)) {
        validMarks = somethings.toArray();
      } else if (isAnything(mark)) {
        validMarks = anythings.toArray();
      } else if (isNot(mark)) {
        validMarks = anythings.filter(markToInclude => !mark.marks.includes(markToInclude));
      } else if (isAny(mark)) {
        validMarks = mark.marks;
      } else {
        error('?????', mark);
      }

      flavours = flatMap(validAnnotations, annotation =>
        validMarks.map(mark =>
          [currentState, isNothing(annotation) ? mark : Annotated(annotation, mark), nextState, ...instructions]
        )
      );

      return flavours.map(
        ([currentState, match, nextState, ..._instructions]) => {
          const { annotation: currentAnnotation, mark: currentMark } = split(match);

          if (isSomething(currentMark) || isAnything(currentMark)) {
            error(`No 'wildcard' marks allowed here ${match}`);
          } else if (isnt(currentMark)) {
            error(`Must have a concrete mark ${match}`, match);
          }

          const instructions = _instructions.map(instruction => {
            if (instruction instanceof Write) {
              const { annotation, mark } = split(instruction.mark);

              if (isnt(annotation) && isConcrete(mark)) {
                // just write an unannotated mark
                return Write(mark);
              } else if (isConcrete(annotation) && isConcrete(mark)) {
                // just write an annotated mark
                return Write(markFor(instruction.mark));
              } else if (isSomething(annotation) && isConcrete(mark)) {
                if (isConcrete(currentAnnotation)) {
                  // write the current annotation and the new mark
                  return Write(markFor(Annotated(currentAnnotation, mark)));
                } else if (isnt(currentAnnotation)) {
                  // write the new mark, unadorned
                  return Write(mark);
                } else {
                  error(`Don't know how to write ${Write.mark} when recognizing ${match}`);
                }
              } else if (isConcrete(annotation) && isSomething(mark)) {
                return Write(markFor(Annotated(annotation, currentMark)));
              } else {
                error(`Don't know how to write ${Write.mark}`);
              }
            } else if (instruction instanceof Annotate) {
                const { annotation } = instruction;

                return Write(markFor(Annotated(annotation, currentMark)));
            } else if (instruction instanceof Deannotate) {
              return Write(currentMark);
            } else {
              return instruction;
            }
          });

          return [currentState, markFor(match), nextState, ...instructions];
        }
      );
    });

    // console.log(tape.join(' '));

    // pd('annotated', description);

    return { description, tape, after: _=>_ };
  }

  return Object.assign(compiler, { constants: { Annotated, Unannotated, Annotate, Deannotate, Nothing, Something, Anything, Not, Any }});

})();

// compile a two-dimensional tape down to a one-dimensional tape
const twoDimensional = (() => {

  const UP = 'UP';
  const DOWN = 'DOWN';

  const compile = ({ description: _description = [], tape: _tape, LEFT, RIGHT, Move, Annotated, Unannotated, Annotate, Deannotate, Nothing, Something, Anything, Not, Any, Write }) => {

    // annotations
    // consider naming them with genysms or giving them ids
    const V = gensym('V');
    const H = gensym('H');
    const VEND = gensym('$V');
    const HEND = gensym('$H');
    const Slow = gensym('slow');
    const Fast = gensym('fast');
    const L = gensym('L');
    const R = gensym('R');

    const max = Math.max(Math.sqrt(_tape.length), 2);

    const tape2d = chunksOf(max, _tape);

    const tape = [V];

    for (let sum = 0; sum < max * 2 - 1; ++sum) {
      const topDown = sum % 2 === 1;

      for (let innerCount = 0; innerCount <= sum; ++innerCount) {
        let h;
        let v;

        if (topDown) {
          v = innerCount;
          h = sum - innerCount;
        } else {
          h = innerCount;
          v = sum - innerCount;
        }
        if (v >= tape2d.length || h >= tape2d[v].length) {
          tape.push(0);
        } else {
          tape.push(tape2d[v][h]);
        }
      }

      if (topDown) {
        tape.push(H)
      } else {
        tape.push(V);
      }
    }

    const lastCell = tape[tape.length - 1];

    tape[tape.length - 1] = lastCell === V ? VEND : HEND;

    // console.log(tape.join(' '));

    const firstState = _description[0][0];

    const moveToTheRightOfTheFirstV = gensym('moveToTheRightOfTheFirstV');

    const description = [
      [moveToTheRightOfTheFirstV, V, firstState, Move(RIGHT)]
    ].concat(
      flatMap(_description, ([currentState, currentMatch, nextState, ..._instructions]) => {
        const subDescription = [];
        let fromState = currentState;
        let toMatch = currentMatch;
        let toState = nextState;
        let subInstructions = [];

        let thisInstruction;
        while (thisInstruction = _instructions.shift()) {
          if (thisInstruction instanceof Move) {

            // what is the begininng state?
            let stateBeforeMove;
            // what do we need to match before marking things up?
            let matchBeforeMove;
            if (subInstructions.length > 0) {
              // flush existing instructions
              stateBeforeMove = gensym(`before-move-${nextState}`);
              matchBeforeMove = Anything;
              subDescription.push([fromState, toMatch, stateBeforeMove, ...subInstructions]);
              subInstructions = [];
            } else if (fromState === currentState) {
              stateBeforeMove = fromState;
              matchBeforeMove = currentMatch;
            } else {
              stateBeforeMove = fromState;
              matchBeforeMove = Anything;
            }

            // are we the last instruction?
            let stateAfterMove;
            if (_instructions.length === 0) {
              stateAfterMove = nextState;
            } else {
              stateAfterMove = gensym('after-move');
            }
            fromState = stateAfterMove;

            const seekVH = gensym(`seek-v-or-h-${nextState}`);
            const moveBackToSlow = gensym(`move-back-to-slow-${nextState}`);
            const testVorH = gensym(`test-V-or-H-${nextState}`);
            const solveForV = gensym(`solve-for-v-${nextState}`);
            const solveForH = gensym(`solve-for-h-${nextState}`);
            const resetFast = gensym(`reset-fast-${nextState}`);
            const fastBackToSlow = gensym(`fast-back-to-slow-${nextState}`);
            const fastToSlow = gensym(`fast-to-slow-${nextState}`);

            const applyVR = gensym(`apply-v-right-${nextState}`);
            const moveBackToVLeft = gensym(`move-back-to-v-left-${nextState}`);
            const testLVHV = gensym('test-l-v-h-v');
            const moveUpToRH = gensym('move-up-to-r-h');
            const moveUpToRMoveV = gensym('move-up-to-r-move-v');
            const moveBackToFastV = gensym('move-back-to-fast-v');

            const applyHR = gensym(`apply-h-right-${nextState}`);
            const moveBackToHLeft = gensym(`move-back-to-h-left-${nextState}`);
            const testLVHH = gensym('test-l-v-h-h');
            const moveUpToRV = gensym('move-up-to-r-v');
            const moveUpToRMoveH = gensym('move-up-to-r-move-h');
            const moveBackToFastH = gensym('move-back-to-fast-h');

            if (thisInstruction.direction === UP) {
              subDescription.push(
                [stateBeforeMove, matchBeforeMove, fastBackToSlow, Annotate(Slow), Move(LEFT), Move(LEFT)],
                [fastBackToSlow, Anything, moveBackToSlow, Annotate(Fast), Move(RIGHT)],
                [moveBackToSlow, Unannotated(Anything), moveBackToSlow, Move(RIGHT)],
                [moveBackToSlow, Annotated(Slow), testVorH, Deannotate(), Move(LEFT)],
                [testVorH, V, solveForV, Move(LEFT)],
                [testVorH, H, solveForH, Move(LEFT)],
                [testVorH, Not(V, H), resetFast, Annotate(Slow), Move(LEFT)],
                [resetFast, Unannotated(Anything), resetFast, Move(LEFT)],
                [resetFast, Annotated(Fast), moveBackToSlow, Deannotate(), Move(LEFT), Move(LEFT), Annotate(Fast), Move(RIGHT)],
                [solveForV, Unannotated(Anything), solveForV, Move(LEFT)],
                [solveForV, Annotated(Fast), stateAfterMove, Deannotate(), Move(RIGHT)],
                [solveForH, Unannotated(Anything), solveForH, Move(LEFT)],
                [solveForH, Annotated(Fast), stateAfterMove, Deannotate()]
              );
            } else if (thisInstruction.direction === DOWN) {
              subDescription.push(
                [stateBeforeMove, matchBeforeMove, fastBackToSlow, Annotate(Slow), Move(RIGHT), Move(RIGHT)],
                [fastBackToSlow, Anything, moveBackToSlow, Annotate(Fast), Move(LEFT)],
                [moveBackToSlow, Unannotated(Anything), moveBackToSlow, Move(LEFT)],
                [moveBackToSlow, Annotated(Slow), testVorH, Deannotate(), Move(RIGHT)],
                [testVorH, V, solveForV, Move(RIGHT)],
                [testVorH, H, solveForH, Move(RIGHT)],
                [testVorH, Not(V, H, VEND, HEND), resetFast, Annotate(Slow), Move(RIGHT)],
                [resetFast, Unannotated(Anything), resetFast, Move(RIGHT)],
                [resetFast, Annotated(Fast), moveBackToSlow, Deannotate(), Move(RIGHT), Move(RIGHT), Annotate(Fast), Move(LEFT)],
                [solveForV, Unannotated(Anything), solveForV, Move(RIGHT)],
                [solveForV, Annotated(Fast), stateAfterMove, Deannotate(), Move(RIGHT)],
                [solveForH, Unannotated(Anything), solveForH, Move(RIGHT)],
                [solveForH, Annotated(Fast), stateAfterMove, Deannotate()],

                // expansion 1: Found V at the end
                // write a V, move left and annotate L, move right twice
                [testVorH, VEND, applyVR, Write(V), Move(LEFT), Annotate(L), Move(RIGHT), Move(RIGHT)],
                // is it marked? skip the mark and write R
                [applyVR, Annotated(Fast, 0), moveBackToVLeft, Move(RIGHT), Write(R)],
                // otherwise just write R
                [applyVR, Unannotated(0), moveBackToVLeft, Write(R)],
                //move back to annotated L
                [moveBackToVLeft, Unannotated(Anything), moveBackToVLeft, Move(LEFT)],
                [moveBackToVLeft, Annotated(Fast, 0), moveBackToVLeft, Move(LEFT)],
                // deannotate and move left
                [moveBackToVLeft, Annotated(L), testLVHV, Deannotate(), Move(LEFT)],
                // is it an H? we're almost done move up to the R
                [testLVHV, H, moveUpToRH, Move(RIGHT)],
                [moveUpToRH, Not(H), moveUpToRH, Move(RIGHT)],
                [moveUpToRH, Annotated(Fast, 0), moveUpToRH, Move(RIGHT)],
                // found the R! Write an H.
                [moveUpToRH, R, moveBackToFastV, Write(0), Move(RIGHT), Write(HEND), Move(LEFT)],
                // move back to the fast, deannotate it, move right, and we're done
                [moveBackToFastV, Unannotated(Anything), moveBackToFastV, Move(LEFT)],
                [moveBackToFastV, Annotated(Fast), stateAfterMove, Deannotate(), Move(RIGHT)],
                // the L is not an H, sigh. Annotate it and move right
                [testLVHV, Not(H), moveUpToRMoveV, Annotate(L), Move(RIGHT)],
                [moveUpToRMoveV, Not(H), moveUpToRMoveV, Move(RIGHT)],
                [moveUpToRMoveV, Annotated(Fast, 0), moveUpToRMoveV, Move(RIGHT)],
                // // found it, deannotate, move right and test it
                [moveUpToRMoveV, R, applyVR, Write(0), Move(RIGHT)],

                // expansion 2: Found H at the end
                // write an H, move left and annotate L, move right twice
                [testVorH, HEND, applyHR, Write(H), Move(LEFT), Annotate(L), Move(RIGHT), Move(RIGHT)],
                // is it marked? skip the mark and write R
                [applyHR, Annotated(Fast, 0), moveBackToHLeft, Move(RIGHT), Write(R)],
                // otherwise just write R
                [applyHR, Unannotated(0), moveBackToHLeft, Write(R)],
                //move back to annotated L
                [moveBackToHLeft, Unannotated(Anything), moveBackToHLeft, Move(LEFT)],
                [moveBackToHLeft, Annotated(Fast, 0), moveBackToHLeft, Move(LEFT)],
                // deannotate and move left
                [moveBackToHLeft, Annotated(L), testLVHH, Deannotate(), Move(LEFT)],
                // is it a V? we're almost done move up to the R
                [testLVHH, V, moveUpToRV, Move(RIGHT)],
                [moveUpToRV, Not(V),     moveUpToRV, Move(RIGHT)],
                [moveUpToRV, Annotated(Fast, 0), moveUpToRV, Move(RIGHT)],
                // found the R! Write a V.
                [moveUpToRV, R, moveBackToFastH, Write(0), Move(RIGHT), Write(VEND), Move(LEFT)],
                // move back to the fast, deannotate it, and we're done
                [moveBackToFastH, Unannotated(Anything), moveBackToFastH, Move(LEFT)],
                [moveBackToFastH, Annotated(Fast), stateAfterMove, Deannotate()],
                // the L is not a V, sigh. Annotate it and move right
                [testLVHH, Not(H), moveUpToRMoveH, Annotate(L), Move(RIGHT)],
                [moveUpToRMoveH, Anything, moveUpToRMoveH, Move(RIGHT)],
                [moveUpToRMoveH, Annotated(Fast, 0), moveUpToRMoveH, Move(RIGHT)],
                // // found it, deannotate, move right and test it
                [moveUpToRMoveH, R, applyHR, Write(0), Move(RIGHT)]
              );
            } else if (thisInstruction.direction === LEFT) {
              subDescription.push(
                [stateBeforeMove, matchBeforeMove, fastBackToSlow, Annotate(Slow), Move(LEFT), Move(LEFT)],
                [fastBackToSlow, Anything, moveBackToSlow, Annotate(Fast), Move(RIGHT)],
                [moveBackToSlow, Unannotated(Anything), moveBackToSlow, Move(RIGHT)],
                [moveBackToSlow, Annotated(Slow), testVorH, Deannotate(), Move(LEFT)],
                [testVorH, V, solveForV, Move(LEFT)],
                [testVorH, H, solveForH, Move(LEFT)],
                [testVorH, Not(V, H), resetFast, Annotate(Slow), Move(LEFT)],
                [resetFast, Unannotated(Anything), resetFast, Move(LEFT)],
                [resetFast, Annotated(Fast), moveBackToSlow, Deannotate(), Move(LEFT), Move(LEFT), Annotate(Fast), Move(RIGHT)],
                [solveForV, Unannotated(Anything), solveForV, Move(LEFT)],
                [solveForV, Annotated(Fast), stateAfterMove, Deannotate()],
                [solveForH, Unannotated(Anything), solveForH, Move(LEFT)],
                [solveForH, Annotated(Fast), stateAfterMove, Deannotate(), Move(RIGHT)]
              );
            } else if (thisInstruction.direction === RIGHT) {
              subDescription.push(
                [stateBeforeMove, matchBeforeMove, fastBackToSlow, Annotate(Slow), Move(RIGHT), Move(RIGHT)],
                [fastBackToSlow, Anything, moveBackToSlow, Annotate(Fast), Move(LEFT)],
                [moveBackToSlow, Unannotated(Anything), moveBackToSlow, Move(LEFT)],
                [moveBackToSlow, Annotated(Slow), testVorH, Deannotate(), Move(RIGHT)],
                [testVorH, V, solveForV, Move(RIGHT)],
                [testVorH, H, solveForH, Move(RIGHT)],
                [testVorH, Not(V, H, VEND, HEND), resetFast, Annotate(Slow), Move(RIGHT)],
                [resetFast, Unannotated(Anything), resetFast, Move(RIGHT)],
                [resetFast, Annotated(Fast), moveBackToSlow, Deannotate(), Move(RIGHT), Move(RIGHT), Annotate(Fast), Move(LEFT)],
                [solveForV, Unannotated(Anything), solveForV, Move(RIGHT)],
                [solveForV, Annotated(Fast), stateAfterMove, Deannotate()],
                [solveForH, Unannotated(Anything), solveForH, Move(RIGHT)],
                [solveForH, Annotated(Fast), stateAfterMove, Deannotate(), Move(RIGHT)],

                // expansion 1: Found V at the end
                // write a V, move left and annotate L, move right twice
                [testVorH, VEND, applyVR, Write(V), Move(LEFT), Annotate(L), Move(RIGHT), Move(RIGHT)],
                // is it marked? skip the mark and write R
                [applyVR, Annotated(Fast, 0), moveBackToVLeft, Move(RIGHT), Write(R)],
                // otherwise just write R
                [applyVR, Unannotated(0), moveBackToVLeft, Write(R)],
                //move back to annotated L
                [moveBackToVLeft, Unannotated(Anything), moveBackToVLeft, Move(LEFT)],
                [moveBackToVLeft, Annotated(Fast, 0), moveBackToVLeft, Move(LEFT)],
                // deannotate and move left
                [moveBackToVLeft, Annotated(L), testLVHV, Deannotate(), Move(LEFT)],
                // is it an H? we're almost done move up to the R
                [testLVHV, H, moveUpToRH, Move(RIGHT)],
                [moveUpToRH, Not(H), moveUpToRH, Move(RIGHT)],
                [moveUpToRH, Annotated(Fast, 0), moveUpToRH, Move(RIGHT)],
                // found the R! Write an H.
                [moveUpToRH, R, moveBackToFastV, Write(0), Move(RIGHT), Write(HEND), Move(LEFT)],
                // move back to the fast, deannotate it, and we're done
                [moveBackToFastV, Unannotated(Anything), moveBackToFastV, Move(LEFT)],
                [moveBackToFastV, Annotated(Fast), stateAfterMove, Deannotate()],
                // the L is not an H, sigh. Annotate it and move right
                [testLVHV, Not(H), moveUpToRMoveV, Annotate(L), Move(RIGHT)],
                [moveUpToRMoveV, Not(H), moveUpToRMoveV, Move(RIGHT)],
                [moveUpToRMoveV, Annotated(Fast, 0), moveUpToRMoveV, Move(RIGHT)],
                // // found it, deannotate, move right and test it
                [moveUpToRMoveV, R, applyVR, Write(0), Move(RIGHT)],

                // expansion 2: Found H at the end
                // write an H, move left and annotate L, move right twice
                [testVorH, HEND, applyHR, Write(H), Move(LEFT), Annotate(L), Move(RIGHT), Move(RIGHT)],
                // is it marked? skip the mark and write R
                [applyHR, Annotated(Fast, 0), moveBackToHLeft, Move(RIGHT), Write(R)],
                // otherwise just write R
                [applyHR, Unannotated(0), moveBackToHLeft, Write(R)],
                //move back to annotated L
                [moveBackToHLeft, Unannotated(Anything), moveBackToHLeft, Move(LEFT)],
                [moveBackToHLeft, Annotated(Fast, 0), moveBackToHLeft, Move(LEFT)],
                // deannotate and move left
                [moveBackToHLeft, Annotated(L), testLVHH, Deannotate(), Move(LEFT)],
                // is it a V? we're almost done move up to the R
                [testLVHH, V, moveUpToRV, Move(RIGHT)],
                [moveUpToRV, Not(V),     moveUpToRV, Move(RIGHT)],
                [moveUpToRV, Annotated(Fast, 0), moveUpToRV, Move(RIGHT)],
                // found the R! Write a V.
                [moveUpToRV, R, moveBackToFastH, Write(0), Move(RIGHT), Write(VEND), Move(LEFT)],
                // move back to the fast, deannotate it, move right, and we're done
                [moveBackToFastH, Unannotated(Anything), moveBackToFastH, Move(LEFT)],
                [moveBackToFastH, Annotated(Fast), stateAfterMove, Deannotate(), Move(RIGHT)],
                // the L is not a V, sigh. Annotate it and move right
                [testLVHH, Not(H), moveUpToRMoveH, Annotate(L), Move(RIGHT)],
                [moveUpToRMoveH, Anything, moveUpToRMoveH, Move(RIGHT)],
                [moveUpToRMoveH, Annotated(Fast, 0), moveUpToRMoveH, Move(RIGHT)],
                // // found it, deannotate, move right and test it
                [moveUpToRMoveH, R, applyHR, Write(0), Move(RIGHT)]
              );
            } else {
              error('unknown move direction');
            }

            // now that we've moved, any following instructions must be prepared for anything

            toMatch = Not(V, H);

            // set up following instructions
          } else {
            subInstructions.push(thisInstruction)
          }
        }

        if (subInstructions.length > 0) {
          subDescription.push([fromState, toMatch, nextState, ...subInstructions])
        }

        return subDescription;
      })
    );

    const after = _tape => {
      const tape2d = Array.from({ length: max },
        () => Array.from({ length: max }, () => 0)
      );

      const tape = Array.from(_tape);

      // console.log(tape.join(' '));

      tape.shift(); // initial V

      for (let sum = 0; tape.length > 0; ++sum) {
        const topDown = sum % 2 === 1;

        for (let innerCount = 0; innerCount <= sum; ++innerCount) {
          let h;
          let v;

          if (topDown) {
            v = innerCount;
            h = sum - innerCount;
          } else {
            h = innerCount;
            v = sum - innerCount;
          }
          if (v === tape2d.length || h === tape2d.length) {
            tape2d.forEach( row => row.push(0));
            tape2d.push(Array.from({ length: tape2d.length + 1 }, () => 0))
          }
          if (v < tape2d.length && h < tape2d[v].length) {
            tape2d[v][h] = tape.shift();
          } else {
            error('reg, you made a mistake', { v, h, tape2d });
          }
        }

        tape.shift();
      }

      // console.log(tape2d)

      return flatMap(tape2d, I);
    }

    // pd('2d', description);

    return { description, tape, after };

  };

  return Object.assign(compile, { constants: { UP, DOWN } });
})();

// pretty-print two-dimensional tapes
const p2d = tape => {
  const size = Math.sqrt(tape.length);
  const rows = chunksOf(size, tape);
  for (const row of rows) {
    console.log(row.join(' '));
  }
}

// define macros to be expanded
const macros = (() => {

  function Expand (macroFunction) {
    if (this == null) {
      return new Expand(macroFunction);
    }
    this.name = macroFunction.name || 'anonymous';
    this.macroFunction = (stateBeforeExpand, matchBeforeExpand, stateAfterExpand) => {
      const macroBody = macroFunction(stateBeforeExpand, matchBeforeExpand, stateAfterExpand);
      const states = macroBody.reduce(
        (states, [state1, _, state2, ...__]) => {
          if (!states.get(state1)) {
            if ([stateBeforeExpand, stateAfterExpand].includes(state1)) {
              states.set(state1, state1);
            } else {
              states.set(state1, gensym(state1));
            }
          }
          if (!states.get(state2)) {
            if ([stateBeforeExpand, stateAfterExpand].includes(state2)) {
              states.set(state2, state2);
            } else {
              states.set(state2, gensym(state2));
            }
          }
          return states;
        },
        new Map()
      );
      const gensymedBody = macroBody.map(
        ([state1, match, state2, ...instructions]) =>
          [states.get(state1), match, states.get(state2), ...instructions]
      );
      return gensymedBody;
    };
  }

  Expand.prototype.toString = function () { return `Expand(${this.name})`; }

  const compiler = ({ description: _description, Anything }) => ({
    description: flatMap(_description,
      ([currentState, currentMatch, nextState, ..._instructions]) => {
        const subDescription = [];
        let fromState = currentState;
        let toMatch = currentMatch;
        let toState = nextState;
        let subInstructions = [];

        let thisInstruction;
        while (thisInstruction = _instructions.shift()) {
          if (thisInstruction instanceof Expand) {
            // what is the beginnng state?
            let stateBeforeExpand;
            // what do we need to match before marking things up?
            let matchBeforeExpand;
            if (subInstructions.length > 0) {
              // flush existing instructions
              stateBeforeExpand = gensym(`before-expand-${nextState}`);
              matchBeforeExpand = Anything;
              subDescription.push([fromState, toMatch, stateBeforeExpand, ...subInstructions]);
              subInstructions = [];
            } else if (fromState === currentState) {
              stateBeforeExpand = fromState;
              matchBeforeExpand = currentMatch;
            } else {
              stateBeforeExpand = fromState;
              matchBeforeExpand = Anything;
            }

            // are we the last instruction?
            let stateAfterExpand;
            if (_instructions.length === 0) {
              stateAfterExpand = nextState;
            } else {
              stateAfterExpand = gensym('after-expand');
            }
            fromState = stateAfterExpand;

            const macro = thisInstruction.macroFunction;

            if (typeof macro !== 'function') {
              error(`I don't know how to expand this macro`);
            }

            subDescription.push(
              ...macro(stateBeforeExpand, matchBeforeExpand, stateAfterExpand)
            )

            // now that we've expanded, any following instructions must be prepared for anything

            toMatch = Anything;

            // set up following instructions
          } else {
            subInstructions.push(thisInstruction)
          }
        }

        if (subInstructions.length > 0) {
          subDescription.push([fromState, toMatch, nextState, ...subInstructions])
        }

        return subDescription;
      }
    )
  });

  return Object.assign(compiler, { constants: { Expand } })
})();

// An implementation of Conway's Game of Life
(() => {

  // The "tableau machine" that understands macros, annotations, and a two-dimensional 'tableau'
  const tableauMachine = compile(macros, annotations, twoDimensional, annotations, stats('tsMachine program'), tsMachine);

  // extract the constants we'll need to write our program
  const { constants: { LEFT, RIGHT, UP, DOWN, HALT, Move, Write, Annotated, Unannotated, Annotate, Deannotate, Nothing, Something, Anything, Expand } } = tableauMachine;

  // this macro preumes the TM is on a cell. it movves left and up, then circumnavigates the cell,
  // counting neighbours. it then annotates the cell with 'alive' or 'dead' to indicate the
  // future.
  const annotateWithFuture = (stateBeforeExpand, matchBeforeExpand, stateAfterExpand) => [
    [stateBeforeExpand, matchBeforeExpand, 'start-cell', Move(LEFT), Move(UP)],
    ['start-cell', 0, 'ul-zero', Move(RIGHT)],
    ['start-cell', 1, 'ul-one', Move(RIGHT)],

    ['ul-zero', 1, 'uc-one', Move(RIGHT)],
    ['ul-zero', 0, 'uc-zero', Move(RIGHT)],
    ['uc-zero', 0, 'ur-zero', Move(DOWN)],
    ['uc-zero', 1, 'ur-one', Move(DOWN)],
    ['ur-zero', 0, 'mr-zero', Move(DOWN)],
    ['ur-zero', 1, 'mr-one', Move(DOWN)],
    ['mr-zero', 0, 'lr-zero', Move(LEFT)],
    ['mr-zero', 1, 'lr-one', Move(LEFT)],
    ['lr-zero', 0, 'lc-zero', Move(LEFT)],
    ['lr-zero', 1, 'lc-one', Move(LEFT)],
    ['lc-zero', 0, 'll-zero', Move(UP)],
    ['lc-zero', 1, 'll-one', Move(UP)],
    ['ll-zero', 0, 'zero', Move(RIGHT)],
    ['ll-zero', 1, 'one', Move(RIGHT)],

    ['ul-one', 0, 'uc-one', Move(RIGHT)],
    ['ul-one', 1, 'uc-two', Move(RIGHT)],
    ['uc-one', 0, 'ur-one', Move(DOWN)],
    ['uc-one', 1, 'ur-two', Move(DOWN)],
    ['ur-one', 0, 'mr-one', Move(DOWN)],
    ['ur-one', 1, 'mr-two', Move(DOWN)],
    ['mr-one', 0, 'lr-one', Move(LEFT)],
    ['mr-one', 1, 'lr-two', Move(LEFT)],
    ['lr-one', 0, 'lc-one', Move(LEFT)],
    ['lr-one', 1, 'lc-two', Move(LEFT)],
    ['lc-one', 0, 'll-one', Move(UP)],
    ['lc-one', 1, 'll-two', Move(UP)],
    ['ll-one', 0, 'one', Move(RIGHT)],
    ['ll-one', 1, 'two', Move(RIGHT)],

    ['uc-two', 0, 'ur-two', Move(DOWN)],
    ['uc-two', 1, 'ur-three', Move(DOWN)],
    ['ur-two', 0, 'mr-two', Move(DOWN)],
    ['ur-two', 1, 'mr-three', Move(DOWN)],
    ['mr-two', 0, 'lr-two', Move(LEFT)],
    ['mr-two', 1, 'lr-three', Move(LEFT)],
    ['lr-two', 0, 'lc-two', Move(LEFT)],
    ['lr-two', 1, 'lc-three', Move(LEFT)],
    ['lc-two', 0, 'll-two', Move(UP)],
    ['lc-two', 1, 'll-three', Move(UP)],
    ['ll-two', 0, 'two', Move(RIGHT)],
    ['ll-two', 1, 'three', Move(RIGHT)],

    ['ur-three', 0, 'mr-three', Move(DOWN)],
    ['ur-three', 1, 'too-many', Move(LEFT)], // short circuit
    ['mr-three', 0, 'lr-three', Move(LEFT)],
    ['mr-three', 1, 'too-many', Move(LEFT), Move(UP)], // short circuit
    ['lr-three', 0, 'lc-three', Move(LEFT)],
    ['lr-three', 1, 'too-many', Move(UP)], // short circuit
    ['lc-three', 0, 'll-three', Move(UP)],
    ['lc-three', 1, 'too-many', Move(UP), Move(RIGHT)], // short circuit
    ['ll-three', 0, 'three', Move(RIGHT)],
    ['ll-three', 1, 'too-many', Move(RIGHT)],

    ['zero', 0, stateAfterExpand, Annotate('dead')],
    ['zero', 1, stateAfterExpand, Annotate('dead')],
    ['one', 0, stateAfterExpand, Annotate('dead')],
    ['one', 1, stateAfterExpand, Annotate('dead')],
    ['two', 0, stateAfterExpand, Annotate('dead')],
    ['two', 1, stateAfterExpand, Annotate('alive')],
    ['three', 0, stateAfterExpand, Annotate('alive')],
    ['three', 1, stateAfterExpand, Annotate('alive')],
    ['too-many', 0, stateAfterExpand, Annotate('dead')],
    ['too-many', 1, stateAfterExpand, Annotate('dead')]
  ];

    // this macro reads the annotation and updates the cell's state
  const updateFromAnnotation = (stateBeforeExpand, matchBeforeExpand, stateAfterExpand) => [
    [stateBeforeExpand, Annotated('dead'), stateAfterExpand, Deannotate(), Write(0)],
    [stateBeforeExpand, Annotated('alive'), stateAfterExpand, Deannotate(), Write(1)]
  ];

  // Here's a program for a simple 3x3 life universe. It assumes that the universe is padded with zeroes,
  // so it begins by moving right and down to get to the first cell we care about.
  //
  // the program is written as one 'state', but our compilers translate the sequence of instructions into
  // states for us.
  //
  // The exact number of states in the fully compiled program varies as adjustments are made, but when this comment was written
  // this program compiled into a program with 755,296 instructions and 23,699 states.
  const description = [
    [
      'start', 0, HALT, Move(RIGHT), Move(DOWN),

      // annotate the nine cells in the 3x3 grid
      Expand(annotateWithFuture), Move(RIGHT), Expand(annotateWithFuture), Move(RIGHT), Expand(annotateWithFuture), Move(DOWN),
      Expand(annotateWithFuture), Move(LEFT),  Expand(annotateWithFuture), Move(LEFT),  Expand(annotateWithFuture), Move(DOWN),
      Expand(annotateWithFuture), Move(RIGHT), Expand(annotateWithFuture), Move(RIGHT), Expand(annotateWithFuture),

      // update their contents from the annotations
      Expand(updateFromAnnotation), Move(LEFT),  Expand(updateFromAnnotation), Move(LEFT),  Expand(updateFromAnnotation), Move(UP),
      Expand(updateFromAnnotation), Move(RIGHT), Expand(updateFromAnnotation), Move(RIGHT), Expand(updateFromAnnotation), Move(UP),
      Expand(updateFromAnnotation), Move(LEFT),  Expand(updateFromAnnotation), Move(LEFT),  Expand(updateFromAnnotation), Move(RIGHT)
    ]
  ];

  // here's a simple life organism, a 'blinker'
  const tape = [
    0, 0, 0, 0, 0,
    0, 0, 1, 0, 0,
    0, 0, 1, 0, 0,
    0, 0, 1, 0, 0,
    0, 0, 0, 0, 0
  ];

  // run the program!
  p2d(tableauMachine({ description, tape }));

})();