Programmimg with Sequence and Context Variables: Foundations and Applications
Besiki Dundua · Open Repository of the University of Porto (University of Porto) · 2014
In this thesis we study integration of sequence and context variables into declarative programming. These variables are useful in various areas of computer science. Sequence variables can be instantiated by finite sequences of terms. Context variables are second order variables that stand for contexts: terms with a single occurrence of a single bound variable (called the hole). In the first part of the thesis, we develop a constraint solver for equational and membership constraints over sequences and contexts, incorporate it in the constraint logic programming schema, and explore the semantics of the obtained language. Next, we propose a rule-based system PρLog, which extends Prolog with strategic conditional rewriting rules and supports programming with sequence and context variables. In addition, PρLog permits regular constraints to restrict possible values of sequence and context variables by regular sequence expressions and regular tree (context) expressions, respectively. We illustrate expressive power of the system using examples and show its application in XML transformation, Web reasoning and for specifying rewriting strategies. Finally, we integrate sequence variables in pattern calculus (a formalism for functional programming) and propose a generic confluence proof, where the way pattern abstractions are applied in a non-deterministic calculus is axiomatized.