Lean2Js.Bound
How big a thing a program can ask a value to size #
Whether a program keeps every result whose size a value rather than the syntax decides inside a bound the checks can carry.
Two operations answer with something that big. Str.repeat builds a string as many times over as its
count says, and Str.padStart is it in disguise: it repeats its pad until the width is reached.
Arr.range builds an array with one element per whole number below its argument, which is how the
subset writes a loop that runs a number of times rather than once per element it was handed.
Everything that runs before emit writes -- eval on every generated vector, the model of the JS, the
JSON handed to Node -- holds that result whole, so a size nothing bounds is a size the checks cannot
survive. Without this the Lean evaluator walks off its stack and lean2js aborts naming nothing.
So the deciding value has to be bounded by the program text. rangeOf reads an upper bound off the
syntax -- literals, min/max, arithmetic, and the branches of a cond or a match -- and a caller's
parameter has none.
Two things multiply, and both are counted. Nesting: Str.repeat (Str.repeat s 4096) 4096 is bounded at
both nodes and still asks for sixteen million code points, so repeatBound carries the bound of the
string being repeated into the bound of the repeat. Repetition: a traversal runs its body once per
element, so (Arr.range 4096).map (fun i => Arr.range 4096) asks for sixteen million elements from two
counts that are each inside the ceiling. arrayBound is what says how many times a traversal runs, and
it answers only where the text says -- an array a caller passes is as long as the vector generator made
it, which is what bounds a body that repeats over one.
This is not a claim about JavaScript. An engine holds far longer strings and far longer arrays than these bounds; what cannot hold them is the differential test, which writes every result it compares into one file and runs it twice.
Lean2Js.Bound.maxRepeat
sourceThe copies of a base string one Str.repeat may ask for. eval appends one copy at a time, so the
differential run costs quadratic time in it: one declaration repeating a caller's string emits in 7 s at
this count, 17 s at four times it and 198 s at sixteen times it.
Equations
- Lean2Js.Bound.maxRepeat = 4096
Instances For
Used by
Lean2Js.Bound.maxRange
sourceThe elements one Arr.range may ask for. What the ceiling buys is what maxRepeat buys -- every
vector of the differential run holds the array whole -- but the cost is linear in the count rather than
quadratic: one declaration ranging over this count adds half a second to a 1.7 s run, where a declaration
repeating a caller's string at the same count costs 7 s. The number is maxRepeat again so that there is
one ceiling to know rather than two, not because this is where ranging starts to hurt.
Equations
- Lean2Js.Bound.maxRange = 4096
Instances For
Used by
Lean2Js.Bound.Range
sourceWhat the syntax says about the value of an Int53 expression. none at an end is the checker
declining to say, never a claim that the value is unbounded there.
Instances For
Used by
Lean2Js.Bound.instReprRange
sourceEquations
- Lean2Js.Bound.instReprRange = { reprPrec := Lean2Js.Bound.instReprRange.repr }
Used by
Lean2Js.Bound.instReprRange.repr
sourceEquations
- One or more equations did not get rendered due to their size.
Instances For
Used by
Lean2Js.Bound.instInhabitedRange
sourceEquations
Used by
Lean2Js.Bound.Range.unknown
sourceInstances For
Used by
Lean2Js.Bound.Range.exact
sourceInstances For
Used by
Lean2Js.Bound.Range.union
sourceEverything either branch can produce.
Equations
Instances For
Used by
Lean2Js.Bound.Range.ofBin
sourceEquations
- One or more equations did not get rendered due to their size.
- Lean2Js.Bound.Range.ofBin Lean2Js.Core.BinOp.min x✝¹ x✝ = { lo := Lean2Js.Bound.both✝ min x✝¹.lo x✝.lo, hi := Lean2Js.Bound.tighter✝ min x✝¹.hi x✝.hi }
- Lean2Js.Bound.Range.ofBin Lean2Js.Core.BinOp.max x✝¹ x✝ = { lo := Lean2Js.Bound.tighter✝ max x✝¹.lo x✝.lo, hi := Lean2Js.Bound.both✝ max x✝¹.hi x✝.hi }
- Lean2Js.Bound.Range.ofBin x✝² x✝¹ x✝ = Lean2Js.Bound.Range.unknown
Instances For
Used by
Lean2Js.Bound.Range.ofUn
sourceEquations
- Lean2Js.Bound.Range.ofUn Lean2Js.Core.UnOp.neg x✝ = { lo := Option.map (fun (x : Int) => -x) x✝.hi, hi := Option.map (fun (x : Int) => -x) x✝.lo }
- Lean2Js.Bound.Range.ofUn Lean2Js.Core.UnOp.abs x✝ = { lo := some 0, hi := Lean2Js.Bound.both✝ (fun (x y : Int) => Int.ofNat (max x.natAbs y.natAbs)) x✝.lo x✝.hi }
- Lean2Js.Bound.Range.ofUn x✝¹ x✝ = Lean2Js.Bound.Range.unknown
Instances For
Used by
Lean2Js.Bound.Env
sourceRanges the program text has pinned to a name. A binder that shadows one drops it rather than letting the body read through to the outer value.
Equations
Instances For
Used by
Lean2Js.Bound.Env.without
sourceEquations
- env.without names = List.filter (fun (e : String × Lean2Js.Bound.Range) => !names.contains e.fst) env
Instances For
Used by
Lean2Js.Bound.Env.at
sourceEquations
- env.at name = (List.lookup name env).getD Lean2Js.Bound.Range.unknown
Instances For
Used by
Lean2Js.Bound.patBinds
sourceEquations
Instances For
Used by
Lean2Js.Bound.patBindsList
sourceEquations
Instances For
Used by
Lean2Js.Bound.rangeOf
sourceWhat the syntax says about an Int53 expression. A length is never negative and has no upper bound
the text can name; Int53.div and % are read as unknown, which only ever refuses more.
Equations
- Lean2Js.Bound.rangeOf env (Lean2Js.Core.Expr.lit (Lean2Js.Core.Lit.int53 i)) = Lean2Js.Bound.Range.exact i
- Lean2Js.Bound.rangeOf env (Lean2Js.Core.Expr.var x_1) = env.at x_1
- Lean2Js.Bound.rangeOf env arr.length = { lo := some 0, hi := none }
- Lean2Js.Bound.rangeOf env (Lean2Js.Core.Expr.un op x_1) = Lean2Js.Bound.Range.ofUn op (Lean2Js.Bound.rangeOf env x_1)
- Lean2Js.Bound.rangeOf env (Lean2Js.Core.Expr.bin op a b) = Lean2Js.Bound.Range.ofBin op (Lean2Js.Bound.rangeOf env a) (Lean2Js.Bound.rangeOf env b)
- Lean2Js.Bound.rangeOf env (c.cond t e) = (Lean2Js.Bound.rangeOf env t).union (Lean2Js.Bound.rangeOf env e)
- Lean2Js.Bound.rangeOf env (Lean2Js.Core.Expr.letE n ty v b) = Lean2Js.Bound.rangeOf ((n, Lean2Js.Bound.rangeOf env v) :: env.without [n]) b
- Lean2Js.Bound.rangeOf env (scrut.matchE alts) = Lean2Js.Bound.rangeOfAlts env alts
- Lean2Js.Bound.rangeOf env x✝ = Lean2Js.Bound.Range.unknown
Instances For
Used by
Lean2Js.Bound.rangeOfAlts
sourceEquations
- Lean2Js.Bound.rangeOfAlts env [] = Lean2Js.Bound.Range.unknown
- Lean2Js.Bound.rangeOfAlts env [a] = Lean2Js.Bound.rangeOf (env.without (Lean2Js.Bound.patBinds a.fst)) a.snd
- Lean2Js.Bound.rangeOfAlts env (a :: rest) = (Lean2Js.Bound.rangeOf (env.without (Lean2Js.Bound.patBinds a.fst)) a.snd).union (Lean2Js.Bound.rangeOfAlts env rest)
Instances For
Used by
Lean2Js.Bound.repeatBound
sourceHow many copies of a base string an expression can hold, once every Str.repeat inside it has
multiplied. A name stands for whatever the caller passes, which is one copy of itself.
Equations
- One or more equations did not get rendered due to their size.
- Lean2Js.Bound.repeatBound env (s.substring lo hi) = Lean2Js.Bound.repeatBound env s
- Lean2Js.Bound.repeatBound env (Lean2Js.Core.Expr.strUn op s) = Lean2Js.Bound.repeatBound env s
- Lean2Js.Bound.repeatBound env (c.cond t e) = match Lean2Js.Bound.repeatBound env t, Lean2Js.Bound.repeatBound env e with | some x, some y => some (max x y) | x, x_1 => none
- Lean2Js.Bound.repeatBound env (Lean2Js.Core.Expr.letE n ty v b) = Lean2Js.Bound.repeatBound ((n, Lean2Js.Bound.rangeOf env v) :: env.without [n]) b
- Lean2Js.Bound.repeatBound env (scrut.matchE alts) = Lean2Js.Bound.repeatBoundAlts env alts
- Lean2Js.Bound.repeatBound env (scrut.foldE typeName tyArgs result alts) = none
- Lean2Js.Bound.repeatBound env x✝ = some 1
Instances For
Used by
Lean2Js.Bound.repeatBoundAlts
sourceEquations
- One or more equations did not get rendered due to their size.
- Lean2Js.Bound.repeatBoundAlts env [] = some 1
Instances For
Used by
Lean2Js.Bound.Sized
sourceWhich of the two a refusal is about, so that it can name the operation the author wrote and the clamp that would fix it.
Instances For
Used by
Lean2Js.Bound.instReprSized.repr
sourceEquations
- One or more equations did not get rendered due to their size.
Instances For
Used by
Lean2Js.Bound.instReprSized
sourceEquations
- Lean2Js.Bound.instReprSized = { reprPrec := Lean2Js.Bound.instReprSized.repr }
Used by
Lean2Js.Bound.instBEqSized.beq
sourceEquations
- Lean2Js.Bound.instBEqSized.beq x✝ y✝ = (x✝.ctorIdx == y✝.ctorIdx)
Instances For
Used by
Lean2Js.Bound.instBEqSized
sourceEquations
Used by
Lean2Js.Bound.instInhabitedSized
sourceEquations
Used by
Lean2Js.Bound.arrayBound
sourceHow many times the text says a traversal over this array runs. none is the checker declining to
say, and that is the ordinary answer: an array a caller passes is as long as the vector generator made
it, which is what bounds a body that repeats per element. An Arr.range is the exception -- its length
is in the text -- so it is the one traversal whose body has to be counted against the ceiling as many
times as it runs.
Equations
- Lean2Js.Bound.arrayBound env (Lean2Js.Core.Expr.un Lean2Js.Core.UnOp.range n) = Option.map (fun (x : Int) => max x 0) (Lean2Js.Bound.rangeOf env n).hi
- Lean2Js.Bound.arrayBound env (Lean2Js.Core.Expr.arrayLit elem items) = some ↑items.length
- Lean2Js.Bound.arrayBound env a.arrayReverse = Lean2Js.Bound.arrayBound env a
- Lean2Js.Bound.arrayBound env (a.sortByKeyE binder body) = Lean2Js.Bound.arrayBound env a
- Lean2Js.Bound.arrayBound env (a.mapE binder body) = Lean2Js.Bound.arrayBound env a
- Lean2Js.Bound.arrayBound env x✝ = none
Instances For
Used by
Lean2Js.Bound.times
sourceWhat one traversal multiplies the size its body asks for by.
Equations
- Lean2Js.Bound.times env arr = (Lean2Js.Bound.arrayBound env arr).getD 1
Instances For
Used by
Lean2Js.Bound.unboundedIn
sourceThe first result in a body whose size the text does not bound, which of the two it is, and how far past the bound it reaches when the text does bound it.
factor is how many times the traversals above this point can run it. A body inside a traversal over an
Arr.range 64 builds sixty-four of whatever it builds, so what is measured against the ceiling is the
product rather than one result.
Equations
- One or more equations did not get rendered due to their size.
- Lean2Js.Bound.unboundedIn factor env (Lean2Js.Core.Expr.lit l) = none
- Lean2Js.Bound.unboundedIn factor env (Lean2Js.Core.Expr.var name) = none
- Lean2Js.Bound.unboundedIn factor env (Lean2Js.Core.Expr.fnRef name) = none
- Lean2Js.Bound.unboundedIn factor env (Lean2Js.Core.Expr.noneE elem) = none
- Lean2Js.Bound.unboundedIn factor env (Lean2Js.Core.Expr.un op x_1) = Lean2Js.Bound.unboundedIn factor env x_1
- Lean2Js.Bound.unboundedIn factor env (Lean2Js.Core.Expr.strUn op x_1) = Lean2Js.Bound.unboundedIn factor env x_1
- Lean2Js.Bound.unboundedIn factor env x_1.someE = Lean2Js.Bound.unboundedIn factor env x_1
- Lean2Js.Bound.unboundedIn factor env (Lean2Js.Core.Expr.okE err x_1) = Lean2Js.Bound.unboundedIn factor env x_1
- Lean2Js.Bound.unboundedIn factor env (Lean2Js.Core.Expr.errorE ok x_1) = Lean2Js.Bound.unboundedIn factor env x_1
- Lean2Js.Bound.unboundedIn factor env (x_1.proj field) = Lean2Js.Bound.unboundedIn factor env x_1
- Lean2Js.Bound.unboundedIn factor env x_1.length = Lean2Js.Bound.unboundedIn factor env x_1
- Lean2Js.Bound.unboundedIn factor env x_1.arrayReverse = Lean2Js.Bound.unboundedIn factor env x_1
- Lean2Js.Bound.unboundedIn factor env x_1.dictKeys = Lean2Js.Bound.unboundedIn factor env x_1
- Lean2Js.Bound.unboundedIn factor env x_1.dictValues = Lean2Js.Bound.unboundedIn factor env x_1
- Lean2Js.Bound.unboundedIn factor env (Lean2Js.Core.Expr.bin op a b) = (Lean2Js.Bound.unboundedIn factor env a <|> Lean2Js.Bound.unboundedIn factor env b)
- Lean2Js.Bound.unboundedIn factor env (Lean2Js.Core.Expr.strBin op a b) = (Lean2Js.Bound.unboundedIn factor env a <|> Lean2Js.Bound.unboundedIn factor env b)
- Lean2Js.Bound.unboundedIn factor env (a.index b) = (Lean2Js.Bound.unboundedIn factor env a <|> Lean2Js.Bound.unboundedIn factor env b)
- Lean2Js.Bound.unboundedIn factor env (a.dictGet b) = (Lean2Js.Bound.unboundedIn factor env a <|> Lean2Js.Bound.unboundedIn factor env b)
- Lean2Js.Bound.unboundedIn factor env (a.dictHas b) = (Lean2Js.Bound.unboundedIn factor env a <|> Lean2Js.Bound.unboundedIn factor env b)
- Lean2Js.Bound.unboundedIn factor env (a.dictDelete b) = (Lean2Js.Bound.unboundedIn factor env a <|> Lean2Js.Bound.unboundedIn factor env b)
- Lean2Js.Bound.unboundedIn factor env (a.mapE x_1 b) = (Lean2Js.Bound.unboundedIn factor env a <|> Lean2Js.Bound.unboundedIn (factor * Lean2Js.Bound.times env a) (env.without [x_1]) b)
- Lean2Js.Bound.unboundedIn factor env (a.filterE x_1 b) = (Lean2Js.Bound.unboundedIn factor env a <|> Lean2Js.Bound.unboundedIn (factor * Lean2Js.Bound.times env a) (env.without [x_1]) b)
- Lean2Js.Bound.unboundedIn factor env (a.findE x_1 b) = (Lean2Js.Bound.unboundedIn factor env a <|> Lean2Js.Bound.unboundedIn (factor * Lean2Js.Bound.times env a) (env.without [x_1]) b)
- Lean2Js.Bound.unboundedIn factor env (a.sortByKeyE x_1 b) = (Lean2Js.Bound.unboundedIn factor env a <|> Lean2Js.Bound.unboundedIn (factor * Lean2Js.Bound.times env a) (env.without [x_1]) b)
- Lean2Js.Bound.unboundedIn factor env (a.cond b c) = (Lean2Js.Bound.unboundedIn factor env a <|> Lean2Js.Bound.unboundedIn factor env b <|> Lean2Js.Bound.unboundedIn factor env c)
- Lean2Js.Bound.unboundedIn factor env (a.substring b c) = (Lean2Js.Bound.unboundedIn factor env a <|> Lean2Js.Bound.unboundedIn factor env b <|> Lean2Js.Bound.unboundedIn factor env c)
- Lean2Js.Bound.unboundedIn factor env (a.arraySlice b c) = (Lean2Js.Bound.unboundedIn factor env a <|> Lean2Js.Bound.unboundedIn factor env b <|> Lean2Js.Bound.unboundedIn factor env c)
- Lean2Js.Bound.unboundedIn factor env (a.dictSet b c) = (Lean2Js.Bound.unboundedIn factor env a <|> Lean2Js.Bound.unboundedIn factor env b <|> Lean2Js.Bound.unboundedIn factor env c)
- Lean2Js.Bound.unboundedIn factor env (Lean2Js.Core.Expr.ctor typeName tyArgs ctorName args) = Lean2Js.Bound.unboundedInList factor env args
- Lean2Js.Bound.unboundedIn factor env (Lean2Js.Core.Expr.arrayLit elem args) = Lean2Js.Bound.unboundedInList factor env args
- Lean2Js.Bound.unboundedIn factor env (Lean2Js.Core.Expr.call fn args) = Lean2Js.Bound.unboundedInList factor env args
- Lean2Js.Bound.unboundedIn factor env (Lean2Js.Core.Expr.dictLit value obj entries) = Lean2Js.Bound.unboundedInEntries factor env entries
- Lean2Js.Bound.unboundedIn factor env (scrut.matchE alts) = (Lean2Js.Bound.unboundedIn factor env scrut <|> Lean2Js.Bound.unboundedInAlts factor env alts)
- Lean2Js.Bound.unboundedIn factor env (scrut.foldE typeName tyArgs result alts) = (Lean2Js.Bound.unboundedIn factor env scrut <|> Lean2Js.Bound.unboundedInAlts factor env alts)
Instances For
Used by
Lean2Js.Bound.unboundedInList
sourceEquations
- Lean2Js.Bound.unboundedInList factor env [] = none
- Lean2Js.Bound.unboundedInList factor env (e :: rest) = (Lean2Js.Bound.unboundedIn factor env e <|> Lean2Js.Bound.unboundedInList factor env rest)
Instances For
Used by
Lean2Js.Bound.unboundedInAlts
sourceEquations
- Lean2Js.Bound.unboundedInAlts factor env [] = none
- Lean2Js.Bound.unboundedInAlts factor env (a :: rest) = (Lean2Js.Bound.unboundedIn factor (env.without (Lean2Js.Bound.patBinds a.fst)) a.snd <|> Lean2Js.Bound.unboundedInAlts factor env rest)
Instances For
Used by
Lean2Js.Bound.unboundedInEntries
sourceEquations
- Lean2Js.Bound.unboundedInEntries factor env [] = none
- Lean2Js.Bound.unboundedInEntries factor env (e :: rest) = (Lean2Js.Bound.unboundedIn factor env e.snd <|> Lean2Js.Bound.unboundedInEntries factor env rest)
Instances For
Used by
Lean2Js.Bound.refusal
sourceWhat the refusal says about one result the text does not bound. Str.padStart is named alongside
Str.repeat because that is the spelling a user wrote; the repeat only appears once it expands.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Used by
Lean2Js.Bound.programBounded
sourceEvery result a program can reach whose size a value decides, bounded by the text. The parameters start unknown, which is what makes a size a caller chooses the thing this refuses.
Equations
- One or more equations did not get rendered due to their size.