A Caltech Library Service

A Comparison of Strict and Non-Strict Semantics for Lists


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.


[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.

Item Type:Thesis (Master's thesis)
Subject Keywords:Computer Science
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Computer Science
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Martin, Alain J.
Thesis Committee:
  • Unknown, Unknown
Defense Date:1 January 1988
Other Numbering System:
Other Numbering System NameOther Numbering System ID
Computer Science Technical Reports1988-12
Record Number:CaltechTHESIS:03262012-113851465
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:6868
Deposited By: Benjamin Perez
Deposited On:26 Mar 2012 18:46
Last Modified:07 Oct 2021 20:13

Thesis Files

[img] PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page