Publications

This paper contributes to the unification of semantic models and program development techniques by making a link from multirelations and predicate transformer semantics to algebraic semantics and the derivation of programs by calculation, as used in functional programming and relational program development. Two common ways to characterise iteration, namely the functional programming operators map and fold, are extended to multirelations, using concepts from category theory, power allegories and monads.

This paper presents an introduction to a calculus of binary multirelations, which can model both angelic and demonic kinds of non-determinism. The isomorphism between up-closed multirelations and monotonic predicate transformers allows a different view of program transformation, and program transformation calculations using multirelations are easier to perform in some circumstances. Multirelations are illustrated by modelling both kinds of nondeterministic behaviour in games and resource-sharing protocols.

The map and fold operators are both key elements of every functional programmer's toolkit. In this paper we examine the corresponding concepts in the domain of multirelations, which can be used to model both angelic and demonic nondeterminism.

This paper describes some functional programming exercises in the form of implementing some interactive word puzzle games. The games share a common framework and provide good opportunities for practising higher-order functions, recursion, and other list processing functions. Experience suggests that these games are motivating and enjoyable for students.

This paper describes an on-line assessment system (HCIQ) for HCI. The assessment questions were structured to assess understanding of HCI concepts in a way that allows for automated marking. The HCIQ system was designed so that for a large number of students, the on-line test could take place in multiple short sittings in computer labs, and in such a way that cheating was prevented.

This study investigated the effects of two computer-implemented techniques (colour and interactive animation) on learning 3D vectors. The participants were 43 female Saudi Arabian high school students, who were pre-tested on 3D vectors using a paper questionnaire consisting of calculation and visualization types of questions, and then divided into four groups. Each group was allocated to a different version of software for learning 3D vectors: the versions differed in their use of colour/greyscale and static images/interactive animation. After using the software, a post-test was administered. All students improved their overall test scores, with no significant difference between the groups. However, test scores on the visualization questions differed noticeably, with the groups viewing animated versions scoring higher than the groups seeing static versions.

This paper presents a greedy algorithm for the design of circular dartboards and linear (hoopla) boards. The algorithm's correctness also leads to a simple verification of the optimality of certain arrangements.

A calculus of multirelations is presented, which can model two kinds of non-determinism: angelic and demonic. The basic operators, refinement and correctness conditions of the calculus are illustrated with examples of games and resource division protocols.

Our grand challenge:
Develop materials and approaches that permit scientific techniques of software development to be taught successfully to all who aspire to become programmers, as a fundamental part of their programming education.

This paper presents principles for the classification of greedy algorithms for optimization problems. These principles are made precise by their expression in the relational calculus, and illustrated by various examples. A discussion compares this work to other greedy algorithms theory.

This presents a generic algorithm to obtain a minimum sized partition of a partially ordered set into chains. The algorithm is illustrated with three examples, including a novel box stacking problem and solution.

This concerns a combinatorial problem to allocate drugs for a medical trial. Two algorithms are presented which solve a more general problem, one of these making crucial use of laziness to achieve a (not straightforward) linear complexity. These results are then used to solve the original problem.

Quilting (including the patchwork that the typical quilter indulges in) is primarily a leisure activity, one which on the surface seems to have little to do with functional programming. However, both the patchwork and the social participation in group projects often yield interesting combinatorial problems. This paper looks at the suitability of functional programming for solving these types of problems, considering two representative problems and their functional solutions.

We examine the use of the relational limit operator for the solution of combinatorial problems. In particular, the first developmental steps from specifications and the construction of feasible solutions are considered.

Dynamic programming has long been used as an algorithm design technique, with various mathematical theories proposed to model it. Here we take a different perspective, using a relational calculus to model both problems and their solutions obtained from dynamic programming. This approach serves to shed new light on the different styles of dynamic programming, represneting them by different search strategies of the tree-like space of partial solutions.

Defines a graphical calculus for aiding reasoning in the relational and sequential calculi. In particular the power and expressivity of the graph calculus is emphasized.

The main contribution of this thesis is a study of the dynamic programming and greedy strategies for solving combinatorial optimization problems. The study is carried out in the context of a calculus of relations, and generalises previous work by using a loop operator in the imperative programming style for generating feasible solutions, rather than the fold and unfold operators of the functional programming style. The relationship between fold operators and loop operators is explored, and it is shown how to convert from the former to the latter.
This fresh approach provides additional insights into the relationship between dynamic programming and greedy algorithms, and helps to unify previously distinct approaches to solving combinatorial optimization problems. Some of the solutions discovered are new and solve problems which had previously proved difficult. The material is illustrated with a selection of problems and solutions that is a mixture of old and new.
Another contribution is the invention of a new calculus, called the graph calculus, which is a useful tool for reasoning in the relational calculus and other non-relational calculi. The graph calculus represents formulae by formal pictures, and this enables proofs to be expressed more simply. It is also more powerful than standard point-free reasoning, and its simple intuitive basis aids greater understanding of the structure of formulae and certain proofs.

We present a graphical calculus, which allows mathematical formulae to be represented and reasoned about using a visual representation. We define how a formula may be represented by a graph, and present a number of laws for transforming graphs, and describe the effects these transformations have on the corresponding formulae. We then use these transformation laws to perform proofs. We illustrate the graphical calculus by applying it to the relational and sequential calculi. The graphical calculus makes formulae easier to understand, and so often makes the next step in a proof more obvious. Furthermore, it is more expressive, and so allows a number of proofs that cannot otherwise be undertaken in a point-free way.