Informatics Report Series
Report
 EDI-INF-RR-0414
 Related Pages Report (by Number) Index Report (by Date) Index Author Index Institute Index Home
Title:Generic models for computational effects
Authors: John Power
Date: 2006
Publication Title:Theoretical Computer Science
Publisher:Elsevier
Publication Type:Journal Article Publication Status:Published
Volume No:364 Page Nos:254-269
DOI:10.1016/j.tcs.2006.08.006
Abstract:
A \textit{Freyd}-category is a subtle generalisation of the notion of a category with finite products. It is suitable for modelling environments in call-by-value programming languages, such as the computational $\lambda$-calculus, with computational effects. We develop the theory of \textit{Freyd}-categories with that in mind. We first show that any countable Lawvere theory, hence any signature of operations with countable arity subject to equations, directly generates a \textit{Freyd}-category. We then give canonical, universal embeddings of \textit{Freyd}-categories into closed \textit{Freyd}-categories, characterised by being free cocompletions. The combination of the two constructions sends a signature of operations and equations to the Kleisli category for the monad on the category $Set$ generated by it, thus refining the analysis of computational effects given by monads. That in turn allows a more structural analysis of the $\lambda_c$-calculus. Our leading examples of signatures arise from side-effects, interactive input/output and exceptions. We extend our analysis to an enriched setting in order to account for recursion and for computational effects and signatures that inherently involve it, such as partiality, nondeterminism and probabilistic nondeterminism.