Edinburgh Research Archive >
Informatics, School of >
Informatics thesis and dissertation collection >
Please use this identifier to cite or link to this item:
Files in This Item:
||Size||Format||packages.zip||File not available for download||9.67 MB||Unknown|
|Pretnar2010.pdf||PhD thesis||795.38 kB||Adobe PDF||View/Open|
|Title: ||Logic and handling of algebraic effects|
|Authors: ||Pretnar, Matija|
|Supervisor(s): ||Plotkin, Gordon|
|Issue Date: ||2010|
|Publisher: ||The University of Edinburgh|
|Abstract: ||In the thesis, we explore reasoning about and handling of algebraic effects. Those
are computational effects, which admit a representation by an equational theory.
Their examples include exceptions, nondeterminism, interactive input and output,
state, and their combinations.
In the first part of the thesis, we propose a logic for algebraic effects. We
begin by introducing the a-calculus, which is a minimal equational logic with
the purpose of exposing distinct features of algebraic effects. Next, we give a
powerful logic, which builds on results of the a-calculus. The types and terms
of the logic are the ones of Levy’s call-by-push-value framework, while the reasoning
rules are the standard ones of a classical multi-sorted first-order logic
with predicates, extended with predicate fixed points and two principles that describe
the universality of free models of the theory representing the effects at
hand. Afterwards, we show the use of the logic in reasoning about properties of
effectful programs, and in the translation of Moggi’s computational ¸-calculus,
Hennessy-Milner logic, and Moggi’s refinement of Pitts’s evaluation logic.
In the second part of the thesis, we introduce handlers of algebraic effects.
Those not only provide an algebraic treatment of exception handlers, but generalise
them to arbitrary algebraic effects. Each such handler corresponds to a
model of the theory representing the effects, while the handling construct is interpreted
by the homomorphism induced by the universal property of the free
model. We use handlers to describe many previously unrelated concepts from
both theory and practice, for example CSS renaming and hiding, stream redirection,
timeout, and rollback.|
|Sponsor(s): ||Engineering and Physical Sciences Research Council (EPSRC)|
Microsoft Research in Silicon Valley
Slovenian Academy of Sciences and Arts
|Keywords: ||computational effects|
|Appears in Collections:||Informatics thesis and dissertation collection|
Items in ERA are protected by copyright, with all rights reserved, unless otherwise indicated.