Higher-Order Pattern Match Analysis

Abstract

In this thesis we attempt to answer the research question:

Can we use a type and effect system in combination with refinement types to develop a pattern-match analysis for a non-strict higher-order functional language that is both performant and precise enough to be of practical use?

In Chapter 1 we present a number of examples to demonstrate why this is an interesting problem. In Chapter 2 we give a short in- troduction to the relevant concepts of the research question: higher- order functional languages and type and effect systems. In Chap- ter 3 we give an overview of the pattern match analysis we devel- oped and give a detailed description of the constraint generation and constraint solving phases in respectively Chapter 4 and Chap- ter 5. In Chapter 7 we discussion the implementation of the analysis we have built. We evaluate the effectiveness and limitations of our analysis in Chapter 6. In Chapter 8 we present work related to our research question and discuss which aspects of that work are rele- vant to or different from our proposed system. Finally, in Chapter 9, we propose a number of directions for further research and future implementation work to improve the precision and applicability of the analysis.