Weak call-by-value lambda calculus as a model of computation in Coq

Y Forster, G Smolka - International Conference on Interactive Theorem …, 2017 - Springer
International Conference on Interactive Theorem Proving, 2017Springer
We formalise a weak call-by-value λ-calculus we call L in the constructive type theory of Coq
and study it as a minimal functional programming language and as a model of computation.
We show key results including (1) semantic properties of procedures are undecidable,(2) the
class of total procedures is not recognisable,(3) a class is decidable if it is recognisable,
corecognisable, and logically decidable, and (4) a class is recognisable if and only if it is
enumerable. Most of the results require a step-indexed self-interpreter. All results are …
Abstract
We formalise a weak call-by-value -calculus we call L in the constructive type theory of Coq and study it as a minimal functional programming language and as a model of computation. We show key results including (1) semantic properties of procedures are undecidable, (2) the class of total procedures is not recognisable, (3) a class is decidable if it is recognisable, corecognisable, and logically decidable, and (4) a class is recognisable if and only if it is enumerable. Most of the results require a step-indexed self-interpreter. All results are verified formally and constructively, which is the challenge of the project. The verification techniques we use for procedures will apply to call-by-value functional programming languages formalised in Coq in general.
Springer
以上显示的是最相近的搜索结果。 查看全部搜索结果