Parameterised notions of computation

Research output: Contribution to journalArticle

54 Citations (Scopus)

Abstract

Moggi’s Computational Monads and Power et al’s equivalent notion of Freyd category have captured a large range of computational effects present in programming languages. Examples include non-termination, non-determinism, exceptions, continuations, side-effects and input/output. We present generalisations of both computational monads and Freyd categories, which we call parameterised monads and parameterised Freyd categories, that also capture computational effects with parameters. Examples of such are composable continuations, side-effects where the type of the state varies and input/output where the range of inputs and outputs varies. By also considering structured parameterisation, we extend the range of effects to cover separated side-effects and multiple independent streams of I/O. We also present two typed λ-calculi that soundly and completely model our categorical definitions — with and without symmetric monoidal parameterisation — and act as prototypical languages with parameterised effects.
LanguageEnglish
Pages335-376
Number of pages42
JournalJournal of Functional Programming
Volume19
Issue number3-4
DOIs
Publication statusPublished - 9 Jun 2009

Fingerprint

Parameterization
Computer programming languages

Keywords

  • computational effects
  • programming language
  • parameters

Cite this

@article{a9f5b73ecb22436f85c3a4bbacb569bb,
title = "Parameterised notions of computation",
abstract = "Moggi’s Computational Monads and Power et al’s equivalent notion of Freyd category have captured a large range of computational effects present in programming languages. Examples include non-termination, non-determinism, exceptions, continuations, side-effects and input/output. We present generalisations of both computational monads and Freyd categories, which we call parameterised monads and parameterised Freyd categories, that also capture computational effects with parameters. Examples of such are composable continuations, side-effects where the type of the state varies and input/output where the range of inputs and outputs varies. By also considering structured parameterisation, we extend the range of effects to cover separated side-effects and multiple independent streams of I/O. We also present two typed λ-calculi that soundly and completely model our categorical definitions — with and without symmetric monoidal parameterisation — and act as prototypical languages with parameterised effects.",
keywords = "computational effects , programming language, parameters",
author = "Robert Atkey",
year = "2009",
month = "6",
day = "9",
doi = "10.1017/S095679680900728X",
language = "English",
volume = "19",
pages = "335--376",
journal = "Journal of Functional Programming",
issn = "0956-7968",
number = "3-4",

}

Parameterised notions of computation. / Atkey, Robert.

In: Journal of Functional Programming, Vol. 19, No. 3-4, 09.06.2009, p. 335-376.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Parameterised notions of computation

AU - Atkey, Robert

PY - 2009/6/9

Y1 - 2009/6/9

N2 - Moggi’s Computational Monads and Power et al’s equivalent notion of Freyd category have captured a large range of computational effects present in programming languages. Examples include non-termination, non-determinism, exceptions, continuations, side-effects and input/output. We present generalisations of both computational monads and Freyd categories, which we call parameterised monads and parameterised Freyd categories, that also capture computational effects with parameters. Examples of such are composable continuations, side-effects where the type of the state varies and input/output where the range of inputs and outputs varies. By also considering structured parameterisation, we extend the range of effects to cover separated side-effects and multiple independent streams of I/O. We also present two typed λ-calculi that soundly and completely model our categorical definitions — with and without symmetric monoidal parameterisation — and act as prototypical languages with parameterised effects.

AB - Moggi’s Computational Monads and Power et al’s equivalent notion of Freyd category have captured a large range of computational effects present in programming languages. Examples include non-termination, non-determinism, exceptions, continuations, side-effects and input/output. We present generalisations of both computational monads and Freyd categories, which we call parameterised monads and parameterised Freyd categories, that also capture computational effects with parameters. Examples of such are composable continuations, side-effects where the type of the state varies and input/output where the range of inputs and outputs varies. By also considering structured parameterisation, we extend the range of effects to cover separated side-effects and multiple independent streams of I/O. We also present two typed λ-calculi that soundly and completely model our categorical definitions — with and without symmetric monoidal parameterisation — and act as prototypical languages with parameterised effects.

KW - computational effects

KW - programming language

KW - parameters

UR - http://personal.cis.strath.ac.uk/~raa/paramnotions-jfp.html

U2 - 10.1017/S095679680900728X

DO - 10.1017/S095679680900728X

M3 - Article

VL - 19

SP - 335

EP - 376

JO - Journal of Functional Programming

T2 - Journal of Functional Programming

JF - Journal of Functional Programming

SN - 0956-7968

IS - 3-4

ER -