reduce.zig (12351B)
1 const Arena = @import("arena.zig").Arena; 2 3 pub const ReduceError = error{ FuelExhausted, InvalidApply, OutOfMemory }; 4 5 const Frame = @import("arena.zig").ReductionFrame; 6 7 /// Call-by-need WHNF machine. Every suspended demand lives on the heap, and 8 /// every update targets the original application (including shared redexes). 9 /// Fuel counts application entries, not observations or continuation dispatch. 10 /// Collection is opt-in: callers must register all externally held node IDs. 11 pub fn reduce(root: u32, arena: *Arena, fuel: u64) ReduceError!u32 { 12 return reduceWithLimit(root, arena, fuel); 13 } 14 15 /// No work ceiling. Host cancellation must dispose the owning Worker. 16 pub fn reduceUnbounded(root: u32, arena: *Arena) ReduceError!u32 { 17 return reduceWithLimit(root, arena, null); 18 } 19 20 fn reduceWithLimit(root: u32, arena: *Arena, fuel: ?u64) ReduceError!u32 { 21 // Codecs repeatedly observe already-normal constructors. Do not borrow the 22 // continuation buffers for those calls, but never skip a due collection. 23 if (!arena.collectionDue() and arena.get(root).* != .app) return root; 24 var remaining = fuel orelse 0; 25 const bounded = fuel != null; 26 // Reuse scratch capacity across codec/IO demands. Move it out while active; 27 // no stale redex IDs survive a return, including fuel/allocation failures. 28 var frames = arena.reduction_frames; 29 arena.reduction_frames = .empty; 30 defer { 31 frames.clearRetainingCapacity(); 32 arena.reduction_frames = frames; 33 } 34 var roots = arena.reduction_roots; 35 arena.reduction_roots = .empty; 36 defer { 37 roots.clearRetainingCapacity(); 38 arena.reduction_roots = roots; 39 } 40 var current = root; 41 42 while (true) { 43 // The only GC safepoint: no unlinked allocation or raw Node pointer is 44 // held here. Suspended redexes retain their function and argument trees. 45 if (arena.collectionDue()) { 46 roots.clearRetainingCapacity(); 47 try roots.append(arena.allocator, root); 48 try roots.append(arena.allocator, current); 49 for (frames.items) |frame| try roots.append(arena.allocator, frame.redex); 50 try arena.collect(roots.items); 51 } 52 var frame: Frame = undefined; 53 if (arena.get(current).* == .app) { 54 if (bounded and remaining == 0) return error.FuelExhausted; 55 if (bounded) remaining -= 1; 56 frame = .{ .kind = .function, .redex = current }; 57 current = arena.get(current).app.func; 58 } else { 59 frame = frames.pop() orelse return current; 60 } 61 62 // Constructor demands need no suspension or extra machine-loop turn. 63 // Only an unevaluated application needs a continuation on the stack. 64 // Allocating rules always return to the safepoint before further work. 65 demand: while (arena.get(current).* != .app) { 66 const orig = frame.redex; 67 if (frame.kind == .update) { 68 arena.get(orig).* = arena.get(current).*; 69 current = orig; 70 break :demand; 71 } 72 const app = arena.get(orig).app; 73 switch (frame.kind) { 74 .function => switch (arena.get(current).*) { 75 .leaf => { 76 arena.get(orig).* = .{ .stem = .{ .child = app.arg } }; 77 current = orig; 78 break :demand; 79 }, 80 .stem => |s| { 81 arena.get(orig).* = .{ .fork = .{ .left = s.child, .right = app.arg } }; 82 current = orig; 83 break :demand; 84 }, 85 .fork => |f| { 86 frame.kind = .discriminator; 87 current = f.left; 88 }, 89 .app => unreachable, 90 }, 91 .discriminator => { 92 const f = arena.get(app.func).fork; 93 switch (arena.get(current).*) { 94 .leaf => { 95 frame.kind = .update; 96 current = f.right; 97 }, 98 .stem => |s| { 99 // The generated left application is demanded immediately. 100 // Fuse its constructor-only reduction when two further 101 // application entries fit in the caller's fuel budget. 102 if (!bounded or remaining >= 2) { 103 switch (arena.get(s.child).*) { 104 .leaf => { 105 const b = try arena.allocApp(f.right, app.arg); 106 if (bounded) remaining -= 2; 107 arena.get(orig).* = .{ .fork = .{ .left = app.arg, .right = b } }; 108 current = orig; 109 break :demand; 110 }, 111 .stem => |k| if (arena.get(k.child).* == .leaf) { 112 if (bounded) remaining -= 2; 113 frame.kind = .update; 114 current = app.arg; 115 continue :demand; 116 }, 117 .fork => |k| if (arena.get(k.left).* == .leaf) { 118 // (K value arg) is the immediately demanded 119 // function of the outer application. Its 120 // private thunk need not be allocated. 121 const value = arena.get(k.right).*; 122 if (value == .fork and arena.get(value.fork.left).* == .leaf) { 123 if (bounded) remaining -= 2; 124 frame.kind = .update; 125 current = value.fork.right; 126 continue :demand; 127 } 128 const b = try arena.allocApp(f.right, app.arg); 129 switch (value) { 130 .leaf => { 131 if (bounded) remaining -= 2; 132 arena.get(orig).* = .{ .stem = .{ .child = b } }; 133 }, 134 .stem => |v| { 135 if (bounded) remaining -= 2; 136 arena.get(orig).* = .{ .fork = .{ .left = v.child, .right = b } }; 137 }, 138 else => { 139 if (bounded) remaining -= 1; 140 arena.get(orig).* = .{ .app = .{ .func = k.right, .arg = b } }; 141 }, 142 } 143 current = orig; 144 break :demand; 145 }, 146 else => {}, 147 } 148 } 149 const a = try arena.allocApp(s.child, app.arg); 150 const b = try arena.allocApp(f.right, app.arg); 151 arena.get(orig).* = .{ .app = .{ .func = a, .arg = b } }; 152 current = orig; 153 break :demand; 154 }, 155 .fork => { 156 frame.kind = .argument; 157 current = app.arg; 158 }, 159 .app => unreachable, 160 } 161 }, 162 .argument => { 163 const f = arena.get(app.func).fork; 164 const branches = arena.get(f.left).fork; 165 switch (arena.get(current).*) { 166 .leaf => { 167 frame.kind = .update; 168 current = branches.left; 169 }, 170 .stem => |s| { 171 arena.get(orig).* = .{ .app = .{ .func = branches.right, .arg = s.child } }; 172 current = orig; 173 break :demand; 174 }, 175 .fork => |arg| { 176 // Triage produces (handler left) right. The inner 177 // application is private and immediately demanded; 178 // preserve both application-entry charges when fused. 179 if (!bounded or remaining >= 2) { 180 switch (arena.get(f.right).*) { 181 .leaf => { 182 if (bounded) remaining -= 2; 183 arena.get(orig).* = .{ .fork = .{ .left = arg.left, .right = arg.right } }; 184 current = orig; 185 break :demand; 186 }, 187 .stem => |k| if (arena.get(k.child).* == .leaf) { 188 if (bounded) remaining -= 2; 189 frame.kind = .update; 190 current = arg.left; 191 continue :demand; 192 }, 193 .fork => |k| if (arena.get(k.left).* == .leaf) { 194 const value = arena.get(k.right).*; 195 if (value == .fork and arena.get(value.fork.left).* == .leaf) { 196 if (bounded) remaining -= 2; 197 frame.kind = .update; 198 current = value.fork.right; 199 continue :demand; 200 } 201 switch (value) { 202 .leaf => { 203 if (bounded) remaining -= 2; 204 arena.get(orig).* = .{ .stem = .{ .child = arg.right } }; 205 }, 206 .stem => |v| { 207 if (bounded) remaining -= 2; 208 arena.get(orig).* = .{ .fork = .{ .left = v.child, .right = arg.right } }; 209 }, 210 else => { 211 if (bounded) remaining -= 1; 212 arena.get(orig).* = .{ .app = .{ .func = k.right, .arg = arg.right } }; 213 }, 214 } 215 current = orig; 216 break :demand; 217 }, 218 else => {}, 219 } 220 } 221 const inner = try arena.allocApp(f.right, arg.left); 222 arena.get(orig).* = .{ .app = .{ .func = inner, .arg = arg.right } }; 223 current = orig; 224 break :demand; 225 }, 226 .app => unreachable, 227 } 228 }, 229 .update => unreachable, 230 } 231 } else { 232 try frames.append(arena.allocator, frame); 233 } 234 } 235 }