Back to search

University of Glasgow

Between Functions and Relations in Calculating Programs

Abstract

dc:description.abstract

This thesis is about the calculational approach to programming, in which one derives programs from specifications. One such calculational paradigm is Ruby, the relational calculus developed by Jones and Sheeran for describing and designing circuits. We identify two shortcomings with derivations made using Ruby. The first is that the notion of a program being an implementation of a specification has never been made precise. The second is to do with types. Fundamental to the use of type information in deriving programs is the idea of having types as special kinds of programs. In Ruby, types are partial equivalence relations (pers). Unfortunately, manipulating some formulae involving types has proved difficult within Ruby. In particular, the preconditions of the 'induction' laws that are much used within program derivation often work out to be assertions about types; such assertions have typically been verified either by informal arguments or by using predicate calculus, rather than by applying algebraic laws from Ruby. In this thesis we address both of the shortcomings noted above. We define what it means for a Ruby program to be an implementation, by introducing the notion of a causal relation, and the network denoted by a Ruby program. A relation is causal if it is functional in some structural way, but not necessarily from domain to range; a network captures the connectivity between the primitive relations in a program. Moreover, we present an interpreter for Ruby programs that are implementations. Our technique for verifying an assertion about types is to first express it using operators that give the best left and right types for a relation, and then verify this assertion by using algebraic properties of these operators.

Degree

thesis:*
Level dc:type.qualificationlevel
PhD
Grantor dc:publisher.institution
University of Glasgow
Year dc:date.issued
1992

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Hutton, Graham Muir

Rights

Language dc:language
en

Chain of custody

source
Harvested from
University of Glasgow
Base URL
theses.gla.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Hutton, Graham Muir. Between Functions and Relations in Calculating Programs. PhD thesis, University of Glasgow, 1992.