tiny.pluck.runtime

1pub const runtime = @import("runtime.zig");

1const std = @import("std");2const Allocator = std.mem.Allocator;3const pexpr = @import("pexpr.zig");4const PExpr = pexpr.PExpr;5const Symbol = pexpr.Symbol;6const bdd = @import("bdd.zig");7const Bdd = bdd.Bdd;89pub const Env = union(enum) {10    cons: *EnvCons,11    nil: void,1213    const Self = @This();1415    pub const empty: Self = .nil;1617    pub fn get(self: Self, name: Symbol) ?*RuntimeValue {18        return switch (self) {19            .cons => |c| c.get(name),20            .nil => null,21        };22    }2324    pub fn tail(self: Self) ?Self {25        return switch (self) {26            .cons => |c| c.tail,27            .nil => null,28        };29    }3031    pub fn first(self: Self) ?*RuntimeValue {32        return switch (self) {33            .cons => |c| c.val,34            .nil => null,35        };36    }3738    pub fn firstName(self: Self) ?Symbol {39        return switch (self) {40            .cons => |c| c.name,41            .nil => null,42        };43    }4445    pub fn isEmpty(self: Self) bool {46        return self == .nil;47    }4849    pub fn len(self: Self) usize {50        return switch (self) {51            .cons => |c| 1 + c.tail.len(),52            .nil => 0,53        };54    }5556    pub fn extend(self: Self, allocator: Allocator, name: Symbol, val: *RuntimeValue) !Self {57        const cons = try allocator.create(EnvCons);58        cons.* = EnvCons{59            .name = name,60            .val = val,61            .tail = self,62        };63        return Self{ .cons = cons };64    }6566    pub fn deinit(self: Self, allocator: Allocator) void {67        switch (self) {68            .cons => |c| {69                c.tail.deinit(allocator);70                allocator.destroy(c);71            },72            .nil => {},73        }74    }7576    pub fn parseEnv(self: Self, allocator: Allocator) ![]Symbol {77        var names: std.ArrayList(Symbol) = .empty;78        errdefer names.deinit(allocator);7980        var current = self;81        while (current != .nil) {82            const cons = current.cons;83            try names.append(allocator, cons.name);84            current = cons.tail;85        }86        return names.toOwnedSlice(allocator);87    }8889    pub fn format(90        self: Self,91        comptime fmt: []const u8,92        options: std.fmt.Options,93        writer: anytype,94    ) !void {95        _ = fmt;96        _ = options;97        try writer.writeAll("[");98        var current = self;99        var first_item = true;100        while (current != .nil) {101            if (!first_item) try writer.writeAll(", ");102            const cons = current.cons;103            try writer.print("{s}={}", .{ cons.name, cons.val });104            current = cons.tail;105            first_item = false;106        }107        try writer.writeAll("]");108    }109110    pub fn eql(self: Self, other: Self) bool {111        var a = self;112        var b = other;113        while (true) {114            switch (a) {115                .nil => return b == .nil,116                .cons => |ac| {117                    switch (b) {118                        .nil => return false,119                        .cons => |bc| {120                            if (!std.mem.eql(u8, ac.name, bc.name)) return false;121                            if (!ac.val.eql(bc.val)) return false;122                            a = ac.tail;123                            b = bc.tail;124                        },125                    }126                },127            }128        }129    }130131    pub fn hash(self: Self) u64 {132        var h = std.hash.Wyhash.init(0);133        var current = self;134        while (current != .nil) {135            const cons = current.cons;136            h.update(cons.name);137            h.update(std.mem.asBytes(&cons.val.hash()));138            current = cons.tail;139        }140        return h.final();141    }142};143144pub const EnvCons = struct {145    name: Symbol,146    val: *RuntimeValue,147    tail: Env,148149    pub fn get(self: *EnvCons, name: Symbol) ?*RuntimeValue {150        if (std.mem.eql(u8, self.name, name)) {151            return self.val;152        }153        return self.tail.get(name);154    }155};156157pub const IntDist = struct {158    bits: []Bdd,159160    pub fn init(bits: []Bdd) IntDist {161        return IntDist{ .bits = bits };162    }163164    pub fn eql(self: IntDist, other: IntDist, manager: *@import("bdd.zig").Manager) Allocator.Error!Bdd {165        if (self.bits.len != other.bits.len) {166            return Bdd.FALSE;167        }168        var result = Bdd.TRUE;169        for (self.bits, other.bits) |a, b| {170            result = try manager.bddAnd(result, try manager.bddIff(a, b));171            if (result.isFalse()) {172                return Bdd.FALSE;173            }174        }175        return result;176    }177178    pub fn format(179        self: IntDist,180        comptime fmt: []const u8,181        options: std.fmt.Options,182        writer: anytype,183    ) !void {184        _ = fmt;185        _ = options;186        try writer.print("IntDist{{{d}}}", .{self.bits.len});187    }188};189190pub const NativeValueData = union(enum) {191    int: i64,192    float: f64,193    symbol: Symbol,194    bool_val: bool,195    pexpr: *PExpr,196    int_dist: IntDist,197198    pub fn eql(self: NativeValueData, other: NativeValueData) bool {199        if (@as(std.meta.Tag(NativeValueData), self) != @as(std.meta.Tag(NativeValueData), other)) {200            return false;201        }202        return switch (self) {203            .int => |i| i == other.int,204            .float => |f| f == other.float,205            .symbol => |s| std.mem.eql(u8, s, other.symbol),206            .bool_val => |b| b == other.bool_val,207            .pexpr => |p| p == other.pexpr,208            .int_dist => |d| {209                if (d.bits.len != other.int_dist.bits.len) return false;210                for (d.bits, other.int_dist.bits) |a, b| {211                    if (a.toRaw() != b.toRaw()) return false;212                }213                return true;214            },215        };216    }217218    pub fn hash(self: NativeValueData) u64 {219        var h = std.hash.Wyhash.init(0);220        h.update(std.mem.asBytes(&@as(u8, @backingInt(self))));221        switch (self) {222            .int => |i| h.update(std.mem.asBytes(&i)),223            .float => |f| h.update(std.mem.asBytes(&f)),224            .symbol => |s| h.update(s),225            .bool_val => |b| h.update(std.mem.asBytes(&b)),226            .pexpr => |p| h.update(std.mem.asBytes(&@intFromPtr(p))),227            .int_dist => |d| {228                for (d.bits) |bit| {229                    h.update(std.mem.asBytes(&bit.toRaw()));230                }231            },232        }233        return h.final();234    }235236    pub fn format(237        self: NativeValueData,238        comptime fmt: []const u8,239        options: std.fmt.Options,240        writer: anytype,241    ) !void {242        _ = fmt;243        _ = options;244        switch (self) {245            .int => |i| try writer.print("{d}", .{i}),246            .float => |f| try writer.print("{d}", .{f}),247            .symbol => |s| try writer.print("'{s}", .{s}),248            .bool_val => |b| try writer.print("{}", .{b}),249            .pexpr => |p| try writer.print("{}", .{p}),250            .int_dist => |d| try writer.print("{}", .{d}),251        }252    }253};254255pub const ConstructedValue = struct {256    constructor: Symbol,257    args: []*RuntimeValue,258259    pub fn eql(self: ConstructedValue, other: ConstructedValue) bool {260        if (!std.mem.eql(u8, self.constructor, other.constructor)) return false;261        if (self.args.len != other.args.len) return false;262        for (self.args, other.args) |a, b| {263            if (!a.eql(b)) return false;264        }265        return true;266    }267268    pub fn hash(self: ConstructedValue) u64 {269        var h = std.hash.Wyhash.init(0);270        h.update(self.constructor);271        for (self.args) |arg| {272            h.update(std.mem.asBytes(&arg.hash()));273        }274        return h.final();275    }276};277278pub const RuntimeValue = struct {279    data: Data,280281    pub const Data = union(enum) {282        native: NativeValueData,283        constructed: ConstructedValue,284        closure: *Closure,285        lazy_kc_thunk: *LazyKCThunk,286        lazy_kc_thunk_union: *LazyKCThunkUnion,287        lazy_enum_thunk: *LazyEnumeratorThunk,288    };289290    const Self = @This();291292    pub fn initNative(allocator: Allocator, native: NativeValueData) !*Self {293        const val = try allocator.create(Self);294        val.* = Self{ .data = .{ .native = native } };295        return val;296    }297298    pub fn initConstructed(allocator: Allocator, constructor: Symbol, args: []*Self) !*Self {299        const val = try allocator.create(Self);300        val.* = Self{ .data = .{ .constructed = .{ .constructor = constructor, .args = args } } };301        return val;302    }303304    pub fn initTrue(allocator: Allocator) !*Self {305        return initConstructed(allocator, "True", &[_]*Self{});306    }307308    pub fn initFalse(allocator: Allocator) !*Self {309        return initConstructed(allocator, "False", &[_]*Self{});310    }311312    pub fn initUnit(allocator: Allocator) !*Self {313        return initConstructed(allocator, "Unit", &[_]*Self{});314    }315316    pub fn initClosure(allocator: Allocator, closure: *Closure) !*Self {317        const val = try allocator.create(Self);318        val.* = Self{ .data = .{ .closure = closure } };319        return val;320    }321322    pub fn initLazyKCThunk(allocator: Allocator, thunk: *LazyKCThunk) !*Self {323        const val = try allocator.create(Self);324        val.* = Self{ .data = .{ .lazy_kc_thunk = thunk } };325        return val;326    }327328    pub fn initLazyKCThunkUnion(allocator: Allocator, thunk_union: *LazyKCThunkUnion) !*Self {329        const val = try allocator.create(Self);330        val.* = Self{ .data = .{ .lazy_kc_thunk_union = thunk_union } };331        return val;332    }333334    pub fn deinit(self: *Self, allocator: Allocator) void {335        switch (self.data) {336            .constructed => |c| {337                for (c.args) |arg| {338                    arg.deinit(allocator);339                }340                allocator.free(c.args);341            },342            .closure => |cl| cl.deinit(allocator),343            .lazy_kc_thunk => |t| t.deinit(allocator),344            .lazy_kc_thunk_union => |t| t.deinit(allocator),345            .lazy_enum_thunk => |t| t.deinit(allocator),346            .native => |n| {347                switch (n) {348                    .int_dist => |d| allocator.free(d.bits),349                    else => {},350                }351            },352        }353        allocator.destroy(self);354    }355356    pub fn eql(self: *const Self, other: *const Self) bool {357        if (@as(std.meta.Tag(Data), self.data) != @as(std.meta.Tag(Data), other.data)) {358            return false;359        }360        return switch (self.data) {361            .native => |n| n.eql(other.data.native),362            .constructed => |c| c.eql(other.data.constructed),363            .closure => |cl| cl.eql(other.data.closure),364            .lazy_kc_thunk => |t| t == other.data.lazy_kc_thunk,365            .lazy_kc_thunk_union => |t| t == other.data.lazy_kc_thunk_union,366            .lazy_enum_thunk => |t| t == other.data.lazy_enum_thunk,367        };368    }369370    pub fn hash(self: *const Self) u64 {371        var h = std.hash.Wyhash.init(0);372        h.update(std.mem.asBytes(&@as(u8, @backingInt(self.data))));373        switch (self.data) {374            .native => |n| h.update(std.mem.asBytes(&n.hash())),375            .constructed => |c| h.update(std.mem.asBytes(&c.hash())),376            .closure => |cl| h.update(std.mem.asBytes(&cl.hash())),377            .lazy_kc_thunk => |t| h.update(std.mem.asBytes(&@intFromPtr(t))),378            .lazy_kc_thunk_union => |t| h.update(std.mem.asBytes(&@intFromPtr(t))),379            .lazy_enum_thunk => |t| h.update(std.mem.asBytes(&@intFromPtr(t))),380        }381        return h.final();382    }383384    pub fn isThunk(self: *const Self) bool {385        return switch (self.data) {386            .lazy_kc_thunk, .lazy_kc_thunk_union, .lazy_enum_thunk => true,387            else => false,388        };389    }390391    pub fn isTrue(self: *const Self) bool {392        return switch (self.data) {393            .constructed => |c| std.mem.eql(u8, c.constructor, "True") and c.args.len == 0,394            else => false,395        };396    }397398    pub fn isFalse(self: *const Self) bool {399        return switch (self.data) {400            .constructed => |c| std.mem.eql(u8, c.constructor, "False") and c.args.len == 0,401            else => false,402        };403    }404405    pub fn maybeIntDist(self: *const Self) ?IntDist {406        return switch (self.data) {407            .native => |n| switch (n) {408                .int_dist => |d| d,409                else => null,410            },411            else => null,412        };413    }414415    pub fn maybeNat(self: *const Self) ?i64 {416        switch (self.data) {417            .constructed => |c| {418                if (std.mem.eql(u8, c.constructor, "O") and c.args.len == 0) {419                    return 0;420                } else if (std.mem.eql(u8, c.constructor, "S") and c.args.len == 1) {421                    if (c.args[0].maybeNat()) |inner| {422                        return inner + 1;423                    }424                }425                return null;426            },427            .lazy_kc_thunk => |thunk| {428                switch (thunk.expr) {429                    .pexpr => |expr| return Self.maybeNatFromPExpr(expr),430                    .thunk => return null,431                }432            },433            else => return null,434        }435    }436437    fn maybeNatFromPExpr(expr: *const @import("pexpr.zig").PExpr) ?i64 {438        if (expr.head == .construct) {439            const constructor = expr.head.construct.constructor;440            if (std.mem.eql(u8, constructor, "O") and expr.args.len == 0) {441                return 0;442            } else if (std.mem.eql(u8, constructor, "S") and expr.args.len == 1) {443                return if (Self.maybeNatFromPExpr(expr.args[0])) |inner| inner + 1 else null;444            }445        }446        return null;447    }448449    pub fn maybeNatBounded(self: *const Self, max_value: i64) ?i64 {450        var current: *const Self = self;451        var count: i64 = 0;452        while (true) {453            switch (current.data) {454                .constructed => |c| {455                    if (std.mem.eql(u8, c.constructor, "O") and c.args.len == 0) {456                        return count;457                    } else if (std.mem.eql(u8, c.constructor, "S") and c.args.len == 1) {458                        count += 1;459                        if (count > max_value) {460                            return null;461                        }462                        current = c.args[0];463                    } else {464                        return null;465                    }466                },467                else => return null,468            }469        }470    }471472    pub fn maybeList(self: *const Self, allocator: Allocator) !?[]*Self {473        var items: std.ArrayList(*Self) = .empty;474        errdefer items.deinit(allocator);475476        var current = self;477        while (true) {478            switch (current.data) {479                .constructed => |c| {480                    if (std.mem.eql(u8, c.constructor, "Nil") and c.args.len == 0) {481                        const slice = try items.toOwnedSlice(allocator);482                        return slice;483                    } else if (std.mem.eql(u8, c.constructor, "Cons") and c.args.len == 2) {484                        try items.append(allocator, c.args[0]);485                        current = c.args[1];486                    } else {487                        items.deinit(allocator);488                        return null;489                    }490                },491                else => {492                    items.deinit(allocator);493                    return null;494                },495            }496        }497    }498499    pub fn maybePair(self: *const Self) ?struct { fst: *Self, snd: *Self } {500        switch (self.data) {501            .constructed => |c| {502                if (std.mem.eql(u8, c.constructor, "Pair") and c.args.len == 2) {503                    return .{ .fst = c.args[0], .snd = c.args[1] };504                }505                return null;506            },507            else => return null,508        }509    }510511    pub fn format(512        self: *const Self,513        comptime fmt: []const u8,514        options: std.fmt.Options,515        writer: anytype,516    ) !void {517        switch (self.data) {518            .native => |n| {519                switch (n) {520                    .int => |i| try writer.print("{d}", .{i}),521                    .float => |f| try writer.print("{d}", .{f}),522                    .symbol => |s| try writer.writeAll(s),523                    .bool_val => |b| try writer.writeAll(if (b) "True" else "False"),524                    .pexpr => |p| try writer.print("{any}", .{p}),525                    .int_dist => |d| try writer.print("IntDist({d} bits)", .{d.bits.len}),526                }527            },528            .constructed => |c| {529                if (self.maybeNat()) |n| {530                    try writer.print("{d}", .{n});531                    return;532                }533                if (std.mem.eql(u8, c.constructor, "True") and c.args.len == 0) {534                    try writer.writeAll("True");535                    return;536                }537                if (std.mem.eql(u8, c.constructor, "False") and c.args.len == 0) {538                    try writer.writeAll("False");539                    return;540                }541                if (std.mem.eql(u8, c.constructor, "Unit") and c.args.len == 0) {542                    try writer.writeAll("()");543                    return;544                }545                try writer.print("({s}", .{c.constructor});546                for (c.args) |arg| {547                    try writer.writeAll(" ");548                    try arg.format(fmt, options, writer);549                }550                try writer.writeAll(")");551            },552            .closure => |cl| try writer.print("{any}", .{cl}),553            .lazy_kc_thunk => |t| try writer.print("LazyKCThunk({any})", .{t.expr}),554            .lazy_kc_thunk_union => |t| try t.format(fmt, options, writer),555            .lazy_enum_thunk => |t| try writer.print("LazyEnumThunk(id={d})", .{t.id}),556        }557    }558};559560pub const FromValueResult = struct {561    value: ConvertedValue,562    concrete: bool,563};564565pub const ConvertedValue = union(enum) {566    bool_val: bool,567    int: i64,568    unit: void,569    list: []*RuntimeValue,570    pair: struct { fst: *RuntimeValue, snd: *RuntimeValue },571    original: *RuntimeValue,572};573574pub fn fromValue(val: *RuntimeValue) FromValueResult {575    switch (val.data) {576        .constructed => |c| {577            if (std.mem.eql(u8, c.constructor, "True") and c.args.len == 0) {578                return .{ .value = .{ .bool_val = true }, .concrete = true };579            }580            if (std.mem.eql(u8, c.constructor, "False") and c.args.len == 0) {581                return .{ .value = .{ .bool_val = false }, .concrete = true };582            }583            if (std.mem.eql(u8, c.constructor, "Unit") and c.args.len == 0) {584                return .{ .value = .unit, .concrete = true };585            }586            if (val.maybeNat()) |n| {587                return .{ .value = .{ .int = n }, .concrete = true };588            }589            if (std.mem.eql(u8, c.constructor, "Pair") and c.args.len == 2) {590                const fst_result = fromValue(c.args[0]);591                const snd_result = fromValue(c.args[1]);592                if (fst_result.concrete and snd_result.concrete) {593                    return .{ .value = .{ .pair = .{ .fst = c.args[0], .snd = c.args[1] } }, .concrete = true };594                }595                return .{ .value = .{ .original = val }, .concrete = false };596            }597            if (std.mem.eql(u8, c.constructor, "Nil") and c.args.len == 0) {598                return .{ .value = .{ .original = val }, .concrete = true };599            }600            if (std.mem.eql(u8, c.constructor, "Cons") and c.args.len == 2) {601                var concrete = true;602                var current: *RuntimeValue = val;603                while (true) {604                    switch (current.data) {605                        .constructed => |inner| {606                            if (std.mem.eql(u8, inner.constructor, "Nil") and inner.args.len == 0) {607                                break;608                            } else if (std.mem.eql(u8, inner.constructor, "Cons") and inner.args.len == 2) {609                                if (inner.args[0].isThunk()) {610                                    concrete = false;611                                    break;612                                }613                                current = inner.args[1];614                            } else {615                                break;616                            }617                        },618                        else => {619                            concrete = current.isThunk() == false;620                            break;621                        },622                    }623                }624                return .{ .value = .{ .original = val }, .concrete = concrete };625            }626            for (c.args) |arg| {627                if (arg.isThunk()) {628                    return .{ .value = .{ .original = val }, .concrete = false };629                }630            }631            return .{ .value = .{ .original = val }, .concrete = true };632        },633        .native => return .{ .value = .{ .original = val }, .concrete = true },634        .closure => return .{ .value = .{ .original = val }, .concrete = true },635        .lazy_kc_thunk, .lazy_kc_thunk_union, .lazy_enum_thunk => {636            return .{ .value = .{ .original = val }, .concrete = false };637        },638    }639}640641pub fn pluckNat(allocator: Allocator, n: i64) !*RuntimeValue {642    if (n <= 0) {643        return RuntimeValue.initConstructed(allocator, "O", &[_]*RuntimeValue{});644    }645    const pred = try pluckNat(allocator, n - 1);646    errdefer pred.deinit(allocator);647    const args = try allocator.alloc(*RuntimeValue, 1);648    args[0] = pred;649    return RuntimeValue.initConstructed(allocator, "S", args);650}651652pub fn pluckList(allocator: Allocator, items: []*RuntimeValue) !*RuntimeValue {653    var result = try RuntimeValue.initConstructed(allocator, "Nil", &[_]*RuntimeValue{});654    var i = items.len;655    while (i > 0) {656        i -= 1;657        const args = try allocator.alloc(*RuntimeValue, 2);658        args[0] = items[i];659        args[1] = result;660        result = try RuntimeValue.initConstructed(allocator, "Cons", args);661    }662    return result;663}664665pub const Closure = struct {666    expr: ClosureExpr,667    env: Env,668    name: Symbol,669670    pub const ClosureExpr = union(enum) {671        pexpr: *PExpr,672        thunk: *RuntimeValue,673    };674675    const Self = @This();676677    pub fn init(allocator: Allocator, expr: *PExpr, env: Env, name: Symbol) !*Self {678        const closure = try allocator.create(Self);679        closure.* = Self{680            .expr = .{ .pexpr = expr },681            .env = env,682            .name = name,683        };684        return closure;685    }686687    pub fn initWithThunk(allocator: Allocator, thunk: *RuntimeValue, env: Env, name: Symbol) !*Self {688        const closure = try allocator.create(Self);689        closure.* = Self{690            .expr = .{ .thunk = thunk },691            .env = env,692            .name = name,693        };694        return closure;695    }696697    pub fn makeSelfLoop(698        allocator: Allocator,699        body: *PExpr,700        env: Env,701        rec_name: Symbol,702        nonrec_name: Symbol,703    ) !*Self {704        const closure = try allocator.create(Self);705        errdefer allocator.destroy(closure);706707        const closure_val = try allocator.create(RuntimeValue);708        errdefer allocator.destroy(closure_val);709        closure_val.* = RuntimeValue{ .data = .{ .closure = closure } };710711        const new_env = try env.extend(allocator, rec_name, closure_val);712        errdefer new_env.deinit(allocator);713714        closure.* = Self{715            .expr = .{ .pexpr = body },716            .env = new_env,717            .name = nonrec_name,718        };719720        return closure;721    }722723    pub fn isSelfLoop(self: *const Self) bool {724        if (self.env.isEmpty()) return false;725        if (self.env.first()) |first_val| {726            if (first_val.data == .closure) {727                return first_val.data.closure == self;728            }729        }730        return false;731    }732733    pub fn deinit(self: *Self, allocator: Allocator) void {734        if (!self.isSelfLoop()) {735            self.env.deinit(allocator);736        }737        allocator.destroy(self);738    }739740    pub fn eql(self: *const Self, other: *const Self) bool {741        if (!std.mem.eql(u8, self.name, other.name)) return false;742        switch (self.expr) {743            .pexpr => |p| {744                if (other.expr != .pexpr) return false;745                if (p != other.expr.pexpr) return false;746            },747            .thunk => |t| {748                if (other.expr != .thunk) return false;749                if (t != other.expr.thunk) return false;750            },751        }752        if (self.isSelfLoop() and other.isSelfLoop()) {753            const self_tail = self.env.tail() orelse return true;754            const other_tail = other.env.tail() orelse return true;755            return self_tail.eql(other_tail);756        }757        return self.env.eql(other.env);758    }759760    pub fn hash(self: *const Self) u64 {761        var h = std.hash.Wyhash.init(0);762        switch (self.expr) {763            .pexpr => |p| h.update(std.mem.asBytes(&@intFromPtr(p))),764            .thunk => |t| h.update(std.mem.asBytes(&@intFromPtr(t))),765        }766        h.update(self.name);767        h.update(std.mem.asBytes(&self.env.len()));768        return h.final();769    }770771    pub fn format(772        self: *const Self,773        comptime fmt: []const u8,774        options: std.fmt.Options,775        writer: anytype,776    ) !void {777        _ = fmt;778        _ = options;779        try writer.print("Closure((λ{s} -> ", .{self.name});780        switch (self.expr) {781            .pexpr => |p| try writer.print("{}", .{p}),782            .thunk => try writer.writeAll("<thunk>"),783        }784        try writer.writeAll("), env=[");785786        var env = self.env;787        var first_item = true;788        while (env != .nil) {789            if (!first_item) try writer.writeAll(", ");790            const cons = env.cons;791            if (cons.val.data == .closure and cons.val.data.closure == self) {792                try writer.writeAll("[recursive]");793            } else {794                try writer.print("{}", .{cons.val});795            }796            env = cons.tail;797            first_item = false;798        }799        try writer.writeAll("])");800    }801};802803pub const Callstack = []const i32;804805pub const GuardedWorld = struct {806    value: *RuntimeValue,807    guard: Bdd,808};809810pub const GuardedWorlds = struct {811    worlds: []GuardedWorld,812    validity_guard: Bdd,813};814815pub const RuntimeValueContext = struct {816    pub fn hash(_: RuntimeValueContext, key: *RuntimeValue) u64 {817        return key.hash();818    }819820    pub fn eql(_: RuntimeValueContext, a: *RuntimeValue, b: *RuntimeValue) bool {821        return a.eql(b);822    }823};824825pub const NestedWorld = struct {826    result: GuardedWorlds,827    guard: Bdd,828};829830pub const LazyKCThunk = struct {831    expr: ThunkExpr,832    env: Env,833    cache: std.ArrayList(GuardedWorlds),834    callstack: []i32,835    strict_order_index: i32,836    allocator: Allocator,837838    pub const ThunkExpr = union(enum) {839        pexpr: *PExpr,840        thunk: *LazyKCThunk,841    };842843    const Self = @This();844845    pub fn init(846        allocator: Allocator,847        expr: *PExpr,848        env: Env,849        strict_order_index: i32,850        callstack: []const i32,851    ) !*Self {852        if (expr.head == .var_ref) {853            if (env.get(expr.head.var_ref.name)) |val| {854                if (val.data == .lazy_kc_thunk) {855                    return val.data.lazy_kc_thunk;856                }857            }858        }859860        const thunk = try allocator.create(Self);861        errdefer allocator.destroy(thunk);862863        const callstack_copy = try allocator.dupe(i32, callstack);864        errdefer allocator.free(callstack_copy);865866        thunk.* = Self{867            .expr = .{ .pexpr = expr },868            .env = env,869            .cache = .empty,870            .callstack = callstack_copy,871            .strict_order_index = strict_order_index,872            .allocator = allocator,873        };874        return thunk;875    }876877    pub fn deinit(self: *Self, allocator: Allocator) void {878        allocator.free(self.callstack);879        for (self.cache.items) |gw| {880            allocator.free(gw.worlds);881        }882        self.cache.deinit(allocator);883        allocator.destroy(self);884    }885886    pub fn deinitWithEnv(self: *Self, allocator: Allocator) void {887        self.env.deinit(allocator);888        self.deinit(allocator);889    }890891    pub fn format(892        self: *const Self,893        comptime fmt: []const u8,894        options: std.fmt.Options,895        writer: anytype,896    ) !void {897        try writer.writeAll("LazyKCThunk(");898        switch (self.expr) {899            .pexpr => |p| try p.format(fmt, options, writer),900            .thunk => try writer.writeAll("<nested-thunk>"),901        }902        try writer.writeAll(")");903    }904};905906pub const LazyKCThunkUnion = struct {907    thunks: []ThunkGuard,908    allocator: Allocator,909910    pub const ThunkGuard = struct {911        thunk: *LazyKCThunk,912        guard: Bdd,913    };914915    const Self = @This();916917    pub const ThunkInput = struct {918        value: *RuntimeValue,919        outer_guard: Bdd,920    };921922    pub fn init(allocator: Allocator, manager: *bdd.Manager, worlds: []const ThunkInput) !*Self {923        var uniq_thunks: std.ArrayList(*LazyKCThunk) = .empty;924        defer uniq_thunks.deinit(allocator);925        var uniq_guards: std.ArrayList(Bdd) = .empty;926        defer uniq_guards.deinit(allocator);927        var thunk_indices = std.AutoHashMap(*LazyKCThunk, usize).init(allocator);928        defer thunk_indices.deinit();929930        for (worlds) |input| {931            switch (input.value.data) {932                .lazy_kc_thunk_union => |union_thunk| {933                    for (union_thunk.thunks) |inner| {934                        const combined_guard = try manager.bddAnd(inner.guard, input.outer_guard);935                        if (thunk_indices.get(inner.thunk)) |idx| {936                            uniq_guards.items[idx] = try manager.bddOr(uniq_guards.items[idx], combined_guard);937                        } else {938                            try thunk_indices.put(inner.thunk, uniq_thunks.items.len);939                            try uniq_thunks.append(allocator, inner.thunk);940                            try uniq_guards.append(allocator, combined_guard);941                        }942                    }943                },944                .lazy_kc_thunk => |thunk| {945                    if (thunk_indices.get(thunk)) |idx| {946                        uniq_guards.items[idx] = try manager.bddOr(uniq_guards.items[idx], input.outer_guard);947                    } else {948                        try thunk_indices.put(thunk, uniq_thunks.items.len);949                        try uniq_thunks.append(allocator, thunk);950                        try uniq_guards.append(allocator, input.outer_guard);951                    }952                },953                else => {954                    return error.InvalidThunkUnion;955                },956            }957        }958959        const result = try allocator.create(Self);960        errdefer allocator.destroy(result);961962        const thunks = try allocator.alloc(ThunkGuard, uniq_thunks.items.len);963        for (thunks, uniq_thunks.items, uniq_guards.items) |*t, thunk, guard| {964            t.* = .{ .thunk = thunk, .guard = guard };965        }966967        result.* = Self{968            .thunks = thunks,969            .allocator = allocator,970        };971        return result;972    }973974    pub fn deinit(self: *Self, allocator: Allocator) void {975        allocator.free(self.thunks);976        allocator.destroy(self);977    }978979    pub fn format(980        self: *const Self,981        comptime fmt: []const u8,982        options: std.fmt.Options,983        writer: anytype,984    ) !void {985        try writer.print("LazyKCThunkUnion{{{d}}}(", .{self.thunks.len});986        for (self.thunks, 0..) |tg, i| {987            try tg.thunk.format(fmt, options, writer);988            if (i < self.thunks.len - 1) {989                try writer.writeAll(" | ");990            }991        }992        try writer.writeAll(")");993    }994};995996pub const LazyEnumeratorThunk = struct {997    expr: *PExpr,998    env: Env,999    callstack: []i32,1000    strict_order_index: i32,1001    id: u32,10021003    const Self = @This();10041005    pub fn init(1006        allocator: Allocator,1007        expr: *PExpr,1008        env: Env,1009        callstack: []const i32,1010        strict_order_index: i32,1011        next_id: *u32,1012    ) !*Self {1013        if (expr.head == .var_ref) {1014            if (env.get(expr.head.var_ref.name)) |val| {1015                if (val.data == .lazy_enum_thunk) {1016                    return val.data.lazy_enum_thunk;1017                }1018            }1019        }10201021        const thunk = try allocator.create(Self);1022        errdefer allocator.destroy(thunk);10231024        const callstack_copy = try allocator.dupe(i32, callstack);1025        errdefer allocator.free(callstack_copy);10261027        const id = next_id.*;1028        next_id.* += 1;10291030        thunk.* = Self{1031            .expr = expr,1032            .env = env,1033            .callstack = callstack_copy,1034            .strict_order_index = strict_order_index,1035            .id = id,1036        };1037        return thunk;1038    }10391040    pub fn deinit(self: *Self, allocator: Allocator) void {1041        allocator.free(self.callstack);1042        allocator.destroy(self);1043    }10441045    pub fn deinitWithEnv(self: *Self, allocator: Allocator) void {1046        self.env.deinit(allocator);1047        self.deinit(allocator);1048    }10491050    pub fn format(1051        self: *const Self,1052        comptime fmt: []const u8,1053        options: std.fmt.Options,1054        writer: anytype,1055    ) !void {1056        _ = fmt;1057        _ = options;1058        try writer.print("LazyEnumeratorThunk(id={d}, {})", .{ self.id, self.expr });1059    }1060};10611062pub const StateVars = struct {1063    initial_fuel: i64,1064    remaining_fuel: i64,10651066    const Self = @This();10671068    pub fn init() Self {1069        return Self{ .initial_fuel = 0, .remaining_fuel = 0 };1070    }10711072    pub fn initWithFuel(fuel: i64) Self {1073        return Self{ .initial_fuel = fuel, .remaining_fuel = fuel };1074    }10751076    pub fn exhausted(self: *const Self) bool {1077        return self.initial_fuel > 0 and self.remaining_fuel <= 0;1078    }10791080    pub fn consumeFuel(self: *Self) bool {1081        if (self.initial_fuel == 0) {1082            return true;1083        }1084        if (self.remaining_fuel > 0) {1085            self.remaining_fuel -= 1;1086            return true;1087        }1088        return false;1089    }10901091    pub fn reset(self: *Self) void {1092        self.remaining_fuel = self.initial_fuel;1093    }1094};10951096pub const ThunkPath = []const usize;10971098pub fn findFirstThunk(allocator: Allocator, val: *RuntimeValue) !?[]usize {1099    var path: std.ArrayList(usize) = .empty;1100    errdefer path.deinit(allocator);11011102    if (try findFirstThunkInto(allocator, val, &path)) {1103        const slice = try path.toOwnedSlice(allocator);1104        return slice;1105    }1106    path.deinit(allocator);1107    return null;1108}11091110pub fn findFirstThunkInto(allocator: Allocator, val: *RuntimeValue, path: *std.ArrayList(usize)) !bool {1111    path.clearRetainingCapacity();1112    return findFirstThunkInner(allocator, val, path);1113}11141115fn findFirstThunkInner(allocator: Allocator, val: *RuntimeValue, path: *std.ArrayList(usize)) !bool {1116    switch (val.data) {1117        .lazy_kc_thunk, .lazy_kc_thunk_union, .lazy_enum_thunk => {1118            return true;1119        },1120        .constructed => |c| {1121            for (c.args, 0..) |arg, i| {1122                try path.append(allocator, i);1123                if (try findFirstThunkInner(allocator, arg, path)) {1124                    return true;1125                }1126                _ = path.pop();1127            }1128        },1129        .native => |n| {1130            if (n == .pexpr) {}1131        },1132        .closure => {},1133    }1134    return false;1135}11361137pub fn getValueAtPath(val: *RuntimeValue, path: []const usize) ?*RuntimeValue {1138    if (path.len == 0) return val;11391140    switch (val.data) {1141        .constructed => |c| {1142            if (path[0] >= c.args.len) return null;1143            return getValueAtPath(c.args[path[0]], path[1..]);1144        },1145        else => return null,1146    }1147}11481149pub fn replaceAtPath(1150    allocator: Allocator,1151    val: *RuntimeValue,1152    path: []const usize,1153    new_val: *RuntimeValue,1154) !*RuntimeValue {1155    if (path.len == 0) return new_val;11561157    switch (val.data) {1158        .constructed => |c| {1159            const new_args = try allocator.alloc(*RuntimeValue, c.args.len);1160            errdefer allocator.free(new_args);1161            @memcpy(new_args, c.args);11621163            if (path[0] < c.args.len) {1164                new_args[path[0]] = try replaceAtPath(allocator, c.args[path[0]], path[1..], new_val);1165            }11661167            return RuntimeValue.initConstructed(allocator, c.constructor, new_args);1168        },1169        else => return val,1170    }1171}11721173test "empty environment" {1174    const env = Env.empty;1175    try std.testing.expect(env.isEmpty());1176    try std.testing.expectEqual(@as(usize, 0), env.len());1177    try std.testing.expectEqual(@as(?*RuntimeValue, null), env.get("x"));1178}11791180test "environment extension and lookup" {1181    const allocator = std.testing.allocator;11821183    const val = try RuntimeValue.initNative(allocator, .{ .int = 42 });1184    defer val.deinit(allocator);11851186    var env = Env.empty;1187    env = try env.extend(allocator, "x", val);1188    defer env.deinit(allocator);11891190    try std.testing.expect(!env.isEmpty());1191    try std.testing.expectEqual(@as(usize, 1), env.len());1192    try std.testing.expectEqual(val, env.get("x").?);1193    try std.testing.expectEqual(@as(?*RuntimeValue, null), env.get("y"));1194}11951196test "runtime value nat conversion" {1197    const allocator = std.testing.allocator;11981199    const nat3 = try pluckNat(allocator, 3);1200    defer nat3.deinit(allocator);12011202    try std.testing.expectEqual(@as(?i64, 3), nat3.maybeNat());1203}12041205test "runtime value bounded nat conversion" {1206    const allocator = std.testing.allocator;12071208    const nat50 = try pluckNat(allocator, 50);1209    defer nat50.deinit(allocator);1210    try std.testing.expectEqual(@as(?i64, 50), nat50.maybeNatBounded(100));12111212    try std.testing.expectEqual(@as(?i64, 50), nat50.maybeNatBounded(50));12131214    try std.testing.expectEqual(@as(?i64, null), nat50.maybeNatBounded(49));12151216    const nat0 = try pluckNat(allocator, 0);1217    defer nat0.deinit(allocator);1218    try std.testing.expectEqual(@as(?i64, 0), nat0.maybeNatBounded(100));1219}12201221test "runtime value true/false" {1222    const allocator = std.testing.allocator;12231224    const true_val = try RuntimeValue.initTrue(allocator);1225    defer true_val.deinit(allocator);12261227    const false_val = try RuntimeValue.initFalse(allocator);1228    defer false_val.deinit(allocator);12291230    try std.testing.expect(true_val.isTrue());1231    try std.testing.expect(!true_val.isFalse());1232    try std.testing.expect(!false_val.isTrue());1233    try std.testing.expect(false_val.isFalse());1234}12351236test "closure creation" {1237    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);1238    defer arena.deinit();1239    const allocator = arena.allocator();12401241    var types = try pexpr.TypeRegistry.initWithDefaults(allocator);1242    var defs = pexpr.Definitions.init(allocator);12431244    const expr = try pexpr.parseExpr(allocator, "(λ x -> x)", &types, &defs);1245    const body = expr.args[0];12461247    const closure = try Closure.init(allocator, body, Env.empty, "x");12481249    try std.testing.expect(!closure.isSelfLoop());1250    try std.testing.expectEqualStrings("x", closure.name);1251}12521253test "state vars" {1254    const state = StateVars.init();1255    try std.testing.expectEqual(@as(i64, 0), state.initial_fuel);1256    try std.testing.expect(!state.exhausted());12571258    var limited_state = StateVars.initWithFuel(3);1259    try std.testing.expect(!limited_state.exhausted());1260    try std.testing.expect(limited_state.consumeFuel());1261    try std.testing.expect(limited_state.consumeFuel());1262    try std.testing.expect(limited_state.consumeFuel());1263    try std.testing.expect(limited_state.exhausted());1264    try std.testing.expect(!limited_state.consumeFuel());12651266    limited_state.reset();1267    try std.testing.expect(!limited_state.exhausted());1268}