Search

This thesis presents a variety of models for probabilistic programming languages in the framework of concurrent games. Our starting point is the model of concurrent games with symmetry of Castellan, Clairambault and Winskel. We show that they form a symmetric monoidal closed bicategory, and that this can be turned into a cartesian closed bicategory using a linear exponential pseudo-comonad inspired by linear logic. Then, we enrich this with probability, relying heavily on Winskel's model of probabilistic concurrent strategies. We see that the bicategorical structure is not perturbed by the addition of probability. We apply this model to two probabilistic languages: a probabilistic untyped λ-calculus, and Probabilistic PCF. For the former, we relate the semantics to the probabilistic Nakajima trees of Leventis, thus obtaining a characterisation of observational equivalence for programs in terms of strategies. For the latter, we show a definability result in the spirit of the game semantics tradition. This solves an open problem, as it is notoriously difficult to model Probabilistic PCF with sequential game semantics. Finally, we introduce a model for measurable game semantics, in which games and strategies come equipped with measure-theoretic structure allowing for an accurate description of computation with continuous data types. The objective of this model is to support computation with arbitrary probability measures on the reals. In the last part of this thesis we see how this can be done by equipping strategies with parametrised families of probability measures (also known as stochastic kernels), and we construct a bicategory of measurable concurrent games and probabilistic measurable strategies.

Starting with a Fully Abstract denotational semantics for an Algol-like programming language, we investigate how we can use techniques of categorical algebra to adapt the semantics when the original language is extended with various nondeterministic effects. Our running example for the base denotational semantics is Abramsky and McCusker’s game semantics for Idealized Algol. We give a full presentation of this game semantics, including an alternative proof of Computational Adequacy that uses Laird’s concept of a sequoidal category rather than the combinatorial proof from Abramsky and McCusker’s original paper. We introduce the familiar concepts of monads and Kleisli categories, and prove a Full Abstraction result that shows how the process of passing to certain Kleisli categories corresponds to particular language extensions. We link these language extensions to may-and must-testing for finite and countable nondeterminism, showing how we can construct Fully Abstract models of these effects using Kleisli categories. We introduce a generalization of monads: lax actions, also known as parametric monads. We investigate various corresponding generalizations of Kleisli categories, and prove a Full Abstraction result for one such generalization, showing how it too can be used to construct a model of an extended version of our original Algol-like language. We show how a special case of this construction can be adapted to model a probabilistic language.

In the 1980s and 1990s, Joyal and Street developed a graphical notation for various flavours of monoidal category using graphs drawn in the plane, commonly known as string diagrams. In particular, their work comprised a rigorous topological foundation of the notation. In 2007, Harmer, Hyland and Melliès gave a formal mathematical foundation for game semantics using a notions they called ⊸-schedules, ⊗-schedules and heaps. Schedules described interleavings of plays in games formed using ⊸ and ⊗, and heaps provided pointers used for backtracking. Their definitions were combinatorial in nature, but researchers often draw certain pictures when working in practice. In this thesis, we extend the framework of Joyal and Street to give a formal account of the graphical methods already informally employed by researchers in game semantics. We give a geometric formulation of ⊸-schedules and ⊗-schedules, and prove that the games they describe are isomorphic to those described in Harmer et al.’s terms, and also those given by a more general graphical representation of interleaving across games of multiple components. We further illustrate the value of the geometric methods by demonstrating that several proofs of key properties (such as that the composition of ⊸-schedules is associative) can be made straightforward, reflecting the geometry of the plane, and overstepping some of the cumbersome combinatorial detail of proofs in Harmer et al.’s terms. We further extend the framework of formal plane diagrams to account for the heaps and pointer structures used in the backtracking functors for O and P.

This thesis presents a new integrated tool and decision support framework to approach complex problems resulting from the interaction of many multi-criteria issues. The framework is embedded in an integrated tool called OUTDO (Oxford University Tool for Decision Organisation). OUTDO integrates Multi-Criteria Decision Analysis (MCDA), decision rationale management with a modified Issue-Based Information Systems (IBIS) representation, and probabilistic forecasting to effectively capture the essential reasons why decisions are made and to dynamically re-use the rationale. In doing so, it allows exploration of how changes in external parameters affect complicated and uncertain decision making processes in the present and in the future. Once the decision maker constructs his or her own decision process, OUTDO checks if the decision process is consistent and coherent and looks for possible ways to improve it using three new semantic-based decision support approaches. For this reason, two ontologies (the Decision Ontology and the Energy Ontology) were integrated into OUTDO to provide it with these semantic capabilities. The Decision Ontology keeps a record of the decision rationale extracted from OUTDO and the Energy Ontology describes the energy generation domain, focusing on the water requirement in thermoelectric power plants. A case study, with the objective of recommending electricity generation and steam condensation technologies for ten different regions in the UK, is used to verify OUTDO’s features and reach conclusions about the overall work.

