CS Theses 1978

For 1978 graduation dates (in alphabetical order by last name):

A Semantic Representation for Translation of High-Level Algorithmic Languages
Appelbe, William Frederick
URI : http://hdl.handle.net/2429/21145
Degree : Doctor of Philosophy – PhD
Graduation Date : 1978-11
Supervisor : Dr. Abramson

Although new high-level programming languages continue to be proposed, major software development efforts are still devoted to developing translators for the current languages. As yet there is no clear methodology for designing and implementing translators; instead there are a large number of tools and techniques applicable to different aspects of translator development. This thesis proposes a new technique for structuring the development of translators for high-level algorithmic languages, based upon an intermediate graphical program representation called GRAIL. Using this approach, the semantic phase of the translator converts source language programs into a corresponding GRAIL representation, then subsequently into code for the target machine. The primary advantage of this approach is to simplify the task of developing translators for high-level algorithmic languages. GRAIL is designed to enable adaptable and efficient translators to be developed for a wide range of source languages. GRAIL was incorporated into a translator writing system, which was used to implement a translator for the programming language ASPLE. The ASPLE translator was highly adaptable, as both the syntax and semantics of ASPLE could be easily modified. The translator writing system demonstrated the feasibility of using GRAIL to implement adaptable translators, although the software used had limited capabilities.

Numerical Prameter Estimation in Differential Equations
Benson, Maurice
URI : http://hdl.handle.net/2429/21231
Degree : Doctor of Philosophy – PhD
Graduation Date : 1978-05
Supervisor : Dr. Varah

The problem of numerical least squares parameter estimation in differential equations is considered. Several new algorithms that pay particular attention to the differential equation aspect of the problem are presented. These reduce some of the difficulties encountered when the problem is treated solely as a question of nonlinear optimization. The extremely powerful interactive approach is considered and an interactive package incorporating standard techniques using sensitivity equations along with a selection of our special algorithms is presented. We consider methods involving the fitting of integrals and derivatives using piecewise polynomial approximations to the observations. Continuation methods with a quasi multiple shooting technique to bridge the gap between these coarse but well behaved methods and the full least squares problem are explored. Special methods are developed for the important case of two state variables with observations available on only one of them. In particular we consider algorithms which use an initial guess at the behavior of the unobserved state variable and then iteratively improve this guess. The need for effective algorithms for fitting population growth models in ecology is one motivation for this thesis. We devote a chapter to an important predator-prey model of population dynamics and extensive experiments are presented which demonstrate some of the typical difficulties which can arise and which illustrate the ability of our algorithms to overcome some of these difficulties. Some special problems involving jumps from one equilibrium to another (loosely referred to as catastrophes) are examined. This type of model has important applications in ecology. Models involving stiff differential equations are also considered. A short chapter is devoted to the use of sequential reestimation techniques. Experiments indicate that such methods can be useful for improving a crude initial guess at the parameters and this improvement can be crucial for the successful solution of the problem. Finally a chapter is devoted to a selection of "real world" problems. It is on such problems that the true value of an algorithm is determined.

Machine Architecture and the Programming Language BCPL
Fox, Mark
URI : http://hdl.handle.net/2429/20999
Degree : Master of Science – MSc
Graduation Date : 1978-11

Computation by One-Way Multihead Marker Automata
Gorlick, Michael Martin
URI : http://hdl.handle.net/2429/21005
Degree : Master of Science – MSc
Graduation Date : 1978-11
Supervisor : Dr. Baker

A Procedural Model of Recognition for Machine Perception
Havens, William S.
URI : http://hdl.handle.net/2429/21238
Degree : Doctor of Philosophy – PhD
Graduation Date : 1978-05
Supervisor : Dr. Mackworth

This thesis is concerned with aspects of a theory of machine perception. It is shown that a comprehensive theory is emerging from research in computer vision, natural language understanding, cognitive psychology, and Artificial Intelligence programming language technology. A number of aspects of machine perception are characterized. Perception is a recognition process which composes new descriptions of sensory experience in terms of stored stereotypical knowledge of the world. Perception requires both a schema-based formalism for the representation of knowledge and a model of the processes necessary for performing search and deduction on that representation. As an approach towards the development of a theory of machine perception, a computational model of recognition is presented. The similarity of the model to formal mechanisms in parsing theory is discussed. The recognition model integrates top-down, hypothesis-driven search with bottom-up, data-driven search in hierarchical schemata representations. Heuristic procedural methods are associated with particular schemata as models to guide their recognition. Multiple methods may be applied concurrently in both top-down and bottom-up search modes. The implementation of the recognition model as an Artificial Intelligence programming language called MAYA is described. MAYA is a multiprocessing dialect of LISP that provides data structures for representing schemata networks and control structures for integrating top-down and bottom-up processing. A characteristic example from scene analysis, written in MAYA, is presented to illustrate the operation of the model and the utility of the programming language. A programming reference manual for MAYA is included. Finally, applications for both the recognition model and MAYA are discussed and some premising directions for future research proposed.

The Design and Implementation of a Run-Time Analysis and Interactive Debugging Environment
Johnson, Mark Scott
URI : http://hdl.handle.net/2429/21543
Degree : Doctor of Philosophy – PhD
Graduation Date : 1978-11
Supervisor : Dr. Abramson

The design and implementation of a language-independent, interactive system to facilitate the analysis and symbolic debugging of computer programs written in high-level languages is presented. The principal features of the system, called RAIDE, are: (1) Host source language independence is supported by the abstraction of language entities and constructs (for example, variables, constants, procedures, statements, and events) with a language interfacer providing language-dependent details; (2) Translators can cooperate with RAIDE at varying levels of detail; (3) The user interacts with RAIDE and an executing object program using an extendable debugging language, called Dispel; (4) Primitive debugging actions are kept to a minimum and nonprimitive actions (for example, tracing, snapshots, and postmortem dumping) are provided by user-supplied and library procedures written in Dispel; and (5) The implementation is aided by simulation of a virtual debugging machine, called SPAM. To demonstrate RAIDE's feasibility, a prototype implementation was undertaken, including a SPAM simulator and the modification of two language translators (namely, Asple and BCPL) to interface with RAIDE. Besides describing the external and internal designs of the debugging system, the abstract machine, and the debugging language, the thesis also discusses the advantages and shortcomings of each of these components. Numerous examples of debugging commands written in Dispel are given. Two significant side-effects of the research are reported; reflections on the software tools supporting the implementation, and suggestions for translator design to facilitate run-time debugging. The thesis contains a substantial annotated bibliography and an extensive index.

Defining Semantics with Attribute Grammars
Rushworth, Thomas B.
URI : http://hdl.handle.net/2429/21038
Degree : Master of Science – MSc
Graduation Date : 1978-11
Supervisors : Dr. Peck, Dr. Abramson