Logo image
Back
Normalization by Origin, Not by Shape
Conference proceeding   Open access

Normalization by Origin, Not by Shape

Marco Servetto and Colin S. Gordon
Proceedings of the 2026 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software, pp 31-44
01 Oct 2026
DOI: https://doi.org/10.1145/3840586.3843208
Featured in Collection :   Drexel's Newest Publications
url
https://doi.org/10.1145/3840586.3843208View
Published, Version of Record (VoR) Open

Abstract

Software and its engineering -- General programming languages Theory of computation -- Program constructs
Memoization is about avoiding recomputation, by caching results and retrieving them when previously-seen inputs are provided again in the future. In the literature, many different ways have been proposed to efficiently (and correctly) check if such input has indeed already been seen. Prior work largely focuses on structural equality of the keys. In many commonly-used approaches, like Python’s @cache avoiding (or accepting) observable semantic changes is the responsibility of the programmer. Here we propose a new approach, where cache keys are considered equal if they are created in the same way. We implement our approach on top of Fearless, a language with reference and object capabilities allowing to control side effects and enforcing determinism of localized code expressions. Our technique guarantees language-enforced unobservable caching: removing the caching annotations does not change the observable program semantic.

Metrics

1 Record Views

Details

Logo image