Technical Reports

## 1979 UBC CS Technical Report Abstracts

TR-79-01 In Search of an Optimal Machine Architecture for BCPL, January 1979 R. Agarwal and Samuel T. Chanson

This paper investigates the problem of generating optimal space-efficient code for the language BCPL. Designing such a code was seen to be a two-phase process. The first phase was to describe an internal representation scheme for BCPL programs which preserved those program features which are salient to translation and at the same time minimize the number of instructions generated. The second phase consisted of the realization of the internal representation as an actual machine taking into account the usage frequencies of instructions and other real world constraints such as word size and addressing space. The \underline{i}ntermediate \underline{c}od\underline{e}, called ICE and an encoding scheme (known as ESO, standing for \underline{e}ncoding \underline{s}cheme \underline{0}) are described. ICE/ESO is seen to reduce code size by an average of about 32% compared to BCODE which is a realization of OCODE, the intermediate language currently used in BCPL program translation.

TR-79-02 Anaphoria in natural Language Understanding: A Survey, May 1979 Graeme Hirst

A problem that all computer-based natural language understanding (NLU) systems encounter is that of linguistic reference, and in particular anaphora (abbreviated reference). For example, in a text as simple as: \begin{quote} Nadia showed Sue her new car. The seats were Day-Glo orange. \end{quote} knowing that her'' probably means Nadia and not Sue and that the seats'' means the seats of Nadia's new car is not a simple task. .br This thesis is an extensive review of the reference and anaphor problem, and the approaches to it that NLU systems have taken, from early systems such as STUDENT through to current discourse-oriented ones such as PAL. .br The problem is first examined in detail, and examples are given of many different types of anaphor, some of which have been ignored by previous authors. The approaches taken in traditional systems are then described and abstracted and it is shown why they were inadequate, and why discourse theme and anaphoric focus need to be taken into account. The strengths and weaknesses of current anaphora theories and approaches are evaluated. The thesis closes with a list of some remaining research problems. .br The thesis has been written so as to be as comprehensible as possible to both AI workers who know no linguistics, and linguists who have not studied artificial intelligence.

TR-79-03 Equality and Domain Closure in First Order Data Bases, January 1979 Raymond Reiter

(Abstract not available on-line)

TR-79-04 Programming Skill Acquisition --- Progress Report, January 1979 V. Manis

(Abstract not available on-line)

TR-79-05 Multi-process Structuring and the THOTH Operating System, March 1979 David R. Cheriton

This report explores the idea of structuring programs as many concurrent processes. It is based on work done in designing, implementing, and using the Thoth operating system. Thoth implements an ahstraction that provides facilities to make this type of structuring attractive, namely inexpensive processes, efficient interprocess communication, dynamic process creation and destruction, and groups of processes sharing a common address space. .br The Thoth abstraction is described, including measurements of its performance and comments on its portability. This abstraction is motivated by considering various design and implementation tradeoffs. Then, the design of multi-process programs is discussed, both in terms of general principles and by giving specific uses and examples to demonstrate the adequacy of the abstraction. Examples are drawn from the operating system and the Thoth text editor. Finally, the feasibility of verifying the system is considered. This is motivated by the desire to exploit the multi-process structure of the system to aid in verification. .br We conclude that structuring programs as multiple processes can have significant benefits, especially for programs that respond to asynchronous events.

TR-79-06 Message-Passing, Spaces and Agents, January 1979 David R. Cheriton

(Abstract not available on-line)

TR-79-07 Saturation Estimation in Interactive Computer Systems, June 1979 Samuel T. Chanson

This paper presents a systematic method for estimating the saturation point of interactive computer systems in an environment of incomplete information (in particular, where per interaction information is unavailable). This method is an improvement over the ad hoc and time-consuming iterative approach commonly used. Following an operational analysis approach and using only commonly available data, a simple model was constructed to estimate the mean response time of a task characterized by its CPU and i/o requests running in a given system CPU, disk, drum and channel load factors. The systems saturation point is obtained from the model using a modified version of the method first proposed by Kleinrock. The interesting concept that tasks with different resource demands experience different saturation loads is discussed. It is shown that the saturation loads as seen by different tasks vary only slightly as the characteristics of the tasks change. The method has been applied on an IBM 370/168 running under the Michigan Terminal System at the University of British Columbia.

TR-79-08 A Logic for Default Reasoning, July 1979 Raymond Reiter

The need to make default assumptions is frequently encountered in reasoning about incompletely specified worlds. Inferences sanctioned by default are best viewed as beliefs which may well be modified or rejected by subsequent observations. It is this property which leads to the non monotonicity of any logic of defaults. .br In this paper we propose a logic for default reasoning. We then specialize our treatment to a very large class of commonly occurring defaults. For this class we develop a complete proof theory and show how to interface it with a top down resolution theorem prover. Finally, we provide criteria under which the revision of derived beliefs must be effected.

TR-79-09 Designing an Operating System to be Verifiable, 1979 David R. Cheriton

(Abstract not available on-line)

TR-79-10 Process Identification in THOTH, October 1979 David R. Cheriton

A scheme is presented for the identification of processes in a minicomputer operating system. This scheme was designed and implemented as part of the development of the Thoth operating system. The scheme is efficient in time and space as well as exhibiting a reasonable lower bound on the minimum recycle time for process identifiers.

TR-79-11 Three BCPL Machines, January 1979 Harvey Abramson

We describe three virtual BCPL machines designed in the Department of Computer Science at the University of British Columbia. The first machine is the Pica-B which is an Intcode machine with an added interrupt register, plus several execute instructions to manipulate this register, and a modification of the routine calling mechanism so that interrupts can be treated as unexptected routine calls. An inline code command, the \underline{vile} command, allows the writing of interrupt routines in BCPL, and also facilitates the portability of the BCPL library by allowing certain routines such as level, longjump, and aptovec to be written in BCPL. The second machine is the SLIM (\underline{S}tack \underline{L}anguage for \underline{I}ntermediate \underline{M}achine) machine which is a stack machine with an accumulator. This architecture permits the representation of BCPL programs with fewer instructions than the OCODE representation requires. The third machine is the ICE machine which permits highly space-efficent representations of BCPL programs by having a large instruction set which includes many variants of the BCPL operators.

TR-79-12 The Pica-B Computer, January 1979 Harvey Abramson, Mark Fox, J. Peck, V. Manis and M. Gorlick

The Pica-B computer is a simple abstract machine designed to: \begin{enumerate} \item facilitate the portability of a simple single user operating environment written in BCPL. \item serve the pedagogic goal of providing a basis for teaching concepts of hardware and system architecture, systems programming and programming language design in a unified setting, and \item serve as a possible solution to the current and future software crisis caused by the advent of the micro-computer. \end{enumerate} The Pica-B is based on Richards' Intcode machine but differs from it in the addition of an (interrupt) status register and a PDP-11 style memory map of I/O devices. The status register and hence interrupt and device handlers may be programmed in Pica-B code (an extention of Intcode) or in a version of BCPL with an added inline code facility, the so-called \underline{vile} command. An example is given of how interrupts and I/O are handled in Pica-B computer.

TR-79-13 Approaching Discourse Computationally: A Review, January 1979 Richard S. Rosenberg

(Abstract not available on-line)

TR-79-14 Representation Spatial Experience \& Solving Spatial Problems in a Simulated Robot Environment, October 1979 Peter Forbes Rowat

This thesis is concerned with spatial aspects of perception and action in a simple robot. To this end, the problem of designing a robot-controller for a robot in a simulated robot-envoronment system is considered. The environment is two-dimentional tabletop with movable polygonal shapes on it. The robot has an eye which `sees' an area of the tabletop centred on itself, with a resolution which decreases from the centre to the periphery. Algorithms are presented for simulating the motion and collision of two dimentional shapes in this environment. These algorithms use representations of shape both as a sequence of boundary points and as a region in digital image. A method is outlined for constructing and updating the world model of the robot as new visual input is received from the eye. It is proposed that, in the world model, the spacial problems of path-finding and object-moving be based on algorithms that find the skeleton of the shape of empty space and of the shape of the moved object. A new iterative algorithm for finding the skeleton, with the property tbat the skeleton of a connected shape is connected, is presented. This is applied to path-finding and simple object-moving problems. Finally, directions for future work are outlined.

TR-79-15 The Design of a Verifiable Operating System Kernel, January 1979 T. Lockhart

(Abstract not available on-line)