Last active
February 11, 2020 18:45
-
-
Save mseddon/5d5ae57e266f4df0f4a8557448909d11 to your computer and use it in GitHub Desktop.
Scarab-∞ CESK core
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 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]; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment