THE UNIVERSITY OF CALGARY

Design of an Object-Oriented Database Language:
Bridging the gap between Organizational Requirements and
the Technical Implementation of an Object-Oriented Information System

by
Bruce A. Conrad





A THESIS
SUBMITTED TO THE FACULTY OF GRADUATE STUDIES
IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE
DEGREE OF
DOCTOR OF PHILOSOPHY


DEPARTMENT OF COMPUTER SCIENCE

CALGARY, ALBERTA
JUNE 1995




Copyright © 1995 Bruce A. Conrad

THE UNIVERSITY OF CALGARY FACULTY OF GRADUATE STUDIES The undersigned certify that they have read, and recommend to the Faculty of Graduate Studies for acceptance, a thesis entitled, "Design of an Object-Oriented Database Language: Bridging the gap between Organizational Requirements and the Technical Implementation of an Object-Oriented Information System" submitted by Bruce A. Conrad in partial fulfillment of the requirements for the degree of Doctor of Philosophy. Supervisor, Dr. B.R. Gaines Department of Computer Science D.R. Hill Department of Computer Science Dr. B. Samuels Department of Sociology Dr. M.L.G. Shaw Department of Computer Science External Examiner, Dr. University Date

Copyright © March 8, 1995 Bruce Conrad


Abstract

People need appropriate access to the data of their organization in order to further the goals of the organization. This dissertation studies the creation of database applications, computer systems to provide this access. I begin by interviewing the people responsible for creating or configuring database applications, to determine their requirements and aspirations. After evaluating the effectiveness of current technology in meeting their needs, I explore the promise of object-oriented systems by dissecting an exemplar, Smalltalk, identifying its essential and inessential features. Combining the essential nature of Smalltalk with database capabilities, I present a new object-oriented programming language designed to facilitate the construction of database applications. I conclude by describing the implementation of a prototype of the language and its evaluation by the people it is intended to serve.

Copyright © March 8, 1995 Bruce Conrad


Acknowledgements

I wish to express gratitude to my graduate advisor, friend, and mentor, Brian Gaines. His patient and quiet belief that I would actually someday complete the writing of this dissertation, especially given the lack of much hard evidence, has been a sustaining force. Together with other faculty members at the University of Calgary, including Jon Rokne, David Hill, Ian Witten, Mildred Shaw, and Joan Vickers, he has introduced me to more interesting concepts that I could possibly explore in a lifetime. I greatly enjoyed the numerous intellectual discussions with Debbie Leishman, Frank Deur, and other fellow graduate students. Many of the ideas presented here first came to light or were polished in their company. Special thanks go to Burt Conrad and his family who gave me a home away from home during my residency at Calgary.

I am also indebted to my former colleagues at the University of Lethbridge. Frank Shaffer, Don Ferguson, and Jack Hiscocks, as department heads, facilitated my becoming a faculty member and pursuing doctoral studies. Together with Steve Wismath, Rex Forsyth, Shelly Wismath, Dennis Connelly, Charles Jorgenson, Wolf Holzman, Amar Sodhi, X. Wu and others, they gave friendship, confidence, and a stimulating work environment. Thanks also to many of my students there, who inspired me with their own intellectual efforts and enthusiasm.

Thanks also go to Alan Ashton of WordPerfect Corporation for providing a wonderful place to work, and encouragement to proceed with the development of the object-oriented language described in this dissertation. This work was done there in close collaboration with Lew Bastian and Scott Christensen, friends whose experience, insights and deep understanding I value and admire.

I am grateful to Layne Cannon who organized an Advanced Technology Group at WordPerfect Corporation, and invited me to continue the work described here in a stimulating environment of research and unrestrained thought. Here, I have also enjoyed friendship and many hours of stimulating discussion with Lynn Brough, James Gates, Layne Cannon, Thom Boyer, Jim Tinney, and others. I have especially appreciated Lynn's analytical mind and numerous insights into how the world works and how people think. James and Thom have challenged my thinking about desirable characteristics of high level programming languages.

