Since 2014
Program Extraction from Proofs of Weak Head Normalization
BRICS Report Series
View Archive Info| Field | Value | |
| Title |
Program Extraction from Proofs of Weak Head Normalization
|
|
| Creator |
Biernacka, Malgorzata
Danvy, Olivier Støvring, Kristian |
|
| Description |
We formalize two proofs of weak head normalization for the simply typed lambda-calculus in first-order minimal logic: one for normal-order reduction, and one for applicative-order reduction in the object language. Subsequently we use Kreisel's modified realizability to extract evaluation algorithms from the proofs, following Berger; the proofs are based on Tait-style reducibility predicates, and hence the extracted algorithms are instances of (weak head) normalization by evaluation, as already identified by Coquand and Dybjer.
|
|
| Publisher |
Aarhus University
|
|
| Contributor |
—
|
|
| Date |
2005-04-11
|
|
| Type |
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion — |
|
| Format |
application/pdf
|
|
| Identifier |
https://tidsskrift.dk/brics/article/view/21878
10.7146/brics.v12i12.21878 |
|
| Source |
BRICS Report Series; No 12 (2005): RS-12 Program Extraction from Proofs of Weak Head Normalization
BRICS Report Series; No 12 (2005): RS-12 Program Extraction from Proofs of Weak Head Normalization 1601-5355 0909-0878 |
|
| Language |
eng
|
|
| Relation |
https://tidsskrift.dk/brics/article/view/21878/19305
|
|
| Rights |
Copyright (c) 2015 BRICS Report Series
|
|