Demonstrates a useful pattern of defining and (semi-)automatically deriving evaluators for domain-specific languages in TypeScript

arith.ts

import { _, Functor, Fix, _in, cata, Algebra } from './base';
import { strict as assert } from 'assert';

// The type parameter goes where the grammar would otherwise reference itself.
type ArithF<A>
  = { tag: 'add' ; lhs: A ; rhs: A }
  | { tag: 'mul' ; lhs: A ; rhs: A }
  | { tag: 'num' ; n: number }
  | { tag: 'paren' ; e: A } ;

// I wish I had a concise summary of this one.
const ArithFunctor: Functor<ArithF<_>> = {
  map: (f, arith) => { switch (arith.tag) {
    case 'add': return { ...arith , lhs: f(arith.lhs), rhs: f(arith.rhs) };
    case 'mul': return { ...arith , lhs: f(arith.lhs), rhs: f(arith.rhs) };
    case 'paren': return { ...arith, e: f(arith.e) };
    default: return { ...arith }; } } };

// Export-able interface (clean type + smart constructors).
type Arith = Fix<ArithF<_>>;
const add = (lhs: Arith, rhs: Arith): Arith => _in({ tag: 'add', lhs, rhs });
const mul = (lhs: Arith, rhs: Arith): Arith => _in({ tag: 'mul', lhs, rhs });
const paren = (e: Arith): Arith => _in({ tag: 'paren', e });
const num = (n: number): Arith => _in({ tag: 'num', n });

// First algebra reduces arithmetic expressions to numeric results.
const ArithNumAlg: Algebra<ArithF<number>,number> = ex => { switch (ex.tag) {
  case 'add': return ex.lhs + ex.rhs;
  case 'mul': return ex.lhs * ex.rhs;
  case 'paren': return ex.e;
  default: return ex.n; } };
const eval_arith = (ex: Arith): number => cata(ArithFunctor, ArithNumAlg, ex);

// Second algebra serializes arithmetic expressions to human-readable strings.
const ArithStrAlg: Algebra<ArithF<string>,string> = ex => { switch (ex.tag) {
  case 'add': return `${ex.lhs} + ${ex.rhs}`;
  case 'mul': return `${ex.lhs} * ${ex.rhs}`;
  case 'paren': return `( ${ex.e} )`;
  default: return ex.n.toString(); } };
const print_arith = (ex: Arith): string => cata(ArithFunctor, ArithStrAlg, ex);

// Our test subject: a very cool number.
const cool_number: Arith =
  add(
    num(69),
    mul(
      num(3),
      paren(
        add(
          num(110),
          num(7)))));

const stringified = print_arith(cool_number);
const evaluated   = eval_arith (cool_number);

assert.equal(stringified, '69 + 3 * ( 110 + 7 )');
assert.equal(evaluated,  420);
console.log(`${stringified} =>`, evaluated);

base.ts

// Simplifies, adapts, documents, and extends the following work:
// https://github.com/pelotom/hkts

/**
 * `$` solves a weird problem in what might be a weird way, so it's helpful to
 * separate what those are.
 *
 * THE PROBLEM IT SOLVES: in typescript, a type variable introduced by a
 * generic can't itself be generic. Eg,
 *
 *   type Foo<T,A> = T<A>;
 *
 * is not legal because T is not generic.
 *
 * Instead, we can use $<T,A> ~ T<A>.
 *
 * HOW IT SOLVES IT: conditional typing (ab)used to construct an indexed type
 * wrapping the type application result (whatever it may be), which is then
 * immediately indexed. This part I leave for you to explore.
 */
// prettier-ignore
export type $<T, S extends any> = (
  T extends Fix<infer U> ? { [indirect]: U } :
  T extends _ ? { [indirect]: S } :
  T extends undefined | null | boolean | string | number ? { [indirect]: T } :
  T extends (...x: infer I) => infer O ? { [indirect]: (...x: $<I, S>) => $<O, S> } :
  T extends object ? { [indirect]: { [K in keyof T]: $<T[K], S> } } :
  { [indirect]: never }
)[typeof indirect];

/**
 * Used as a level of indirection to avoid circularity errors.
 */
declare const indirect: unique symbol;

/**
 * Placeholder representing an indexed type variable.
 */
export interface _<N extends number = 0> {
  [index]: N;
}
declare const index: unique symbol;

/**
 * Marks a type to be ignored by the application operator `$`. This is used to protect
 * bound type parameters.
 * In combination with the functions `_in` and `out` this also serves to
 * construct type-level fixpoint terms with no runtime penalty.
 */
export interface Fix<T> {
  [fixed]: T;
}
declare const fixed: unique symbol;
export const _in = <F>(term: $<F,Fix<F>>): Fix<F> => (<any>term);
export const out = <F>(term: Fix<F>): $<F,Fix<F>> => (<any>term);

export interface Functor<T> {
  map: <A, B>(
    f: (x: A) => B,
    t: $<T, A>
  ) => $<T, B>; }

// An f-algebra reduces functor values parameterized by a given carrier type
// "A" to that particular type.
export type Algebra<F,A> = (fa: $<F,A>) => A;

/**
 * Produces "catamorphisms" (ie, evaluators / reducers / folds) for algebraic
 * functor types from a given functor algebra.
 */
export function cata<F,A>(
  functor: Functor<F>,
  transformer: Algebra<F,A>,
  term: Fix<F>
): A {
  const extracted = out(term);
  const children_mapped = functor.map(
    v => cata(functor, transformer, v),
    extracted );
  const transformed = transformer(children_mapped);
  return transformed; }