raganwald

// a post machine emulator

function validatedAlphabet({ description: { A } }) {
  if (A == null) throw new Error('description missing alphabet');
  
  return A;
}

function validatedDeletionNumber({ description: { m } }) {
  if (m == null) throw new Error('description is missing its m');

raganwald

const truncated = a => {
  let aa = [...a];
  
  while (aa.length > 1 && (aa[aa.length - 1] === 0 || aa[aa.length - 1] == null)) {
    aa = aa.slice(0, aa.length - 1);
  }
  
  return aa;
}

raganwald

// handles primitives like integers and arrays of simple primitives
// all other behaviour is undefined

function superSimpleEquivalent(a, b) {
  if (a instanceof Array && b instanceof Array) {
    if (a.length != b.length) return false;
    
    for (let i = 0; i < a.length; ++i) {
      if (!superSimpleEquivalent(a[i], b[i])) return false;
    }

raganwald

We wish to compute fib(7).

This is a FRACTRAN program for computing any Fibonacci number: 17/65, 133/34, 17/19, 23/17, 2233/69, 23/29, 31/23, 74/341, 31/37, 41/31, 129/287, 41/43, 13/41, 1/13, 1/3.

The seed n is computed n = 78 * 5^(x - 1). Therefore, we start with n = 78 * 5^(7-1), which is 1,218,750.

• The first fraction in the program is 17/65. 1,218,750 multiplied by 17/65 is 318,750, so we replace 1,218,750 with 318,750 and begin again.
• The first fraction in the program is 17/65. 318,750 leaves a remainder when divided by 65, so we move on.
• The next fraction in the program is 133/34. 318,750 multiplied by 133/34 is 1,246,875, so we replace 318,750 with 1,246,875 and begin again.
• The first fraction in the program is 17/65. 1,246,875 leaves a remainder when divided by 65, so we move on.

raganwald

const END = Symbol('end');

class PushdownAutomaton {
  constructor(internal = 'start', external = []) {
    this.internal = internal;
    this.external = external;
    this.halted = false;
    this.recognized = false;
  }

raganwald

// See: http://raganwald.com/2019/02/27/enumerability.html

// combinators

function slice (generator, n, limit = Infinity) {
  return function * sliced () {
    let i = 0;
    
    for (const element of generator()) {
      if (i++ < n) continue;

raganwald

// Inspired by:
//
// "Eh, have another semi-periodic reminder that ()() is not a palindrome but ())( is"
//
// --https://twitter.com/_julesh_/status/1101262745092218882

const END = Symbol('end');

class PushdownAutomaton {
  constructor(internal = 'start', external = []) {

raganwald

// memoizes ordinary functions
const memoized = (fn, keymaker = JSON.stringify) => {
  const lookupTable = new Map();

  return function (...args) {
    const key = keymaker.call(this, args);

    return lookupTable[key] || (lookupTable[key] = fn.apply(this, args));
  }
};

raganwald

// The Deterministic Pushdown Automata Engine

const END = Symbol('end');
const RECOGNIZED = Symbol('recognized');
const UNRECOGNIZED = Symbol('unrecognized');
const POP = Symbol('pop');

function DPA (start) {
  return string => {
    const stack = [];

raganwald

function balanced (string) {
  const iterator = string[Symbol.iterator]();
  
  return balancedIterator(iterator) === true;
}

const CLOSE = {
  '(': ')',
  '[': ']',
  '{': '}'