When Novell, Inc. acquired WordPerfect Corporation, David Brewer helped our group to weather the storm and, for the most part, stay together. I thank him for allowing me to continue my research in end user programming with the Advanced Technology Group he now leads.

Thanks to the many people, who over the years have endured my enthusiasm for computers and technology. A special thanks to those who allowed me to introduce them into the magical world of programming, and who amazed me with their prowess. They play a privileged role in the work described herein, which is about people at least as much as it is about computers.

Special thanks go to Jim Tinney who believed in the TOOL vision from the moment he saw it, and whose expertise with word processing technology was invaluable in creating this document.

I have been most fortunate to have parents and an extended family who have always believed in me and supported me. Finally, I acknowledge the essential contribution of my wife, Judy, whose love and confidence seem to know no bounds, and who sustains and motivates me. She and our children, Elizabeth and Andrew, give meaning to everything I do.

Copyright © March 8, 1995 Bruce Conrad


Table of Contents



Abstract    iii

Acknowledgements    iv

Table of Contents    vii

List of Figures    xiii

Chapter 1: Introduction    1
1.1 Social Needs and Computing    1
1.1.1 Case studies    3
1.1.1.1 Recording the hunt    4
1.1.1.2 Tilling the ground    4
1.1.1.3 Computer literacy    6
1.1.1.4 Genetic research    7
1.1.2 The Programming Bottleneck    8
1.2 Programming as a natural human activity    8
1.2.1 Programming vs. Performance    9
1.2.2 Programming by Example  10
1.2.3 Programmed people  10
1.2.4 Conclusion  11
1.2.5 The Fundamental Theorem of Computing  11
1.2.5.1 Finding the program: creation or selection  12
1.2.5.2 The programmer creates the program  13
1.2.5.3 Identifying the programmer  14
1.2.5.4 Conclusion  20
1.2.6 The power of modeling and abstraction  20
1.2.7 Spreadsheets  23
1.3 DataPerfect: databases for end users  23
1.3.1 Innovative Features of DataPerfect  24
1.3.2 Problems Encountered  24
1.3.3 Future Vision  25
1.4 Objectives of the TOOL project  27
1.5 Summary and overview  27

Chapter 2: User Requirements  30
2.1 Philosophical and Social Context  30
2.1.1 Ontology--what is  30
2.1.1.1 Popper's three worlds  31
2.1.1.2 General Evolution  32
2.1.1.3 The role of information  35
2.1.2 Epistemology--knowing what is  36
2.1.2.1 Theories of truth  36
2.1.2.2 Conversation theory  37
2.1.2.3 Individuals and societies--who knows what is  37
2.2 Organizations  38
2.2.1 Organizations as entities  38
2.2.2 Programming and organizations  39
2.2.3 Organizations, People, and Technology  41
2.3 Case studies  43
2.3.1 An engineering and manufacturing company  44
2.3.2 A university  45
2.3.3 A non-profit organization  46
2.4 Summary  48
2.4.1 Derived requirements  49
2.4.2 TOOL requirements  50
2.4.2.1 Computational completeness  50
2.4.2.2 Simplicity  50
2.4.2.3 Prototyping methodology  51
2.4.2.4 Primitive operations  51

Chapter 3: Existing Technology  52
3.1 Computer mediated data storage  52
3.2 Persistence--knowledge transfer over time and space  53
3.2.1 Origins of information and persistency  54
3.2.2 Properties of persistent information  55
3.2.2.1 Information retrieval  55
3.2.2.2 Uniqueness constraints  56
3.2.2.3 Indexing  57
3.2.2.4 Classification  57
3.2.2.5 Relationships  57
3.2.3 A Model of Information Storage  57
3.2.4 Conclusion  59
3.3 BRETAM: from Invention to Products  59
3.3.1 Smalltalk and the BRETAM model  60
3.3.2 Relational databases and the BRETAM model  61
3.4 A Review of Existing Technology  61
3.4.1 Flat files  61
3.4.2 Relational databases  62
3.4.3 Computer programming languages  62
3.5 Meeting User Requirements  63

