# Changeset d438111

Ignore:
Timestamp:
Mar 7, 2019, 3:44:17 PM (3 years ago)
Branches:
aaron-thesis, arm-eh, cleanup-dtors, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr
Children:
4ba22b8
Parents:
1836081
Message:

thesis: update second draft of ch.5

File:
1 edited

### Legend:

Unmodified
 r1836081 As discussed in Chapter~\ref{resolution-chap}, being able to efficiently determine which type variables are bound to which concrete types or whether two type environments are compatible is a core requirement of the resolution algorithm. Furthermore, expression resolution involves a search through many related possible solutions, so the ability to re-use shared subsets of type-environment data and to switch between environments quickly is desirable for performance. In this chapter, I discuss a number of type environment data-structure variants, including some novel variations on the union-find \cite{Galler64} data structure introduced in this thesis. In this chapter, I discuss a number of type-environment data-structure variants, including some novel variations on the union-find \cite{Galler64} data structure introduced in this thesis. Chapter~\ref{expr-chap} contains empirical comparisons of the performance of these data structures when integrated into the resolution algorithm. \section{Conclusion \& Future Work} This chapter presents the type environment data structure in Section~\ref{env-defn-sec}, as well as some more sophisticated approaches to optimize performance for workloads encountered in the expression resolution problem in Section~\ref{env-approaches-sec}, and asymptotic analysis of each approach in Section~\ref{env-analysis-sec}. This chapter presents the type environment abstract data type, some type-environment data-structures optimized for workloads encountered in the expression resolution problem, and asymptotic analysis of each data structure. Chapter~\ref{expr-chap} provides experimental performance results for a representative set of these approaches. One contribution of this thesis is the union-find with classes data structure for efficient retrieval of union-find class members, along with a related algorithm for reversing the history of $union$ operations in this data structure.