Skip to content

Instantly share code, notes, and snippets.

@gatlin

gatlin/arith.ts

Last active Dec 16, 2020
Embed
What would you like to do?
Demonstrates a useful pattern of defining and (semi-)automatically deriving evaluators for domain-specific languages in TypeScript
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);
// 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; }
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment