AORTA Diagrams As An Aid To

Visualising The Execution Of Prolog Programs1

Marc Eisenstadt and Mike Brayshaw

Human Cognition Research Laboratory
The Open University
Milton Keynes MK7 6AA, UK

Abstract: Logic programs have traditionally been described by means of
'AND/OR' trees. The AORTA diagram is an And/OR Tree, Augmented to include invocation history 'status boxes' at each node. This augmentation makes it possible to present a graphical view of Prolog execution which is very compact, yet which
contains complete details of unification and control history, including multiple
(backtracking) invocations and extra-logical features such as the cut. The notation
described herein serves as the uniform basis for textbook diagrams, video-based
animations, and an advanced tracing and debugging facility running on modern
graphics workstations.

1 Introduction

For the past two years, we have been experimenting with ways of expressing the execution of Prolog programs in an easy-to-visualise manner. Our focus has been on producing an account of the language which is rich enough to satisfy the needs of experts, and has the descriptive power and clarity needed to teach difficult concepts to novice Prolog programmers. Toward this end, we have developed an execution model which serves as the basis for a 'cradle-to-grave' Prolog environment, serving not only as the basis for textbook diagrams and video animations aimed at Prolog novices (Eisenstadt, 1988), but also as the underlying graphical paradigm for a fullyimplemented Prolog tracer/debugger intended for expert Prolog users (Eisenstadt and Brayshaw, 1987; 1988a).

The main purpose of this paper is to provide the full details of just the graphical notation. We therefore omit certain related issues which are discussed elsewhere. In particular, the full user environment of the graphical tracer, with its 'replay' buttons, hierarchical zoom, and ability to handle search spaces comprising thousands of nodes, is described in detail in Eisenstadt and Brayshaw (1988a). An overview of the teaching curriculum built around our graphical notation is presented in Eisenstadt and Brayshaw (1988b). The relationship of our work to that of Bundy et. al. (1986), Dewar and Cleary (1986), and numerous other seminal researchers is provided in Eisenstadt and Brayshaw (1987; 1988a). We take for granted the significance of providing program visualisation tools, as amply discussed elsewhere in this volume. Finally, we assume that the reader is a competent Prolog user.

1Paper presented at Symposium on Visual Programming and Program Visualisation, London, England, March, 1988. The authors gratefully acknowledge the support of the UK Science and Engineering Research Council. AORTA diagrams were developed for teaching purposes under the aegis of the SERC Information Technology Training Initiative, which funded the development of the Open University's 'Intensive Prolog' course. The graphical tracer/debugger implementation is funded by SERC grant numbers GR/C/69344 and GR/E/2333.3, as part of Alvey Project IKBS/161, undertaken collaboratively with Expert Systems International, Ltd.