The probabilistic (or quantitative) modal μ-calculus is a fixed-point logic designed for expressing properties of probabilistic labeled transition systems (PLTS’s). Two semantics have been studied for this logic, both assigning to every process state a value in the interval [0, 1] representing the probability that the property expressed by the formula holds at the state. One semantics is denotational and the other is a game semantics, specified in terms of two-player stochastic games. The two semantics have been proved to coincide on all finite PLTS’s. A first contribution of the thesis is to extend this coincidence result to arbitrary PLTS’s. A shortcoming of the probabilistic μ-calculus is the lack of expressiveness required to encode other important temporal logics for PLTS’s such as Probabilistic Computation Tree Logic (PCTL). To address this limitation, we extend the logic with a new pair of operators: independent product and coproduct, and we show that the resulting logic can encode the qualitative fragment of PCTL. Moreover, a further extension of the logic, with the operation of truncated sum and its dual, is expressive enough to encode full PCTL. A major contribution of the thesis is the definition of appropriate game semantics for these extended probabilistic μ-calculi. This relies on the definition of a new class of games, called tree games, which generalize standard 2-player stochastic games. In tree games, a play can be split into concurrent subplays which continue their evolution independently. Surprisingly, this simple device supports the encoding of the whole class of imperfect-information games known as Blackwell games. Moreover, interesting open problems in game theory, such as qualitative determinacy for 2-player stochastic parity games, can be reformulated as determinacy problems for suitable classes of tree games. Our main technical result about tree games is a proof of determinacy for 2-player stochastic metaparity games, which is the class of tree games that we use to give game semantics to the extended probabilistic μ-calculi. In order to cope with measure-theoretic technicalities, the proof is carried out in ZFC set theory extended with Martin’s Axiom at the first uncountable cardinal (MAℵ1). The final result of the thesis shows that the game semantics of the extended logics coincides with the denotational semantics, for arbitrary PLTS’s. However, in contrast to the earlier coincidence result, which is proved in ZFC, the proof of coincidence for the extended calculi is once again carried out in ZFC +MAℵ1.

An interesting problem in proof theory is to find representations of proof that do not distinguish between proofs that are ‘morally’ the same. For many logics, the presentation of proofs in a traditional formalism, such as Gentzen’s sequent calculus, introduces artificial syntactic structure called ‘bureaucracy’; e.g., an arbitrary ordering of freely permutable inferences. A proof system that is free of bureaucracy is called canonical for a logic. In this dissertation two canonical proof systems are presented, for two logics: a notion of proof nets for additive linear logic with units, and ‘classical proof forests’, a graphical formalism for first-order classical logic. Additive linear logic (or sum–product logic) is the fragment of linear logic consisting of linear implication between formulae constructed only from atomic formulae and the additive connectives and units. Up to an equational theory over proofs, the logic describes categories in which finite products and coproducts occur freely. A notion of proof nets for additive linear logic is presented, providing canonical graphical representations of the categorical morphisms and constituting a tractable decision procedure for this equational theory. From existing proof nets for additive linear logic without units by Hughes and Van Glabbeek (modified to include the units naively), canonical proof nets are obtained by a simple graph rewriting algorithm called saturation. Main technical contributions are the substantial correctness proof of the saturation algorithm, and a correctness criterion for saturated nets. Classical proof forests are a canonical, graphical proof formalism for first-order classical logic. Related to Herbrand’s Theorem and backtracking games in the style of Coquand, the forests assign witnessing information to quantifiers in a structurally minimal way, reducing a first-order sentence to a decidable propositional one. A similar formalism ‘expansion tree proofs’ was presented by Miller, but not given a method of composition. The present treatment adds a notion of cut, and investigates the possibility of composing forests via cut-elimination. Cut-reduction steps take the form of a rewrite relation that arises from the structure of the forests in a natural way. Yet reductions are intricate, and initially not well-behaved: from perfectly ordinary cuts, reduction may reach unnaturally configured cuts that may not be reduced. Cutelimination is shown using a modified version of the rewrite relation, inspired by the game-theoretic interpretation of the forests, for which weak normalisation is shown, and strong normalisation is conjectured. In addition, by a more intricate argument, weak normalisation is also shown for the original reduction relation.

