A number of program transformations currently of interest can be derived from Wadler's ‘free theorems’ for calculi approximating modern functional languages. Although delicate but fundamental issues arise in proving the correctness of free theorems-based program transformations, these issues have usually been left unaddressed in the correctness proofs appearing in the literature. As a result, most such proofs are incomplete, and most free theorems-based transformations are applied to programs in calculi for which they are not actually known to be correct.

The purpose of this paper is three-fold. First, we raise and clarify some of the issues that must be addressed when constructing correctness proofs for free theorems-based program transformations. Second, we offer a principled approach to developing such proofs. Third, we use Pitts' recent work on parametricity and observational equivalence to show how our approach can be used to give the first proof that transformations based on the Acid Rain theorems preserve observational equivalence of programs in a polymorphic lambda calculus supporting FPC-style fixpoints and algebraic data types. Correctness of the foldr-build rule, the destroy-unfoldr rule, and the hylofusion program transformation for this calculus follows immediately. The same approach is expected to yield complete correctness proofs for free theorems-based transformations in calculi that even more closely resemble languages with which programmers are concerned in practice.

Divisibility monoids are a natural algebraic generalisation of Mazurkiewicz trace monoids, namely monoids in which the distributivity of the underlying lattices is kept as a hypothesis, but the relations between the generators are not necessarily supposed to be commutations. Garside monoids are a natural algebraic generalisation of spherical Artin monoids, namely monoids in which the existence of common multiples is kept as a hypothesis, but the relations between the generators are not necessarily supposed to be of Coxeter type. Here, we show that the quasi-centre of these monoids can be studied and described in a similar way, and then we exhibit the intersection between the two classes of monoids.

A class $K$ of coalgebras for an endofunctor $T\,{:}\,\Set\to\Set$ is a behavioural covariety if it is closed under disjoint unions and images of bisimulation relations (hence closed under images and domains of coalgebraic morphisms, including subcoalgebras). $K$ may be thought of as the class of all coalgebras that satisfy some computationally significant property. In any logical system suitable for specifying properties of state-transition systems in the Hennessy–Milner style, each formula will define a class of models that is a behavioural covariety.

Assuming that the forgetful functor on $T$-coalgebras has a right adjoint, providing for the construction of cofree coalgebras, and letting $\G^T$ be the comonad arising from this adjunction, we show that behavioural covarieties $K$ are (isomorphic to) the Eilenberg–Moore categories of coalgebras for certain comonads $\G^K$ naturally associated with $\G^T$. These are called pure subcomonads of $\G^T$, and a categorical characterisation of them is given that involves a pullback condition on the naturality squares of a transformation from $\G^K$ to $\G^T$. We show that there is a bijective correspondence between behavioural covarieties of $T$-coalgebras and isomorphism classes of pure subcomonads of $\G^T$.

Continuous valuations have been proposed by several authors as a way of modelling probabilistic non-determinism in programming language semantics. Let $(X, {\cal O})$ be a topological space. A quasi-simple valuation on $X$ is the sup of a directed family of simple valuations. We show that quasi-simple valuations are exactly those valuations that extend to continuous valuations to the Alexandroff topology on the specialisation preordering of the topology $\cal O$. A number of applications are presented. In particular, we recover Jones' result that every continuous valuation is quasi-simple if $X$ is a continuous dcpo – in this case there is a least extension to the Alexandroff topology. We show that this can be refined if $X$ is algebraic, where every continuous valuation is the sup of a directed family of simple valuations based on finite elements. We exhibit another class of spaces in which every continuous valuation is quasi-simple, the so-called finitarily coherent spaces – in this case there is a largest extension to the Alexandroff topology. In general, the extension to the Alexandroff topology is not unique, unless, for example, the original valuation is bicontinuous. We also show that other natural spaces of valuations, namely those of discrete valuations and point-continuous valuations, can be characterised by similar extension theorems.

This paper addresses a conjecture of Smyth that says that if $D$ and $[D \rightarrow D]$ are effectively algebraic directed-complete partial orders with least element (cpo's), then $D$ is an effectively strongly algebraic cpo, though what is meant by an effectively algebraic and an effectively strongly algebraic cpo was not made precise.

Notions of an effectively strongly algebraic cpo and an effective SFP domain are introduced and shown to be (effectively) equivalent. Moreover, the conjecture is shown to hold if instead of being effectively algebraic, $[D \rightarrow D]$ is only required to be $\omega$-algebraic and $D$ is forced to have a completeness test, that is a procedure that decides for any two finite sets $X$ and $Y$ of compact cpo elements whether $X$ is a complete set of upper bounds of $Y$. As a consequence, the category of effective SFP objects and continuous maps turns out to be the largest Cartesian closed full subcategory of the category of $\omega$-algebraic cpo's that have a completeness test.

We then consider whether such a result also holds in a constructive framework, where one considers categories with constructive domains as objects, that is, domains consisting only of the constructive (computable) elements of an indexed $\omega$-algebraic cpo, and computable maps as morphisms. This is indeed the case: the category of constructive SFP domains is the largest constructively Cartesian closed weakly indexed effectively full subcategory of the category of constructive domains that have a completeness test and satisfy a further effectivity requirement.

We give a simple term calculus for the multiplicative exponential fragment of Classical Linear Logic, by extending Barber and Plotkin's dual-context system for the intuitionistic case. The calculus has the non-linear and linear implications as the basic constructs, and this design choice allows a technically manageable axiomatisation without commuting conversions. Despite this simplicity, the calculus is shown to be sound and complete for category-theoretic models given by *-autonomous categories with linear exponential comonads.

Starting from the $\lambda$-calculus with names, we develop a family of calculi with explicit substitutions that overcome the usual syntactical problems of substitution. The key idea is that only closed substitutions can be moved through certain constructs. This gives a weak form of reduction, called closed reduction, which is rich enough to capture both the call-by-value and call-by-name evaluation strategies in the $\lambda$-calculus. Moreover, since substitutions can move through abstractions and reductions are allowed under abstractions (if certain conditions hold), closed reduction naturally provides an efficient notion of reduction with a high degree of sharing and low overheads. We present a family of abstract machines for closed reduction. Our benchmarks show that closed reduction performs better than all standard weak strategies, and its low overheads make it more efficient than optimal reduction in many cases.

In this paper we introduce a new mathematical modelling technique called Periodic Linear Programming; the periodic properties of Periodic Linear Programs (PLPs) permit the specification of inter-period constraints in embedded systems, in a straightforward and natural manner. We analyse PLPs in which the relationship between program variables is restricted to the class of difference constraints. Our analysis establishes that such PLPs can be reduced to simple linear programs, and hence decided in polynomial time. The class of difference constraints is extremely important from the perspective of embedded systems design, in that it permits the specification of complex timing constraints in real-time specification languages. A PLP can be thought of as a finite-description tool that represents infinite-state systems; although we use this tool purely for the purpose of modelling real-time scheduling problems, PLPs also find applications in other areas, such as concurrency design. In studying this programming paradigm, we develop novel techniques that, to the best of our knowledge, are not part of the literature. We build on the PLP structure to introduce a generalisation called Periodic Quantified Linear Programming; this programming paradigm permits the specification and analysis of uncertainty in the parameters of a PLP. Consequently, a Periodic Quantified Linear Program (PQLP) is the natural modelling tool to capture the requirements of periodic, embedded systems that are characterised by uncertainty in the execution times of processes, periodicity and relative timing constraints. In this paper, we use the PQLP structure to model and solve the periodic version of the zero-clairvoyant scheduling problem. Modelling uncertainty in the problem description is a typical technique used to incorporate a measure of fault-tolerance in the specification.