Lune

POPL2021Top-tier venue

A unifying type-theory for higher-order (amortized) cost analysis

Vineet Rajani, Marco Gaboardi, Deepak Garg, Jan Hoffmann

Abstract

This paper presents λ-amor, a new type-theoretic framework for amortized cost analysis of higher-order functional programs and shows that existing type systems for cost analysis can be embedded in it. λ-amor introduces a new modal type for representing potentials – costs that have been accounted for, but not yet incurred, which are central to amortized analysis. Additionally, λ-amor relies on standard type-theoretic concepts like affineness, refinement types and an indexed cost monad. λ-amor is proved sound using a rather simple logical relation. We embed two existing type systems for cost analysis in λ-amor showing that, despite its simplicity, λ-amor can simulate cost analysis for different evaluation strategies (call-by-name and call-by-value), in different styles (effect-based and coeffect-based), and with or without amortization. One of the embeddings also implies that λ-amor is relatively complete for all terminating PCF programs.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

10 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Automatic Amortized Resource Analysis with Regular Recursive Types cites A cost-aware logical framework
  • Automatic Amortized Resource Analysis with Regular Recursive Types cites Recurrence extraction for functional programs through call-by-push-value
  • A cost-aware logical framework cites Liquidate your assets: reasoning about resource usage in liquid Haskell
  • A cost-aware logical framework cites Recurrence extraction for functional programs through call-by-push-value
  • Decalf: A Directed, Effectful Cost-Aware Logical Framework cites A cost-aware logical framework
  • Decalf: A Directed, Effectful Cost-Aware Logical Framework cites Recurrence extraction for functional programs through call-by-push-value
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers10

  1. A cost-aware logical frameworkYue Niu, Jonathan Sterling, Harrison Grodin, Robert HarperPOPL 2022 · 23 citations
  2. A Calculus for Amortized Expected RuntimesKevin Batz, Benjamin Lucien Kaminski, Joost-Pieter Katoen, Christoph Matheja et al.POPL 2023 · 22 citations
  3. Decalf: A Directed, Effectful Cost-Aware Logical FrameworkHarrison Grodin, Yue Niu, Jonathan Sterling, Robert HarperPOPL 2024 · 11 citations
  4. Automatic Amortized Resource Analysis with Regular Recursive TypesJessie Grosen, David M. Kahn, Jan HoffmannLICS 2023 · 5 citations
  5. Effects and Coeffects in Call-by-Push-ValueCassia Torczon, Emmanuel Suárez Acevedo, Shubh Agrawal, Joey Velez-Ginorio et al.OOPSLA 2024 · 5 citations

Builds on2

  1. Liquidate your assets: reasoning about resource usage in liquid HaskellMartin A. T. Handley, Niki Vazou, Graham HuttonPOPL 2020 · 38 citations
  2. Recurrence extraction for functional programs through call-by-push-valueG. A. Kavvos, Edward Morehouse, Daniel R. Licata, Norman DannerPOPL 2020 · 20 citations

Related papers

  1. A Modal Type Theory of Expected Cost in Higher-Order Probabilistic ProgramsVineet Rajani, Gilles Barthe, Deepak GargOOPSLA 2024 · 3 citations
  2. Handling Exceptions and Effects with Automatic Resource AnalysisEthan Chu, Yiyang Guo, Jan HoffmannOOPSLA 2026
  3. A relational theory of effects and coeffectsUgo Dal Lago, Francesco GavazzoPOPL 2022 · 22 citations
  4. Automated Amortised Analysis of Skew Heaps and Leftist HeapsArmin Walch, Georg Moser, Berry Schoenmakers, Florian ZulegerCAV 2026
  5. Automated Expected Amortised Cost Analysis of Probabilistic Data StructuresLorenz Leutgeb, Georg Moser, Florian ZulegerCAV 2022 · 19 citations
Dusk over the sea between two cliffs drawn in fine vertical lines