Source lean/Determinize/Runtime/Eval.lean
import Determinize.Runtime.Samplingnamespace Determinize.Runtimeopen Spec.Paperinductive Value where  | unit | bool (b : Bool) | number (x : Float)  | pair (a b : Value) | inl (v : Value) | inr (v : Value)  | nil | cons (h t : Value)  | closure (body : Expr Float) (env : List Value)  | recursive (body : Expr Float) (env : List Value)deriving Inhabitedpartial def Value.display : Value → String  | .unit => "()"  | .bool b => toString b  | .number x => toString x  | .pair a b => s!"({a.display}, {b.display})"  | .inl a => s!"inl ({a.display})"  | .inr a => s!"inr ({a.display})"  | .nil => "[]"  | .cons h t => s!"{h.display} :: {t.display}"  | .closure .. | .recursive .. => "<function>"structure EvalState where  fuel : Nat  eSeed : UInt64  gSeed : UInt64  draws : Nat := 0inductive EvalError where  | rejected  | failure (message : String)inductive Outcome where  | returned (value : Value) (state : EvalState)  | rejectedabbrev EvalM := StateT EvalState (Except EvalError)private def tick : EvalM Unit := do  let s ← get  if s.fuel == 0 then throw (EvalError.failure "step limit reached")  set {s with fuel := s.fuel - 1}private def number : Value → EvalM Float  | .number x => pure x  | _ => throw (EvalError.failure "expected a numeric value")private def bool : Value → EvalM Bool  | .bool b => pure b  | _ => throw (EvalError.failure "expected a Boolean value")private def checkedNumber (x : Float) : EvalM Value := do  if x.isNaN || x.isInf then throw (EvalError.failure "nonfinite arithmetic result")  return .number xprivate def draw (op : Op) (action : DistributionAction) (args : List Float) : EvalM Value := do  let s ← get  match action with  | .mean =>    let (value, _) ← (sample op action args |>.run s.eSeed).mapError EvalError.failure    return .number value  | .sample affinity =>    let seed := if affinity == .G then s.gSeed else s.eSeed    let (value, next) ← (sample op action args |>.run seed).mapError EvalError.failure    if affinity == .G then set {s with gSeed := next, draws := s.draws + 1}    else set {s with eSeed := next, draws := s.draws + 1}    return .number valueprivate def numbers : Value → EvalM (List Float)  | .nil => pure []  | .cons head tail => return (← number head) :: (← numbers tail)  | _ => throw (.failure "expected a list of probabilities")private partial def eval (env : List Value) (e : Expr Float) : EvalM Value := do  tick  match e with  | .bvar i => match env[i]? with    | some v => pure v    | none => throw (EvalError.failure "unbound runtime variable")  | .reject => throw EvalError.rejected  | .unit => return .unit  | .bool b => return .bool b  | .real x => checkedNumber x  | .lam b => return .closure b env  | .fix b => return .recursive b env  | .app f x =>    let f ← eval env f; let x ← eval env x    match f with    | .closure b saved => eval (x :: saved) b    | .recursive b saved => eval (x :: f :: saved) b    | _ => throw (EvalError.failure "application of nonfunction")  | .pair a b => return .pair (← eval env a) (← eval env b)  | .fst p => match (← eval env p) with    | .pair a _ => pure a    | _ => throw (EvalError.failure "fst of nonpair")  | .snd p => match (← eval env p) with    | .pair _ b => pure b    | _ => throw (EvalError.failure "snd of nonpair")  | .inl v => return .inl (← eval env v)  | .inr v => return .inr (← eval env v)  | .matchSum s a b => match (← eval env s) with    | .inl v => eval (v :: env) a    | .inr v => eval (v :: env) b    | _ => throw (EvalError.failure "sum match of nonsum")  | .nil => return .nil  | .cons h t => return .cons (← eval env h) (← eval env t)  | .matchList s n c => match (← eval env s) with    | .nil => eval env n    | .cons h t => eval (h :: t :: env) c    | _ => throw (EvalError.failure "list match of nonlist")  | .ite c a b => if (← bool (← eval env c)) then eval env a else eval env b  | .letE v b => let v ← eval env v; eval (v :: env) b  | .neg b => checkedNumber (-(← number (← eval env b)))  | .add a b | .mul a b | .div a b | .lt a b =>    let a ← number (← eval env a); let b ← number (← eval env b)    match e with    | .add .. => checkedNumber (a + b)    | .mul .. => checkedNumber (a * b)    | .div .. =>      if b == 0 then throw (.failure "division by zero")      checkedNumber (a / b)    | _ => return .bool (a < b)  | .uniform k a b | .gaussian k a b | .beta k a b | .gamma k a b =>    let a ← number (← eval env a); let b ← number (← eval env b)    let op := match e with      | .uniform .. => Op.uniform | .gaussian .. => .gaussian | .beta .. => .beta | _ => .gamma    draw op k [a, b]  | .discrete k p =>    let probabilities ← numbers (← eval env p)    draw (.discrete probabilities.length) k probabilities  | .bernoulli k a =>    let a ← number (← eval env a)    draw .bernoulli k [a]  | .poisson k a | .exponential k a =>    let a ← number (← eval env a)    draw (match e with | .poisson .. => .poisson | _ => .exponential) k [a]/-- Observation rejection is separate from invalid operations and exhausted fuel. -/def runOutcome (e : Core) (seed : UInt64 := 0) (fuel : Nat := 100000) : Except String Outcome :=  let expression := e.map (fun q ↦ Float.ofInt q.num / Float.ofNat q.den) id  match (eval [] expression).run ⟨fuel, seed ^^^ 0x517cc1b727220a95, seed, 0⟩ with  | .ok (value, state) => .ok (.returned value state)  | .error .rejected => .ok .rejected  | .error (.failure message) => .error message/-- Compatibility interface for callers requiring a returned value. -/def run (e : Core) (seed : UInt64 := 0) (fuel : Nat := 100000) :    Except String (Value × EvalState) := do  match ← runOutcome e seed fuel with  | .returned value state => return (value, state)  | .rejected => throw "observation rejected"end Determinize.Runtime