lean2js

Lean2Js.HelperSem

source

The semantics of the fragment the runtime helpers are written in #

The semantics of the fragment the runtime helpers are written in.

What this model assumes about JavaScript #

Everything the helpers borrow from the platform is in prim, method, binOp, field and index below, and nowhere else. Each is defined only where a helper actually reaches for it and is stuck elsewhere, so an assumption that is never used cannot be smuggled in.

Three of them are worth stating out loud.

  • An iterator is the array of its elements. d.keys() yields the keys and Array.from on an array is the identity, so Array.from(d.keys()) is the list of keys. The model does not distinguish an iterator from the array it produces, because nothing in the fragment can observe the difference.
  • A number prints in decimal. String(n) falls back to exponent notation at 1e21, so the model answers only inside the Int53 range, which is below it.
  • A quotient is truncated before anything looks at it. / on two numbers yields quot a b, which only Math.trunc accepts. Real JavaScript computes a double there; the truncation agrees with exact integer division whenever the numerator is below 2^53, which the one caller (__u32div) guarantees. __i53div goes through BigInt precisely because it cannot.

=== on objects, arrays and maps is false, matching JsSem.arith: this model has no references. The one helper that compares non-scalars with === is __eq, whose structural path returns the same answer the reference path would. Functions are the exception: a value of a function type is a reference to a top-level function, so === on two of them is decided by the name, and __eq has no structural path to fall back on.

inductive

Lean2Js.HelperSem.Val

source

The values the fragment computes with: the ones JsSem has, plus the ones only hand-written code meets — null and undefined reach __ck from the caller, and a function value reaches __map.

