raganwald

// ---------- Mockingbirds and Why Birds with Higher-Kinded Types ----------
//
// The nicknames "Mockingbird" and "Why Bird" are derived from "To Mock a
// Mockingbird" by Raymond Smullyan.
//
// requires https://github.com/poteat/hkt-toolbelt

import { Kind, $, $$ } from "hkt-toolbelt";
import { _$inputOf } from "hkt-toolbelt/kind";
import { _$cast } from "hkt-toolbelt/type";

raganwald

// --------- Utilities ---------

type Expect<T extends true> = T;
type Equal<X, Y> = (<T>() => T extends X ? 1 : 2) extends <T>() => T extends Y ? 1 : 2
  ? true
  : false;
type Extends<A, B> = A extends B ? true : false;
type IsNever<T> = Extends<[T], [never]>;
type IsFalse<T> = T extends false ? true : false;

raganwald

/*
  FRACTRAN in type-level TypeScript:

  Q. What is FRACTRAN?
  A. FRACTRAN is a Turing-complete esoteric programming language invented by the mathematician John Conway.
     A FRACTRAN program is an ordered list of positive fractions together with an initial positive integer
     input n. The program is run by updating the integer n as follows:

      1. for the first fraction f in the list for which nf is an integer, replace n by nf
      2. repeat this rule until no fraction in the list produces an integer when multiplied by n, then halt.

raganwald

// TypeScript Playground link:
//
// https://www.typescriptlang.org/play/?#code/C4TwDgpgBAogHpAxsAPAFShOwIDsAmAzlMAE4CuEAfFALxRoDcAUKJLAI7kCGANigA0ANFACaNegAp0VSQEo6NDFhwFiAqAH4oARigAuKACYFKvESgz5ihpmzniorboPHmUZ2UrvXAMz6EECxs0AByAPaoyvZqUABG4eG8ENy4ErZmsf68gZ4U0IbZgSys4NAAysDcOHRQAEQ6dVAAPvUADHUlIVAASuTJOjpttQDePnVtk3WGE3VC45ONM43zHhND0-UrC4ObDXPjQx0zHatbbUtbB2uDx1dnDbsnBwC+XWVQoSoA4ngQpNUAJbhXDoOyqCyEMiA3AAcxEAEEAMJI8EOKBQ0gw2G1Op1CQ+aIQ4h4lpQSrVaCtAAGABIRhScC96YyIC9qT5tMikT5DET0XSRjDfP8oAAJFL4PSZCys5lC3Ai0jiyVGNGxOX04WiiXcfAAZnVsqqTK1itFPQgUPZPg82i+2F+uH+QJBKEFuvwRnlnv18st1upIkF3P9-QgtwA2h7JTofar43q-dSALrsqi21zOgBu-3e7AA+kZhvR4EhUDAuHwULMRA7gE6XcBgaCJlMqB3gh8i3pSwgIMgUJWePx9nWfn8Ac23W3Gh2qF3C0Y1X3y0Oq6OVp8J86py2axcOvPF9Ai4bVwOKxua1v6429zOLnPO6UlwAWWply-rkcHubbx1J1dVsjnxF9uiLABWT9+0HYdqzHACGyA6cQIuMCF1fU8jAANhgtd4M3f87xQ-dHiPcDuyMAB2fDv0Iv9x0A3dgJvXZj2YLCoALfUS1gWCr1-NtiJ3JsyMmdtKMLfVe34gjr3WETmLEx9Fgwk9uP1Fc5PohTdiY5CWNQg9D3UriePPHS4L029RIfVtFmfTCIP1D8L2soSNgM+9WPWSTnO7fVoPcwSEP0pCfOMvynI0ni8JCn8wts5T7IPW4

raganwald

type Expect<T extends true> = T;
type Equal<X, Y> = (<T>() => T extends X ? 1 : 2) extends <T>() => T extends Y ? 1 : 2
  ? true
  : false;

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;
  }