pipette
ESEspañol

Normalization by Evaluation with Substitutions as Operations

Jason Z. S. Hu

Preprint

In the authors' words

In previous works on normalization by evaluation (NbE) with an untyped domain model, explicit substitutions are a major decision choice, which, in retrospect, is taken to simplify subsequent semantic proofs. This choice hence is taken for a purely technical reason. In addition, there is no obvious lemma to test the completeness of the definition or the laws for explicit substitutions. In this technical report, we investigate NbE in a typical setting, i.e. defining substitutions as operations. We show that this setting brings simplifications in proving syntactic properties and soundness of NbE, though complications are introduced in the completeness proof of NbE.

Main resultLimitation the authors admit

Appeared: Friday, October 16. arXiv. Preprint, not yet peer-reviewed.