Explicit Substitutions and All That

Abstract

Explicit substitution calculi are extensions of the lambda-calculus where the substitution mechanism is internalized into the theory. This feature makes them suitable for implementation and theoretical study of logic-based tools such as strongly typed programming languages and proof assistant systems. In this paper we explore new developments on two of the most successful styles of explicit substitution calculi: the lambda sigma- and lambda S(e)-calculi.