Normalization by Origin, Not by Shape

Servetto, Marco, Gordon, Colin S.

Onward! Papers, October 2026

Abstract

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.

Bibtex

@inproceedings{memo,
	title = {Normalization by Origin, Not by Shape},
	author = {Servetto, Marco and Gordon, Colin S.},
	year = {2026},
	abbr = {Onward!},
	booktitle = {Onward! Papers},
	month = {October},
	abstract = { 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. },
}