The fine-structure of lambda calculus
RP Rob Nederpelt · TU/e Research Portal · 1992
This paper starts by setting the ground for a lambda calculus notation that strongly mirrors the two fundamental operations of term construction, namely abstraction and application.Such notation singles out those parts of a term, called items in the report, that are added during abstraction and application.It turns out that this item-based notation offers many advantages for various notions of the lambda calculus.It allows a linear representation of terms and makes it, for example, straightforward to locate free and bound variables and to find the binding A-operators relevant to particular occurrences.Furthermore, step-wise explicit substitution is easily embeddable in the lambda calculus using the new notation.The item notation proves to be a powerful device for the representation of basic substitution steps, giving rise to different versions of ,a-reduction.Last but not least, the new notation allows for segment abbreviations, enabling one to prevent a lot of duplications in A-terms, while remaining in the general proposed frame.In this paper we don't stop at the advantages of the new notation, but go further to accomlllodate important notions of the lambda calculus in the new framework.We discuss the role of types in the presented setting and provide a type operator which gives a representative type for a typeable tenll.Moreover, in accommodating types in our system, it turns out that a general framework for many typed lambda calculi can be obtained in the presented setting.Another attraction of our new approach is that by specifying a number of parameters, one defines one system of typed lambda calculus or another.In fact, it turns out that many known systems of typed lambda calculus fit in the proposed setting, in particular the ones connected with "Barendregt's cube" [Barendregt 9x].The general framework leads naturally to a number of generalizations.It gives much freedom and is at the same time simple and perspicuous.It allows theorists to compare the different systems as to important properties and enables practical users to make their choices at the relevant place.