Documentation

PolyFun.Interaction.Execution.RequestNetwork

FIFO execution of polynomial request clients #

Clients have stable identities and at most one outstanding request. A shared service answers requests in FIFO order; responses travel through the same queue before resuming their client. Each request carries a fresh ticket, and a response resumes only the matching waiting client. Schedules explicitly distinguish client activation from packet delivery. One RPC therefore requires three activations, even when the service computation itself is pure.

The service's monadic effect is atomic at this runtime boundary. Its internal cost is separate from packet-delivery fuel. No fairness or completion assumption is built into finite execution. Typed response traffic uses PolyFun's Interface.RoutedPacket vocabulary.

State.initial starts every client ready, with no traffic and a fresh ticket counter. ClientState.result observes a returned client without discarding the network state.

A client either has executable code or awaits one particular response.

Instances For

    Requests and typed responses share one FIFO queue.

    Instances For

      The complete runtime state, including pending traffic and delivered responses.

      • clients : Client → ClientState p α

        Residual code or the single pending continuation of each static client.

      • service : S

        Private state shared by all calls to the service.

      • queue : List (Envelope Client p)

        Outstanding requests and responses, oldest packet first.

      • nextTicket : ℕ

        Fresh ticket reserved for the next emitted request.

      • transcript : List (Interface.RoutedPacket p Client)

        Responses actually delivered to matching clients, in delivery order.

      Instances For
        def Interaction.Execution.RequestNetwork.State.initial {Client α S : Type} {p : PFunctor.{0, 0}} (programs : Client → p.FreeM α) (service : S) :
        State Client p α S

        Initialize ready clients and a service with no outstanding or delivered traffic.

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

          Observe a completed client without discarding any pending network state.

          Equations
          Instances For
            @[simp]
            theorem Interaction.Execution.RequestNetwork.ClientState.result_waiting {α : Type} {p : PFunctor.{0, 0}} (ticket : ℕ) (query : p.A) (next : p.B query → p.FreeM α) :
            (waiting ticket query next).result = none

            A schedule either activates a client or delivers the oldest queued packet.

            Instances For
              def Interaction.Execution.RequestNetwork.emit {Client α S : Type} {p : PFunctor.{0, 0}} [DecidableEq Client] (id : Client) (state : State Client p α S) :
              State Client p α S

              Emit one request and suspend its client. Waiting and returned clients emit nothing.

              Equations
              • One or more equations did not get rendered due to their size.
              Instances For
                theorem Interaction.Execution.RequestNetwork.emit_ready_pure {Client α S : Type} {p : PFunctor.{0, 0}} [DecidableEq Client] {id : Client} {state : State Client p α S} {value : α} (h : state.clients id = ClientState.ready (pure value)) :
                emit id state = state

                A returned client emits nothing.

                theorem Interaction.Execution.RequestNetwork.emit_ready_lift_bind {Client α S : Type} {p : PFunctor.{0, 0}} [DecidableEq Client] {id : Client} {state : State Client p α S} {a : p.A} {next : p.B a → p.FreeM α} (h : state.clients id = ClientState.ready (PFunctor.FreeM.lift a >>= next)) :
                emit id state = { clients := Function.update state.clients id (ClientState.waiting state.nextTicket a next), service := state.service, queue := state.queue ++ [Envelope.request id state.nextTicket a], nextTicket := state.nextTicket + 1, transcript := state.transcript }

                A ready client at an operation node emits that request. Stated on the simp normal form FreeM.lift a >>= next of the node, as it appears after constructor normalisation.

                theorem Interaction.Execution.RequestNetwork.emit_waiting {Client α S : Type} {p : PFunctor.{0, 0}} [DecidableEq Client] (id : Client) (state : State Client p α S) (ticket : ℕ) (a : p.A) (next : p.B a → p.FreeM α) (h : state.clients id = ClientState.waiting ticket a next) :
                emit id state = state

                A suspended client cannot enqueue a second request.

                def Interaction.Execution.RequestNetwork.accept {Client α S : Type} {p : PFunctor.{0, 0}} [DecidableEq Client] [DecidableEq p.A] (ticket : ℕ) (reply : Interface.RoutedPacket p Client) (state : State Client p α S) :
                State Client p α S

                Resume a waiting client only when both ticket and dependent query tag match.

                Equations
                • One or more equations did not get rendered due to their size.
                Instances For
                  def Interaction.Execution.RequestNetwork.deliver {Client α S : Type} {p : PFunctor.{0, 0}} [DecidableEq Client] [DecidableEq p.A] {m : Type → Type} [Monad m] (impl : PFunctor.Handler (StateT S m) p) (state : State Client p α S) :
                  m (State Client p α S)

                  Deliver the oldest packet. Servicing a request appends its response at the queue's tail.

                  Equations
                  • One or more equations did not get rendered due to their size.
                  Instances For
                    def Interaction.Execution.RequestNetwork.step {Client α S : Type} {p : PFunctor.{0, 0}} [DecidableEq Client] [DecidableEq p.A] {m : Type → Type} [Monad m] (impl : PFunctor.Handler (StateT S m) p) (activation : Activation Client) (state : State Client p α S) :
                    m (State Client p α S)

                    Execute one scheduled activation, including a no-op activation in its fuel count.

                    Equations
                    Instances For
                      def Interaction.Execution.RequestNetwork.run {Client α S : Type} {p : PFunctor.{0, 0}} [DecidableEq Client] [DecidableEq p.A] {m : Type → Type} [Monad m] (impl : PFunctor.Handler (StateT S m) p) :
                      List (Activation Client) → State Client p α S → m (State Client p α S)

                      Execute an explicit finite schedule. Unserviced packets remain in the returned state.

                      Equations
                      Instances For
                        theorem Interaction.Execution.RequestNetwork.run_append {Client α S : Type} {p : PFunctor.{0, 0}} [DecidableEq Client] [DecidableEq p.A] {m : Type → Type} [Monad m] [LawfulMonad m] (impl : PFunctor.Handler (StateT S m) p) (first second : List (Activation Client)) (state : State Client p α S) :
                        run impl (first ++ second) state = run impl first state >>= run impl second

                        Splitting a schedule retains all pending traffic, tickets, and private service state.

                        theorem Interaction.Execution.RequestNetwork.accept_wrong_ticket {Client α S : Type} {p : PFunctor.{0, 0}} [DecidableEq Client] [DecidableEq p.A] (ticket expected : ℕ) (reply : Interface.RoutedPacket p Client) (state : State Client p α S) (a : p.A) (next : p.B a → p.FreeM α) (h : state.clients reply.sender = ClientState.waiting expected a next) (hne : ticket ≠ expected) :
                        accept ticket reply state = state

                        A stale ticket cannot resume a waiting client or enter its delivered transcript.

                        theorem Interaction.Execution.RequestNetwork.run_roundtrip {Client α S : Type} {p : PFunctor.{0, 0}} [DecidableEq Client] [DecidableEq p.A] {m : Type → Type} [Monad m] [LawfulMonad m] (impl : PFunctor.Handler (StateT S m) p) (id : Client) (state : State Client p α S) (a : p.A) (next : p.B a → p.FreeM α) (hclient : state.clients id = ClientState.ready (PFunctor.FreeM.lift a >>= next)) (hqueue : state.queue = []) :
                        run impl [Activation.client id, Activation.deliver, Activation.deliver] state = do let __x ← (impl a).run state.service match __x with | (answer, service) => pure { clients := Function.update state.clients id (ClientState.ready (next answer)), service := service, queue := [], nextTicket := state.nextTicket + 1, transcript := state.transcript ++ [{ sender := id, packet := ⟨a, answer⟩ }] }

                        Three activations complete one query when the queue starts empty. The continuation sees the actual service answer, and the final transcript records that answer with its stable client id.