The Algebraic Properties of if-then-else with Commutative Three-Valued Tests

Abstract

This thesis studies an algebraic model of computable programs and the if-then-else operation. The programs here are considered deterministic, but not assumed to be always halting, so they are modelled by a semigroup of partial functions, with several extra operations in addition to the original binary operation of the semigroup. The if-then-else operation involves not only programs, but logical tests too. Hence, it calls for a separate algebra of tests. Evaluating a test often requires running another program, so the tests are also possibly non halting. When tests do not always halt, the results of conjunctions (logical ‘and’) and disjunctions (logical ‘or’) can differ, depending on whether sequential or parallel evaluation is applied. The parallel evaluation is what this thesis adopts. The overall ‘program algebra’ consists of two sorts, one of programs and the other of tests. Each sort has its own operations, and there are hybrid operations such as if-then-else which involve both sorts. This thesis establishes the axioms of all these operations by building an embedding from the abstract program algebra into a concrete one. At the end is a discussion on the algebra of tests without the programs, where the differences between the two evaluation paradigms are explored in detail.