Towards patterns for heaps and imperative lambdas

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

In functional programming, pointfree relation calculi have been fruitful for general theories of program construction, but for specific applications pointwise expressions can be more convenient and comprehensible. In imperative programming, refinement calculi have been tied to pointwise expression in terms of state variables, with the curious exception of the ubiquitous but invisible heap. To integrate pointwise with pointfree, de Moor and Gibbons [12] extended lambda calculus with non-injective pattern matching interpreted using relations. This article gives a semantics of that language using “ideal relations” between partial orders, and a second semantics using predicate transformers. The second semantics is motivated by its potential use with separation algebra, for pattern matching in programs acting on the heap. Laws including lax beta and eta are proved in these models and a number of open problems are posed.

Original languageEnglish
Pages (from-to)1038-1056
Number of pages19
JournalJournal of Logical and Algebraic Methods in Programming
Volume85
Issue number5
DOIs
StatePublished - 1 Aug 2016

Fingerprint

Dive into the research topics of 'Towards patterns for heaps and imperative lambdas'. Together they form a unique fingerprint.

Cite this