"""Additive output equations and their Lean certificate, used by storm.py."""from collections import defaultdictfrom fractions import Fractionfrom pathlib import Pathdef read_edges(prefix, size, controller, labels): lines = Path(str(prefix) + ".additive.edges").read_text().splitlines() if not lines or lines[0] != "additive-rewards 1": raise ValueError("unsupported additive reward format") n = size - 1 edges = [] weights = defaultdict(Fraction) for line in lines[1:]: source, target, probability, reward = line.split() i, j, p, r = int(source), int(target), Fraction(probability), Fraction(reward) if not (0 <= i < n and 0 <= j < n and p > 0): raise ValueError("invalid additive edge") edges.append((i, j, p, r)) weights[i, j] += p expected = defaultdict(Fraction) terminals = labels["returned"] | labels["rejected"] for i, j, p in controller: if i < n: expected[i, i if i in terminals else j] += p if weights != expected: raise ValueError("additive edges disagree with the probability controller") for i, j, p, r in edges: if i in terminals and (i != j or r != 0): raise ValueError("terminal additive rows must have zero reward") return edgesdef moments(query, size, labels, outputs, dead, edges): mass = query([int(i in labels["returned"]) for i in range(size)]) rejection = query([int(i in labels["rejected"]) for i in range(size)]) stopped = labels["returned"] | labels["rejected"] | dead def signed(rhs): positive = query([max(q, 0) for q in rhs]) negative = query([max(-q, 0) for q in rhs]) return [p - n for p, n in zip(positive, negative)] rhs = list(outputs) for i, j, p, r in edges: if i not in stopped: rhs[i] += p * r * mass[j] first = signed(rhs) rhs = [q*q for q in outputs] for i, j, p, r in edges: if i not in stopped: rhs[i] += p * (2*r*first[j] + r*r*mass[j]) second = signed(rhs) return {"mass": mass, "rejection": rejection, "first": first, "second": second}def certificate_text(prefix, values, dead, ranks, following): def rat(q): return f"(({q.numerator} : Rat) / {q.denominator})" text = Path(str(prefix) + ".replay.lean").read_text().replace( "import Determinize.Proof.RewardModel.Soundness", "import Determinize.Proof.RewardModel.Soundness\nimport Determinize.Proof.RewardModel.Sparse") for name, vector in values.items(): text += f"\ndef {name}Values : Vector Rat model.size := ⟨#[{', '.join(map(rat, vector))}], by rfl⟩\n" text += f"\ndef deadStates : Vector Bool model.size := ⟨#[{', '.join(str(b).lower() for b in dead)}], by rfl⟩\n" text += f"def ranks : Vector Nat model.size := ⟨#[{', '.join(map(str, ranks))}], by rfl⟩\n" destinations = ', '.join(f"⟨{j}, by decide +kernel⟩" for j in following) text += f"def nextStates : Vector (Fin model.size) model.size := ⟨#[{destinations}], by rfl⟩\n" n = len(dead) text += """def certificate : Determinize.Proof.RewardModel.Certificate model.size := Determinize.Proof.RewardModel.Certificate.ofVectors deadStates ranks nextStates massValues firstValues secondValues rejectionValuesabbrev resultClaim (i : Fin model.size) := certificate.StateValid model i""" for i in range(n): text += f"\ntheorem result_{i} : resultClaim (⟨{i}, by decide +kernel⟩ : Fin model.size) := by\n decide +kernel\n" entries = ", ".join(f"⟨⟨{i}, by decide +kernel⟩, result_{i}⟩" for i in range(n)) text += f"""def resultEvidence : Vector (Subtype resultClaim) model.size := ⟨#[{entries}], by rfl⟩theorem resultIndices : ∀ i : Fin model.size, (resultEvidence[i]).val = i := by decide +kerneltheorem allResults (i : Fin model.size) : resultClaim i := (resultIndices i) ▸ (resultEvidence[i]).propertydef solution := certificate.solution model allResults""" text += """abbrev statistics := solution.statisticstheorem checkedResult : Determinize.Spec.RewardModel.ResultMatches model (checkedSubject.program checkedSource) statistics := Determinize.Proof.RewardModel.solution_result model _ modelMatches solutiontheorem integrability : MeasureTheory.Integrable (fun x : ℝ => x) (bigStepMeasure (checkedSubject.program checkedSource)) ∧ MeasureTheory.Integrable (fun x : ℝ => x^2) (bigStepMeasure (checkedSubject.program checkedSource)) := by simpa only [modelMatches.2] using Determinize.Proof.RewardModel.integrable_outputMeasure modeltheorem outputStatistics : statistics.Matches (bigStepMeasure (checkedSubject.program checkedSource)) := by simpa only [modelMatches.2] using Determinize.Proof.RewardModel.solution_statistics model solutiontheorem conditionalVariance (positive : 0 < statistics.returnMass) : ProbabilityTheory.variance id ((bigStepMeasure (checkedSubject.program checkedSource) Set.univ)⁻¹ • bigStepMeasure (checkedSubject.program checkedSource)) = ((statistics.secondMoment / statistics.returnMass - (statistics.firstMoment / statistics.returnMass)^2 : Rat) : ℝ) := by simpa only [modelMatches.2] using Determinize.Proof.RewardModel.solution_conditional_variance model solution positivetheorem terminationProbabilities : (⟨solution.mass model.initial, solution.rejection model.initial, 1-solution.mass model.initial-solution.rejection model.initial⟩ : TerminationStatistics).Matches model.control := Determinize.Proof.RewardModel.solution_termination model solution#print axioms checkedResult#print axioms integrability#print axioms outputStatistics#print axioms conditionalVariance#print axioms terminationProbabilities""" return text