Source lean/Determinize/Frontend/Parser.lean
import Determinize.Frontend.Syntaxnamespace Determinize.Frontendopen Spec.Paperprivate def identStart (c : Char) := c.isAlpha || c == '_'private def identRest (c : Char) := identStart c || c.isDigit || c == '\''private partial def comment (cs : List Char) (depth : Nat) : Except String (List Char) :=  match cs with  | [] => .error "unterminated comment"  | '(' :: '*' :: rest => comment rest (depth + 1)  | '*' :: ')' :: rest => if depth == 1 then .ok rest else comment rest (depth - 1)  | _ :: rest => comment rest depthprivate def discreteArguments : List String → Bool  | "discrete" :: _ => true  | "]" :: _ :: "[" :: "discrete" :: _ => true  | _ => falseprivate partial def tokenize (cs : List Char) (before : List String := []) :    Except String (List String) := do  let emit (token : String) (tail : List Char) : Except String (List String) := do    return token :: (← tokenize tail (token :: before))  match cs with  | [] => return []  | '(' :: '*' :: rest =>    if discreteArguments before then      if let ')' :: tail := rest.dropWhile Char.isWhitespace then        return ["(", "*", ")"] ++ (← tokenize tail (")" :: "*" :: "(" :: before))    tokenize (← comment rest 1) before  | c :: rest =>    if c.isWhitespace then return ← tokenize rest before    if identStart c then      let (word, tail) := rest.span identRest      return ← emit (String.ofList (c :: word)) tail    if c.isDigit then      let (whole, tail) := cs.span Char.isDigit      let (digits, tail) := match tail with        | '.' :: tail => let (frac, tail) := tail.span Char.isDigit; (whole ++ '.' :: frac, tail)        | _ => (whole, tail)      let (digits, tail) ← match tail with        | e :: tail =>          if e == 'e' || e == 'E' then do            let (sign, tail) := match tail with              | '+' :: t => (['+'], t)              | '-' :: t => (['-'], t)              | _ => ([], tail)            let (exp, tail) := tail.span Char.isDigit            if exp.isEmpty then throw "missing decimal exponent"            pure (digits ++ e :: sign ++ exp, tail)          else pure (digits, e :: tail)        | [] => pure (digits, [])      return ← emit (String.ofList digits) tail    match cs with    | '=' :: '>' :: tail => emit "=>" tail    | ':' :: ':' :: tail => emit "::" tail    | '<' :: '=' :: tail => emit "<=" tail    | _ =>      if "()[],|=+-*/<>\\".toList.contains c then        emit (String.singleton c) rest      else throw s!"unexpected character {c}"private def decimal (s : String) : Except String Rat := do  let parts := s.toLower.splitOn "e"  let mantissa := parts.head!  let exp ← match parts with    | [_] => pure (0 : Int)    | [_, e] => match (if e.startsWith "+" then e.drop 1 |>.toString else e).toInt? with        | some n => pure n        | none => throw "invalid decimal exponent"    | _ => throw "invalid decimal"  if exp.natAbs > 10000 then throw "decimal exponent exceeds 10000"  let pieces := mantissa.splitOn "."  let frac := (pieces[1]?).getD ""  let some n := ((pieces.head!) ++ frac).toNat? | throw "invalid decimal"  let q : Rat := (n : Rat) / (10 ^ frac.length : Nat)  return if exp ≥ 0 then q * (10 ^ exp.toNat : Nat) else q / (10 ^ exp.natAbs : Nat)private structure ParserState where  tokens : Array String  pos : Nat := 0private abbrev P := StateT ParserState (Except String)private def peek : P String := do return ((← get).tokens[(← get).pos]?).getD "<end>"private def take : P String := do  let t ← peek  modify fun s ↦ {s with pos := s.pos + 1}  return tprivate def expect (t : String) : P Unit := do  let got ← take  unless got == t do throw s!"expected '{t}', got '{got}' at token {(← get).pos}"private def name : P String := do  let t ← take  unless t.toList.head?.any identStart do throw s!"expected a name, got '{t}'"  return tprivate def primitives :=  ["uniform", "gauss", "gaussian", "poisson", "exponential", "gamma", "beta", "flip", "bernoulli",    "discrete", "discrete_list", "observe"]private def startsAtom (t : String) : Bool :=  t == "(" || t == "[" ||  (t.toList.head?.any (fun c ↦ identStart c || c.isDigit) &&    !(["in", "then", "else", "with", "let", "if", "match", "fun", "rec"].contains t))private partial def expr (minPrec : Nat := 0) : P Surface := do  let t ← take  let mut left ← match t with    | "let" => do      let x ← name; expect "="; let a ← expr; expect "in"      pure (.letE x a (← expr))    | "fun" | "lambda" | "\\" => do      let x ← name; expect "=>"; pure (.lam x (← expr))    | "rec" => do      let f ← name; let x ← name; expect "=>"; pure (.fix f x (← expr))    | "if" => do      let c ← expr; expect "then"; let a ← expr; expect "else"      pure (.ite c a (← expr))    | "match" => do      let e ← expr; expect "with"      if (← peek) == "|" then discard take      if (← peek) == "[" then        expect "["; expect "]"; expect "=>"; let n ← expr        expect "|"; let x ← name; expect "::"; let xs ← name; expect "=>"        pure (.matchList x xs e n (← expr))      else        expect "inl"; let x ← name; expect "=>"; let a ← expr        expect "|"; expect "inr"; let y ← name; expect "=>"        pure (.matchSum x y e a (← expr))    | "(" => do      if (← peek) == ")" then expect ")"; pure (.unit)      else        let a ← expr        if (← peek) == "," then          expect ","; let b ← expr; expect ")"; pure (.pair a b)        else expect ")"; pure a    | "[" => do expect "]"; pure (.nil)    | "-" => do pure (.neg (← expr 70))    | "fst" => do pure (.fst (← expr 81))    | "snd" => do pure (.snd (← expr 81))    | "inl" => do pure (.inl (← expr 81))    | "inr" => do pure (.inr (← expr 81))    | "true" => pure (.bool true)    | "false" => pure (.bool false)    | _ => do      if primitives.contains t then        let mut affinity := none        if (← peek) == "[" then          expect "["          affinity ← match (← take) with            | "E" => pure (some Affinity.E)            | "G" => pure (some Affinity.G)            | x => throw s!"expected E or G, got {x}"          expect "]"        expect "("        let mut args := []        let mut remainder := false        if t == "discrete" && (← peek) == "*" then          expect "*"          remainder := true        else if (← peek) != ")" then          args := [← expr]          while (← peek) == "," do            expect ","            if t == "discrete" && (← peek) == "*" then              expect "*"              remainder := true              break            args := args ++ [← expr]        expect ")"        match t, args with        | "uniform", [a, b] => pure (.uniform affinity a b)        | "gauss", [a, b] | "gaussian", [a, b] => pure (.gaussian affinity a b)        | "poisson", [a] => pure (.poisson affinity a)        | "exponential", [a] => pure (.exponential affinity a)        | "bernoulli", [a] => pure (.bernoulli affinity a)        | "beta", [a, b] => pure (.beta affinity a b)        | "gamma", [a, b] => pure (.gamma affinity a b)        | "discrete_list", [probabilities] => pure (.discreteRemainder affinity probabilities)        | "discrete", probabilities =>          if remainder then            pure (.discreteRemainder affinity (probabilities.foldr Surface.cons .nil))          else pure (.discrete affinity probabilities)        | "flip", [a] => pure (.flip affinity a)        | "observe", [a] =>          if affinity.isSome then throw "observe has no sampling affinity"          pure (.observe a)        | _, _ => throw s!"wrong arguments for {t}"      else if t.toList.head?.any Char.isDigit then        pure (.number (← decimal t))      else if t.toList.head?.any identStart then pure (.var t)      else throw s!"expected expression, got '{t}'"  repeat    let op ← peek    let infixInfo := match op with      | "<" | "<=" => some (30, 31)      | "::" => some (40, 40)      | "+" | "-" => some (50, 51)      | "*" | "/" => some (60, 61)      | _ => none    match infixInfo with    | some (l, r) =>      if l < minPrec then break      discard take      let right ← expr r      left ← match op with        | "<" => pure (.lt left right)        | "<=" => pure (.le left right)        | "::" => pure (.cons left right)        | "+" => pure (.add left right)        | "-" => pure (.sub left right)        | "*" => pure (.mul left right)        | "/" => pure (.div left right)        | _ => throw s!"unknown operator {op}"    | none =>      if minPrec ≤ 80 && startsAtom op then        left := .app left (← expr 81)      else break  return leftdef parse (text : String) : Except String Surface := do  let tokens ← tokenize text.toList  let (result, state) ← (expr 0).run { tokens := tokens.toArray }  unless state.pos == tokens.length do    throw s!"unexpected trailing token {(state.tokens[state.pos]?).getD "<end>"}"  return resultend Determinize.Frontend