Defunctionalized continuations in JS using algebraic data types

lambdastack.js

// Copyright 2025 Simon Meskens
// Licensed under the MIT License
//
// Permission to use, copy, modify, and/or distribute this software for any
// purpose with or without fee is hereby granted, provided this license is
// preserved. This software is offered as-is, without any warranty.

// Based on: https://www.youtube.com/watch?v=O6s8_4agu4c
// https://gist.github.com/paf31/16f25ef70eaf256fbf301b571db6d533

const { data, free, closure, bind, lookup, match, id } = lambda();

const Term = data({
  Var: ["binding"],
  Lam: ["binding", "term"],
  App: ["term", "arg"],
});

const { Var, Lam, App } = Term;

const test = (evaluate, term, env = free) =>
  console.log(`${term} => ${evaluate(term, env)}`);

const debugMatch = (term, cases, fallback) => {
  debugger;
  const result = match(term, cases, fallback);
  console.log(`term: ${term} => ${result}`);
  return result;
};

const example = {
  term: App(Lam("x", Var("x")), Var("y")),
  env: bind("y", "ok", free),
};

{
  // Eager evaluation
  const evaluate = (term, env = free) => {
    return match(term, {
      [Var]: ({ binding }) => lookup(binding, env),
      [Lam]: ({ binding, term }) => closure(binding, term, env),
      [App]: ({ term, arg }) => apply(evaluate(term, env), evaluate(arg, env)),
    });
  };

  const apply = ({ binding, term, env }, val) =>
    evaluate(term, bind(binding, val, env));

  const x = lookup(Var("x"), free);
  debugger;

  test(evaluate, example.term, example.env);
}

{
  // CPS using callbacks
  const evaluate = (term, env = free, cb = id) =>
    match(term, {
      [Var]: ({ binding }) => cb(lookup(binding, env)),
      [Lam]: ({ binding, term }) => cb(closure(binding, term, env)),
      [App]: ({ term, arg }) =>
        evaluate(term, env, ({ binding, term, env }) =>
          evaluate(arg, env, (val) =>
            evaluate(term, bind(binding, val, env), cb)
          )
        ),
    });

  test(evaluate, example.term, example.env);
}

{
  // Defunctionalized CPS
  const { Done, Fun, Arg } = data({
    Done: ["cont"],
    Fun: ["term", "env", "cont"],
    Arg: ["val", "cont"],
  });

  const evaluate = (term, env = free, cont = Done(id)) =>
    match(term, {
      [Var]: ({ binding }) => apply(lookup(binding, env), cont),
      [Lam]: ({ binding, term }) => apply(closure(binding, term, env), cont),
      [App]: ({ term, arg }) => evaluate(term, env, Fun(arg, env, cont)),
    });

  const apply = (val, cont) =>
    match(cont, {
      [Done]: ({ cont }) => cont(val),
      [Fun]: ({ term, env, cont }) => evaluate(term, env, Arg(val, cont)),
      [Arg]: ({ val: { binding, term, env }, cont }) =>
        evaluate(term, bind(binding, val, env), cont),
    });

  test(evaluate, example.term, example.env);
}

// === BONUS === //

/*
{
  const trampoline =
    (fn) =>
    (...args) => {
      let gen = fn(...args),
        result = gen.next();
      while (!result.done) result = gen.next(result.value);
      return result.value;
    };

  // CPS using generators
  const evaluate = trampoline(function* recur(term, env) {
    return yield* match(term, {
      [Var]: function* ({ binding }) {
        return lookup(binding, env);
      },
      [Lam]: function* ({ binding, term }) {
        return closure(binding, term, env);
      },
      [App]: function* ({ term, arg }) {
        const fnVal = yield* recur(term, env);
        const argVal = yield* recur(arg, env);
        return yield* recur(fnVal.term, bind(fnVal.binding, argVal, fnVal.env));
      },
    });
  });

  test(evaluate, example.term, example.env);
}

{
  // CPS using generators
  const evaluate = (
    term,
    env = free,
    recur = function* (term, env) {
      return yield* match(term, {
        [Var]: function* ({ binding }) {
          return lookup(binding, env);
        },
        [Lam]: function* ({ binding, term }) {
          return closure(binding, term, env);
        },
        [App]: function* ({ term, arg }) {
          const fnVal = yield* recur(term, env);
          const argVal = yield* recur(arg, env);
          return yield* recur(
            fnVal.term,
            bind(fnVal.binding, argVal, fnVal.env)
          );
        },
      });
    }
  ) => {
    // Trampoline
    let gen = recur(term, env),
      result = gen.next();
    while (!result.done) result = gen.next(result.value);
    return result.value;
  };

  test(evaluate, example.term, example.env);
}

{
  const testAsync = async (evaluate, term, env = free) =>
    console.log(`${term} => ${await evaluate(term, env)}`);

  // CPS using async/await
  const evaluate = async (term, env = free) =>
    match(term, {
      [Var]: ({ binding }) => lookup(binding, env),
      [Lam]: ({ binding, term }) => closure(binding, term, env),
      [App]: async ({ term, arg }) => {
        const fnVal = await evaluate(term, env);
        const argVal = await evaluate(arg, env);
        return evaluate(fnVal.term, bind(fnVal.binding, argVal, fnVal.env));
      },
    });

  testAsync(evaluate, example.term, example.env);
}
*/

// === UTILS === //

function lambda() {
  const { create, assign, entries, defineProperty, defineProperties } = Object;

  const proto = defineProperty({}, "toString", {
    value: function toString() {
      const props = entries(this).filter(([key]) => key !== "type");
      return this.type
        ? `${this.type.name}(${props.map(([_, val]) => val).join(", ")})`
        : `{ ${props.map(([key, val]) => `${key}: ${val}`).join(", ")} }`;
    },
  });
  const printable = (props) => assign(create(proto), props);

  const constructor = (type, keys) => {
    const ctor = defineProperties(
      (...values) =>
        values.reduce(
          (obj, value, i) => ((obj[keys[i]] = value), obj),
          defineProperty(create(proto), "type", { value: ctor })
        ),
      { name: { value: type }, length: { value: keys.length } }
    );
    return ctor;
  };

  const data = (types) =>
    entries(types).reduce(
      (ctors, [type, keys]) => ((ctors[type] = constructor(type, keys)), ctors),
      {}
    );

  const free = new Proxy({}, { get: (_, binding) => printable({ binding }) });
  const closure = (binding, term, env) => printable({ binding, term, env });
  const bind = (binding, val, env) => ({ ...env, [binding]: val });
  const lookup = (binding, env) => env[binding];

  const match = (term, cases, fallback) =>
    typeof cases === "function"
      ? cases(term)
      : term?.type in cases
      ? cases[term.type](term)
      : fallback?.(term);

  const id = (x) => x;

  return { data, free, closure, bind, lookup, match, id };
}