In the study of computational effects, it is important to consider the notion of computational effects with parameters. The need of such a notion arises when, for example, statically estimating the range of effects caused by a program, or studying the ways in which effects with local scopes are derived from effects with only the global scope. Extending the classical observation that computational effects can be modeled by monads, these computational effects with parameters are modeled by various mathematical structures including graded monads and indexed monads, which are two different generalizations of ordinary monads. The former has been employed in the semantics of effect systems, whereas the latter in the study of the relationship between the local state monads and the global state monads, each exemplifying the two situations mentioned above. However, despite their importance, the mathematical theory of graded and indexed monads is far less developed than that of ordinary monads. Here we develop the mathematical theory of graded and indexed monads from a 2-categorical viewpoint. We first introduce four 2-categories and observe that in two of them graded monads are in fact monads in the 2-categorical sense, and similarly indexed monads are monads in the 2-categorical sense in the other two. We then construct explicitly the Eilenberg--Moore and the Kleisli objects of graded monads, and the Eilenberg--Moore objects of indexed monads in the sense of Street in appropriate 2-categories among these four. The corresponding results for graded and indexed comonads also follow. We expect that the current work will provide a theoretical foundation to a unified study of computational effects with parameters, or dually (using the comonad variants), of computational resources with parameters, arising for example in Bounded Linear Logic.
Corresponding to this on the side of computational effects, various notions of have been employed in the study of those computational effects with parameters. The notion of has been used to give semantics of effect systems @cite_5 , whereas the notion of arose and has been applied in the study of local state @cite_9 @cite_8 @cite_22 .
@cite_5 @cite_9 @cite_22 @cite_8
2115785609 2046137117 1521014576 2038897673
One main challenge of the theory of computational effects is to understand how to combine various notions of effects in a meaningful way. Here, we study the particular case of the local state monad, which we would like to express as the result of combining together a family of global state monads parametrized by the number of available registers. To that purpose, we develop a notion of indexed monad which refines and generalizes Power's recent notion of indexed Lawvere theory. One main achievement of the paper is to integrate the block structure necessary to encode allocation as part of the resulting notion of indexed state monad. We then explain how to recover the local state monad from the functorial data provided by our notion of indexed state monad. This reconstruction is based on the guiding idea that an algebra of the indexed state monad should be defined as a section of a 2-categorical notion of fibration associated to the indexed state monad by a Grothendieck construction. We present a new approach to programming languages for parallel computers that uses an effect system to discover expression scheduling constraints. This effect system is part of a 'kinded' type system with three base kinds: types , which describe the value that an expression may return; effects , which describe the side-effects that an expression may have; and regions , which describe the area of the store in which side-effects may occur. Types, effects and regions are collectively called descriptions . Expressions can be abstracted over any kind of description variable -- this permits type, effect and region polymorphism. Unobservable side-effects can be masked by the effect system; an effect soundness property guarantees that the effects computed statically by the effect system are a conservative approximation of the actual side-effects that a given expression may have. The effect system we describe performs certain kinds of side-effect analysis that were not previously feasible. Experimental data from the programming language FX indicate that an effect system can be used effectively to compile programs for parallel computers. We model notions of computation using algebraic operations and equations. We show that these generate several of the monads of primary interest that have been used to model computational effects, with the striking omission of the continuations monad. We focus on semantics for global and local state, showing that taking operations and equations as primitive yields a mathematical relationship that reflects their computational relationship. Computational efficiency is a central concern in the design of knowledge representation systems. In order to obtain efficient systems, it has been suggested that one should limit the form of the statements in the knowledge base or use an incomplete inference mechanism. The former approach is often too restrictive for practical applications, whereas the latter leads to uncertainty about exactly what can and cannot be inferred from the knowledge base. We present a third alternative, in which knowledge given in a general representation language is translated (compiled) into a tractable form—allowing for efficient subsequent query answering. We show how propositional logical theories can be compiled into Horn theories that approximate the original information. The approximations bound the original theory from below and above in terms of logical strength. The procedures are extended to other tractable languages (for example, binary clauses) and to the first-order case. Finally, we demonstrate the generality of our approach by compiling concept descriptions in a general frame-based language into a tractable form.