Explicit environments
We introduce lambda epsilon, a simply typed calculus with environments as first class values. As well as the usual constructs of lambda and application, we have e[a] which evaluates term a in an environment e. Our environments are sets of variable-value pairs, but environments can also be computed by function application and evaluation in some other environments. The notion of environments here is a generalization of explicit substitutions and records. We show that the calculus has desirable properties such as subject reduction, confluence, conservativity over the simply typed lambda beta -calculus and strong normalizability.
explicit environments simply typed calculus confluence conservativity strong normalizability