Memoization of mutable state

Abstract

Memoização é uma otimização que consiste em armazenar em cache os resultados das funções para evitar recomputações de chamadas repetidas. Esta técnica é incorporada nativamente em algumas linguagens de programação e implementada como um padrão de design em outras. No entanto, apesar de sua popularidade, a memoização tem limitações. Em particular, objetos mutáveis não podem ser armazenados em cache, pois se um objeto memoizado sofrer mutação, essa modificação poderá afetar todas as instâncias memo- izadas dele. Esta dissertação apresenta uma técnica para resolver esta restrição usando ponteiros de posse compartilhada para distinguir entre objetos memoizados e não mem- oizados. Se um objeto memoizado for modificado, esse objeto será removido da tabela de memoização e todos os seus aliases serão atualizados por meio do ponteiro compartil- hado. Implementamos esta técnica no ambiente de execução da linguagem de programação Hush. Nossa implementação não incorre em penalidades em objetos não memoizados e adiciona sobrecarga mínima aos objetos armazenados em cache. Para demonstrar a cor- retude dessa abordagem, nós a formalizamos na linguagem de modelagem Alloy. Esta especificação certifica que um objeto memorizado permanece assim, a menos que seja modificado.