Scarab-∞ CESK core

interpreter.ts

/**
 * Scarab Lisp interpreter. Runs Scarab-∞ in ANF with full first class continuations.
 * 
 * This is a CEK machine, with *mutable* environments. (so remember to migrate to CESK for formal work, derp).
 * 
 */
import { Let0, Lit, VarRef, App, If, SetQ, Fn, CallCC, RuntimeEnv, Var, Env, AExp, Exp, PApp } from "./ir";
import { NIL } from "../scarab-core/lists";
export const STEP: unique symbol = Symbol("step");
export const AEXP: unique symbol = Symbol("aexp");

export type Kont = ((x: any) => any) | [Var, Exp, RuntimeEnv, Kont]
export type State = [Exp, RuntimeEnv, Kont];
export class Closure {
    constructor(public fn: Fn, public r: RuntimeEnv) { }
}

const boolify = (x: any) => x !== NIL || !!x;

export function inject(e: Exp, r: RuntimeEnv): State {
    return [e, r, (x: any) => console.log(x)];
}

export function step(s: State): State {
    return (s[0] as any)[STEP](s[1], s[2]);
}

(Lit.prototype as any)[AEXP] = function(this: Lit, r: RuntimeEnv) {
    return this.value;
};

(VarRef.prototype as any)[AEXP] = function(this: VarRef, r: RuntimeEnv) {
    return r.lookup(this.v.name);
};

(Fn.prototype as any)[AEXP] = function(this: Fn, v: Var, r: RuntimeEnv) {
    return new Closure(this, r);
};

(AExp.prototype as any)[STEP] = function(this: Lit, r: RuntimeEnv, k: Kont): State {
    return applyKont(k, (this as any)[AEXP](r, k), r) as State
};

(Let0.prototype as any)[STEP] = function(this: Let0, r: RuntimeEnv, k: Kont): State {
    return [this.exp, r, [this.v, this.body, r, k]];
};

(App.prototype as any)[STEP] = function(this: App, r: RuntimeEnv, k: Kont) {
    return applyProc((this.fn as any)[AEXP](r), this.args.map((x: any) => x[AEXP](r)), r, k)
};

(PApp.prototype as any)[STEP] = function(this: PApp, r: RuntimeEnv, k: Kont) {
    return applyKont(k, this.fn.fn.apply(null, this.args.map((x: any) => x[AEXP](r))), r);
};

(If.prototype as any)[STEP] = function(this: If, r: RuntimeEnv, k: Kont) {
    if(boolify((this.test as any)[AEXP](r)))
        return [this.truePart, r, k]
    return [this.falsePart, r, k];
};

(SetQ.prototype as any)[STEP] = function(this: SetQ, r: RuntimeEnv, k: Kont) {
    return applyKont(k, null, r)
};

(CallCC.prototype as any)[STEP] = function(this: CallCC, r: RuntimeEnv, k: Kont) {
    let proc = (this.e as any)[AEXP](r);
    return applyProc(proc, [new Lit(k)], r, k);
};

function applyKont(k: Kont, value: any, r: RuntimeEnv): State{
    if(k instanceof Function) {
        k(value);
        return undefined!;
    }
    let [v0, e0, r0, k0] = k;
    return [e0, r0.extend(v0.name, value), k0];
}

function applyProc(v: Closure, vs: any[], r: RuntimeEnv, k: Kont): State  {
    let r2 = new RuntimeEnv(r);
    for(let i=0; i<v.fn.a.length; i++)
        r2.vars[v.fn.a[i].name] = vs[i];
    return [v.fn.body, r2, k];
}