MSc thesis of Petros Barbagiannis
Non-Strict Pattern Matching and Delimited Control
Supervisor: Nikolaos S. Papaspyrou
It has been long known that continuations and evaluation strategies are two intimately related concepts of functional programming languages. In one of the earliest results, continuation-passing style (CPS) was introduced as a means to decouple the evaluation order of a source language from the evaluation order of its interpreter. Since then, this style of programming has been proved extremely useful in areas ranging from compiler implementation to denotational semantics. Since the introduction of CPS, a wide variety of control operators have been developed. Delimited control operators, in particular, are a powerful mechanism of functional programming languages that generalize traditional first-class control operators, such as call/cc, and provide the means to abstract control. One notable application of delimited control operators is the construction of a novel abstract machine for the call-by-need λ-calculus that simulates store-based effects with delimited continuations. Pattern matching on algebraic data types is an essential feature of functional programming languages. However, pattern matching is often thought to be syntactic sugar that can be merely represented by a proper encoding. In this thesis, we study the operational characteristics of non-strict pattern matching. We also explore the semantics of control operators, as well as some of their applications. Finally, we seek to examine the connection between implementing a non-strict pattern matching evaluator and delimited continuations.Work in progress.