Efficient Hash-Consing of Recursive Types
Date
2000-01-21
DOI
Authors
Considine, Jeffrey
Version
OA Version
Citation
Considine, Jeffrey. "Efficient Hash-Consing of Recursive Types", Technical Report BUCS-2000-006, Computer Science Department, Boston University, January 29, 2000. [Available from: http://hdl.handle.net/2144/1800]
Abstract
Efficient storage of types within a compiler is necessary to avoid large blowups in space during compilation. Recursive types in particular are important to consider, as naive representations of recursive types may be arbitrarily larger than necessary through unfolding. Hash-consing has been used to efficiently store non-recursive types. Deterministic finite automata techniques have been used to efficiently perform various operations on recursive types. We present a new system for storing recursive types combining hash-consing and deterministic finite automata techniques. The space requirements are linear in the number of distinct types. Both update and lookup operations take polynomial time and linear space and type equality can be checked in constant time once both types are in the system.