Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userScalability using effects
107
0
0.0
(
0
)
Added by
Dominique Duval
Publication date
2013
fields
Informatics Engineering
and research's language is
English
Authors
Dominique Duval
Ask ChatGPT about the research
No Arabic abstract
This note is about using computational effects for scalability. With this method, the specification gets more and more complex while its semantics gets more and more correct. We show, from two fundamental examples, that it is possible to design a deduction system for a specification involving an effect without expliciting this effect.
rate research
Read More
We define a proof system for exceptions which is close to the syntax for exceptions, in the sense that the exceptions do not appear explicitly in the type of any expression. This proof system is sound with respect to the intended denotational semantics of exceptions. With this inference system we prove several properties of exceptions.
In this paper we consider the two major computational effects of states and exceptions, from the point of view of diagrammatic logics. We get a surprising result: there exists a symmetry between these two effects, based on the well-known categorical duality between products and coproducts. More precisely, the lookup and update operations for states are respectively dual to the throw and catch operations for exceptions. This symmetry is deeply hidden in the programming languages; in order to unveil it, we start from the monoidal equational logic and we add progressively the logical features which are necessary for dealing with either effect. This approach gives rise to a new point of view on states and exceptions, which bypasses the problems due to the non-algebraicity of handling exceptions.
Computational effects may often be interpreted in the Kleisli category of a monad or in the coKleisli category of a comonad. The duality between monads and comonads corresponds, in general, to a symmetry between construction and observation, for instance between raising an exception and looking up a state. Thanks to the properties of adjunction one may go one step further: the coKleisli-on-Kleisli category of a monad provides a kind of observation with respect to a given construction, while dually the Kleisli-on-coKleisli category of a comonad provides a kind of construction with respect to a given observation. In the previous examples this gives rise to catching an exception and updating a state. However, the interpretation of computational effects is usually based on a category which is not self-dual, like the category of sets. This leads to a breaking of the monad-comonad duality. For instance, in a distributive category the state effect has much better properties than the exception effect. This remark provides a novel point of view on the usual mechanism for handling exceptions. The aim of this paper is to build an equational semantics for handling exceptions based on the coKleisli-on-Kleisli category of the monad of exceptions. We focus on n-ary functions and conditionals. We propose a programmers language for exceptions and we prove that it has the required behaviour with respect to n-ary functions and conditionals.
It is well established that equational algebraic theories, and the monads they generate, can be used to encode computational effects. An important insight of Power and Shkaravska is that comodels of an algebraic theory T -- i.e., models in the opposite category Set^op -- provide a suitable environment for evaluating the computational effects encoded by T. As already noted by Power and Shkaravska, taking comodels yields a functor from accessible monads to accessible comonads on Set. In this paper, we show that this functor is part of an adjunction -- the costructure-cosemantics adjunction of the title -- and undertake a thorough investigation of its properties. We show that, on the one hand, the cosemantics functor takes its image in what we term the presheaf comonads induced by small categories; and that, on the other, costructure takes its image in the presheaf monads induced by small categories. In particular, the cosemantics comonad of an accessible monad will be induced by an explicitly-described category called its behaviour category that encodes the static and dynamic properties of the comodels. Similarly, the costructure monad of an accessible comonad will be induced by a behaviour category encoding static and dynamic properties of the comonad coalgebras. We tie these results together by showing that the costructure-cosemantics adjunction is idempotent, with fixpoints to either side given precisely by the presheaf monads and comonads. Along the way, we illustrate the value of our results with numerous examples drawn from computation and mathematics.
We give a complete presentation for the fragment, ZX&, of the ZX-calculus generated by the Z and X spiders (corresponding to copying and addition) along with the not gate and the and gate. To prove completeness, we freely add a unit and counit to the category TOF generated by the Toffoli gate and ancillary bits, showing that this yields the full subcategory of finite ordinals and functions with objects powers of two; and then perform a two way translation between this category and ZX&. A translation to some extension of TOF, as opposed to some fragment of the ZX-calculus, is a natural choice because of the multiplicative nature of the Toffoli gate. To this end, we show that freely adding counits to the semi-Frobenius algebras of a discrete inverse category is the same as constructing the Cartesian completion. In particular, for a discrete inverse category, the category of classical channels, the Cartesian completion and adding counits all produce the same category. Therefore, applying these constructions to TOF produces the full subcategory of finite ordinals and partial maps with objects powers of two. By glueing together the free counit completion and the free unit completion, this yields qubit multirelations.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
