Back to search

University of Glasgow

Supporting formal reasoning about functional programs

Abstract

dc:description.abstract

It is often claimed that functional programming languages, and in particular pure functional languages are suitable for formal reasoning. This claim is supported by the fact that many people in the functional programming community do reason about languages and programs in a formal or semi-formal way. Different reasoning principles such as equational reasoning, induction and co-induction, are used, depending on the nature of the problem. Using a computer program to check the application of rules and to mechanise the tedious bookkeeping involved can simplify proofs and provide more confidence in their correctness. When reasoning about programs, this can also allow experiments with new rules and reasoning styles, where a user may not be confident about structuring a proof on paper. Checking the applicability of a rule can eliminate the risk of mistakes caused by misunderstanding the theory being used. Just as there are different ways in which formal or informal reasoning can be applied in functional programming, there are different ways in which tools can be provided to support this reasoning. This thesis describes an investigation of how to develop a mechanised reasoning system to allow reasoning about algorithms as a functional programmer would write them, not an encoding of the algorithm into a significantly different form. In addition, this work aims to develop a system to support a user who is not a theorem proving expert or an expert in the theoretical foundations of functional programming. The work is aimed towards a system that could be used by a functional programmer developing real programs and wishing to prove some or all of the programs correct or to prove that two programs are equivalent.

Degree

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

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Collins, Graham Richard McFarlane

Subjects

dc:subject × 1

Rights

Language dc:language
en

Identifiers

dc:identifier.*

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
citation

Collins, Graham Richard McFarlane. Supporting formal reasoning about functional programs. PhD thesis, University of Glasgow, 2001. https://doi.org/10.5525/gla.thesis.4609