Unit:
Κατεύθυνση Λογική και Θεωρία Αλγορίθμων και ΥπολογισμούLibrary of the School of Science
Author:
Barbagiannis Petros
Supervisors info:
Νικόλαος Παπασπύρου, Αναπληρωτής Καθηγητής
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών
Εθνικό Μετσόβιο Πολυτεχνείο
Original Title:
Non-Strict Pattern Matching and Delimited Control
Translated title:
Non-Strict Pattern Matching and Delimited Control
Summary:
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 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 \texttt{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 $\lambda$-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.
Main subject category:
Science
Other subject categories:
Mathematics
Keywords:
functional programming languages, delimited continuations, pattern matching, lazy evaluation
