tiny.pluck.lpsmc
Defined in tiny.pluck.
API (41)
Actions
Public operations.
LPSMCVarianceStats.effectiveSampleSizeLPSMCVarianceStats.essRatioLPSMCVarianceStats.isHighVarianceLPSMCVarianceStats.recordWeightPathChoice.deinitRunToSuspendResult.hasSuspensionsRunToSuspendResult.isCompleteSubproblemCache.deinitSuspendedComputation.initaffectsPathChoicesclampAdaptiveKclearCachesdeinitgetAffectedSubproblemsinitinvalidateForRefinementnextAdaptiveKnormalizeAdaptiveKPolicyrecordDependencyrunrunToSuspendselectSuspensionsubproblemMonteCarloImpl
Types and contracts
Public types and contracts.
AdaptiveKPolicyEvaluateThunkFnEvaluatorOpsFreeWorldsSliceFnIncrementalLPSMCLPSMCVarianceStatsLpsmcRunStatsPathChoiceRunToSuspendResultSetWeightFnSubproblemCacheSuspendedComputationSuspensionSelectionWorkItemWorldWorldsResult
Values and defaults
Public values and defaults.
Source
Source: lib/pluck/src/lpsmc.zig
zig
const std = @import("std");const random_seed = @import("seed.zig");const Allocator = std.mem.Allocator;const bdd = @import("bdd.zig");const Bdd = bdd.Bdd;const VarLabel = bdd.VarLabel;const Manager = bdd.Manager;const WmcParams = bdd.WmcParams;const runtime = @import("runtime.zig");const RuntimeValue = runtime.RuntimeValue;const GuardedWorlds = runtime.GuardedWorlds;pub const World = runtime.GuardedWorld;pub const WorldsResult = GuardedWorlds;const VarLabelSet = bdd.VarLabelSet;pub const EvaluateThunkFn = *const fn ( allocator: Allocator, val: *RuntimeValue, path_condition: Bdd, state: *anyopaque,) anyerror!WorldsResult;pub const FreeWorldsSliceFn = *const fn (allocator: Allocator, worlds: []World) void;pub const SetWeightFn = *const fn (wmc_params: *WmcParams, variable: VarLabel, low: f64, high: f64) Allocator.Error!void;pub const EvaluatorOps = struct { evaluateThunk: EvaluateThunkFn, freeWorldsSlice: FreeWorldsSliceFn, setWeight: SetWeightFn, state: *anyopaque, wmc_params: *WmcParams,};fn setWeightForTests(wmc_params: *WmcParams, variable: VarLabel, low: f64, high: f64) Allocator.Error!void { return wmc_params.setWeight(variable, low, high);}pub const PathChoice = struct { top_k_bdd: Bdd, sampled_bdd: ?Bdd, sampled_probability: f64, k_used: usize, ess_ratio: f64, depends_on_vars: VarLabelSet, const Self = @This(); pub fn deinit(self: *Self, allocator: Allocator) void { self.depends_on_vars.deinit(allocator); }};pub const SubproblemCache = struct { available_info: Bdd, return_worlds: std.ArrayList(World), multiplier: f64, depends_on_vars: VarLabelSet, const Self = @This(); pub fn deinit(self: *Self, allocator: Allocator) void { self.return_worlds.deinit(allocator); self.depends_on_vars.deinit(allocator); }};pub const SuspendedComputation = struct { continuation: *RuntimeValue, guard: Bdd, multiplier: f64, iteration: u32, const Self = @This(); pub fn init(continuation: *RuntimeValue, guard: Bdd, multiplier: f64, iteration: u32) Self { return Self{ .continuation = continuation, .guard = guard, .multiplier = multiplier, .iteration = iteration, }; }};pub const WorkItem = struct { continuation: *RuntimeValue, available_info: Bdd, multiplier: f64, iteration: u32,};pub const RunToSuspendResult = struct { return_worlds: []World, suspended: []SuspendedComputation, validity_guard: Bdd, const Self = @This(); pub fn hasSuspensions(self: *const Self) bool { return self.suspended.len > 0; } pub fn isComplete(self: *const Self) bool { return self.suspended.len == 0; }};pub const LPSMCVarianceStats = struct { sum_weights: f64 = 0.0, sum_squared_weights: f64 = 0.0, num_samples: u32 = 0, max_multiplier: f64 = 1.0, high_variance_warning: bool = false, pub const DEFAULT_ESS_THRESHOLD: f64 = 0.1; pub fn effectiveSampleSize(self: *const LPSMCVarianceStats) f64 { if (self.sum_squared_weights == 0.0) return 0.0; return (self.sum_weights * self.sum_weights) / self.sum_squared_weights; } pub fn essRatio(self: *const LPSMCVarianceStats) f64 { if (self.num_samples == 0) return 1.0; return self.effectiveSampleSize() / @as(f64, @floatFromInt(self.num_samples)); } pub fn recordWeight(self: *LPSMCVarianceStats, weight: f64) void { self.sum_weights += weight; self.sum_squared_weights += weight * weight; self.num_samples += 1; if (weight > self.max_multiplier) { self.max_multiplier = weight; } } pub fn isHighVariance(self: *const LPSMCVarianceStats, threshold: f64) bool { return self.essRatio() < threshold; }};pub const AdaptiveKPolicy = struct { enabled: bool = false, min_k: usize = 1, max_k: usize = 64, ess_low: f64 = 0.25, ess_high: f64 = 0.8, min_samples: u32 = 2, growth_factor: f64 = 2.0, shrink_factor: f64 = 0.5, sampled_prob_low: f64 = 0.05,};pub fn normalizeAdaptiveKPolicy(policy: AdaptiveKPolicy) AdaptiveKPolicy { var out = policy; if (out.min_k == 0) out.min_k = 1; if (out.max_k < out.min_k) out.max_k = out.min_k; if (out.ess_low <= 0.0 or out.ess_low >= 1.0) out.ess_low = 0.25; if (out.ess_high <= out.ess_low or out.ess_high > 1.0) out.ess_high = 0.8; if (out.min_samples == 0) out.min_samples = 1; if (out.growth_factor < 1.0) out.growth_factor = 1.0; if (out.shrink_factor <= 0.0 or out.shrink_factor >= 1.0) out.shrink_factor = 0.5; if (out.sampled_prob_low <= 0.0 or out.sampled_prob_low > 1.0) out.sampled_prob_low = 0.05; return out;}pub fn clampAdaptiveK(policy: AdaptiveKPolicy, k: usize) usize { if (!policy.enabled) return k; return std.math.clamp(k, policy.min_k, policy.max_k);}pub fn nextAdaptiveK( policy: AdaptiveKPolicy, current_k: usize, stats: *const LPSMCVarianceStats, used_sampling: bool, sampled_probability: f64,) usize { if (!policy.enabled) return current_k; var k = clampAdaptiveK(policy, current_k); if (stats.num_samples < policy.min_samples and !used_sampling) { return k; } const ess_ratio = stats.essRatio(); const low_sample_prob = used_sampling and sampled_probability > 0.0 and sampled_probability < policy.sampled_prob_low; if (low_sample_prob or ess_ratio < policy.ess_low) { const grown = @ceil(@as(f64, @floatFromInt(k)) * policy.growth_factor); const grown_k = @as(usize, @intFromFloat(grown)); k = std.math.clamp(grown_k, policy.min_k, policy.max_k); } else if (ess_ratio > policy.ess_high) { const shrunk = @floor(@as(f64, @floatFromInt(k)) * policy.shrink_factor); const shrunk_k = @as(usize, @intFromFloat(@max(shrunk, 1.0))); k = std.math.clamp(shrunk_k, policy.min_k, policy.max_k); } return k;}pub const LpsmcRunStats = struct { total_k: usize = 0, subproblem_count: u32 = 0, min_k: usize = 0, max_k: usize = 0, avg_k: f64 = 0.0, iterations: u32 = 0,};pub const IncrementalLPSMC = struct { subproblem_cache: std.AutoHashMapUnmanaged(u32, SubproblemCache), path_choices: std.AutoHashMapUnmanaged(u32, PathChoice), var_to_subproblems: std.AutoHashMapUnmanaged(VarLabel, std.AutoHashMapUnmanaged(u32, void)), last_iteration_count: u32, final_return_worlds: []World, final_multiplier: f64, variance_stats: LPSMCVarianceStats, last_run_stats: LpsmcRunStats, allocator: Allocator, prng: std.Random.DefaultPrng, cache_valid: bool, pub const DEFAULT_ESS_THRESHOLD: f64 = 0.1;};pub fn init(allocator: Allocator) IncrementalLPSMC { const prng = std.Random.DefaultPrng.init(random_seed.systemSeed()); return .{ .subproblem_cache = .{}, .path_choices = .{}, .var_to_subproblems = .{}, .last_iteration_count = 0, .final_return_worlds = &[_]World{}, .final_multiplier = 1.0, .variance_stats = .{}, .last_run_stats = .{}, .allocator = allocator, .prng = prng, .cache_valid = false, };}pub fn deinit(lpsmc: *IncrementalLPSMC) void { var cache_iter = lpsmc.subproblem_cache.iterator(); while (cache_iter.next()) |entry| { entry.value_ptr.deinit(lpsmc.allocator); } lpsmc.subproblem_cache.deinit(lpsmc.allocator); var path_iter = lpsmc.path_choices.iterator(); while (path_iter.next()) |entry| { entry.value_ptr.deinit(lpsmc.allocator); } lpsmc.path_choices.deinit(lpsmc.allocator); var var_iter = lpsmc.var_to_subproblems.iterator(); while (var_iter.next()) |entry| { entry.value_ptr.deinit(lpsmc.allocator); } lpsmc.var_to_subproblems.deinit(lpsmc.allocator); if (lpsmc.final_return_worlds.len > 0) { lpsmc.allocator.free(lpsmc.final_return_worlds); }}pub fn recordDependency(lpsmc: *IncrementalLPSMC, subproblem_idx: u32, var_label: VarLabel) !void { const entry = try lpsmc.var_to_subproblems.getOrPut(lpsmc.allocator, var_label); if (!entry.found_existing) { entry.value_ptr.* = .{}; } try entry.value_ptr.put(lpsmc.allocator, subproblem_idx, {});}fn recordBddDependencies(lpsmc: *IncrementalLPSMC, subproblem_idx: u32, bdd_val: Bdd, manager: *const Manager) !VarLabelSet { var vars = VarLabelSet{}; try collectBddVars(lpsmc, bdd_val, manager, &vars); var it = vars.iterator(); while (it.next()) |entry| { try recordDependency(lpsmc, subproblem_idx, entry.key_ptr.*); } return vars;}fn collectBddVars(lpsmc: *IncrementalLPSMC, bdd_val: Bdd, manager: *const Manager, vars: *VarLabelSet) !void { if (bdd_val.isConst()) return; const var_label = manager.topVar(bdd_val); try vars.put(lpsmc.allocator, var_label, {}); const low_bdd = manager.low(bdd_val); const high_bdd = manager.high(bdd_val); try collectBddVars(lpsmc, low_bdd, manager, vars); try collectBddVars(lpsmc, high_bdd, manager, vars);}pub fn affectsPathChoices(lpsmc: *const IncrementalLPSMC, affected_var: VarLabel) bool { var path_iter = lpsmc.path_choices.iterator(); while (path_iter.next()) |entry| { if (entry.value_ptr.depends_on_vars.contains(affected_var)) { return true; } } return false;}pub fn getAffectedSubproblems(lpsmc: *const IncrementalLPSMC, affected_var: VarLabel, out: *std.ArrayList(u32)) !void { if (lpsmc.var_to_subproblems.get(affected_var)) |subproblems| { var it = subproblems.iterator(); while (it.next()) |entry| { try out.append(lpsmc.allocator, entry.key_ptr.*); } }}pub fn invalidateForRefinement(lpsmc: *IncrementalLPSMC, affected_var: VarLabel) bool { if (affectsPathChoices(lpsmc, affected_var)) { clearCaches(lpsmc); return true; } if (lpsmc.var_to_subproblems.get(affected_var)) |subproblems| { var it = subproblems.iterator(); while (it.next()) |entry| { const subproblem_id = entry.key_ptr.*; if (lpsmc.subproblem_cache.getPtr(subproblem_id)) |cache_entry| { cache_entry.deinit(lpsmc.allocator); } _ = lpsmc.subproblem_cache.remove(subproblem_id); if (lpsmc.path_choices.getPtr(subproblem_id)) |path_choice| { path_choice.deinit(lpsmc.allocator); } _ = lpsmc.path_choices.remove(subproblem_id); } if (lpsmc.var_to_subproblems.getPtr(affected_var)) |var_entry| { var_entry.deinit(lpsmc.allocator); } _ = lpsmc.var_to_subproblems.remove(affected_var); } lpsmc.cache_valid = false; return false;}pub fn clearCaches(lpsmc: *IncrementalLPSMC) void { var cache_iter = lpsmc.subproblem_cache.iterator(); while (cache_iter.next()) |entry| { entry.value_ptr.deinit(lpsmc.allocator); } lpsmc.subproblem_cache.clearRetainingCapacity(); var path_iter = lpsmc.path_choices.iterator(); while (path_iter.next()) |entry| { entry.value_ptr.deinit(lpsmc.allocator); } lpsmc.path_choices.clearRetainingCapacity(); var var_iter = lpsmc.var_to_subproblems.iterator(); while (var_iter.next()) |entry| { entry.value_ptr.deinit(lpsmc.allocator); } lpsmc.var_to_subproblems.clearRetainingCapacity(); if (lpsmc.final_return_worlds.len > 0) { lpsmc.allocator.free(lpsmc.final_return_worlds); lpsmc.final_return_worlds = &[_]World{}; } lpsmc.last_iteration_count = 0; lpsmc.final_multiplier = 1.0; lpsmc.variance_stats = .{}; lpsmc.cache_valid = false;}fn copyWorlds(allocator: Allocator, worlds: []const World) ![]World { const copy = try allocator.alloc(World, worlds.len); @memcpy(copy, worlds); return copy;}fn cachedRunResult(lpsmc: *IncrementalLPSMC, result_allocator: Allocator) !?[]World { if (!lpsmc.cache_valid or lpsmc.final_return_worlds.len == 0) { return null; } return try copyWorlds(result_allocator, lpsmc.final_return_worlds);}fn resetRunState(lpsmc: *IncrementalLPSMC) void { lpsmc.last_iteration_count = 0; lpsmc.variance_stats = .{};}fn evidenceGuard( allocator: Allocator, evidence_thunk: ?*RuntimeValue, ops: EvaluatorOps, manager: *Manager,) !Bdd { var guard = Bdd.TRUE; if (evidence_thunk) |ev_thunk| { const evidence_result = try ops.evaluateThunk(allocator, ev_thunk, Bdd.TRUE, ops.state); defer ops.freeWorldsSlice(allocator, evidence_result.worlds); guard = Bdd.FALSE; for (evidence_result.worlds) |world| { if (world.value.data == .constructed) { const c = world.value.data.constructed; if (std.mem.eql(u8, c.constructor, "True") and c.args.len == 0) { guard = try manager.bddOr(guard, world.guard); } } } } return guard;}fn appendInitialWork( worklist: *std.ArrayList(WorkItem), allocator: Allocator, suspendible_thunk: *RuntimeValue, guard: Bdd,) !void { try worklist.append(allocator, .{ .continuation = suspendible_thunk, .available_info = guard, .multiplier = 1.0, .iteration = 0, });}fn appendSubproblemResult( lpsmc: *IncrementalLPSMC, id: u32, item: WorkItem, subproblem_vars: VarLabelSet, worlds: []const World, return_worlds: *std.ArrayList(World),) !void { var cache_entry = SubproblemCache{ .available_info = item.available_info, .return_worlds = .empty, .multiplier = item.multiplier, .depends_on_vars = subproblem_vars, }; errdefer cache_entry.deinit(lpsmc.allocator); for (worlds) |world| { try return_worlds.append(lpsmc.allocator, world); try cache_entry.return_worlds.append(lpsmc.allocator, world); } try lpsmc.subproblem_cache.put(lpsmc.allocator, id, cache_entry);}fn recordSuspensionStats(run_stats: *LpsmcRunStats, k_used: usize) void { run_stats.total_k += k_used; run_stats.subproblem_count += 1; run_stats.min_k = if (run_stats.subproblem_count == 1) k_used else @min(run_stats.min_k, k_used); run_stats.max_k = @max(run_stats.max_k, k_used);}fn recordSelectionState( lpsmc: *IncrementalLPSMC, id: u32, selection: SuspensionSelection, k_used: usize, manager: *Manager,) !void { if (selection.used_sampling) { lpsmc.variance_stats.recordWeight(selection.new_multiplier); } const ess_ratio = lpsmc.variance_stats.essRatio(); var path_vars = try recordBddDependencies(lpsmc, id, selection.top_k_bdd, manager); errdefer path_vars.deinit(lpsmc.allocator); try lpsmc.path_choices.put(lpsmc.allocator, id, PathChoice{ .top_k_bdd = selection.top_k_bdd, .sampled_bdd = selection.sampled_bdd, .sampled_probability = selection.sampled_probability, .k_used = k_used, .ess_ratio = ess_ratio, .depends_on_vars = path_vars, }); if (selection.used_sampling and lpsmc.variance_stats.isHighVariance(LPSMCVarianceStats.DEFAULT_ESS_THRESHOLD)) { lpsmc.variance_stats.high_variance_warning = true; }}fn enqueueSelectionChildren( allocator: Allocator, worklist: *std.ArrayList(WorkItem), suspended: []const SuspendedComputation, selection: SuspensionSelection, next_iteration: u32, manager: *Manager,) !void { for (suspended) |susp| { const child_guard = try manager.bddAnd(selection.selection_guard, susp.guard); if (child_guard.isFalse()) continue; try worklist.append(allocator, .{ .continuation = susp.continuation, .available_info = child_guard, .multiplier = selection.new_multiplier, .iteration = next_iteration, }); }}fn finishRunStats( lpsmc: *IncrementalLPSMC, subproblem_count: u32, multiplier: f64, max_iterations: u32, run_stats: LpsmcRunStats,) void { var stats = run_stats; lpsmc.last_iteration_count = subproblem_count; lpsmc.final_multiplier = multiplier; if (lpsmc.last_iteration_count == 0) { lpsmc.last_iteration_count = max_iterations; } stats.iterations = lpsmc.last_iteration_count; if (stats.subproblem_count > 0) { stats.avg_k = @as(f64, @floatFromInt(stats.total_k)) / @as(f64, @floatFromInt(stats.subproblem_count)); } lpsmc.last_run_stats = stats;}fn publishRunResult( lpsmc: *IncrementalLPSMC, result_allocator: Allocator, return_worlds: *std.ArrayList(World),) ![]World { const cached_result = try return_worlds.toOwnedSlice(lpsmc.allocator); if (lpsmc.final_return_worlds.len > 0) { lpsmc.allocator.free(lpsmc.final_return_worlds); } lpsmc.final_return_worlds = cached_result; lpsmc.cache_valid = true; return try copyWorlds(result_allocator, cached_result);}pub fn run( lpsmc: *IncrementalLPSMC, result_allocator: Allocator, suspendible_thunk: *RuntimeValue, evidence_thunk: ?*RuntimeValue, k: usize, k_policy: AdaptiveKPolicy, ops: EvaluatorOps, manager: *Manager,) ![]World { if (try cachedRunResult(lpsmc, result_allocator)) |copy| { return copy; } resetRunState(lpsmc); const max_iterations: u32 = 1000; const policy = normalizeAdaptiveKPolicy(k_policy); var current_k: usize = clampAdaptiveK(policy, k); var run_stats = LpsmcRunStats{}; const random = lpsmc.prng.random(); const initial_guard = try evidenceGuard(result_allocator, evidence_thunk, ops, manager); if (initial_guard.isFalse()) { lpsmc.last_run_stats = .{}; return &[_]World{}; } var return_worlds = std.ArrayList(World).empty; errdefer return_worlds.deinit(lpsmc.allocator); var worklist: std.ArrayList(WorkItem) = .empty; defer worklist.deinit(lpsmc.allocator); try appendInitialWork(&worklist, lpsmc.allocator, suspendible_thunk, initial_guard); var multiplier: f64 = 1.0; var subproblem_id: u32 = 0; var processed: u32 = 0; while (worklist.pop()) |item| { processed += 1; if (processed > max_iterations) break; const id = subproblem_id; subproblem_id += 1; multiplier = item.multiplier; const run_result = try runToSuspend( result_allocator, item.continuation, item.available_info, item.multiplier, item.iteration, ops, manager, ); defer if (run_result.return_worlds.len > 0) result_allocator.free(run_result.return_worlds); defer if (run_result.suspended.len > 0) result_allocator.free(run_result.suspended); const subproblem_vars = try recordBddDependencies(lpsmc, id, item.available_info, manager); try appendSubproblemResult(lpsmc, id, item, subproblem_vars, run_result.return_worlds, &return_worlds); if (!run_result.hasSuspensions() or item.iteration + 1 >= max_iterations) { continue; } const k_used = current_k; recordSuspensionStats(&run_stats, k_used); const selection_opt = try selectSuspension( lpsmc.allocator, run_result.suspended, item.available_info, item.multiplier, k_used, ops, manager, random, ); if (selection_opt == null) { continue; } const selection = selection_opt.?; try recordSelectionState(lpsmc, id, selection, k_used, manager); current_k = nextAdaptiveK(policy, current_k, &lpsmc.variance_stats, selection.used_sampling, selection.sampled_probability); const next_iteration = item.iteration + 1; try enqueueSelectionChildren(lpsmc.allocator, &worklist, run_result.suspended, selection, next_iteration, manager); } finishRunStats(lpsmc, subproblem_id, multiplier, max_iterations, run_stats); return try publishRunResult(lpsmc, result_allocator, &return_worlds);}fn appendWeightedReturnWorld( allocator: Allocator, output: *std.ArrayList(World), value: *RuntimeValue, guard: Bdd, available_info: Bdd, multiplier: f64, ops: EvaluatorOps, manager: *Manager,) !void { const new_var = try manager.newVar(true); const new_guard = try manager.bddAnd(new_var, try manager.bddAnd(guard, available_info)); try ops.setWeight(ops.wmc_params, manager.topVar(new_var), 1.0, multiplier); if (!new_guard.isFalse()) { try output.append(allocator, World{ .value = value, .guard = new_guard, }); }}fn handleConstructedRunWorld( allocator: Allocator, world: World, available_info: Bdd, multiplier: f64, iteration: u32, ops: EvaluatorOps, manager: *Manager, return_worlds: *std.ArrayList(World), suspended: *std.ArrayList(SuspendedComputation),) !bool { if (world.value.data != .constructed) return false; const c = world.value.data.constructed; if (std.mem.eql(u8, c.constructor, "Suspend")) { if (c.args.len >= 1) { try suspended.append(allocator, SuspendedComputation.init( c.args[0], world.guard, multiplier, iteration, )); } return true; } if (std.mem.eql(u8, c.constructor, "FinallyTrue")) { const true_val = try RuntimeValue.initConstructed(allocator, "True", &[_]*RuntimeValue{}); try appendWeightedReturnWorld(allocator, return_worlds, true_val, world.guard, available_info, multiplier, ops, manager); return true; } if (std.mem.eql(u8, c.constructor, "FinallyFalse")) { const false_val = try RuntimeValue.initConstructed(allocator, "False", &[_]*RuntimeValue{}); try appendWeightedReturnWorld(allocator, return_worlds, false_val, world.guard, available_info, multiplier, ops, manager); return true; } return false;}pub fn runToSuspend( allocator: Allocator, thunk: *RuntimeValue, available_info: Bdd, multiplier: f64, iteration: u32, ops: EvaluatorOps, manager: *Manager,) !RunToSuspendResult { const eval_result = try ops.evaluateThunk(allocator, thunk, available_info, ops.state); defer ops.freeWorldsSlice(allocator, eval_result.worlds); var return_worlds_list: std.ArrayList(World) = .empty; errdefer return_worlds_list.deinit(allocator); var suspended_list: std.ArrayList(SuspendedComputation) = .empty; errdefer suspended_list.deinit(allocator); for (eval_result.worlds) |world| { if (try handleConstructedRunWorld(allocator, world, available_info, multiplier, iteration, ops, manager, &return_worlds_list, &suspended_list)) { continue; } try appendWeightedReturnWorld(allocator, &return_worlds_list, world.value, world.guard, available_info, multiplier, ops, manager); } return RunToSuspendResult{ .return_worlds = try return_worlds_list.toOwnedSlice(allocator), .suspended = try suspended_list.toOwnedSlice(allocator), .validity_guard = eval_result.validity_guard, };}pub const SuspensionSelection = struct { selection_guard: Bdd, new_multiplier: f64, used_sampling: bool, top_k_bdd: Bdd, sampled_bdd: ?Bdd, sampled_probability: f64,};const MixResult = struct { mixed_bdd: Bdd, mult_increment: f64,};fn mixTopKAndSample( manager: *Manager, ops: EvaluatorOps, top_k_bdd: Bdd, sampled_bdd: Bdd, sampled_probability: f64,) !MixResult { const mult_increment = 1.0 + (1.0 / sampled_probability); const topk_prob = 1.0 / mult_increment; const sampled_prob = 1.0 - topk_prob; const mix_var = try manager.newVar(true); try ops.setWeight(ops.wmc_params, manager.topVar(mix_var), sampled_prob, topk_prob); const mixed_bdd = try manager.ite(mix_var, top_k_bdd, sampled_bdd); return MixResult{ .mixed_bdd = mixed_bdd, .mult_increment = mult_increment, };}pub fn selectSuspension( allocator: Allocator, suspensions: []const SuspendedComputation, available_info: Bdd, current_multiplier: f64, k: usize, ops: EvaluatorOps, manager: *Manager, random: std.Random,) !?SuspensionSelection { if (suspensions.len == 0) return null; var combined_susp_guard = Bdd.FALSE; for (suspensions) |susp| { combined_susp_guard = try manager.bddOr(combined_susp_guard, susp.guard); } const new_available = try manager.bddAnd(available_info, combined_susp_guard); if (new_available.isFalse()) { return null; } const top_k_bdd = try bdd.topKPaths(manager, new_available, k, ops.wmc_params, allocator); const posterior_guard = try manager.bddAnd(new_available, manager.bddNot(top_k_bdd)); var new_multiplier = current_multiplier; var combined_guard = top_k_bdd; var used_sampling = false; var sampled_bdd: ?Bdd = null; var sampled_probability: f64 = 0.0; if (!posterior_guard.isFalse()) { const posterior_mass = bdd.wmc(manager, posterior_guard, ops.wmc_params); if (posterior_mass > 0.0) { const sampled = try bdd.weightedSample(manager, posterior_guard, ops.wmc_params, random); if (!sampled.sample.isFalse() and sampled.probability > 0.0) { const conditional_prob_raw = sampled.probability / posterior_mass; const conditional_prob = if (conditional_prob_raw > 1.0) 1.0 else conditional_prob_raw; if (conditional_prob > 0.0) { const sampled_guard = try manager.bddAnd(posterior_guard, sampled.sample); sampled_bdd = sampled_guard; sampled_probability = conditional_prob; const mix_result = try mixTopKAndSample(manager, ops, top_k_bdd, sampled_guard, conditional_prob); new_multiplier *= mix_result.mult_increment; combined_guard = mix_result.mixed_bdd; used_sampling = true; } } } } const selection_guard = try manager.bddAnd(available_info, combined_guard); if (selection_guard.isFalse()) return null; return SuspensionSelection{ .selection_guard = selection_guard, .new_multiplier = new_multiplier, .used_sampling = used_sampling, .top_k_bdd = top_k_bdd, .sampled_bdd = sampled_bdd, .sampled_probability = sampled_probability, };}pub fn subproblemMonteCarloImpl( allocator: Allocator, suspendible_thunk: *RuntimeValue, evidence_thunk: ?*RuntimeValue, k: usize, k_policy: AdaptiveKPolicy, ops: EvaluatorOps, manager: *Manager, external_rng: ?std.Random,) ![]World { const max_iterations = 1000; const policy = normalizeAdaptiveKPolicy(k_policy); var current_k: usize = clampAdaptiveK(policy, k); var variance_stats = LPSMCVarianceStats{}; var internal_prng: ?std.Random.DefaultPrng = null; const random = if (external_rng) |rng| rng else blk: { internal_prng = std.Random.DefaultPrng.init(random_seed.systemSeed()); break :blk internal_prng.?.random(); }; const initial_guard = try evidenceGuard(allocator, evidence_thunk, ops, manager); if (initial_guard.isFalse()) { return &[_]World{}; } var return_worlds: std.ArrayList(World) = .empty; defer return_worlds.deinit(allocator); var worklist: std.ArrayList(WorkItem) = .empty; defer worklist.deinit(allocator); try appendInitialWork(&worklist, allocator, suspendible_thunk, initial_guard); var processed: usize = 0; while (worklist.pop()) |item| { processed += 1; if (processed > max_iterations) break; const run_result = try runToSuspend( allocator, item.continuation, item.available_info, item.multiplier, item.iteration, ops, manager, ); defer if (run_result.return_worlds.len > 0) allocator.free(run_result.return_worlds); defer if (run_result.suspended.len > 0) allocator.free(run_result.suspended); for (run_result.return_worlds) |world| { try return_worlds.append(allocator, world); } if (!run_result.hasSuspensions() or item.iteration + 1 >= max_iterations) { continue; } const k_used = current_k; const selection_opt = try selectSuspension( allocator, run_result.suspended, item.available_info, item.multiplier, k_used, ops, manager, random, ); if (selection_opt == null) { continue; } const selection = selection_opt.?; if (selection.used_sampling) { variance_stats.recordWeight(selection.new_multiplier); } current_k = nextAdaptiveK(policy, current_k, &variance_stats, selection.used_sampling, selection.sampled_probability); const next_iteration = item.iteration + 1; for (run_result.suspended) |susp| { const child_guard = try manager.bddAnd(selection.selection_guard, susp.guard); if (child_guard.isFalse()) continue; try worklist.append(allocator, .{ .continuation = susp.continuation, .available_info = child_guard, .multiplier = selection.new_multiplier, .iteration = next_iteration, }); } } return try return_worlds.toOwnedSlice(allocator);}test "LPSMCVarianceStats basic operations" { var stats = LPSMCVarianceStats{}; try std.testing.expectEqual(@as(u32, 0), stats.num_samples); try std.testing.expectEqual(@as(f64, 1.0), stats.essRatio()); stats.recordWeight(1.0); stats.recordWeight(1.0); stats.recordWeight(1.0); try std.testing.expectEqual(@as(u32, 3), stats.num_samples); try std.testing.expectApproxEqAbs(@as(f64, 3.0), stats.effectiveSampleSize(), 1e-10); try std.testing.expectApproxEqAbs(@as(f64, 1.0), stats.essRatio(), 1e-10); try std.testing.expect(!stats.isHighVariance(LPSMCVarianceStats.DEFAULT_ESS_THRESHOLD));}test "LPSMCVarianceStats high variance detection" { var stats = LPSMCVarianceStats{}; stats.recordWeight(100.0); stats.recordWeight(1.0); stats.recordWeight(1.0); stats.recordWeight(1.0); try std.testing.expectEqual(@as(u32, 4), stats.num_samples); const ess = stats.effectiveSampleSize(); try std.testing.expect(ess < 2.0); try std.testing.expect(stats.isHighVariance(0.5));}test "AdaptiveKPolicy adjusts k based on ESS and sampled probability" { var policy = AdaptiveKPolicy{ .enabled = true, .min_k = 2, .max_k = 16, .ess_low = 0.3, .ess_high = 0.8, .min_samples = 1, .growth_factor = 2.0, .shrink_factor = 0.5, .sampled_prob_low = 0.1, }; policy = normalizeAdaptiveKPolicy(policy); var stats = LPSMCVarianceStats{}; stats.recordWeight(100.0); stats.recordWeight(1.0); stats.recordWeight(1.0); stats.recordWeight(1.0); const k_up = nextAdaptiveK(policy, 4, &stats, true, 0.2); try std.testing.expect(k_up > 4); var stats_high = LPSMCVarianceStats{}; stats_high.recordWeight(1.0); stats_high.recordWeight(1.0); const k_down = nextAdaptiveK(policy, 8, &stats_high, true, 0.5); try std.testing.expect(k_down < 8); const k_prob = nextAdaptiveK(policy, 4, &stats_high, true, 0.01); try std.testing.expect(k_prob > 4);}test "PathChoice init and deinit" { const allocator = std.testing.allocator; var vars = VarLabelSet{}; try vars.put(allocator, 1, {}); try vars.put(allocator, 2, {}); var choice = PathChoice{ .top_k_bdd = Bdd.TRUE, .sampled_bdd = null, .sampled_probability = 0.0, .k_used = 1, .ess_ratio = 1.0, .depends_on_vars = vars, }; try std.testing.expect(choice.depends_on_vars.contains(1)); try std.testing.expect(choice.depends_on_vars.contains(2)); choice.deinit(allocator);}test "IncrementalLPSMC init and deinit" { const allocator = std.testing.allocator; var lpsmc = init(allocator); defer deinit(&lpsmc); try std.testing.expectEqual(@as(u32, 0), lpsmc.last_iteration_count); try std.testing.expectEqual(@as(f64, 1.0), lpsmc.final_multiplier); try std.testing.expectEqual(@as(u32, 0), lpsmc.variance_stats.num_samples);}test "IncrementalLPSMC clearCaches resets state" { const allocator = std.testing.allocator; var lpsmc = init(allocator); defer deinit(&lpsmc); lpsmc.last_iteration_count = 5; lpsmc.final_multiplier = 2.5; lpsmc.variance_stats.recordWeight(1.0); lpsmc.variance_stats.recordWeight(2.0); clearCaches(&lpsmc); try std.testing.expectEqual(@as(u32, 0), lpsmc.last_iteration_count); try std.testing.expectEqual(@as(f64, 1.0), lpsmc.final_multiplier); try std.testing.expectEqual(@as(u32, 0), lpsmc.variance_stats.num_samples);}test "deterministic RNG produces reproducible results" { var prng1 = std.Random.DefaultPrng.init(12345); var prng2 = std.Random.DefaultPrng.init(12345); const random1 = prng1.random(); const random2 = prng2.random(); var i: usize = 0; while (i < 10) : (i += 1) { const val1 = random1.float(f64); const val2 = random2.float(f64); try std.testing.expectEqual(val1, val2); }}test "SubproblemCache init and deinit" { const allocator = std.testing.allocator; var vars = VarLabelSet{}; try vars.put(allocator, 1, {}); var cache = SubproblemCache{ .available_info = Bdd.TRUE, .return_worlds = .empty, .multiplier = 1.0, .depends_on_vars = vars, }; try std.testing.expect(cache.depends_on_vars.contains(1)); try std.testing.expectEqual(@as(f64, 1.0), cache.multiplier); cache.deinit(allocator);}test "external_rng parameter is used when provided" { var prng1 = std.Random.DefaultPrng.init(42); var prng2 = std.Random.DefaultPrng.init(42); var prng3 = std.Random.DefaultPrng.init(99); const rng1 = prng1.random(); const rng2 = prng2.random(); const rng3 = prng3.random(); const val1a = rng1.float(f64); const val2a = rng2.float(f64); try std.testing.expectEqual(val1a, val2a); const val3a = rng3.float(f64); try std.testing.expect(val1a != val3a); const val1b = rng1.float(f64); const val2b = rng2.float(f64); try std.testing.expectEqual(val1b, val2b);}test "subproblemMonteCarloImpl accepts external RNG (API contract)" { const FnType = @TypeOf(subproblemMonteCarloImpl); const fn_info = @typeInfo(FnType).@"fn"; try std.testing.expectEqual(@as(usize, 8), fn_info.param_types.len); try std.testing.expect(fn_info.param_types[7].? == ?std.Random);}test "SuspendedComputation init" { const allocator = std.testing.allocator; _ = allocator; const susp = SuspendedComputation{ .continuation = undefined, .guard = Bdd.TRUE, .multiplier = 1.5, .iteration = 3, }; try std.testing.expectEqual(Bdd.TRUE, susp.guard); try std.testing.expectEqual(@as(f64, 1.5), susp.multiplier); try std.testing.expectEqual(@as(u32, 3), susp.iteration);}test "RunToSuspendResult helper methods" { const empty_result = RunToSuspendResult{ .return_worlds = &[_]World{}, .suspended = &[_]SuspendedComputation{}, .validity_guard = Bdd.TRUE, }; try std.testing.expect(empty_result.isComplete()); try std.testing.expect(!empty_result.hasSuspensions()); var suspensions = [_]SuspendedComputation{ SuspendedComputation{ .continuation = undefined, .guard = Bdd.TRUE, .multiplier = 1.0, .iteration = 0, }, }; const suspended_result = RunToSuspendResult{ .return_worlds = &[_]World{}, .suspended = &suspensions, .validity_guard = Bdd.TRUE, }; try std.testing.expect(!suspended_result.isComplete()); try std.testing.expect(suspended_result.hasSuspensions());}test "SuspensionSelection struct fields" { const selection = SuspensionSelection{ .selection_guard = Bdd.TRUE, .new_multiplier = 2.5, .used_sampling = true, .top_k_bdd = Bdd.TRUE, .sampled_bdd = Bdd.FALSE, .sampled_probability = 0.25, }; try std.testing.expectEqual(Bdd.TRUE, selection.selection_guard); try std.testing.expectEqual(@as(f64, 2.5), selection.new_multiplier); try std.testing.expect(selection.used_sampling); try std.testing.expectEqual(Bdd.TRUE, selection.top_k_bdd); try std.testing.expectEqual(Bdd.FALSE, selection.sampled_bdd.?); try std.testing.expectEqual(@as(f64, 0.25), selection.sampled_probability);}test "runToSuspend API contract" { const FnType = @TypeOf(runToSuspend); const fn_info = @typeInfo(FnType).@"fn"; try std.testing.expectEqual(@as(usize, 7), fn_info.param_types.len); const return_info = @typeInfo(fn_info.return_type.?); try std.testing.expect(return_info == .error_union);}test "selectSuspension API contract" { const FnType = @TypeOf(selectSuspension); const fn_info = @typeInfo(FnType).@"fn"; try std.testing.expectEqual(@as(usize, 8), fn_info.param_types.len); const return_info = @typeInfo(fn_info.return_type.?); try std.testing.expect(return_info == .error_union);}test "selectSuspension returns null for empty suspensions" { const allocator = std.testing.allocator; var manager = try Manager.init(allocator); defer manager.deinit(); var wmc_params = WmcParams.init(allocator); defer wmc_params.deinit(); const ops = EvaluatorOps{ .evaluateThunk = undefined, .freeWorldsSlice = undefined, .setWeight = undefined, .state = undefined, .wmc_params = &wmc_params, }; var prng = std.Random.DefaultPrng.init(12345); const random = prng.random(); const empty_suspensions = &[_]SuspendedComputation{}; const result = try selectSuspension( allocator, empty_suspensions, Bdd.TRUE, 1.0, 5, ops, &manager, random, ); try std.testing.expect(result == null);}test "mixTopKAndSample preserves unbiased weighting" { const allocator = std.testing.allocator; var manager = try Manager.init(allocator); defer manager.deinit(); var wmc_params = WmcParams.init(allocator); defer wmc_params.deinit(); const a = try manager.newVar(true); const b = try manager.newVar(true); try wmc_params.setWeight(manager.topVar(a), 0.3, 0.7); try wmc_params.setWeight(manager.topVar(b), 0.6, 0.4); const top_k_bdd = a; const sampled_bdd = try manager.bddAnd(manager.bddNot(a), b); const ops = EvaluatorOps{ .evaluateThunk = undefined, .freeWorldsSlice = undefined, .setWeight = setWeightForTests, .state = undefined, .wmc_params = &wmc_params, }; const sampled_probability: f64 = 0.25; const mix = try mixTopKAndSample(&manager, ops, top_k_bdd, sampled_bdd, sampled_probability); const wmc_top = bdd.wmc(&manager, top_k_bdd, &wmc_params); const wmc_sampled = bdd.wmc(&manager, sampled_bdd, &wmc_params); const wmc_mixed = bdd.wmc(&manager, mix.mixed_bdd, &wmc_params); const expected = wmc_top + (1.0 / sampled_probability) * wmc_sampled; const actual = mix.mult_increment * wmc_mixed; try std.testing.expectApproxEqAbs(expected, actual, 1e-12);}Source: lib/pluck/src/root.zig:15
zig
pub const lpsmc = @import("lpsmc.zig");Complete call list for lpsmc.run
16 direct calls.
lib.pluck.src.lpsmc.appendInitialWork[function] — private source atlib/pluck/src/lpsmc.zig:425in nearest public ownertiny.pluck.lpsmclib.pluck.src.lpsmc.appendSubproblemResult[function] — private source atlib/pluck/src/lpsmc.zig:439in nearest public ownertiny.pluck.lpsmclib.pluck.src.lpsmc.cachedRunResult[function] — private source atlib/pluck/src/lpsmc.zig:388in nearest public ownertiny.pluck.lpsmctiny.pluck.lpsmc.clampAdaptiveK[function] atlib/pluck/src/lpsmc.zig:172lib.pluck.src.lpsmc.enqueueSelectionChildren[function] — private source atlib/pluck/src/lpsmc.zig:499in nearest public ownertiny.pluck.lpsmclib.pluck.src.lpsmc.evidenceGuard[function] — private source atlib/pluck/src/lpsmc.zig:401in nearest public ownertiny.pluck.lpsmclib.pluck.src.lpsmc.finishRunStats[function] — private source atlib/pluck/src/lpsmc.zig:519in nearest public ownertiny.pluck.lpsmctiny.pluck.lpsmc.nextAdaptiveK[function] atlib/pluck/src/lpsmc.zig:177tiny.pluck.lpsmc.normalizeAdaptiveKPolicy[function] atlib/pluck/src/lpsmc.zig:159lib.pluck.src.lpsmc.publishRunResult[function] — private source atlib/pluck/src/lpsmc.zig:540in nearest public ownertiny.pluck.lpsmclib.pluck.src.lpsmc.recordBddDependencies[function] — private source atlib/pluck/src/lpsmc.zig:282in nearest public ownertiny.pluck.lpsmclib.pluck.src.lpsmc.recordSelectionState[function] — private source atlib/pluck/src/lpsmc.zig:470in nearest public ownertiny.pluck.lpsmclib.pluck.src.lpsmc.recordSuspensionStats[function] — private source atlib/pluck/src/lpsmc.zig:463in nearest public ownertiny.pluck.lpsmclib.pluck.src.lpsmc.resetRunState[function] — private source atlib/pluck/src/lpsmc.zig:396in nearest public ownertiny.pluck.lpsmctiny.pluck.lpsmc.runToSuspend[function] atlib/pluck/src/lpsmc.zig:714tiny.pluck.lpsmc.selectSuspension[function] atlib/pluck/src/lpsmc.zig:783
Complete call list for lpsmc.subproblemMonteCarloImpl
8 direct calls.
lib.pluck.src.lpsmc.appendInitialWork[function] — private source atlib/pluck/src/lpsmc.zig:425in nearest public ownertiny.pluck.lpsmctiny.pluck.lpsmc.clampAdaptiveK[function] atlib/pluck/src/lpsmc.zig:172lib.pluck.src.lpsmc.evidenceGuard[function] — private source atlib/pluck/src/lpsmc.zig:401in nearest public ownertiny.pluck.lpsmctiny.pluck.lpsmc.nextAdaptiveK[function] atlib/pluck/src/lpsmc.zig:177tiny.pluck.lpsmc.normalizeAdaptiveKPolicy[function] atlib/pluck/src/lpsmc.zig:159tiny.pluck.lpsmc.runToSuspend[function] atlib/pluck/src/lpsmc.zig:714tiny.pluck.lpsmc.selectSuspension[function] atlib/pluck/src/lpsmc.zig:783tiny.reticulum.node.fixture.World.deinit[method] atlib/reticulum/src/node/fixture/world.zig:271
Audit
| Definitions | 40 |
|---|---|
| Public names | 55 |
| Members | 63 |
| Version | 26.7.0 |
| Revision | daab053ee433 |