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
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
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
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
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
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
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
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
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
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
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