Typing Strictness

Daniel Sainati, Joseph W. Cutler, Benjamin C. Pierce, Stephanie Weirich · 2025

Read Typing Strictness by Daniel Sainati, Joseph W. Cutler, Benjamin C. Pierce, Stephanie Weirich (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-16133.txt.

Introduction

Daniel Sainati, Joseph W Cutler, Benjamin C Pierce, and Stephanie Weirich tackle strictness. Strictness is a trait of code that decides which inputs a function must have before it can run. Knowing strictness lets lazy languages, which delay work until it is needed, run fast instead of slow. Yet strictness at the source level is hard to pin down and easy to misjudge.

The authors give a sharper sense of strictness that tracks how each input gets used, not just whether it is used. They build type systems around it for two styles of running code, and they prove the types match real run-time use. A bridge also moves code safely from one style to the other, keeping its strictness notes intact. All proofs were checked by machine in the Rocq proof tool, so the claims rest on more than hand-waving.

Catalog record

CREATORDaniel Sainati, Joseph W. Cutler, Benjamin C. Pierce, Stephanie Weirich
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE163 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-16133

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Typing Strictness Daniel Sainati, Joseph W. Cutler, Benjamin C. Pierce, Stephanie Weirich Abstract . Strictness analysis is critical to efficient implementation of languages with non-strict evaluation, mitigating much of the performance overhead of laziness. However, reasoning about strictness at the source level can be challenging and unintuitive. We propose a new definition of strictness that refines the traditional one by describing variable usage more precisely. We lay type-theoretic foundations for this definition in both call-by-name and call-by-push-value settings, drawing inspiration from the literature on type systems tracking effects and coeffects. We prove via a logical relation that the strictness attributes computed by our type systems accurately describe the use of variables at runtime, and we offer a strictness-annotation-preserving translation from the call-by-name system to the call-by-push-value one. All our results are mechanized in Rocq. 1. Introduction Non-strict evaluation offers benefits over both fully lazy and fully strict evaluation strategies by allowing expressions to be evaluated at any point between when they are first encountered and when their value is needed. Unlike strict strategies, which must evaluate expressions as soon as they are encountered, non-strict strategies may delay evaluation arbitrarily, improving performance (e.g., by skipping unnecessary computation) and making it easier to work with codata like infinite lists. Unlike lazy strategies, which must wait until an expression is used before evaluating it, non-strict strategies may evaluate earlier to avoid creating thunks. These benefits have led a number of languages to support non-strict evaluation, either as the default strategy, like Haskell ( Haskell.org 1996b ) or R ( Foundation 1999 ) , or optionally via special annotations, like OCaml ( Leroy et al. 2025 ) . Non-strict evaluation is also critical for the performance of streaming libraries like FS2 in Scala ( Scala 2013 ) and code patterns like iterators in Rust ( Klabnik et al. 2024 ) , and it is a useful tool for automatic parallelization ( Calderón Trilla 2015 ) and for opportunistic execution in scripting languages ( Mell et al. 2025 ) . Non-strict evaluation also comes with a number of caveats. Overly lazy strategies suffer from drawbacks such as increased memory usage ( Goel and Vitek 2019 ) , unpredictable behavior ( Flückiger et al. 2019 ) and space complexity ( HaskellWiki 2019 ; de Vries 2020 ; de Vries 2017 ) , and security vulnerabilities ( Vassena et al. 2017 ) . To circumvent these issues, compilers like GHC ( Haskell.org 1996a ) perform strictness analysis ( Mycroft 1980 ; Wadler and Hughes 1987 ) , allowing them to reorder code to evaluate eagerly when they can prove that doing so will not change observable behavior. In pure settings, this analysis enables performance optimizations that can massively reorder evaluation, but such improvements are not limited only to languages like Haskell; strictness analysis can still unlock speedups in impure languages when the compiler is able to ensure that it will not reorder any side effects ( Mell et al. 2025 ) . Strictness analysis, however, comes with its own set of wrinkles. Allowing the compiler to reorder evaluation can result in unpredictable behavior, where modifying the usage of values in one place can change the performance ( Mitchell 2013 ) and even correctness ( Johann and Voigtländer 2004 ) of code elsewhere. Additionally, the inherent imprecision of strictness analysis can result in expressions that seem as though they should evaluate strictly but do not, requiring the programmer to tweak their code to coax the analyzer into triggering the desired optimization ( HaskellWiki 2025 ) . Exacerbating these issues is the fact that the analysis’ model of strictness is specialized to compilation and awkward as a reasoning tool: as we explain in Section 2 , this model is overly extensional and can misrepresent how variables are used. To clarify the traditional model’s murkiness regarding variable usage, we propose a new, static notion of strictness, dubbed intensional strictness , that enables more direct reasoning about how programs use variables; any given occurrence of a variable can be either strict, lazy, or statically unknown. We present intensional strictness type-theoretically via a type-and-effect system ( Lucassen and Gifford 1988 ) , taking additional inspiration from the literature on coeffects ( Petricek et al. 2013 ) . Effect and coeffect annotations extend type systems to describe how programs interact with the world; the standard intuition is that effects describe what a program does to the world, while coeffects describe what a program requires from the world. The interplay between effects and coeffects is an active research area ( Dal Lago and Gavazzo 2022 ; Gaboardi et al. 2016 ; Torczon et al. 2024 ; McDermott and Mycroft 2018 ) , and we adopt mechanisms from these works to characterize the way that strict usage both imposes a demand on a program’s environment (by requiring that a value be successfully produced), and modifies that environment (by triggering the evaluation of suspended computations). Our new definition of strictness, while syntactic in nature like any type system, captures semantic notions of strict and lazy usage that should be intuitively familiar to users of Haskell and similar languages. Furthermore, it refines the extensional characterization of strictness offered by conventional strictness analysis, describing variable usage more precisely and decoupling the definition from questions of “demand” or observable behavior. We formalize our new notion of strictness via \text{CBN}^{{\color[rgb]{0.8,0.33,0}\gamma\!}} , a call-by-name (CBN) calculus with strictness effects, and \text{CBPV}^{{\color[rgb]{0.8,0.33,0}\gamma\!}} , an extension of call-by-push-value (CBPV) ( Levy 1999 ) with similar annotations. CBPV is a convenient foundation for the study of strictness because it specifies explicitly where computation occurs by separating computations from values and including explicit constructs that suspend and resume execution. Furthermore, a canonical translation exists from CBN into CBPV ( Levy 2006 ) , allowing us to use \text{CBPV}^{{\color[rgb]{0.8,0.33,0}\gamma\!}} as a tool to understand strictness in CBN languages. As we argue in Section 5 , this understanding further extends to call-by-need evaluation ( Wadsworth 1971 ; Launchbury 1993 ; Mycroft 1980 ) as well. Our primary motivation, throughout, is conceptual: our proposed definition is intended as a tool for better understanding and reasoning about strictness, not yet as a basis for practical implementation or surface-level design of non-strictly evaluated languages. All of our proofs ( Sainati et al. 2025 ) are mechanized in Rocq ( Team 2025 ) . Concretely, our contributions are: • We propose a new notion of intensional strictness and argue that it refines the extensional definition used by traditional strictness analysis (Section 2 ). • We present \text{CBN}^{{\color[rgb]{0.8,0.33,0}\gamma\!}} , a type-and-effect system for a call-by-name language that embodies this new form of strictness (Section 3 ). • We present \text{CBPV}^{{\color[rgb]{0.8,0.33,0}\gamma\!}} , a variant of CBPV that also embodies intensional strictness. We instrument a big-step operational semantics with strictness attributes and prove the soundness of \text{CBPV}^{{\color[rgb]{0.8,0.33,0}\gamma\!}} typing with respect to this semantics, thus providing a sound semantics for \text{CBN}^{{\color[rgb]{0.8,0.33,0}\gamma\!}} via a translation to \text{CBPV}^{{\color[rgb]{0.8,0.33,0}\gamma\!}} that preserves strictness annotations (Section 4 ). \text{CBPV}^{{\color[rgb]{0.8,0.33,0}\gamma\!}} allows us to factor our proofs about \text{CBN}^{{\color[rgb]{0.8,0.33,0}\gamma\!}} through a lower-level intermediary, simplifying the proofs themselves and potentially offering a setting for reasoning about strictness in other languages with translations into \text{CBPV}^{{\color[rgb]{0.8,0.33,0}\gamma\!}} . • We prove that the strictness attributes computed

Read the complete text