Instances For
    Used by
      instance

      Lean2Js.HelperSem.instInhabitedVal

      source
      @[instance_reducible]
      Equations
      Used by
        abbrev

        Lean2Js.HelperSem.Env

        source
        @[reducible, inline]
        Equations
        Instances For
          Used by
            inductive

            Lean2Js.HelperSem.Res

            source
            (α : Type) :

            stuck is the model declining to answer: a shape no helper produces. It is not an error the generated code can observe, and a theorem about a helper has to rule it out rather than accept it.

            Instances For
              Used by
                instance

                Lean2Js.HelperSem.instInhabitedRes

                source
                @[instance_reducible]
                {a✝ : Type} :
                Inhabited (Res a✝)
                Equations
                Used by
                  def

                  Lean2Js.HelperSem.Res.bind

                  source
                  {α β : Type} (r : Res α) (k : α → Res β) :
                  Res β
                  Equations
                  Instances For
                    Used by
                      instance

                      Lean2Js.HelperSem.instMonadRes

                      source
                      @[instance_reducible]
                      Equations
                      • One or more equations did not get rendered due to their size.
                      Used by

                        Values #

                        def

                        Lean2Js.HelperSem.ofJs

                        source
                        @[irreducible]
                        Equations
                        Instances For
                          Used by
                            def

                            Lean2Js.HelperSem.ofJsList

                            source
                            @[irreducible]
                            Equations
                            Instances For
                              Used by
                                def

                                Lean2Js.HelperSem.ofJsFields

                                source
                                @[irreducible]
                                Equations
                                Instances For
                                  Used by
                                    def

                                    Lean2Js.HelperSem.typeOf

                                    source
                                    :
                                    Equations
                                    Instances For
                                      Used by
                                        def

                                        Lean2Js.HelperSem.strictEq

                                        source
                                        :
                                        Val → Val → Bool

                                        ===. Across two types it is always false, so a number never equals a bigint. Two references to the same top-level function are the same object, so those compare by name; the model has no other references, and the values that carry one compare as unequal here.

                                        Equations
                                        Instances For
                                          Used by

                                            What the fragment borrows from JavaScript #

                                            def

                                            Lean2Js.HelperSem.toInt32

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

                                                Lean2Js.HelperSem.imul

                                                source
                                                (a b : Int) :

                                                Math.imul: both arguments truncated to int32, multiplied, truncated again.

                                                Equations
                                                Instances For
                                                  Used by
                                                    def

                                                    Lean2Js.HelperSem.keep

                                                    source
                                                    Equations
                                                    Instances For
                                                      Used by
                                                        def

                                                        Lean2Js.HelperSem.numOf

                                                        source
                                                        :
                                                        Equations
                                                        Instances For
                                                          Used by
                                                            def

                                                            Lean2Js.HelperSem.compareOp

                                                            source
                                                            (op : String) :
                                                            Val → Val → Res Val

                                                            Comparison. Mixing a number and a bigint is mathematical, the way JS defines it; strings compare by code point, the assumption JsSem.arith already makes.

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

                                                                Lean2Js.HelperSem.binOp

                                                                source
                                                                (op : String) (a b : Val) :
                                                                Equations
                                                                Instances For
                                                                  Used by
                                                                    def

                                                                    Lean2Js.HelperSem.mapSet

                                                                    source
                                                                    (es : List (String × Val)) (key : String) (v : Val) :
                                                                    Equations
                                                                    • One or more equations did not get rendered due to their size.
                                                                    Instances For
                                                                      Used by
                                                                        def

                                                                        Lean2Js.HelperSem.mapSetAll

                                                                        source

                                                                        What a Map filled from a list of entries holds: each one set in the order the list carries them. A later entry under a key an earlier one already took replaces it, at the place the earlier one had.

                                                                        Equations
                                                                        Instances For
                                                                          Used by
                                                                            def

                                                                            Lean2Js.HelperSem.fromPairs

                                                                            source
                                                                            (acc : List (String × Val)) :

                                                                            What Object.fromEntries builds: the pairs written in order, a later one replacing an earlier one that carries the same key, which is where it parts company with a plain List.

                                                                            Equations
                                                                            Instances For
                                                                              Used by
                                                                                def

                                                                                Lean2Js.HelperSem.prim

                                                                                source
                                                                                (name : String) (args : List Val) :
                                                                                Equations
                                                                                Instances For
                                                                                  Used by
                                                                                    def

                                                                                    Lean2Js.HelperSem.lookupV

                                                                                    source
                                                                                    (es : List (String × Val)) (k : String) :

                                                                                    Looking a key up in an object or a dictionary: the first entry that carries it, undefined when none does. Duplicate keys are the caller's problem, not this model's — Object.keys and Map both answer from the first match.

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

                                                                                        Lean2Js.HelperSem.joinStrs

                                                                                        source
                                                                                        Equations
                                                                                        Instances For
                                                                                          Used by
                                                                                            def

                                                                                            Lean2Js.HelperSem.upperOne

                                                                                            source
                                                                                            Equations
                                                                                            Instances For
                                                                                              Used by
                                                                                                def

                                                                                                Lean2Js.HelperSem.lowerOne

                                                                                                source
                                                                                                Equations
                                                                                                Instances For
                                                                                                  Used by
                                                                                                    def

                                                                                                    Lean2Js.HelperSem.method

                                                                                                    source
                                                                                                    (recv : Val) (name : String) (args : List Val) :

                                                                                                    The methods the helpers call. toUpperCase and toLowerCase are defined only on the single ASCII letters the callers guard for: the full Unicode mappings are what the helpers exist to avoid.

                                                                                                    Equations
                                                                                                    Instances For
                                                                                                      Used by
                                                                                                        def

                                                                                                        Lean2Js.HelperSem.field

                                                                                                        source
                                                                                                        (recv : Val) (name : String) :
                                                                                                        Equations
                                                                                                        Instances For
                                                                                                          Used by
                                                                                                            def

                                                                                                            Lean2Js.HelperSem.index

                                                                                                            source
                                                                                                            (recv i : Val) :

                                                                                                            x[k] for a string k is x.k, so it reads the same way field does: the helpers index an object with a key the descriptor carries, and a Map answers such a read out of its prototype rather than out of its entries.

                                                                                                            Equations
                                                                                                            Instances For
                                                                                                              Used by

                                                                                                                The evaluator #

                                                                                                                inductive

                                                                                                                Lean2Js.HelperSem.Outcome

                                                                                                                source

                                                                                                                What a statement list did. A block's own declarations do not escape it, but an assignment to a binding the block did not make does — restore is what tells the two apart.

                                                                                                                Instances For
                                                                                                                  Used by
                                                                                                                    def

                                                                                                                    Lean2Js.HelperSem.lookup

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

                                                                                                                        Lean2Js.HelperSem.update

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

                                                                                                                            Lean2Js.HelperSem.restore

                                                                                                                            source
                                                                                                                            (outer inner : Env) :
                                                                                                                            Equations
                                                                                                                            Instances For
                                                                                                                              Used by
                                                                                                                                def

                                                                                                                                Lean2Js.HelperSem.bindAll

                                                                                                                                source
                                                                                                                                :
                                                                                                                                Equations
                                                                                                                                Instances For
                                                                                                                                  Used by
                                                                                                                                    abbrev

                                                                                                                                    Lean2Js.HelperSem.Ext

                                                                                                                                    source
                                                                                                                                    @[reducible, inline]

                                                                                                                                    ext is how a function the generated code passed in gets called: __map is handed one, and the model of the generated code decides what it does.

                                                                                                                                    Equations
                                                                                                                                    Instances For
                                                                                                                                      Used by
                                                                                                                                        def

                                                                                                                                        Lean2Js.HelperSem.evalExpr

                                                                                                                                        source
                                                                                                                                        @[irreducible]
                                                                                                                                        (ext : Ext) (fuel : Nat) (env : Env) (e : Helper.Expr) :
                                                                                                                                        Equations
                                                                                                                                        Instances For
                                                                                                                                          Used by
                                                                                                                                            def

                                                                                                                                            Lean2Js.HelperSem.evalArgs

                                                                                                                                            source
                                                                                                                                            @[irreducible]
                                                                                                                                            (ext : Ext) (fuel : Nat) (env : Env) (es : List Helper.Expr) :
                                                                                                                                            Equations
                                                                                                                                            Instances For
                                                                                                                                              Used by
                                                                                                                                                def

                                                                                                                                                Lean2Js.HelperSem.evalStmts

                                                                                                                                                source
                                                                                                                                                @[irreducible]
                                                                                                                                                (ext : Ext) (fuel : Nat) (env : Env) (ss : List Helper.Stmt) :
                                                                                                                                                Equations
                                                                                                                                                Instances For
                                                                                                                                                  Used by
                                                                                                                                                    def

                                                                                                                                                    Lean2Js.HelperSem.evalFor

                                                                                                                                                    source
                                                                                                                                                    @[irreducible]
                                                                                                                                                    (ext : Ext) (fuel : Nat) (env : Env) (binder : String) (xs : List Val) (body : List Helper.Stmt) :
                                                                                                                                                    Equations
                                                                                                                                                    Instances For
                                                                                                                                                      Used by
                                                                                                                                                        def

                                                                                                                                                        Lean2Js.HelperSem.callDef

                                                                                                                                                        source
                                                                                                                                                        @[irreducible]
                                                                                                                                                        (ext : Ext) (fuel : Nat) (name : String) (args : List Val) :
                                                                                                                                                        Equations
                                                                                                                                                        Instances For
                                                                                                                                                          Used by
                                                                                                                                                            def

                                                                                                                                                            Lean2Js.HelperSem.applyVal

                                                                                                                                                            source
                                                                                                                                                            @[irreducible]
                                                                                                                                                            (ext : Ext) (fuel : Nat) (fn : Val) (args : List Val) :
                                                                                                                                                            Equations
                                                                                                                                                            Instances For
                                                                                                                                                              Used by
                                                                                                                                                                def

                                                                                                                                                                Lean2Js.HelperSem.Eventually

                                                                                                                                                                source
                                                                                                                                                                (g : Nat → Res Val) (r : Res Val) :

                                                                                                                                                                "With enough fuel". The fuel is the model's device for totality, so a claim about a helper is stated for every large enough amount, the way the claims about the generated code already are.

                                                                                                                                                                Equations
                                                                                                                                                                Instances For
                                                                                                                                                                  Used by
                                                                                                                                                                    def

                                                                                                                                                                    Lean2Js.HelperSem.Helper.Calls

                                                                                                                                                                    source
                                                                                                                                                                    (ext : Ext) (name : String) (args : List Val) (r : Res Val) :

                                                                                                                                                                    What a helper call means: __name(args) settles on r once the fuel is large enough.

                                                                                                                                                                    Equations
                                                                                                                                                                    Instances For
                                                                                                                                                                      Used by