[TYPES] Replacement lemma
Sunil Kothari
skothari at uwyo.edu
Fri Sep 17 14:35:26 EDT 2010
Hello All,
I sent the below query to Coq mailing list but generated no response. My apologies if you receive multiple copies of this email.
I was wondering if there are any machine checked proofs (in any theorem prover) of replacement lemma [1,2] . I reproduce the lemma as stated by Wright and Felleisen in [1] below:
If
1. D is a derivation concluding \Gamma |- C [t]: \tau,
2. D1 is a sub-derivation of D concluding \Gamma’ |- t :\tau',
3. D1 occurs in D in the position corresponding to the hole ([]) in C, and
4. \Gamma' |- t’ : \tau' is derivable.
Then \Gamma |- C[t’] :\tau is derivable .
Also, I wanted to know if there is a corresponding lemma in a constraint setting where the sequent becomes a 4-place relation. For example, \Gamma, E |- t: \tau, where E denotes a list of equational constraints. If there is such a lemma, has it been formalized in any theorem prover ?
Any pointers/references will be highly appreciated.
Thanks,
Sunil
References:
[1] Andrew K. Wright and Matthias Felleisen. A syntactic approach to type
soundness. Information and Computation, 115(1):38-94, 1994.
[2] J. Roger Hindley and Jonathan P. Seldin. Introduction to Combinators
and /\-Calculus. Cambridge University Press, 1986.
More information about the Types-list
mailing list