stg.bend source
stg.bend on the hub · documented module
import Base# Tiny STG-like machine in Bend: heap-allocated thunks (SLet), explicit# update frames (KUpd writes the forced value back, so sharing is real),# de Bruijn env + Nat heap addresses (positional, never compared for# equality -- everything dispatches structurally). ONE fuel-stepped def# (s_run); pure helpers (s_len/s_nth/s_upd) do the heap walks. Parallel# from the start: SAdd evaluates both sides as a parallel pair over copies# of the heap (heap effects inside arithmetic are dropped -- the result is# pure, so this is sound), s_batch runs whole machines in parallel,# s_batch_gpu is the same runner handed to the GPU with `!`.type SExp is Data: SVar{i: U32} SLit{v: Nat} SAdd{a: SExp, b: SExp} SLet{b: SExp, e: SExp} SApp{f: SExp, x: SExp} SCase{e: SExp, z: SExp, s: SExp}type SVal is Data: VNum{v: Nat} VAddr{a: Nat} VClos{body: SExp, env: List<&2, SVal>} VThunk{body: SExp, env: List<&2, SVal>}type SK is Data: KDone{} KAddR{a: SVal, k: SK} KAppA{x: SExp, env: List<&2, SVal>, k: SK} KCaseK{z: SExp, s: SExp, env: List<&2, SVal>, k: SK} KUpd{a: Nat, k: SK}type STask is Data: SEval{e: SExp, env: List<&2, SVal>, heap: List<&2, SVal>, k: SK} SRet{k: SK, v: SVal, heap: List<&2, SVal>} SLook{n: Nat, env: List<&2, SVal>, heap: List<&2, SVal>, k: SK} SLoad{cur: Nat, orig: Nat, rest: List<&2, SVal>, full: List<&2, SVal>, k: SK}def s_len(+h: List<&2, SVal>) -> Nat: match h: case Nil{}: 0n case Con{v, vs}: 1n+s_len(vs)def s_nth(+a: Nat, +h: List<&2, SVal>) -> SVal: match a h: case 0n Con{v, vs}: v case 1n+m Con{v, vs}: s_nth(m, vs) case _ _: VNum{0n}def s_upd(+a: Nat, +v: SVal, +h: List<&2, SVal>) -> List<&2, SVal>: match a h: case 0n Con{w, ws}: Con{v, ws} case 1n+m Con{w, ws}: Con{w, s_upd(m, v, ws)} case _ _: hdef s_num_add(+a: SVal, +b: SVal) -> SVal: match a b: case VNum{x} VNum{y}: VNum{Nat.add(x, y)} case _ _: VNum{0n}def s_run(+f: Nat, +t: STask) -> SVal: match f: case 0n: VNum{0n} case 1n+p: match t: case SEval{e, env, heap, k}: match e: case SVar{i}: s_run(p, SLook{U32.to_nat(i), env, heap, k}) case SLit{v}: s_run(p, SRet{k, VNum{v}, heap}) case SAdd{a, b}: ah bh = s_run(p, SEval{a, env, heap, KDone{}}) s_run(p, SEval{b, env, heap, KDone{}}) s_num_add(ah, bh) case SLet{b, e2}: addr = s_len(heap) heap2 = List.append(&2, SVal, heap, Con{VThunk{b, env}, Nil{}}) s_run(p, SEval{e2, Con{VAddr{addr}, env}, heap2, k}) case SApp{f, x}: s_run(p, SEval{f, env, heap, KAppA{x, env, k}}) case SCase{e2, z, s}: s_run(p, SEval{e2, env, heap, KCaseK{z, s, env, k}}) case SRet{k, v, heap}: match k: case KDone{}: v case KAddR{a, k2}: s_num_add(a, v) case KAppA{x, env, k2}: match v: case VClos{body, cenv}: s_run(p, SEval{body, Con{VThunk{x, env}, cenv}, heap, k2}) case VThunk{body, eenv}: s_run(p, SEval{body, eenv, heap, KAppA{x, env, k2}}) case _: s_run(p, SRet{k2, VNum{0n}, heap}) case KCaseK{z, s, env, k2}: match v: case VNum{n}: match n: case 0n: s_run(p, SEval{z, env, heap, k2}) case 1n+m: s_run(p, SEval{s, Con{VNum{m}, env}, heap, k2}) case _: s_run(p, SRet{k2, VNum{0n}, heap}) case KUpd{a, k2}: s_run(p, SRet{k2, v, s_upd(a, v, heap)}) case SLook{n, env, heap, k}: match n env: case 0n Con{v, vs}: match v: case VAddr{a}: s_run(p, SLoad{a, a, heap, heap, k}) case VThunk{body, eenv}: s_run(p, SEval{body, eenv, heap, k}) case _: s_run(p, SRet{k, v, heap}) case 1n+m Con{v, vs}: s_run(p, SLook{m, vs, heap, k}) case _ _: s_run(p, SRet{k, VNum{0n}, heap}) case SLoad{cur, orig, rest, full, k}: match cur rest: case 0n Con{v, vs}: match v: case VThunk{body, eenv}: s_run(p, SEval{body, eenv, full, KUpd{orig, k}}) case _: s_run(p, SRet{k, v, full}) case 1n+m Con{v, vs}: s_run(p, SLoad{m, orig, vs, full, k}) case _ _: s_run(p, SRet{k, VNum{0n}, full})def s_eval(+f: Nat, +e: SExp) -> SVal: s_run(f, SEval{e, Nil{}, Nil{}, KDone{}})def s_batch(+f: Nat, +es: List<&2, SExp>) -> List<&2, SVal>: match es: case Nil{}: Nil{} case Con{h, t}: r rs = s_eval(f, h) s_batch(f, t) Con{r, rs}def s_batch_gpu(+f: Nat, +es: List<&2, SExp>) -> List<&2, SVal>: s_batch!(f, es)def main() -> List<&2, SVal>: s_batch(30n, [SLit{5n}, SAdd{SLit{2n}, SLit{3n}}, SLet{SLit{42n}, SAdd{SVar{0}, SVar{0}}}])