We investigate Cpo-algebraic completeness and compactness. This is a particularly well behaved setting. For example, we show that Cpo-algebraic completeness and parameterised Cpo-algebraic completeness coincide; whilst, for Cppo⊥-categories, we further show the coincidence of Cpo-algebraic completeness and parameterised Cpo-algebraic compactness. As a by-product, we identify a 2-category of kinds, called Kind, all of whose objects are parameterised Cpo-algebraically ω-compact categories. Kind is 2-cartesian-closed, op-closed, closed under the formation of categories of algebras and coalgebras with lax homomorphisms, and has a unique (up to isomorphism) uniform fixed-point operator. Thus, Kind is appropriate for interpreting type systems with kinds built by recursion from products, exponentials, algebras and coalgebras; but neither such a system nor its interpretation will be discussed here.

Cpo-Algebraic Completeness

Cpo-algebraic completeness is studied. First, we focus on those Cpo-categories for which the initial object embeds in every object of the category. The reason being that in this case the presence of colimits of ω-chains of embeddings guarantees algebraic ω-completeness which turns out to coincide with algebraic completeness. Further, an equational characterisation of initial algebras becomes available. Second, we explore categories of algebras and lax homomorphisms to finally show that algebraic completeness and parameterised algebraic completeness coincide.

Definition 7.1.1 In a Poset-category, an e-initial object is an initial object such that every morphism with it as source is an embedding. The dual notion is called a p-terminal object. An object which is both e-initial and p-terminal is called an ep-zero.

The denotational semantics approach to the semantics of programming languages understands the language constructions by assigning elements of mathematical structures to them. The structures form so-called categories of domains and the study of their closure properties is the subject of domain theory [Sco70,Sco82,Plo83a,GS90,AJ94].

Typically, categories of domains consist of suitably complete partially ordered sets together with continuous maps. But, what is a category of domains? Our aim in this thesis is to answer this question by axiomatising the categorical structure needed on a category so that it can be considered a category of domains. Criteria required from categories of domains can be of the most varied sort. For example, we could ask them to

• have fixed-point operators for endomorphisms and endofunctors;

• have a rich collection of type constructors: coproducts, products, exponentials, powerdomains, dependent types, polymorphic types, etc;

• have a Stone dual providing a logic of observable properties [Abr87, Vic89,Zha91];

• have only computable maps [Sco76,Smy77,McC84,Ros86,Pho90a].

The criteria adopted here will be quite modest but rich enough for the denotational semantics of deterministic programming languages. For us a category of domains will be a category with the structure necessary to support the interpretation of the metalanguage FPC (a type theory with sums, products, exponentials and recursive types). And our axiomatic approach will aim not only at clarifying the categorical structure needed on a category for doing domain theory but also at relating such mathematical criteria with computational criteria.

This thesis is an investigation into axiomatic categorical domain theory as needed for the denotational semantics of deterministic programming languages.

To provide a direct semantic treatment of non-terminating computations, we make partiality the core of our theory. Thus, we focus on categories of partial maps. We study representability of partial maps and show its equivalence with classifiability. We observe that, once partiality is taken as primitive, a notion of approximation may be derived. In fact, two notions of approximation, contextual approximation and specialisation, based on testing and observing partial maps are considered and shown to coincide. Further we characterise when the approximation relation between partial maps is domain-theoretic in the (technical) sense that the category of partial maps Cpo-enriches with respect to it.

Concerning the semantics of type constructors in categories of partial maps, we present a characterisation of colimits of diagrams of total maps; study order-enriched partial cartesian closure; and provide conditions to guarantee the existence of the limits needed to solve recursive type equations. Concerning the semantics of recursive types, we motivate the study of enriched algebraic compactness and make it the central concept when interpreting recursive types. We establish the fundamental property of algebraically compact categories, namely that recursive types on them admit canonical interpretations, and show that in algebraically compact categories recursive types reduce to inductive types. Special attention is paid to Cpo-algebraic compactness, leading to the identification of a 2-category of kinds with very strong closure properties.

Figures B.I to B.8 show the test environments for the exploration experiments. Two figures are given for each environment. The first diagram shows the walls and objects in the environment. It also shows the positions and orientations from which exploration experiments were started. The second diagram for shows the ‘ideal’ free-space map which would result from complete knowledge of the objects in the environment.

16.1 Motivation

Experience with human control of the exploration process suggested that map quality could be increased rapidly in the early stages of exploration by heading into open regions of space instead of staying close to one of the walls (Section 15.4). The ‘Longest Lines’ strategy described in this chapter was motivated by this observation. The essential idea is to perform a full sensor scan and head in the direction of the longest reading. As many steps as possible are then taken in that direction until an obstacle is encountered. The algorithm then continues by heading in the direction of the longest reading from this new position.

This strategy shares with wall-following the fact that it is totally reactive. Navigational decisions are made solely on the basis of the latest sensor readings.

Section 16.2 gives the details of the implementation and Section 16.3 compares the results to those of Wall-Following and Supervised Wall-Following. Section 16.4 summarises the experimental results and considers the strengths and weaknesses of the strategy.

16.2 Implementation

The strategy, as described in the previous section, is straightforward. The only slight complication is the problem of multiple reflections. Wall-following used the shortest range readings from each viewpoint; multiple reflections were not a problem because they typically cause long range readings. On the other hand, the ‘Longest Lines’ strategy is particularly interested in the long readings. It is therefore necessary to acknowledge the likelihood of multiple reflections and to compensate for them.

Section 4.1 described the attraction of wall-following as an exploration strategy and gave examples of its use in a number of research projects. It was argued in Section 4.3 that wall-following should be the first strategy to be implemented and tested because it will give an indication of what can be achieved when ARNE acts only on the basis of immediatelyavailable information and does not use the map to guide its exploration. This chapter describes the way in which wall-following was implemented on ARNE and presents the results of some explorations using this strategy.

12.1 Implementation

Wall-following has been implemented in two stages. First, ARNE approaches the nearest object that it can detect and positions itself ready for wall-following proper to start. The bulk of the exploration is then a repetitive process of ‘scan,turn,move’ actions in which ARNE moves so as to maintain an ideal distance from the nearest detected object. The remainder of this section describes the implementation of these two stages.

The first stage is quite simple. ARNE performs a complete sensor scan and groups the raw returns into readings, as described in Section 6.3. ARNE then selects the smallest range reading and moves so as to be at a standard distance, IDEAL-WALL-CLEARANCE, from the object. If the minimum range is greater than IDEAL-WALL-CLEARANCE, this means turning in the direction of the minimum reading. Otherwise ARNE turns directly away from the shortest reading.