View Related Documents

Abstract

Some new calculi [1,12,7], referred to by the collective name of lambdasgr- calculus, have been recently introduced to provide an explicit treatment of substitutions in the lambda-calculus. They are term rewriting systems, with two sorts: substitution and term. The lambda-terms are exactly the ground lambdasgr-terms of sort term containing no substitutions and the beta-reduction is decomposed in these calculi, into a starting reduction with a rule called (Beta) followed by a derivation computing explicitly the substitution. These calculi differ by their treatment of substitution. In this paper, we extend the lambdasgr-calculi with a conditional rewriting relation, called ceegr. This relation coincides, on lambda-terms, with the classicaleegr-reduction of lambda-calculus. We prove that the confluent lambdasgr-calculus, augmented byceegr, remains confluent and that the ground confluent version [1], extended by ceegr, is still ground confluent. The result extends readily to Categorical Combinatory Logic. The proof is done by the interpretation method introduced in [9].

Keywords  Lambda-calculus - Explicit substitution - Term rewriting system - Eta-conversion

This work has been partially supported by the Eureka Software Factory project.

Fulltext Preview

Image of the first page of the fulltext document