Chapter 4: A Dissection of Smalltalk  65
4.1 A Description of Smalltalk  65
4.1.1 Smalltalk Concepts  66
4.1.2 The Smalltalk Memory Model  68
4.1.3 The Smalltalk Execution System  69
4.1.3.1 The byte code interpreter  70
4.1.3.2 The primitive routines  72
4.1.3.3 Memory management  72
4.1.4 The Smalltalk Language Syntax  73
4.1.4.1 Message sends  73
4.1.4.2 Control constructs  75
4.1.5 The Smalltalk Programming Environment  76
4.2 A Critique of Smalltalk  77
4.2.1 Essential Features of Smalltalk  78
4.2.1.1 Modeling with objects  78
4.2.1.2 Uniformity of representation  78
4.2.1.3 Automatic memory management  79
4.2.1.4 Polymorphism and late binding  79
4.2.1.5 Syntax of message send  81
4.2.1.6 Simple precedence rules  81
4.2.1.7 User-defined control structures  82
4.2.1.8 Incremental compilation  82
4.2.2 Inessential Features of Smalltalk  83
4.2.2.1 The metaclass structure  83
4.2.2.2 The image  84
4.2.2.3 Purity of the message sending paradigm  84
4.2.2.4 Multiple inheritance  85
4.2.2.5 Context objects  85
4.2.2.6 Very large library of classes and methods  86
4.2.3 Missing Features of Smalltalk  86
4.2.3.1 Persistent objects  87
4.2.3.2 Database primitives  87
4.3 Conclusion  87

Chapter 5: Design of an Object-Oriented Language  88
5.1 Memory Model  89
5.1.1 Intrinsic Objects  89
5.1.2 Other Objects  90
5.1.2.1 Object components  90
5.1.2.2 Essential system objects  91
5.1.3 Object interconnections  92
5.1.3.1 The instance hierarchy  93
5.1.3.2 The inheritance hierarchy  94
5.1.3.3 Classes and methods  95
5.2 Execution System  95
5.2.1 The byte code interpreter  95
5.2.1.1 Byte code execution  96
5.2.1.2 Message send preparation  96
5.2.1.3 Method lookup  97
5.2.1.4 Method execution  98
5.2.2 Primitive routines  99
5.2.3 Input/Output  99
5.2.4 Memory management100
5.3 The High-level Language102
5.3.1 TOOL lexemes102
5.3.2 TOOL syntax105
5.3.3 TOOL Semantics111
5.3.3.1 Constants111
5.3.3.2 Variables111
5.3.3.3 Message sends114
5.3.3.4 Expressions114
5.3.3.5 Blocks115
5.3.3.6 Control constructs116
5.3.4 Standard methods125
5.3.4.1 Types126
5.3.4.2 Byte codes126
5.3.4.3 Primitive methods126
5.3.4.4 Ordinary methods126
5.4 Programming Environment128
5.5 Conclusion129

Chapter 6: Implementation130
6.1 Bootstrap130
6.1.1 The Bootstrap Notation131
6.1.2 The Bootstrap Process132
6.2 The TOOL cloner134
6.3 TOOL programming language support136
6.3.1 The TOOL Compiler137
6.3.2 The TOOL Decompiler139
6.4 The Windowing System140
6.4.1 Paned Windows141
6.4.2 User interaction with windows142
6.4.3 Programming environment windows143
6.4.4 Implementation details144

Chapter 7: Evaluation146
7.1 Internal evaluation147
7.2 Evaluation in a commercial project148
7.3 Evaluation in a course on software testing150
7.4 Evaluation by professional software developers151
7.5 Conclusion154
7.5.1 Computational completeness154
7.5.2 Simplicity154
7.5.3 Prototyping155
7.5.4 Primitive operations155
7.5.5 Further evaluation156

