To the top

Page Manager: Webmaster
Last update: 9/11/2012 3:13 PM

Tell a friend about this page
Print version

Operational Semantics Usi… - University of Gothenburg, Sweden Till startsida
Sitemap
To content Read more about how we use cookies on gu.se

Operational Semantics Using the Partiality Monad

Conference paper
Authors Nils Anders Danielsson
Published in Proceedings of the 17th ACM SIGPLAN international conference on Functional programming (ICFP 2012)
Pages 127-138
ISBN 978-1-4503-1054-3
Publication year 2012
Published at Department of Computer Science and Engineering (GU)
Pages 127-138
Language en
Links dx.doi.org/10.1145/2364527.2364546
https://gup.ub.gu.se/file/93812
Keywords dependent types, mixed induction and coinduction, partiality monad
Subject categories Theoretical computer science

Abstract

The operational semantics of a partial, functional language is often given as a relation rather than as a function. The latter approach is arguably more natural: if the language is functional,why not take advantage of this when defining the semantics? One can immediately see that a functional semantics is deterministic and, in a constructive setting, computable.

This paper shows how one can use the coinductive partiality monad to define big-step or small-step operational semantics for lambda-calculi and virtual machines as total, computable functions (total definitional interpreters). To demonstrate that the resulting semantics are useful type soundness and compiler correctness results are also proved. The results have been implemented and checked using Agda, a dependently typed programming language and proof assistant.

Page Manager: Webmaster|Last update: 9/11/2012
Share:

The University of Gothenburg uses cookies to provide you with the best possible user experience. By continuing on this website, you approve of our use of cookies.  What are cookies?