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

• seen in Semantic Analysis as Simplified Interpretation
• correspond to Maps in Math
• standard Map class in Scala
• update returns new map, we get to keep the old

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