Search papers, labs, and topics across Lattice.
This paper synthesizes two perspectives on amortized analysis鈥攐ne from physics using potential functions and another from banking using type-level credit annotations鈥攊nto a unified framework called Calf, a dependent type theory for cost verification. It introduces a fracture and gluing theorem that ensures every type integrates an abstraction function and a potential function, thus maintaining modularity in behavior and cost. The authors also present Giralf, a graded substructural dependent type theory, and adapt an inference algorithm to automate the transformation of Calf programs into Giralf, streamlining cost analysis for common algorithms.
Every program in the new Calf framework must preserve both abstraction and potential, revolutionizing how we approach cost verification in type theory.
Amortized analysis can be framed from the physicist's view, amenable to manual verification in dependent type theory using potential functions, and the banker's view, amenable to automated inference in substructural type theory using type-level credit annotations. In this work, we synthesize these perspectives in Calf, a dependent type theory cost verification. From the physicist's view, we present a fracture and gluing theorem that renders every type as containing a fusion of an abstraction function and a potential function. By construction, every program between two such types must preserve abstraction, to facilitate modularity of behavior, and conserve potential, to facilitate modularity of cost. Incorporating the banker's view, we synthetically construct type operators for credits and debits. We then define Giralf, a graded substructural dependent type theory for programming with credits and debits, which is semantically interpreted as a sub-language of Calf. Finally, we adapt an inference algorithm to transform a limited class of Calf programs into Giralf counterparts, automating the cost analysis of common algorithms in Calf.
CMU ML