Documentation

PolyFun.PFunctor.Free.Cost.Measured

Measured programs and budgeted carriers #

Measured programs. A MeasuredProgram Input Result ω computes a function by a free program whose interface depends on a view of the input:

run interprets the program through the deterministic answers, and is the output of the one path they pick (run_eq_output). Realizes f says the run computes f, and CostAtMost B bounds the charge of every completed path of every view's program, so signed prices are allowed. ofFun f computes f with no operations at cost 0.

comp outer inner runs inner, computes outer's view from the actual intermediate result, and runs outer. It does this on the sum of the two interfaces, each operation tagged with the view it belongs to, keeping both price lists. It computes the composite (run_comp, Realizes.comp), and its budgets add (CostAtMost.comp). contramap precomposes an uncharged map on inputs. A BudgetedProgram f ω bundles a measured program realizing f with a budget, and composes the same way.

Budgeted carriers. Budgeted c B α is the subtype of free programs within budget B. With budgets graded by Multiplicative ω, it is a GradedMonad: gbind adds budgets.

Measured programs #

structure PFunctor.FreeM.MeasuredProgram (Input : Type uI) (Result : Type u) (ω : Type w) :
Type (max (max (u + 1) uI) w)

A function computed by a free program over an interface that depends on an uncharged view of the input, answered deterministically, with a price per operation.

Only the operations are charged. The view, the answering function and the code between calls are free at this layer, so ofFun f realizes any f at cost 0: a statement of the form ∃ M, M.Realizes f ∧ M.CostAtMost B is trivial. Cost statements name the measured program, and the uncharged parts are bounded one layer down.

  • View : Type u

    What the program is allowed to depend on.

  • view : Input → self.View

    The uncharged view of an input.

  • Op : Type u

    The operations the program may call.

  • spec : self.View → self.Op → Type u

    The answers to an operation, which may depend on the view.

  • program (v : self.View) : { A := self.Op, B := self.spec v }.FreeM Result

    The program of each view.

  • answer (v : self.View) (o : self.Op) : self.spec v o

    The deterministic answers of each view.

  • cost : self.Op → ω

    The price of each operation.

