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.