PhD Seminar • Programming Languages — Persistent Union-Find for Efficient Type Environments

Aaron Moss, PhD candidate
David R. Cheriton School of Computer Science

The type environment is a core data structure for a programming language compiler, required to support a variety of queries and updates efficiently in the context of a backtracking search. This seminar discusses the requirements for the type environment data structure in the compiler for the Cforall programming language currently under development and Waterloo, and how those requirements were met efficiently by using some novel variations on the classic union-find data structure.