Ignore:
Timestamp:
Mar 7, 2019, 3:44:17 PM (5 years ago)
Author:
Aaron Moss <a3moss@…>
Branches:
ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum
Children:
4ba22b8
Parents:
1836081
Message:

thesis: update second draft of ch.5

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/theses/aaron_moss_PhD/phd/type-environment.tex

    r1836081 rd438111  
    55As 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.
    66Furthermore, 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.
    7 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.
     7In 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.
    88Chapter~\ref{expr-chap} contains empirical comparisons of the performance of these data structures when integrated into the resolution algorithm.
    99
     
    274274\section{Conclusion \& Future Work}
    275275
    276 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}.
     276This 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.
    277277Chapter~\ref{expr-chap} provides experimental performance results for a representative set of these approaches.
    278278One 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.
Note: See TracChangeset for help on using the changeset viewer.