lib/pluck/src/runtime.zig

daab053ee43316e1809a84551d573ddd1e5bf3d2

   1 const std = @import("std");
   2 const Allocator = std.mem.Allocator;
   3 const pexpr = @import("pexpr.zig");
   4 const PExpr = pexpr.PExpr;
   5 const Symbol = pexpr.Symbol;
   6 const bdd = @import("bdd.zig");
   7 const Bdd = bdd.Bdd;
   8 
   9 pub const Env = union(enum) {
  10     cons: *EnvCons,
  11     nil: void,
  12 
  13     const Self = @This();
  14 
  15     pub const empty: Self = .nil;
  16 
  17     pub fn get(self: Self, name: Symbol) ?*RuntimeValue {
  18         return switch (self) {
  19             .cons => |c| c.get(name),
  20             .nil => null,
  21         };
  22     }
  23 
  24     pub fn tail(self: Self) ?Self {
  25         return switch (self) {
  26             .cons => |c| c.tail,
  27             .nil => null,
  28         };
  29     }
  30 
  31     pub fn first(self: Self) ?*RuntimeValue {
  32         return switch (self) {
  33             .cons => |c| c.val,
  34             .nil => null,
  35         };
  36     }
  37 
  38     pub fn firstName(self: Self) ?Symbol {
  39         return switch (self) {
  40             .cons => |c| c.name,
  41             .nil => null,
  42         };
  43     }
  44 
  45     pub fn isEmpty(self: Self) bool {
  46         return self == .nil;
  47     }
  48 
  49     pub fn len(self: Self) usize {
  50         return switch (self) {
  51             .cons => |c| 1 + c.tail.len(),
  52             .nil => 0,
  53         };
  54     }
  55 
  56     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     }
  65 
  66     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     }
  75 
  76     pub fn parseEnv(self: Self, allocator: Allocator) ![]Symbol {
  77         var names: std.ArrayList(Symbol) = .empty;
  78         errdefer names.deinit(allocator);
  79 
  80         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     }
  88 
  89     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     }
 109 
 110     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     }
 130 
 131     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 };
 143 
 144 pub const EnvCons = struct {
 145     name: Symbol,
 146     val: *RuntimeValue,
 147     tail: Env,
 148 
 149     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 };
 156 
 157 pub const IntDist = struct {
 158     bits: []Bdd,
 159 
 160     pub fn init(bits: []Bdd) IntDist {
 161         return IntDist{ .bits = bits };
 162     }
 163 
 164     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     }
 177 
 178     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 };
 189 
 190 pub const NativeValueData = union(enum) {
 191     int: i64,
 192     float: f64,
 193     symbol: Symbol,
 194     bool_val: bool,
 195     pexpr: *PExpr,
 196     int_dist: IntDist,
 197 
 198     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     }
 217 
 218     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     }
 235 
 236     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 };
 254 
 255 pub const ConstructedValue = struct {
 256     constructor: Symbol,
 257     args: []*RuntimeValue,
 258 
 259     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     }
 267 
 268     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 };
 277 
 278 pub const RuntimeValue = struct {
 279     data: Data,
 280 
 281     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     };
 289 
 290     const Self = @This();
 291 
 292     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     }
 297 
 298     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     }
 303 
 304     pub fn initTrue(allocator: Allocator) !*Self {
 305         return initConstructed(allocator, "True", &[_]*Self{});
 306     }
 307 
 308     pub fn initFalse(allocator: Allocator) !*Self {
 309         return initConstructed(allocator, "False", &[_]*Self{});
 310     }
 311 
 312     pub fn initUnit(allocator: Allocator) !*Self {
 313         return initConstructed(allocator, "Unit", &[_]*Self{});
 314     }
 315 
 316     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     }
 321 
 322     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     }
 327 
 328     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     }
 333 
 334     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     }
 355 
 356     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     }
 369 
 370     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     }
 383 
 384     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     }
 390 
 391     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     }
 397 
 398     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     }
 404 
 405     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     }
 414 
 415     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     }
 436 
 437     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     }
 448 
 449     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     }
 471 
 472     pub fn maybeList(self: *const Self, allocator: Allocator) !?[]*Self {
 473         var items: std.ArrayList(*Self) = .empty;
 474         errdefer items.deinit(allocator);
 475 
 476         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     }
 498 
 499     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     }
 510 
 511     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 };
 559 
 560 pub const FromValueResult = struct {
 561     value: ConvertedValue,
 562     concrete: bool,
 563 };
 564 
 565 pub 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 };
 573 
 574 pub 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 }
 640 
 641 pub 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 }
 651 
 652 pub 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 }
 664 
 665 pub const Closure = struct {
 666     expr: ClosureExpr,
 667     env: Env,
 668     name: Symbol,
 669 
 670     pub const ClosureExpr = union(enum) {
 671         pexpr: *PExpr,
 672         thunk: *RuntimeValue,
 673     };
 674 
 675     const Self = @This();
 676 
 677     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     }
 686 
 687     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     }
 696 
 697     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);
 706 
 707         const closure_val = try allocator.create(RuntimeValue);
 708         errdefer allocator.destroy(closure_val);
 709         closure_val.* = RuntimeValue{ .data = .{ .closure = closure } };
 710 
 711         const new_env = try env.extend(allocator, rec_name, closure_val);
 712         errdefer new_env.deinit(allocator);
 713 
 714         closure.* = Self{
 715             .expr = .{ .pexpr = body },
 716             .env = new_env,
 717             .name = nonrec_name,
 718         };
 719 
 720         return closure;
 721     }
 722 
 723     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     }
 732 
 733     pub fn deinit(self: *Self, allocator: Allocator) void {
 734         if (!self.isSelfLoop()) {
 735             self.env.deinit(allocator);
 736         }
 737         allocator.destroy(self);
 738     }
 739 
 740     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     }
 759 
 760     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     }
 770 
 771     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=[");
 785 
 786         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 };
 802 
 803 pub const Callstack = []const i32;
 804 
 805 pub const GuardedWorld = struct {
 806     value: *RuntimeValue,
 807     guard: Bdd,
 808 };
 809 
 810 pub const GuardedWorlds = struct {
 811     worlds: []GuardedWorld,
 812     validity_guard: Bdd,
 813 };
 814 
 815 pub const RuntimeValueContext = struct {
 816     pub fn hash(_: RuntimeValueContext, key: *RuntimeValue) u64 {
 817         return key.hash();
 818     }
 819 
 820     pub fn eql(_: RuntimeValueContext, a: *RuntimeValue, b: *RuntimeValue) bool {
 821         return a.eql(b);
 822     }
 823 };
 824 
 825 pub const NestedWorld = struct {
 826     result: GuardedWorlds,
 827     guard: Bdd,
 828 };
 829 
 830 pub 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,
 837 
 838     pub const ThunkExpr = union(enum) {
 839         pexpr: *PExpr,
 840         thunk: *LazyKCThunk,
 841     };
 842 
 843     const Self = @This();
 844 
 845     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         }
 859 
 860         const thunk = try allocator.create(Self);
 861         errdefer allocator.destroy(thunk);
 862 
 863         const callstack_copy = try allocator.dupe(i32, callstack);
 864         errdefer allocator.free(callstack_copy);
 865 
 866         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     }
 876 
 877     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     }
 885 
 886     pub fn deinitWithEnv(self: *Self, allocator: Allocator) void {
 887         self.env.deinit(allocator);
 888         self.deinit(allocator);
 889     }
 890 
 891     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 };
 905 
 906 pub const LazyKCThunkUnion = struct {
 907     thunks: []ThunkGuard,
 908     allocator: Allocator,
 909 
 910     pub const ThunkGuard = struct {
 911         thunk: *LazyKCThunk,
 912         guard: Bdd,
 913     };
 914 
 915     const Self = @This();
 916 
 917     pub const ThunkInput = struct {
 918         value: *RuntimeValue,
 919         outer_guard: Bdd,
 920     };
 921 
 922     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();
 929 
 930         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         }
 958 
 959         const result = try allocator.create(Self);
 960         errdefer allocator.destroy(result);
 961 
 962         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         }
 966 
 967         result.* = Self{
 968             .thunks = thunks,
 969             .allocator = allocator,
 970         };
 971         return result;
 972     }
 973 
 974     pub fn deinit(self: *Self, allocator: Allocator) void {
 975         allocator.free(self.thunks);
 976         allocator.destroy(self);
 977     }
 978 
 979     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 };
 995 
 996 pub const LazyEnumeratorThunk = struct {
 997     expr: *PExpr,
 998     env: Env,
 999     callstack: []i32,
1000     strict_order_index: i32,
1001     id: u32,
1002 
1003     const Self = @This();
1004 
1005     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         }
1020 
1021         const thunk = try allocator.create(Self);
1022         errdefer allocator.destroy(thunk);
1023 
1024         const callstack_copy = try allocator.dupe(i32, callstack);
1025         errdefer allocator.free(callstack_copy);
1026 
1027         const id = next_id.*;
1028         next_id.* += 1;
1029 
1030         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     }
1039 
1040     pub fn deinit(self: *Self, allocator: Allocator) void {
1041         allocator.free(self.callstack);
1042         allocator.destroy(self);
1043     }
1044 
1045     pub fn deinitWithEnv(self: *Self, allocator: Allocator) void {
1046         self.env.deinit(allocator);
1047         self.deinit(allocator);
1048     }
1049 
1050     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 };
1061 
1062 pub const StateVars = struct {
1063     initial_fuel: i64,
1064     remaining_fuel: i64,
1065 
1066     const Self = @This();
1067 
1068     pub fn init() Self {
1069         return Self{ .initial_fuel = 0, .remaining_fuel = 0 };
1070     }
1071 
1072     pub fn initWithFuel(fuel: i64) Self {
1073         return Self{ .initial_fuel = fuel, .remaining_fuel = fuel };
1074     }
1075 
1076     pub fn exhausted(self: *const Self) bool {
1077         return self.initial_fuel > 0 and self.remaining_fuel <= 0;
1078     }
1079 
1080     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     }
1090 
1091     pub fn reset(self: *Self) void {
1092         self.remaining_fuel = self.initial_fuel;
1093     }
1094 };
1095 
1096 pub const ThunkPath = []const usize;
1097 
1098 pub fn findFirstThunk(allocator: Allocator, val: *RuntimeValue) !?[]usize {
1099     var path: std.ArrayList(usize) = .empty;
1100     errdefer path.deinit(allocator);
1101 
1102     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 }
1109 
1110 pub fn findFirstThunkInto(allocator: Allocator, val: *RuntimeValue, path: *std.ArrayList(usize)) !bool {
1111     path.clearRetainingCapacity();
1112     return findFirstThunkInner(allocator, val, path);
1113 }
1114 
1115 fn 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 }
1136 
1137 pub fn getValueAtPath(val: *RuntimeValue, path: []const usize) ?*RuntimeValue {
1138     if (path.len == 0) return val;
1139 
1140     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 }
1148 
1149 pub 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;
1156 
1157     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);
1162 
1163             if (path[0] < c.args.len) {
1164                 new_args[path[0]] = try replaceAtPath(allocator, c.args[path[0]], path[1..], new_val);
1165             }
1166 
1167             return RuntimeValue.initConstructed(allocator, c.constructor, new_args);
1168         },
1169         else => return val,
1170     }
1171 }
1172 
1173 test "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 }
1179 
1180 test "environment extension and lookup" {
1181     const allocator = std.testing.allocator;
1182 
1183     const val = try RuntimeValue.initNative(allocator, .{ .int = 42 });
1184     defer val.deinit(allocator);
1185 
1186     var env = Env.empty;
1187     env = try env.extend(allocator, "x", val);
1188     defer env.deinit(allocator);
1189 
1190     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 }
1195 
1196 test "runtime value nat conversion" {
1197     const allocator = std.testing.allocator;
1198 
1199     const nat3 = try pluckNat(allocator, 3);
1200     defer nat3.deinit(allocator);
1201 
1202     try std.testing.expectEqual(@as(?i64, 3), nat3.maybeNat());
1203 }
1204 
1205 test "runtime value bounded nat conversion" {
1206     const allocator = std.testing.allocator;
1207 
1208     const nat50 = try pluckNat(allocator, 50);
1209     defer nat50.deinit(allocator);
1210     try std.testing.expectEqual(@as(?i64, 50), nat50.maybeNatBounded(100));
1211 
1212     try std.testing.expectEqual(@as(?i64, 50), nat50.maybeNatBounded(50));
1213 
1214     try std.testing.expectEqual(@as(?i64, null), nat50.maybeNatBounded(49));
1215 
1216     const nat0 = try pluckNat(allocator, 0);
1217     defer nat0.deinit(allocator);
1218     try std.testing.expectEqual(@as(?i64, 0), nat0.maybeNatBounded(100));
1219 }
1220 
1221 test "runtime value true/false" {
1222     const allocator = std.testing.allocator;
1223 
1224     const true_val = try RuntimeValue.initTrue(allocator);
1225     defer true_val.deinit(allocator);
1226 
1227     const false_val = try RuntimeValue.initFalse(allocator);
1228     defer false_val.deinit(allocator);
1229 
1230     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 }
1235 
1236 test "closure creation" {
1237     var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
1238     defer arena.deinit();
1239     const allocator = arena.allocator();
1240 
1241     var types = try pexpr.TypeRegistry.initWithDefaults(allocator);
1242     var defs = pexpr.Definitions.init(allocator);
1243 
1244     const expr = try pexpr.parseExpr(allocator, "(λ x -> x)", &types, &defs);
1245     const body = expr.args[0];
1246 
1247     const closure = try Closure.init(allocator, body, Env.empty, "x");
1248 
1249     try std.testing.expect(!closure.isSelfLoop());
1250     try std.testing.expectEqualStrings("x", closure.name);
1251 }
1252 
1253 test "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());
1257 
1258     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());
1265 
1266     limited_state.reset();
1267     try std.testing.expect(!limited_state.exhausted());
1268 }