Clipping is the process of determining how much of a given line segment lies within the boundaries of the display screen. Homogeneous coordinates are a convenient mathematical device for representing and transforming objects. The space represented by homogeneous coordinates is not, however, a simple Euclidean…
This thesis is concerned with the construction of a high level language system suitable for the implementation of a general purpose operating system for a computer. There are three aspects to this task: firstly, a suitable high level language must be chosen or designed; secondly,…
This paper came out of my study of the bakery algorithm of [12]. The problem with that algorithm is that it requires unbounded state. To allow the state to be bounded in practice, I needed an algorithm for reading and writing multidigit numbers, one digit…
The filing system for the CAP is based on the idea of preservation of capabilities: if a program has been able to obtain some capability then it has an absolute right to preserve it for subsequent use. The pursuit of this principle, using capability-oriented mechanisms…
We describe a plan to create an auditable version of Multics. The engineering experiments of that plan are now complete. Type extension as a design discipline has been demonstrated feasible, even for the internal workings of an operating system, where many subtle intermodule dependencies were…
This paper describes a system for full-duplex communication between a time-shared computer and its terminals. The system consists of a communications computer directly connected to the time-shared system, a number of small remote computers to which the terminals are attached, and connecting medium speed telephone…
Homogeneous coordinates have long been a standard tool of computer graphics. They afford a convenient representation for various geometric quantities in two and three dimensions. The representation of lines in three dimensions has, however, never been fully described. This paper presents a homogeneous formulation for…
This paper describes some of the techniques which can be used for managing the run time storage required for an ALGOL68 program. The emphasis is on stack storage, since garbage collection techniques would require another paper. The Frcblems caused by some ALGOL68 constructs are described:…
Classical logic is symmetric with respect to True and False but intuitionistic logic is not. We introduce and study a conservative extension of first-order intuitionistic logic that is symmetric with respect to True and False.
The first-order theory of ordered abelian groups was analyzed in 3. However, algebraic results on ordered abelian groups in the literature usually cannot be stated in first-order logic. Typically they involve so-called convex subgroups. Here we introduce an expanded theory of ordered abelian groups that…
We disprove two Shelah's conjectures and prove some more results on the monadic theory of linearly orderings and topological spaces. In particular, if the Continuum Hypothesis holds then there exist monadic formulae expressing the predicates ``X is countable'' and ``X is meager'' over the real…
When I first learned about the mutual exclusion problem, it seemed easy and the published algorithms seemed needlessly complicated. So, I dashed off a simple algorithm and submitted it to CACM. I soon received a referee's report pointing out the error. This had two effects.…
