Back to search

McMaster University

Assignment Calculus: A Pure Imperative Reasoning Language

Abstract

dc:description.abstract

<p> In this thesis, we undertake a study of imperative reasoning. Beginning with a philosophical analysis of the distinction between imperative and functional language features, we define a (pure) imperative language as one whose constructs are inherently referentially opaque. We then give a definition of a reasoning language by identifying desirable properties such a language should have.</p> <p> The rest of the thesis presents a new pure imperative reasoning language, Assignment Calculus AC. The main idea behind AC is that R. Montague's modal operators of intension and extension are useful tools for modeling procedures in programming languages. This line of thought builds on T. Janssen's demonstration that Montague's intensional logic is well suited to dealing with assignment statements, pointers, and other difficult features of imperative languages.</p> <p> AC consists of only four basic constructs, assignment 'X := t', sequence 't; u', procedure formation 'it' and procedure invocation '!t'. Three interpretations are given for AC: an operational semantics, a denotational semantics, and a term-rewriting system. The three are shown to be equivalent. Running examples are used to illustrate each of the interpretations.</p> <p> Five variants of AC are then studied. By removing restrictions from AC's syntactic and denotational definitions, we can incorporate L-values, lazy evaluation, state backtracking, and procedure composition into AC. By incorporating procedure composition, we show that AC becomes a self-contained Turing complete language in the same way as the untyped λ-calculus: by encoding numerals, Booleans, and control structures as AC terms. Finally we look at the combination of AC with a typed λ-calculus.</p>

Degree

thesis:*
Department dc:contributor.department
Computer Science
Year dc:date.issued
2010

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Bender, Marc
Advisor dc:contributor.advisor
  • Zucker, Jeffery

Subjects

dc:subject × 1

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
McMaster University
Base URL
macsphere.mcmaster.ca/server/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Bender, Marc. Assignment Calculus: A Pure Imperative Reasoning Language. 2010. http://hdl.handle.net/11375/18923