Chapter 8: Conclusions157
8.1 Summary of dissertation content157
8.1.1 Design157
8.1.2 of an Object-Oriented157
8.1.3 Database158
8.1.4 Language:158
8.1.5 Bridging the gap between158
8.1.6 organizational requirements159
8.1.7 and the technical implementation of159
8.1.8 an Object-Oriented Information System160
8.2 The TOOL Virtual Environment160
8.3 Contributions of the work described162
8.3.1 Philosophical162
8.3.2 Methodological162
8.3.3 Analytical163
8.3.4 Technical163
8.3.4.1 Simplification163
8.3.4.2 Invention164
8.3.4.3 Portability165
8.3.4.4 Integration of database functionality165
8.4 How well did we succeed? Why did we fail?165
8.5 Bridging the Gap166
8.6 Future work169
8.6.1 Concurrency169
8.6.2 Hypertext170
8.6.3 Computer-supported Cooperative Work170
8.6.4 Artificial Intelligence170
8.6.5 Conclusion171

Bibliography172

Appendix 1: Working with TOOL182
1.1 Starting TOOL182
1.2 Exiting TOOL183
1.3 The TOOL workspace183
1.4 Moving and resizing windows184
1.5 The window menu184
1.6 The TOOL text editor186
1.7 The Evaluate option188
1.8 The Inspect option189

Appendix 2: Creating a TOOL application193

Appendix 3: TOOL program format208
3.1 Overview208
3.2 Literal Methods208
3.3 Conventions209

Copyright © March 8, 1995 Bruce Conrad


List of Figures


Figure 1.1 Normal Distribution  16
Figure 1.2 Pyramid of abilities  17
Figure 1.3 Program code  18
Figure 1.4 Abstraction Hierarchy  22
Figure 1.5 Elaboration of answers  22
Figure 2.1 Popper's three worlds  33
Figure 2.2 Monod's analogy  34
Figure 2.3 Three perspectives on organizations (Scott, 1987)  38
Figure 2.4. Organizations, People, and Technology  42
Figure 3.1 Creation of a computer application  63
Figure 3.2 Chain of technical products  64
Figure 5.1 Instance Hierarchy  93
Figure 5.2 Inheritance Hierarchy  94
Figure 5.3 A class and methods  95
Figure 5.4 TOOL Lexical Diagrams (Part 1 of 2)103
Figure 5.5 TOOL Lexical Diagrams (Part 2 of 2)105
Figure 5.6 TOOL Syntax Diagrams (Part 1 of 4)106
Figure 5.7 Examples of method patterns107
Figure 5.8 TOOL Syntax Diagrams (Part 2 of 4)108
Figure 5.9 TOOL Syntax Diagrams (Part 3 of 4)109
Figure 5.10 TOOL Syntax Diagrams (Part 4 of 4)111
Figure 5.11 TOOL constructs for a single alternative117
Figure 5.12 TOOL constructs for two alternatives118
Figure 5.13 TOOL constructs for multiple alternatives119
Figure 5.14 TOOL construct for iteration: simple repetition120
Figure 5.15 TOOL constructs for iteration: counted loops121
Figure 5.16 TOOL constructs for iteration: while loops122
Figure 5.17 TOOL constructs for Boolean expressions123
Figure 5.18 TOOL construct for method return value124
Figure 5.19 TOOL constructs for primitive methods124
Figure 6.1 The bootstrap process: overview131
Figure 6.2 The bootstrap process: step one132
Figure 6.3 The bootstrap process: step two133
Figure 6.4 The bootstrap process: step three133
Figure 6.5 The bootstrap process: step four134
Figure 6.6 Sample AST138
Figure 6.7 The TOOL Compilers139
Figure 6.8 The TOOL Decompiler140
Figure 6.9 TOOL windows142
Figure 8.1. Programming with the TOOL virtual environment161

Copyright © March 8, 1995 Bruce Conrad


Chapter 1: Introduction
Chapter 2: User Requirements
Chapter 3: Existing Technology
Chapter 4: A Dissection of Smalltalk
Chapter 5: Design of an Object-Oriented Language
Chapter 6: Implementation
Chapter 7: Evaluation
Chapter 8: Conclusions
Bibliography
Appendix 1: Working with TOOL
Appendix 2: Creating a TOOL application
Appendix 3: TOOL program format