A Comparison of Strict and Non-Strict Semantics for Lists

Citation

Burch, Jerry R. (1988) A Comparison of Strict and Non-Strict Semantics for Lists. Master's thesis, California Institute of Technology. doi:10.7907/01bb-3j05. https://resolver.caltech.edu/CaltechTHESIS:03262012-113851465

Abstract

[Introduction] Implementations of functional programming languages can be classified according to whether they apply eager-evaluation or lazy-evaluation. Eager-evaluation gives rise to strict semantics while lazy-evaluation gives rise to non-strict semantics. In this paper we define the syntax of a simple functional programming language, and specify strict and non-strict denotational semantics for that language. These semantics are specified by giving axioms for the domains and semantic functions involved. The axioms for the two different semantics are very similar, differing only in the specification of cons. However, this small difference results in the domains for the two semantics being quite different. Giving axioms, rather than just postulating particular domains and semantic functions, makes more explicit the similarities of the strict and the non-strict semantics. We give a model of the axioms of the nonstrict semantics in order to show their consistency, and show that any two such models are isomorphic.

Thesis Files