Instances For
    def PFunctor.FreeM.MeasuredProgram.run {Input : Type uI} {Result : Type u} {ω : Type w} (M : MeasuredProgram Input Result ω) (i : Input) :
    Result

    Run the program of the input's view, answering every call deterministically.

    Equations
    Instances For
      theorem PFunctor.FreeM.MeasuredProgram.run_eq_output {Input : Type uI} {Result : Type u} {ω : Type w} (M : MeasuredProgram Input Result ω) (i : Input) :
      M.run i = (M.program (M.view i)).output (Path.ofHandler (M.answer (M.view i)) (M.program (M.view i)))

      The run is the output of the path the answers pick.

      def PFunctor.FreeM.MeasuredProgram.Realizes {Input : Type uI} {Result : Type u} {ω : Type w} (M : MeasuredProgram Input Result ω) (f : Input → Result) :

      The program computes f.

      Equations
      Instances For
        def PFunctor.FreeM.MeasuredProgram.CostAtMost {Input : Type uI} {Result : Type u} {ω : Type w} [Add ω] [Zero ω] [LE ω] (M : MeasuredProgram Input Result ω) (B : ω) :

        Every completed path of every view's program costs at most B.

        Equations
        Instances For
          theorem PFunctor.FreeM.MeasuredProgram.CostAtMost.mono {Input : Type uI} {Result : Type u} {ω : Type w} [Add ω] [Zero ω] [Preorder ω] {M : MeasuredProgram Input Result ω} {B B' : ω} (h : M.CostAtMost B) (hB : B ≤ B') :

          A cost bound holds for every larger budget.

          def PFunctor.FreeM.MeasuredProgram.ofFun {Result : Type u} {ω : Type w} {Input : Type u} (f : Input → Result) :
          MeasuredProgram Input Result ω

          The program with no operations that computes f on its whole input. Its view is the input, so the input shares the result's universe.

          Equations
          • One or more equations did not get rendered due to their size.
          Instances For
            theorem PFunctor.FreeM.MeasuredProgram.realizes_ofFun {Result : Type u} {ω : Type w} {Input : Type u} (f : Input → Result) :
            theorem PFunctor.FreeM.MeasuredProgram.costAtMost_ofFun {Result : Type u} {ω : Type w} [Add ω] [Zero ω] [Preorder ω] {Input : Type u} (f : Input → Result) :

            A program with no operations costs nothing.

            def PFunctor.FreeM.MeasuredProgram.CompSpec {Input : Type uI} {Mid Result : Type u} {ω : Type w} (outer : MeasuredProgram Mid Result ω) (inner : MeasuredProgram Input Mid ω) :
            inner.View → (_ : inner.View) × inner.Op ⊕ (_ : outer.View) × outer.Op → Type u

            The answers of the composite interface, which does not depend on the view: each operation is tagged with the view it belongs to, inner's or outer's.

            Equations
            Instances For
              def PFunctor.FreeM.MeasuredProgram.innerLens {Input : Type uI} {Mid Result : Type u} {ω : Type w} (outer : MeasuredProgram Mid Result ω) (inner : MeasuredProgram Input Mid ω) (v : inner.View) :
              { A := inner.Op, B := inner.spec v }.Lens { A := (_ : inner.View) × inner.Op ⊕ (_ : outer.View) × outer.Op, B := outer.CompSpec inner v }

              The inclusion of inner's interface at view v into the composite interface.

              Equations
              • One or more equations did not get rendered due to their size.
              Instances For
                def PFunctor.FreeM.MeasuredProgram.outerLens {Input : Type uI} {Mid Result : Type u} {ω : Type w} (outer : MeasuredProgram Mid Result ω) (inner : MeasuredProgram Input Mid ω) (v : inner.View) (v' : outer.View) :
                { A := outer.Op, B := outer.spec v' }.Lens { A := (_ : inner.View) × inner.Op ⊕ (_ : outer.View) × outer.Op, B := outer.CompSpec inner v }

                The inclusion of outer's interface at view v' into the composite interface.

                Equations
                • One or more equations did not get rendered due to their size.
                Instances For
                  def PFunctor.FreeM.MeasuredProgram.comp {Input : Type uI} {Mid Result : Type u} {ω : Type w} (outer : MeasuredProgram Mid Result ω) (inner : MeasuredProgram Input Mid ω) :
                  MeasuredProgram Input Result ω

                  Run inner, compute outer's view from the actual intermediate result without charging it, and run outer, on the sum of the two interfaces, each operation tagged with its view, with both price lists.

                  Equations
                  • One or more equations did not get rendered due to their size.
                  Instances For
                    theorem PFunctor.FreeM.MeasuredProgram.run_comp {Input : Type uI} {Mid Result : Type u} {ω : Type w} (outer : MeasuredProgram Mid Result ω) (inner : MeasuredProgram Input Mid ω) (i : Input) :
                    (outer.comp inner).run i = outer.run (inner.run i)

                    The composite computes the composite function.

                    theorem PFunctor.FreeM.MeasuredProgram.Realizes.comp {Input : Type uI} {Mid Result : Type u} {ω : Type w} {outer : MeasuredProgram Mid Result ω} {inner : MeasuredProgram Input Mid ω} {f : Input → Mid} {g : Mid → Result} (hg : outer.Realizes g) (hf : inner.Realizes f) :
                    (outer.comp inner).Realizes (g ∘ f)

                    The composite realizes the composite function.

                    theorem PFunctor.FreeM.MeasuredProgram.CostAtMost.comp {Input : Type uI} {Mid Result : Type u} {ω : Type w} [AddMonoid ω] [Preorder ω] [AddLeftMono ω] [AddRightMono ω] {outer : MeasuredProgram Mid Result ω} {inner : MeasuredProgram Input Mid ω} {outerBudget innerBudget : ω} (ho : outer.CostAtMost outerBudget) (hi : inner.CostAtMost innerBudget) :
                    (outer.comp inner).CostAtMost (innerBudget + outerBudget)

                    Composite budgets add: the inner budget, then the outer one. Arguments come in the order of comp, outer first.

                    def PFunctor.FreeM.MeasuredProgram.contramap {Input : Type uI} {Result : Type u} {ω : Type w} {Input' : Type uI'} (M : MeasuredProgram Input Result ω) (g : Input' → Input) :
                    MeasuredProgram Input' Result ω

                    Precompose with an uncharged map on inputs.

                    Equations
                    Instances For
                      theorem PFunctor.FreeM.MeasuredProgram.run_contramap {Input : Type uI} {Result : Type u} {ω : Type w} {Input' : Type uI'} (M : MeasuredProgram Input Result ω) (g : Input' → Input) (i : Input') :
                      (M.contramap g).run i = M.run (g i)
                      theorem PFunctor.FreeM.MeasuredProgram.Realizes.contramap {Input : Type uI} {Result : Type u} {ω : Type w} {Input' : Type uI'} {M : MeasuredProgram Input Result ω} {f : Input → Result} (h : M.Realizes f) (g : Input' → Input) :
                      (M.contramap g).Realizes (f ∘ g)
                      theorem PFunctor.FreeM.MeasuredProgram.CostAtMost.contramap {Input : Type uI} {Result : Type u} {ω : Type w} [Add ω] [Zero ω] [LE ω] {Input' : Type uI'} {M : MeasuredProgram Input Result ω} {B : ω} (h : M.CostAtMost B) (g : Input' → Input) :
                      structure PFunctor.FreeM.BudgetedProgram {Input : Type uI} {Result : Type u} (f : Input → Result) (ω : Type w) [Add ω] [Zero ω] [LE ω] :
                      Type (max (max (u + 1) uI) w)

                      A measured program realizing f, with a budget on every completed path.

                      • program : MeasuredProgram Input Result ω

                        The measured program.

                      • budget : ω

                        The bound on the charge of every completed path.

                      • realizes : self.program.Realizes f

                        The program computes f.

                      • costAtMost : self.program.CostAtMost self.budget

                        Every completed path costs at most the budget.

                      Instances For
                        def PFunctor.FreeM.BudgetedProgram.ofFun {Result : Type u} {ω : Type w} [Add ω] [Zero ω] [Preorder ω] {Input : Type u} (f : Input → Result) :

                        Every function has a budgeted program with budget 0 and no operations.

                        Equations
                        Instances For
                          def PFunctor.FreeM.BudgetedProgram.contramap {Input : Type uI} {Result : Type u} {ω : Type w} [Add ω] [Zero ω] [LE ω] {Input' : Type uI'} {f : Input → Result} (M : BudgetedProgram f ω) (g : Input' → Input) :

                          Precompose with an uncharged map on inputs.

                          Equations
                          Instances For
                            def PFunctor.FreeM.BudgetedProgram.comp {Input : Type uI} {Mid Result : Type u} {ω : Type w} [AddMonoid ω] [Preorder ω] [AddLeftMono ω] [AddRightMono ω] {f : Input → Mid} {g : Mid → Result} (outer : BudgetedProgram g ω) (inner : BudgetedProgram f ω) :

                            Compose budgeted programs; budgets add.

                            Equations
                            Instances For

                              Budgeted carriers #

                              def PFunctor.FreeM.Budgeted {P : PFunctor.{uA, uB}} {ω : Type w} [Add ω] [LE ω] [Zero ω] (c : P.A → ω) (B : Multiplicative ω) (α : Type v) :
                              Type (max uA uB v)

                              Free programs within budget B.

                              Equations
                              Instances For
                                @[instance_reducible]

                                Budgeted programs form a graded monad: sequencing adds budgets.

                                Equations
                                • One or more equations did not get rendered due to their size.