Published in

Elsevier, Information and Computation, 2(105), p. 159-267, 1993

DOI: 10.1006/inco.1993.1044

Links

Tools

Export citation

Search in Google Scholar

Full Abstraction in the Lazy Lambda Calculus

Journal article published in 1993 by S. Abramsky ORCID, C. H. L. Ong ORCID
This paper is made freely available by the publisher.
This paper is made freely available by the publisher.

Full text: Download

Green circle
Preprint: archiving allowed
Orange circle
Postprint: archiving restricted
Red circle
Published version: archiving forbidden
Data provided by SHERPA/RoMEO

Abstract

A theory of lazy λ-calculus is developed as a basis for lazy functional programming languages. This is motivated by a mismatch between the "standard" (i.e., sensible) theory of the classical λ-calculus and the practice of lazy functional programming. Part I sets up the fundamentals of the lazy λ-calculus starting from the pure lazy language λl. We develop the rudiments of weakly sensible λ-theory and characterize λl as the maximal such theory. The axiomatic framework of our theory is based on the notion of applicative transition systems which gives rise to lazy λ-models. The subclass of lazy λ-models which are operationally extensional are called lambda transition systems (lts′s). The canonical model of the lazy λ-calculus is the initial solution to the domain equation D ≅ [D → D]⊥. We set up the domain logic corresponding to the same type expression. In part II, we recast the full abstraction problem in the lazy λ-calculus. The pure lazy language λl is not equationally fully abstract w.r.t. D. In fact, λl, λlω, (a labelled version of λl), and λlc (λl augmented with a convergence testing constant) are all not equationally fully abstract w.r.t. D. We illustrate two approaches to full abstraction: