Memoization of Mutable Objects
Resumo
Memoization is an optimization that consists of caching the results of functions to avoid recomputations of repeated calls. This technique is natively built into some programming languages and implemented as a design pattern in others. Yet, in spite of its popularity, memoization has limitations. In particular, mutable objects cannot be cached, because if a memoized object is mutated, then this modification might have an effect on all the memoized instances of it. This paper presents a technique to address this constraint by using shared-ownership pointers to distinguish between memoized and non-memoized objects. If a memoized object is modified, then this object is removed from the memoization table, and all its aliases are updated through the shared pointer. We have implemented this technique into the runtime environment of the Hush programming language. Our implementation incurs no penalty on non-memoized objects and adds minimum overhead to cached ones. To demonstrate the correctness of this approach, we have formalized it in the Alloy modeling language. This specification certifies that a memoized object remains so unless it is modified.
Referências
Gabriel Bastos. 2021. The Hush Programming Manual. [link]. Accessed: 2024-04-25.
R. S. Bird. 1980. Tabulation Techniques for Recursive Programs. ACM Comput. Surv. 12, 4 (dec 1980), 403–417. DOI: 10.1145/356827.356831
Daniel Bovet and Marco Cesati. 2005. Understanding The Linux Kernel. Oreilly & Associates Inc.
Daniel Brown and William R Cook. 2007. Monadic memoization mixins. Citeseer.
Paul R. Calder and Mark A. Linton. 1990. Glyphs: flyweight objects for user interfaces. In UIST (Snowbird, Utah, USA). Association for Computing Machinery, New York, NY, USA, 92–101. DOI: 10.1145/97924.97935
Ole-Johan Dahl and Kristen Nygaard. 1966. SIMULA: an ALGOLbased simulation language. Commun. ACM 9, 9 (sep 1966), 671–678. DOI: 10.1145/365813.365819
Marty Hall and J Paul McNamee. 1997. Improving software performance with automatic memoization. Johns Hopkins APL Technical Digest 18, 2 (1997), 255.
Ellis Horowitz and Sartaj Sahni. 1974. Computing Partitions with Applications to the Knapsack Problem. J. ACM 21, 2 (apr 1974), 277–292. DOI: 10.1145/321812.321823
Daniel Jackson. 2019. Alloy: a language and tool for exploring software designs. Commun. ACM 62, 9 (aug 2019), 66–76. DOI: 10.1145/3338843.
James Mayfield, Tim Finin, and Marty Hall. 1995. Using automatic memoization as a software engineering tool in real-world AI systems. In AIAI. IEEE, 87–93.
Donald Michie. 1967. Memo Functions and the POP-2 Language. Technical Report. Stanford.
Donald Michie. 1968. Memo Functions and Machine Learning. Nature 218, 5136 (1968), 19–22.
Peter Norvig. 1991. Techniques for automatic memoization with applications to context-free parsing. Comput. Linguist. 17, 1 (mar 1991), 91–98.
Harald Søndergaard and Peter Sestoft. 1990. Referential transparency, definiteness and unfoldability. Acta Informatica 27 (1990), 505–517.
Mirko Stoffers, Daniel Schemmel, Oscar Soria Dustmann, and Klaus Wehrle. 2018. On Automated Memoization in the Field of Simulation Parameter Studies. ACM Trans. Model. Comput. Simul. 28, 4, Article 26 (sep 2018), 25 pages. DOI: 10.1145/3186316
Mirko Stoffers, Daniel Schemmel, Oscar Soria Dustmann, and Klaus Wehrle. 2016. Automated Memoization for Parameter Studies Implemented in Impure Languages. In SIGSIM-PADS (Banff, Alberta, Canada). Association for Computing Machinery, New York, NY, USA, 221–232. DOI: 10.1145/2901378.2901386
Gurram Sunitha, Arman Abouali, Mohammad Gouse Galety, and AV Sriharsha. 2023. Dynamic Programming With Python. In Advanced Applications of Python Data Structures and Algorithms. IGI Global, 102–122.
David Svoboda and Lutz Wrage. 2014. Pointer ownership model. In HICSS. IEEE, 5090–5099.
