Notion of Hash-Consing

Notion of not specific to compilers

  • and need not be used in compilers

A generalization of idea of replacing strings with symbols

  • ensure we can use pointer equality instead of structural equality
  • avoid constructing duplicate objects that are equal
  • only works for immutable trees

Trivially, if pointers equal, then so is structure

Ensuring converse (if structure equal, so are pointers):

  • replace constructor with 'hashing constructor'
  • constructor maps compound object to its components
  • with hash consing, we maintain a mapping from components to compound object
  • if such object already created, we return same address