Functional versus Imperative Maps

Goal is to map identifiers to definitions

We need efficient operations on maps

  • look up identifier to obtain its definition
  • update map to store declarations
  • revert declarations

Functional style

def + : (kv : (A, B)) : Map[A, B]

  • if we write analysis recursively, we just keep values of old maps

Imperative style

  • global map
  • insert new values when entering scope
  • undo changes on exit
    • need an undo stack to know what to remove
    • need data structure to support efficient removal