A Model for a List-Oriented Extension of the Lambda Calculus,
Glenn Durfee · 1997
This work is intended to provide a semantics for a fragment of a programming language described by Gyorgy R'ev'esz in [R'ev88], for which no model was known. We begin with a brief presentation of the syntax of the lambda calculus and some relevant extensions. We then describe a class of complete lattices and use them as models for the lambda calculus. We then find specialized sublattices which we use as models for the extensions of the lambda calculus, thus achieving the original goal of finding a semantics for R'ev'esz's language. Keywords: lambda calculus, applicative lists, denotational semantics, domain theory Contents 1 A List-oriented Extension of the Lambda Calculus 2 1.1 The Lambda Calculus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 The Lambda Calculus with Applicative Lists . . . . . . . . . . . . . . . . . . . . . . 3 1.3 The Lambda Calculus with Explicit Products . . . . . . . . . . . . . . . . . . . . . . 4 2 Powerset Models of the La...