Home
Scholarly Works
Information effects
Conference

Information effects

Abstract

Computation is a physical process which, like all other physical processes, is fundamentally reversible. From the notion of type isomorphisms, we derive a typed, universal, and reversible computational model in which information is treated as a linear resource that can neither be duplicated nor erased. We use this model as a semantic foundation for computation and show that the "gap" between conventional irreversible computation and logically reversible computation can be captured by a type-and-effect system. Our type-and-effect system is structured as an arrow metalanguage that exposes creation and erasure of information as explicit effect operations. Irreversible computations arise from interactions with an implicit information environment, thus making them a derived notion, much like open systems in Physics. We sketch several applications which can benefit from an explicit treatment of information effects, such as quantitative information-flow security and differential privacy.

Authors

James RP; Sabry A

Volume

47

Pagination

pp. 73-84

Publisher

Association for Computing Machinery (ACM)

Publication Date

January 18, 2012

DOI

10.1145/2103621.2103667

Conference proceedings

ACM SIGPLAN Notices

Issue

1

ISSN

0362-1340

Contact the Experts team