This thesis examines the use of game semantics for the automatic equivalence checking of higher-order programs. Game semantics has proved to be a powerful method for constructing fully abstract models of logics and programming languages. Furthermore, the concrete nature of the semantics lends itself to algorithmic analysis. The game-semantic model can be used to identify fragments of languages which have a decidable observational equivalence problem. We investigate decidability results for different languages as well as the efficiency of these algorithms in practice. First we consider the call-by-value higher-order language with state, RML. This can be viewed as a canonical restriction of Standard ML to ground-type references. The O-strict fragment of RML is the largest set of type sequents for which, in the game-semantic denotation, justification pointers from O-moves are always uniquely reconstructible from the underlying move sequence. The O-strict fragment is surprisingly expressive, including higher-order types and difficult examples from the literature. By representing strategies as Visibly Pushdown Automata (VPA) we show that observational equivalence of O-strict terms is decidable (and in fact is ExpTime-complete). We then consider extensions of the O-strict fragment. Adding general recursion or using most non-O-strict types leads to undecidability. However, a limited form of recursion can be added while still preserving decidability (although the full power of DPDA is required). Next we examine languages with non-local control. This involves adding call/cc to our language and is known to correspond to dropping the game-semantic bracketing condition. In the call-by-name game-semantic model of Idealized Algol (IA), in which answers cannot justify questions, the visibility condition still implies a form of weak bracketing. By making bracketing violations explicit we show that we can still model the entire third-order fragment using VPA. We have also implemented tools based on these algorithms. Our model checkers Homer and Hector perform equivalence checking for third-order IA and O-strict RML respectively. Homer uses a naive explicit state method whereas Hector takes advantage of on-the-fly model checking. Our tools perform well on small yet challenging examples. On negative instances, the on-the-fly approach allows Hector to outperform Homer. To improve their performance, we also consider using ideas from symbolic execution. We propose a representation for finite automata using transitions labelled with formulas and guards which aims to take advantage of the symmetries of the game-semantic model so that strategies can be represented compactly. We refer to this representation as Symbolically Executed Automata (SEA). Using SEA allows much larger data types to be handled but is not as effective on larger examples with small data types.

We consider a syntactic restriction for higher-order grammars called safety that constrains occurrences of variables in the production rules according to their type-theoretic order. We transpose and generalize this restriction to the setting of the simply-typed lambda calculus, giving rise to what we call the safe lambda calculus. We analyze its expressivity and obtain a result in the same vein as Schwichtenberg's 1976 characterization of the simply-typed lambda calculus: the numeric functions representable in the safe lambda calculus are exactly the multivariate polynomials; thus conditional is not definable. We also give a similar characterization for representable word functions. We then examine the complexity of deciding beta-eta equality of two safe simply-typed terms and show that this problem is PSPACE-hard. The safety restriction is then extended to other applied lambda calculi featuring recursion and references such as PCF and Idealized Algol (IA for short). The next contribution concerns game semantics. We introduce a new concrete presentation of this semantics using the theory of traversals. It is shown that the revealed game denotation of a term can be computed by traversing some souped-up version of the term's abstract syntax tree using adequately defined traversal rules. Based on this presentation and via syntactic reasoning we obtain a game-semantic interpretation of safety: the strategy denotations of safe lambda-terms satisfy a property called P-incremental justification which says that the player's moves are always justified by the last pending opponent's move of greater order occurring in the player's view. Next we look at models of the safe lambda calculus. We show that these are precisely captured by Incremental Closed Categories. A game model is constructed and is shown to be fully abstract for safe IA. Further, it is effectively presentable: two terms are equivalent just if they have the same set of complete O-incrementally justified plays---where O-incremental justification is defined as the dual of P-incremental justification. Finally we study safety from the point of view of algorithmic game semantics. We observe that in the third-order fragment of IA, the addition of unsafe contexts is conservative for observational equivalence. This implies that all the upper complexity bounds known for the lower-order fragments of IA also hold for the safe fragment; we show that the lower-bounds remain the same as well. At order 4, observational equivalence is known to be undecidable for IA. We conjecture that for the order-4 safe fragment of IA, the problem is reducible to the DPDA-equivalence problem and is thus decidable.

We analyse the semantics of aspect-oriented extensions to functional languages by presenting compositional translations of these primitives into languages with traditional notions of state and control. As a first step, we examine an existing semantic description of aspects which allows the labelling of program points. We show that a restriction of these semantics to aspects which do not preempt the execution of code can be fully abstractly translated into a functional calculus with higher order references, but that removing this restriction requires a notion of exception handling to be added to the target language in order to yield a sound semantics. Next, we proceed to show that abandoning the labelling technique, and consequently relaxing the so-called ``obliviousness'' property of aspectual languages, allows preemptive aspects to be included in the general references model without the need for exceptions. This means that the game model of general references is inherited by the aspect calculus. The net result is a clean semantic description of aspect-orientation, which mirrors recently published techniques for their implementation, and thereby provides theoretical justification for these systems. The practical validity of our semantics is demonstrated by implementing extensions to the basic calculus in Standard ML, and showing how a number of useful aspect-oriented features can be expressed using general references alone. Our theoretical methodology closely follows the proof structure that often appears in the game semantics literature, and therefore provides an operational perspective on notions such as ``bad variables'' and factorisation theorems.