lean2js

Lean2Js.Bound

source

Imports 2

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.

def

Lean2Js.Bound.maxRepeat

source
:

The 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
Instances For
    Used by
      def

      Lean2Js.Bound.maxRange

      source
      :

      The 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
      Instances For
        Used by
          structure

          Lean2Js.Bound.Range

          source

          What 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
              instance

              Lean2Js.Bound.instReprRange

              source
              @[instance_reducible]
              Equations
              Used by
                def

                Lean2Js.Bound.instReprRange.repr

                source
                :
                Equations
                • One or more equations did not get rendered due to their size.
                Instances For
                  Used by
                    instance

                    Lean2Js.Bound.instInhabitedRange

                    source
                    @[instance_reducible]
                    Equations
                    Used by
                      def

                      Lean2Js.Bound.Range.unknown

                      source
                      Equations
                      Instances For
                        Used by
                          def

                          Lean2Js.Bound.Range.exact

                          source
                          (i : Int) :
                          Equations
                          Instances For
                            Used by
                              def

                              Lean2Js.Bound.Range.union

                              source
                              (a b : Range) :

                              Everything either branch can produce.

                              Equations
                              Instances For
                                Used by
                                  def

                                  Lean2Js.Bound.Range.ofBin

                                  source
                                  :
                                  Equations
                                  Instances For
                                    Used by
                                      def

                                      Lean2Js.Bound.Range.ofUn

                                      source
                                      Equations
                                      Instances For
                                        Used by
                                          abbrev

                                          Lean2Js.Bound.Env

                                          source
                                          @[reducible, inline]

                                          Ranges 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
                                              def

                                              Lean2Js.Bound.Env.without

                                              source
                                              (env : Env) (names : List String) :
                                              Equations
                                              Instances For
                                                Used by
                                                  def

                                                  Lean2Js.Bound.Env.at

                                                  source
                                                  (env : Env) (name : String) :
                                                  Equations
                                                  Instances For
                                                    Used by
                                                      def

                                                      Lean2Js.Bound.patBinds

                                                      source
                                                      Equations
                                                      Instances For
                                                        Used by
                                                          def

                                                          Lean2Js.Bound.patBindsList

                                                          source
                                                          Equations
                                                          Instances For
                                                            Used by
                                                              def

                                                              Lean2Js.Bound.rangeOf

                                                              source
                                                              (env : Env) :

                                                              What 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
                                                              Instances For
                                                                Used by
                                                                  def

                                                                  Lean2Js.Bound.rangeOfAlts

                                                                  source
                                                                  (env : Env) :
                                                                  Equations
                                                                  Instances For
                                                                    Used by
                                                                      def

                                                                      Lean2Js.Bound.repeatBound

                                                                      source
                                                                      (env : Env) :

                                                                      How 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
                                                                      Instances For
                                                                        Used by
                                                                          def

                                                                          Lean2Js.Bound.repeatBoundAlts

                                                                          source
                                                                          (env : Env) :
                                                                          Equations
                                                                          Instances For
                                                                            Used by
                                                                              inductive

                                                                              Lean2Js.Bound.Sized

                                                                              source

                                                                              Which 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
                                                                                  def

                                                                                  Lean2Js.Bound.instReprSized.repr

                                                                                  source
                                                                                  :
                                                                                  Equations
                                                                                  • One or more equations did not get rendered due to their size.
                                                                                  Instances For
                                                                                    Used by
                                                                                      instance

                                                                                      Lean2Js.Bound.instReprSized

                                                                                      source
                                                                                      @[instance_reducible]
                                                                                      Equations
                                                                                      Used by
                                                                                        def

                                                                                        Lean2Js.Bound.instBEqSized.beq

                                                                                        source
                                                                                        :
                                                                                        Sized → Sized → Bool
                                                                                        Equations
                                                                                        Instances For
                                                                                          Used by
                                                                                            instance

                                                                                            Lean2Js.Bound.instBEqSized

                                                                                            source
                                                                                            @[instance_reducible]
                                                                                            Equations
                                                                                            Used by
                                                                                              instance

                                                                                              Lean2Js.Bound.instInhabitedSized

                                                                                              source
                                                                                              @[instance_reducible]
                                                                                              Equations
                                                                                              Used by
                                                                                                def

                                                                                                Lean2Js.Bound.arrayBound

                                                                                                source
                                                                                                (env : Env) :

                                                                                                How 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
                                                                                                Instances For
                                                                                                  Used by
                                                                                                    def

                                                                                                    Lean2Js.Bound.times

                                                                                                    source
                                                                                                    (env : Env) (arr : Core.Expr) :

                                                                                                    What one traversal multiplies the size its body asks for by.

                                                                                                    Equations
                                                                                                    Instances For
                                                                                                      Used by
                                                                                                        def

                                                                                                        Lean2Js.Bound.unboundedIn

                                                                                                        source
                                                                                                        (factor : Int) (env : Env) :

                                                                                                        The 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
                                                                                                        Instances For
                                                                                                          Used by
                                                                                                            def

                                                                                                            Lean2Js.Bound.unboundedInList

                                                                                                            source
                                                                                                            (factor : Int) (env : Env) :
                                                                                                            Equations
                                                                                                            Instances For
                                                                                                              Used by
                                                                                                                def

                                                                                                                Lean2Js.Bound.unboundedInAlts

                                                                                                                source
                                                                                                                (factor : Int) (env : Env) :
                                                                                                                Equations
                                                                                                                Instances For
                                                                                                                  Used by
                                                                                                                    def

                                                                                                                    Lean2Js.Bound.unboundedInEntries

                                                                                                                    source
                                                                                                                    (factor : Int) (env : Env) :
                                                                                                                    Equations
                                                                                                                    Instances For
                                                                                                                      Used by
                                                                                                                        def

                                                                                                                        Lean2Js.Bound.refusal

                                                                                                                        source
                                                                                                                        (fn : String) :

                                                                                                                        What 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
                                                                                                                            def

                                                                                                                            Lean2Js.Bound.programBounded

                                                                                                                            source

                                                                                                                            Every 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.
                                                                                                                            Instances For
                                                                                                                              Used by