Search: onr:"swepub:oai:gup.ub.gu.se/249946" >
Normalization by ev...
Normalization by evaluation in the delay monad: A case study for coinduction via copatterns and sized types
-
- Abel, Andreas, 1974 (author)
- Gothenburg University,Göteborgs universitet,Institutionen för data- och informationsteknik (GU),Department of Computer Science and Engineering (GU)
-
Chapman, James (author)
-
(creator_code:org_t)
- 2014
- 2014
- English.
-
In: Electronic Proceedings in Theoretical Computer Science, EPTCS. - 2075-2180.
- Related links:
-
https://gup.ub.gu.se...
-
show more...
-
https://doi.org/10.4...
-
show less...
Abstract
Subject headings
Close
- In this paper, we present an Agda formalization of a normalizer for simply-typed lambda terms. The normalizer consists of two coinductively defined functions in the delay monad: One is a standard evaluator of lambda terms to closures, the other a type-directed reifier from values to h-long b-normal forms. Their composition, normalization-by-evaluation, is shown to be a total function a posteriori, using a standard logical-relations argument. The successful formalization serves as a proof-of-concept for coinductive programming and reasoning using sized types and copatterns, a new and presently experimental feature of Agda.
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap -- Programvaruteknik (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Software Engineering (hsv//eng)
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Publication and Content Type
- ref (subject category)
- kon (subject category)
Find in a library
To the university's database