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.
Examples of include those behaviors of programs involving , , or . Moggi @cite_23 brought breakthrough to the theory of computational effects by advocating that these diverse kinds of computational effects can be uniformly modeled by . For example, corresponding to the notion of global state there is a monad @math (say, on @math ) called the , defined as @math where @math is the set of . Similarly, there are monads for nondeterministic branch, input output, etc. What is especially interesting in Moggi's approach is that, not only mathematical concepts that model these computational effects possess the suitable monad structures, the developed in pure mathematics can be fruitfully applied to the study of computational effects. Indeed, Moggi @cite_23 @cite_20 constructed categorical models of his calculus for computational effects via the .
@cite_20 @cite_23
1997143185 2156876717
Abstract The λ-calculus is considered a useful mathematical tool in the study of programming languages, since programs can be identified with λ-terms. However, if one goes further and uses βη-conversion to prove equivalence of programs, then a gross simplification is introduced (programs are identified with total functions from values to values ) that may jeopardise the applicability of theoretical results. In this paper we introduce calculi, based on a categorical semantics for computations , that provide a correct basis for proving equivalence of programs for a wide range of notions of computation . The lambda -calculus is considered a useful mathematical tool in the study of programming languages. However, if one uses beta eta -conversion to prove equivalence of programs, then a gross simplification is introduced. The author gives a calculus based on a categorical semantics for computations, which provides a correct basis for proving equivalence of programs, independent from any specific computational model. >