Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.TYPES.2019.4
URN: urn:nbn:de:0030-drops-130682
URL: https://drops.dagstuhl.de/opus/volltexte/2020/13068/
Altenkirch, Thorsten ; Geniet, Colin
Big Step Normalisation for Type Theory
| pdf-format: |
|
Abstract
Big step normalisation is a normalisation method for typed lambda-calculi which relies on a purely syntactic recursive evaluator. Termination of that evaluator is proven using a predicate called strong computability, similar to the techniques used to prove strong normalisation of β-reduction for typed lambda-calculi. We generalise big step normalisation to a minimalist dependent type theory. Compared to previous presentations of big step normalisation for e.g. the simply-typed lambda-calculus, we use a quotiented syntax of type theory, which crucially reduces the syntactic complexity introduced by dependent types. Most of the proof has been formalised using Agda.
BibTeX - Entry
@InProceedings{altenkirch_et_al:LIPIcs:2020:13068,
author = {Thorsten Altenkirch and Colin Geniet},
title = {{Big Step Normalisation for Type Theory}},
booktitle = {25th International Conference on Types for Proofs and Programs (TYPES 2019)},
pages = {4:1--4:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-158-0},
ISSN = {1868-8969},
year = {2020},
volume = {175},
editor = {Marc Bezem and Assia Mahboubi},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13068},
URN = {urn:nbn:de:0030-drops-130682},
doi = {10.4230/LIPIcs.TYPES.2019.4},
annote = {Keywords: Normalisation, big step normalisation, type theory, dependent types, Agda}
}
| Keywords: | Normalisation, big step normalisation, type theory, dependent types, Agda | |
| Seminar: | 25th International Conference on Types for Proofs and Programs (TYPES 2019) | |
| Issue date: | 2020 | |
| Date of publication: | 24.09.2020 | |
| Supplementary Material: | https://github.com/colingeniet/big-step-normalisation |
