 |
 |
Selected Papers of the 5th Conference on Algebra and Coalgebra in Computer Science (CALCO 2013)
2013 Editors: Stefan Milius, Reiko Heckel
1. An Effect System for Algebraic Effects and Handlers
We present an effect system for core Eff, a simplified variant of Eff, which is an ML-style programming language with first-class algebraic effects and handlers. We define an expressive effect system and prove safety of operational semantics with respect to it. Then we give a domain-theoretic denotational semantics of core Eff, using Pitts's theory of minimal invariant relations, and prove it adequate. We use this fact to develop tools for finding useful contextual equivalences, including an induction principle. To demonstrate their usefulness, we use these tools to derive the usual equations for mutable state, including a general commutativity law for computations using non-interfering references. We have formalized the effect system, the operational semantics, and the safety theorem in Twelf.
2. Positive Inductive-Recursive Definitions
A new theory of data types which allows for the definition of types as initial algebras of certain functors Fam(C) -> Fam(C) is presented. This theory, which we call positive inductive-recursive definitions, is a generalisation of Dybjer and Setzer's theory of inductive-recursive definitions within which C had to be discrete -- our work can therefore be seen as lifting this restriction. This is a substantial endeavour as we need to not only introduce a type of codes for such data types (as in Dybjer and Setzer's work), but also a type of morphisms between such codes (which was not needed in Dybjer and Setzer's development). We show how these codes are interpreted as functors on Fam(C) and how these morphisms of codes are interpreted as natural transformations between such functors. We then give an application of positive inductive-recursive definitions to the theory of nested data types and we give concrete examples of recursive functions defined on universes by using their elimination principle. Finally we justify the existence of positive inductive-recursive definitions by adapting Dybjer and Setzer's set-theoretic model to our setting.
3. Bialgebraic Semantics for Logic Programming
Bialgebrae provide an abstract framework encompassing the semantics of different kinds of computational models. In this paper we propose a bialgebraic approach to the semantics of logic programming. Our methodology is to study logic programs as reactive systems and exploit abstract techniques developed in that setting. First we use saturation to model the operational semantics of logic programs as coalgebrae on presheaves. Then, we make explicit the underlying algebraic structure by using bialgebrae on presheaves. The resulting semantics turns out to be compositional with respect to conjunction and term substitution. Also, it encodes a parallel model of computation, whose soundness is guaranteed by a built-in notion of synchronisation between different threads.
4. From Kleisli Categories to Commutative C*-algebras: Probabilistic Gelfand Duality
C*-algebras form rather general and rich mathematical structures that can be studied with different morphisms (preserving multiplication, or not), and with different properties (commutative, or not). These various options can be used to incorporate various styles of computation (set-theoretic, probabilistic, quantum) inside categories of C*-algebras. At first, this paper concentrates on the commutative case and shows that there are functors from several Kleisli categories, of monads that are relevant to model probabilistic computations, to categories of C*-algebras. This yields a new probabilistic version of Gelfand duality, involving the "Radon" monad on the category of compact Hausdorff spaces. We then show that the state space functor from C*-algebras to Eilenberg-Moore algebras of the Radon monad is full and faithful. This allows us to obtain an appropriately commuting state-and-effect triangle for C*-algebras.
5. Presenting Distributive Laws
Distributive laws of a monad T over a functor F are categorical tools for specifying algebra-coalgebra interaction. They proved to be important for solving systems of corecursive equations, for the specification of well-behaved structural operational semantics and, more recently, also for enhancements of the bisimulation proof method. If T is a free monad, then such distributive laws correspond to simple natural transformations. However, when T is not free it can be rather difficult to prove the defining axioms of a distributive law. In this paper we describe how to obtain a distributive law for a monad with an equational presentation from a distributive law for the underlying free monad. We apply this result to show the equivalence between two different representations of context-free languages.
6. Service-Oriented Logic Programming
We develop formal foundations for notions and mechanisms needed to support service-oriented computing. Our work builds on recent theoretical advancements in the algebraic structures that capture the way services are orchestrated and in the processes that formalize the discovery and binding of services to given client applications by means of logical representations of required and provided services. We show how the denotational and the operational semantics specific to conventional logic programming can be generalized using the theory of institutions to address both static and dynamic aspects of service-oriented computing. Our results rely upon a strong analogy between the discovery of a service that can be bound to an application and the search for a clause that can be used for computing an answer to a query; they explore the manner in which requests for external services can be described as service queries, and explain how the computation of their answers can be performed through service-oriented derivatives of unification and resolution, which characterize the binding of services and the reconfiguration of applications.
7. Positive fragments of coalgebraic logics
Positive modal logic was introduced in an influential 1995 paper of Dunn as the positive fragment of standard modal logic. His completeness result consists of an axiomatization that derives all modal formulas that are valid on all Kripke frames and are built only from atomic propositions, conjunction, disjunction, box and diamond. In this paper, we provide a coalgebraic analysis of this theorem, which not only gives a conceptual proof based on duality theory, but also generalizes Dunn's result from Kripke frames to coalgebras for weak-pullback preserving functors. To facilitate this analysis we prove a number of category theoretic results on functors on the categories $\mathsf{Set}$ of sets and $\mathsf{Pos}$ of posets: Every functor $\mathsf{Set} \to \mathsf{Pos}$ has a $\mathsf{Pos}$-enriched left Kan extension $\mathsf{Pos} \to \mathsf{Pos}$. Functors arising in this way are said to have a presentation in discrete arities. In the case that $\mathsf{Set} \to \mathsf{Pos}$ is actually $\mathsf{Set}$-valued, we call the corresponding left Kan extension $\mathsf{Pos} \to \mathsf{Pos}$ its posetification. A $\mathsf{Set}$-functor preserves weak pullbacks if and only if its posetification preserves exact squares. A $\mathsf{Pos}$-functor with a presentation in discrete arities preserves surjections. The inclusion $\mathsf{Set} \to \mathsf{Pos}$ is dense. A functor $\mathsf{Pos} \to \mathsf{Pos}$ has a presentation in discrete arities if and only if it preserves coinserters […]