Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper explores the relationship between cost and potential in type systems by introducing a framework that tracks both worst-case and amortized costs through a type system called $\lambda$-amor. By establishing an adjoint relationship between cost and potential using graded functors, the authors provide a theoretical foundation that unifies various existing models and enhances the expressiveness of cost tracking in programming languages. The study presents three concrete models, including a novel approach using copresheaves, demonstrating the versatility and applicability of the proposed framework in denotational semantics.
Amortized cost tracking can be elegantly captured through an adjoint relationship, transforming how we understand computational costs in type systems.
Various type systems have been developed to track the cost $\kappa$ of a computation using a cost-tracking monad $M\ \kappa \tau$. On its own, this only tracks the worst-case cost of a computation. If we also want to track amortized cost, then we can add a type $[\kappa]\tau$ which stores potential $\kappa$ with a type $\tau$, together with operations for storing and releasing potential. In this work, we build on one such system, $\lambda$-amor: $\lambda$-amor allows to track cost and potential in the type system and subsumes effect and coeffect-based systems, call-by-value and call-by-name based languages. In this paper, we identify the abstract properties that denotational models of type theories for cost and potential have to satisfy: Cost and potential must be modelled by an adjoint pair of graded functors, where the functor modelling cost forms both a graded monad and a compatible graded comonad. We present three concrete instances of this general abstract scheme: (1) A simple set-theoretic model that ignores the cost tracked by the type system, (2) the Kripke logical relations model in the original $\lambda$-amor paper (which we show can be turned into an instance of the adjoint model), and (3) a novel model based on copresheaves on a monoidal category of costs, where we model pairs and functions by Day convolution and its right-adjoint.