Source tools/storm_additive.py
"""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