![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to obj.ms CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10dc / vol2 / pi|
Return to obj.ms CVS log | Up to [Research Unix] / researchv10dc / vol2 / pi |
1.1 root 1: .so ../ADM/mac
2: .XX 24 397 "Pi: A Case Study in Object-Oriented Programming"
3: ...\" Wed May 21 16:37:07 EDT 1986
4: .de CW
5: \%\&\\$3\\f(CW\\$1\\fP\&\\$2
6: ..
7: ..
8: .TL
9: Pi: A Case Study in Object-Oriented Programming
10: .AU
11: T. A. Cargill
12: .MH
13: .AB
14: Pi is a debugger written in C++.
15: This paper explains how object-oriented programming in C++ has influenced Pi's
16: evolution.
17: The motivation for object-oriented programming was to experiment with a
18: browser-like graphical user interface.
19: The first unforeseen benefit was in the symbol table: lazy construction of an
20: abstract syntax-based tree gave a clean interface to the remainder of Pi,
21: with an efficient and robust implementation.
22: Next, though not in the original design, Pi was easily modified to control
23: multiple processes simultaneously.
24: Finally, Pi was extended to control processes
25: executing across multiple heterogeneous target processors.
26: .AE
27: .NH
28: Introduction
29: .PP
30: The subject of this paper is the impact of object-oriented programming on the
31: structure and capabilities of a complicated piece of software \- a debugger
32: called Pi.
33: The paper begins with observations about debugging in general and a description
34: of Pi, to motivate the introduction of object-oriented programming.
35: When the design of Pi began, object-oriented programming was chosen as
36: a means of achieving a style of user interface.
37: But the application of object-oriented techniques throughout had unforeseen
38: benefits with respect to symbol table structure, multi-process debugging and
39: target environment independence.
40: .NH
41: User Interfaces for Debugging
42: .PP
43: A debugger must provide many views of its subject.
44: The primary view of the subject program is static: the source text.
45: The primary view of the subject process is dynamic: the callstack, a sequence of
46: activation records.
47: The programmer's insight into the program's behavior comes from merging these
48: views: examining data within the process while controlling its progress through
49: the source text.
50: Debugging purely at the source level may be sufficient for a safe language,
51: correctly implemented, but in practice we also need views of the implementation.
52: Even if none of the subject is written in assembler, it is vital from time
53: to time to consider the process in terms of the instruction stream, registers
54: and uninterpreted memory.
55: .PP
56: A particular view is not used in isolation; it is related to other views.
57: The programmer moves rapidly among a set of related views.
58: This diversity complicates the user interface.
59: Any attempt to base an interface on a coherent model is confounded by the user's
60: need to switch among so many projections of the underlying subject.
61: For example, the keyboard input
62: .P1 0
63: 100
64: .P2
65: could mean ``display the context of line 100'' of the current source file.
66: It could also mean ``evaluate the expression 100'' or ``display the value of
67: the memory cell at location 100'' and so on.
68: There is no natural interpretation; it depends on the programmer's current focus.
69: If there is some simple model on which a user interface for such a
70: (necessarily) powerful tool could be based, no one has yet found it.
71: .PP
72: Switching among a set of input modes might help \- as long as there is no
73: confusion over what mode is current and how one changes mode.
74: However, experience with just two modes in text editors
75: suggests that a larger number of modes would not work.
76: On the other hand, modeless keyboard languages for debuggers tend to need many
77: qualifiers and options for each command, varying from verbose to cryptic and
78: from pedantic to treacherous.
79: But if they are useful, they are large and complicated.
80: Two recent debuggers use programmability of the user interface to permit the
81: custom definition of keyboard languages for different classes of users.
82: Kraut|reference(bruegge) (with ``path expressions'')
83: and Dbx|reference(bsdmanual) (with macros) let
84: new commands be defined in terms of a base language.
85: In contrast, Pi's user interface uses multi-window bitmap graphics, and cannot
86: be extended by the user.
87: .NH
88: Pi's User Interface
89: .PP
90: Pi is primarily an attempt to combine expressive power and ease of use in a
91: graphics interface.
92: The user browses through a network of views, each in its
93: own window with a specialized pop-up command menu and keyboard language.
94: The user selects a window by pointing at it with a mouse or by following a
95: menu or keyboard connection from a related window.
96: All the information within a window is textual, i.e., symbolic and numeric rather
97: than analog or geometric.
98: Moreover, each line of text is also part of the browsing network;
99: it defines its own menu and keyboard interface.
100: .PP
101: The details of the graphics are not essential, but will help make the discussion
102: more concrete.
103: The display has 100 monochrome pixels per inch.
104: Within Pi, windows may overlap and are positioned explicitly by the user.
105: A proportional scroll bar on the left shows how much of a window's text is
106: visible.
107: The current window has a thick border; the current line is video-inverted.
108: A three-button mouse is used.
109: The left button makes selections: to change
110: the current window, to scroll within it or to select a line.
111: The middle and right buttons raise the pop-up menus associated with the current
112: line and window, respectively.
113: A line of accumulated keyboard characters is displayed in a common space
114: below the other windows.
115: If the current line or window accepts keyboard input, its border
116: flashes at each keystroke.
117: At carriage return a complete line of input is sent to the current recipient.
118: .PP
119: The following example shows much of the user interface mechanics, but
120: only a few of Pi's features.
121: A more complete example appears in |reference(pi feel).
122: This trivial C program is taken from |reference(cbook):
123: .P1 0
124: #include <stdio.h>
125:
126: main() /* count lines in input */
127: {
128: int c, nl;
129:
130: nl = 0;
131: while ((c = getchar()) != EOF)
132: if (c == '\en')
133: ++nl;
134: printf("%d\en", nl);
135: }
136: .P2
137: Assume this program has been compiled and invoked by a command interpreter
138: running elsewhere on the screen.
139: The process reads from the keyboard of its virtual terminal.
140: To bind Pi and the process, the user selects the process from a
141: list of accessible processes in Pi's master window.
142: To control this subject process Pi creates a Process window, for which the
143: user must sweep a rectangle with the mouse.
144: The Process window identifies the process and shows its state, as in Figure 1.
145: Process 27775 is in a
146: .CW read
147: system call, waiting for keyboard input for the call to
148: .CW getchar() .
149: .KF
150: .so fig1.so
151: .ce
152: Figure 1. A Process window and its menu.
153: .SP
154: .KE
155: .PP
156: The Process window is the hub of a network of views of
157: the process.
158: Choosing
159: .CW src\ text ' `
160: from the Process window's pop-up menu creates a Source Text window for
161: the source file,
162: .CW count.c ,
163: shown in Figure 2.
164: .LP
165: A breakpoint is set by pointing at a source line
166: and choosing
167: .CW set\ bpt ' `
168: from the line's menu.
169: The presence of the breakpoint is recorded by
170: .CW >>>
171: at the left of the line (Figure 3).
172: .PP
173: The subject process reaches the breakpoint when the user supplies some keyboard
174: input and
175: .CW getchar()
176: returns a character.
177: The Process window announces the change of state and displays a callstack
178: traceback, in this case a degenerate stack of depth 1.
179: Pi shows the source text context by making the Source Text window current
180: and selecting the source line at which the program stopped.
181: Choosing
182: .CW open\ frame ' `
183: from the source line's menu creates a Frame window for evaluating expressions
184: with respect to the activation record associated with that source line.
185: .KF bottom
186: .so fig2.so
187: .ce
188: Figure 2. A Source Text window and a source line's menu.
189: .SP
190: .KE
191: .KF
192: .so fig3.so
193: .ce
194: Figure 3. A Frame window and an expression's menu at a breakpoint.
195: .SP
196: .KE
197: .PP
198: Expressions in a Frame window are built from menus or the keyboard.
199: Choosing an identifier, say
200: .CW c ', `
201: from the Frame's menu of local variables creates and evaluates a simple expression,
202: shown in Figure 3.
203: The variable's type determines the default format in which the value is
204: displayed: an integer in decimal.
205: It makes more sense to display
206: .CW c 's
207: value as an ASCII character.
208: Changing the format is one of the operations in the expression's menu.
209: Choosing
210: .CW format ' `
211: from the expression's menu and
212: .CW ascii\ on ' `
213: from a sub-menu of formats re-evaluates the expression and displays it as:
214: .P1 0
215: c='a'=97
216: .P2
217: .PP
218: In debugging a real program there are likely to be many more windows.
219: (Pi is used daily by dozens of programmers, often on programs of 10,000 lines
220: or more.)
221: The windows shown above may be instantiated arbitrarily often: a Source Text window
222: for each of the program's source files and a Frame window for each of the
223: callstack's activation records.
224: There may be only one instance of each of the other window types:
225: a Frame window bound to global scope rather than an activation record,
226: an Assembler window for controlling the process at the instruction level,
227: a Raw Memory window for manipulating memory as an uninterpreted array of cells,
228: and a Signals window for controlling process exceptions.
229: .PP
230: The resemblance between Pi and Dbxtool|reference(dbxtool) is superficial,
231: even though both debuggers use windows and menus on a bitmap display.
232: Dbxtool is a front-end that translates graphics commands
233: into the command language of a conventional debugger, Dbx.
234: Dbxtool provides a fixed set of windows, one of which, the ``Command Window,''
235: shows the Dbx commands and responses.
236: To see how this affects the user, consider trying to evaluate
237: expressions with respect to two different activations records at once.
238: In Pi, a window is opened for each activation record and the user
239: moves back and forth with the mouse, evaluating expressions in either window;
240: each window then contains a set of related expressions.
241: In Dbxtool, the user enters a mixture of commands that evaluate expressions and
242: move up or down the callstack; the Command Window then contains a transcript of
243: interleaved context changes and evaluated expressions.
244: .PP
245: Pi is also unlike the debugger in Smalltalk's ``integrated environment,''
246: where there is little distinction between the compiler, interpreter, browser and
247: debugger|reference(smalltalk80).
248: Smalltalk's tools cooperate through shared data structures and the
249: computer's uniformly defined graphics.
250: On the other hand, Pi is an isolated tool in a ``toolkit environment.''
251: Pi interacts with graphics, external data and other processes
252: through explicit interfaces.
253: Pi adapts the graphics techniques exemplified by Smalltalk to the toolkit
254: setting.
255: .NH
256: Object-Oriented Programming
257: .PP
258: The remainder of the paper concerns the implementation of Pi.
259: The object-oriented programming model is better suited to the implementation of
260: Pi than the sequential programming model or the multiple sequential processes
261: model.
262: .PP
263: Under the sequential model, a process executes a program.
264: At any time the process is in some state, with control at some location in the
265: program.
266: When the process blocks for input from the user it is in the state from which
267: it resumes when the user responds.
268: This makes it difficult to drive the process with the flexibility described
269: above, where the user is allowed to refuse a given menu and leap to some
270: unrelated context.
271: The process must accept either the menu selection or the context switch.
272: The menu selection is a local operation in the local context;
273: the context switch is a global operation involving unrelated parts of the
274: program.
275: This might be achieved by letting the user traverse a network of contexts.
276: But there is then a tradeoff between ease of use and ease of programming:
277: a tree is easy to program, but tedious for the user to traverse;
278: a fully connected network might be easy to use, but calls for every
279: part of the program to be intimately coupled to every other part.
280: .PP
281: With multiple sequential processes a separate process could be associated with
282: each context.
283: As the user moves around the graphics screen, input is directed to the
284: appropriate process by some agent that maps screen locations to processes.
285: Processes are suspended until the user needs them;
286: they need know only about semantically related processes.
287: As a model this yields a natural architecture,
288: but its implementation is usually very expensive.
289: The overhead for creation and interaction of separate processes
290: might be acceptable for a small number of processes, say one per window.
291: But the desired user interface has each line within each window interacting
292: independently with the user.
293: Many hundreds, even thousands, of processes would be needed.
294: With conventional multi-process techniques the cost is prohibitive.
295: .PP
296: The object-oriented model lies between these two models.
297: Instead of a collection of processes there is a single process containing a
298: collection of
299: .I objects ,
300: each an instance of a type called a
301: .I class .
302: Each object has a copy of the
303: .I data\ members
304: defined in its class and can execute the
305: .I function\ members
306: of the class.
307: Unlike a process, an object has no permanent state other than its data.
308: Objects share a universal address space and communicate with one another
309: by invoking function members as procedures.
310: It is feasible to have many thousands of objects.
311: That objects cannot execute concurrently, as processes do by timeslicing a
312: physical processor, is not significant; such concurrency is not required.
313: .PP
314: The C++|reference(cplusplus) programming language supports this model.
315: C++ is a superset of C with Simula-like classes|reference(simula begin).
316: The members of a class are data and functions, in private and public sections:
317: .P1 0
318: class \fIidentifier\fP {
319: \fIprivate_data_declarations\fP
320: \fIprivate_function_declarations\fP
321: public:
322: \fIpublic_data_declarations\fP
323: \fIpublic_function_declarations\fP
324: };
325: .P2
326: (This grammar generates only a subset of C++ class declarations.)
327: The example of C++ code below defines a class
328: .CW Const
329: that privately represents an integer value; the value is rendered as
330: a hexadecimal, decimal or octal character string
331: by three member functions.
332: Similar code is found in Pi.
333: .P1 0
334: class Const {
335: int val; // private data member
336: public:
337: Const(int); // constructor
338: char *hex(); // public function members
339: char *dec();
340: char *oct();
341: };
342:
343: void Const::Const(int v) // constructor body
344: {
345: val = v;
346: }
347:
348: char *Const::hex() // function member body
349: {
350: \fIbuild character string\fP
351: return \fIpointer to character string\fP;
352: }
353:
354: ...
355:
356: .P2
357: A member function whose name is the same as that of its class is a
358: .I constructor.
359: If defined, the constructor is invoked to initialize a new object.
360: .CW Const 's
361: constructor assigns its argument to the private representation of the value.
362: .CW Const 's
363: member functions
364: .CW hex() ,
365: .CW dec()
366: and
367: .CW oct()
368: return pointers to ASCII representations of the value.
369: The following client code prints 123 as
370: .CW 0x7B=123=0173 :
371: .P1 0
372: {
373: Const c(123); // c.Const(123) called implicitly
374: printf("%s=%s=%s", c.hex(), c.dec(), c.oct());
375: }
376: .P2
377: Here
378: .CW Const\ c(123)
379: declares an object instantiated on the stack for the lifetime of the block;
380: the argument
381: .CW 123
382: is passed to the constructor.
383: The object could also be allocated from the free store by means of the operator
384: .CW new ,
385: in which case the variable's type is pointer-to-\f(CWConst\fP:
386: .P1 0
387: {
388: Const *cp;
389: cp = new Const(123); // allocate from free store
390: printf("%s=%s=%s", cp->hex(), cp->dec(), cp->oct());
391: delete cp; // return to storage pool
392: }
393: .P2
394: .PP
395: In general, an executing C++ program consists of a network of objects,
396: referencing one another with pointers.
397: Subject to the encapsulation rules of C++,
398: objects may access one another's member data and invoke member functions.
399: Consider a Frame window that evaluates expressions with respect to an activation
400: record.
401: Figure 4 shows two objects:
402: .CW F ,
403: an instance of class
404: .CW Frame ,
405: and
406: .CW E ,
407: an instance of class
408: .CW Expr .
409: An arrow represents a pointer; an arrow labeled by a function call indicates
410: that the holder of the pointer may call the member function of the object to
411: which it points.
412: .KF
413: .PS
414: .ft CW
415: F: circle "F"
416: E: circle "E" at F.c+(0,-1)
417: arrow " create_expr(symbol)" "" from F.e+(1,0) to F.e
418: arrow " evaluate()" from F.s to E.n
419: .ft P
420: .PE
421: .ce
422: Figure 4. A sub-network of objects.
423: .KE
424: .PP
425: Here,
426: .CW create_expr()
427: is a member of
428: .CW Frame
429: and
430: .CW evaluate()
431: is a member of
432: .CW Expr :
433: .P1 0
434: class Frame{
435: ...
436: void create_expr(Symbol*);
437: ...
438: };
439:
440: class Expr{
441: ...
442: ErrMsg evaluate();
443: ...
444: };
445: .P2
446: The
447: .CW Symbol*
448: argument to
449: .CW create_expr
450: is a pointer to a symbol table object describing a variable in
451: .CW F 's
452: activation record's scope, from which the
453: .CW Frame
454: creates an
455: .CW Expr
456: object
457: .CW E .
458: .CW F
459: might cause the expression to evaluate itself by calling
460: .CW E.evaluate() ,
461: and so forth.
462: .PP
463: The notation in Figure 4 suggests a message-passing model.
464: Indeed, the terminology of object-oriented programming in
465: Smalltalk|reference(smalltalk80) refers to ``messages'' between objects.
466: However, the communication is by procedure call.
467: .NH
468: Object-Oriented User Interface
469: .PP
470: A user interface to such a network can be created by letting the user communicate
471: directly through the interfaces that objects present to one another|reference(smalltalk80).
472: The user must be able to select an object,
473: see a set of member function calls and select one to be invoked.
474: To receive a member function call from the user an object must describe
475: itself and a set of function calls to the software managing the display.
476: .PP
477: Figure 5 shows the object network of Figure 4 and a screen image.
478: .CW F
479: has associated itself with a window on the screen, and
480: .CW E
481: has associated itself with a line in that window.
482: The new ``pointers'' from images on the screen to objects in the program are
483: shown by dashed arrows.
484: If the user selects
485: .CW E 's
486: line, raises the line's menu and selects
487: .CW ascii\ on ', `
488: then the result is a call of
489: .CW E 's
490: member function:
491: .P1 0
492: E.reformat(ASCII_ON)
493: .P2
494: .KF
495: .PS
496: .ft CW
497: F: circle "F"
498: E: circle "E" at F.c+(0,-1)
499: arrow from F.s to E.n
500: SCREEN: spline from E.s+(2,-.8) \
501: then up 1.2 \
502: then up 0.1 right 0.1 then up 0.1 right 0.1 \
503: then right 1 up 0.1 right 1 down 0.1 \
504: then down 0.1 right 0.1 then down 0.1 right 0.1 \
505: then down 2.4 \
506: then left 0.1 down 0.1 then left 0.1 down 0.1 \
507: then left 1 down 0.1 left 1 up 0.1 \
508: then up 0.1 left 0.1 then up 0.1 left 0.1 \
509: then up 1.2
510: WINDOW: box at SCREEN+(1,0.5) height 1 width 1.5
511: "count.c:9 main()" at WINDOW.nw+(.7,-0.1)
512: "c=97" at WINDOW.nw+(.2,-0.25)
513: arrow dashed from WINDOW.n to F chop 0 chop circlerad
514: arrow "reformat(ASCII_ON)" "" dashed from WINDOW.nw+(.05,-0.3) to E chop 0 chop circlerad
515: MENU: box "." "." "ascii on" "." "." at WINDOW+(.5,-1.2) height 1.2 width .7
516: line dashed from MENU+(-.1,.1) to WINDOW.nw+(.05,-0.3)
517: .ft P
518: .PE
519: .ce
520: Figure 5. Operations invoked by the user.
521: .KE
522: .PP
523: Three points of detail should be mentioned.
524: First, the user does not really see the program's internal interfaces,
525: i.e., the identifiers and types of member functions.
526: The text of a menu entry is chosen to support the user's view of the
527: function and need not reflect program's source literally.
528: For example, the user sees
529: .CW ascii\ on ' `
530: instead of
531: .CW reformat(ASCII_ON) '. `
532: Second, when invoked, a member function cannot distinguish a call
533: originated directly by the user from a call by another object.
534: There is only one procedure call mechanism.
535: Third, once an object has exposed its image and a set of member function calls
536: to the user, it must be prepared to receive any sequence of calls the user
537: chooses to make.
538: To inhibit the user, the object must remove itself or change the set of calls
539: in the menu.
540: Changes in the menu reassure the user about the state of the object:
541: the menu of a line of source text on which the user has already set a breakpoint
542: shows
543: .CW clear\ bpt ' `
544: instead of
545: .CW set\ bpt '. `
546: .PP
547: The interaction between the user and program is now conducted without a
548: ``user interface'' in the conventional sense.
549: There is no part of the program responsible for reading, parsing and interpreting a
550: sequence of commands from the user.
551: The user sees a graphical image of the program and the program sees the user as an
552: active participant in its object-oriented world,
553: with implicit software mapping between the two.
554: .NH
555: Implementation
556: .PP
557: The interface between the graphics and the network of objects is a pair of C++
558: classes:
559: .CW Window
560: and
561: .CW Menu .
562: These classes in turn interact with a graphics package.
563: To create its window, the
564: .CW Frame
565: object executes:
566: .P1 0
567: w = new Window; // Save the pointer to a new
568: // Window in Frame's data member w.
569: w->bind(this); // Pass a pointer to this (a C++ keyword)
570: // instance of Frame to the Window.
571: w->title(description()); // Frame's member function description()
572: // yields a string like "count:9 main()".
573: w->makecurrent(); // To make a newly created window current
574: // the user must sweep a rectangle for it.
575: .P2
576: To display its value in the window an
577: .CW Expr
578: object executes:
579: .P1 0
580: Menu m; // Instantiate a Menu on the local stack.
581: .
582: .
583: m.append("octal on", &reformat, OCTAL_ON);
584: m.append("ascii on", &reformat, ASCII_ON); // Build the menu.
585: m.append("float on", &reformat, FLOAT_ON);
586: .
587: .
588: w->insert(line, this, m, evaltext()); // Insert line in window.
589: .P2
590: Each call to
591: .CW m.append()
592: adds an entry to the menu.
593: Each entry consists of the text string the user sees when the menu is raised,
594: the member function to be called and the argument to be passed.
595: The call to
596: .CW insert() ,
597: using a copy of
598: .CW w
599: passed to the
600: .CW Expr
601: by the
602: .CW Frame ,
603: creates a new line of text in the window.
604: The text string, like
605: \f(CW"c=97"\fP,
606: is obtained from
607: .CW Expr 's
608: member function
609: .CW evaltext() .
610: The
611: .CW line
612: argument is a numeric key that determines where this line will appear
613: relative to other lines in the window.
614: Not shown here is how
615: .CW ascii\ on ' `
616: would be made to appear in a sub-menu, as in Figure 3.
617: Instead of being bound to a window or line of text, one
618: .CW Menu
619: may be embedded in another.
620: The embedded sub-menu pops up when the cursor is positioned over a sub-menu
621: indicator in the super-menu.
622: .PP
623: Note that the code from
624: .CW Frame
625: and
626: .CW Expr
627: does not reflect the terminal's physical attributes.
628: The abstractions are windows and menus, not coordinates and mouse buttons.
629: Pi has no knowledge of, or control over, details such as the placement of
630: windows, the scrolling of text or the assignment of mouse buttons.
631: Though not used here, the most concrete graphics request is that a line of text
632: be made visible to the user.
633: This means that the graphics and mouse protocol described above is just one of
634: many possible choices; the user's view might be quite different in an
635: implementation for a one-button mouse.
636: .PP
637: Operations on
638: .CW Window
639: objects are translated into a stream of messages passed to a separate
640: process responsible for the real-time graphics.
641: Operations from the user are transmitted back to the main process, received by
642: the package and invoked on the Pi's objects.
643: The two processes execute asynchronously on separate processors: the main
644: process on a
645: .UX
646: system, ``the host,'' and the real-time graphics process on
647: a Teletype DMD 5620 bitmap terminal, ``the terminal'' (Figure 6).
648: .KF
649: .PS
650: HOST: circle "Pi and" "window" "package" rad .5
651: TERM: circle at HOST+(2,0) "real-time" "graphics" rad .5
652: TOTERM: arc -> cw from HOST.ne to TERM.nw
653: TOHOST: arc -> cw from TERM.sw to HOST.se
654: "definitions" at TOTERM.n+(0,.1)
655: "operations" at TOHOST.s-(0,.1)
656: LINE: line dashed from TOTERM.n-(0,.1) to TOHOST.s+(0,.1)
657: ABOVE: line dashed from TOTERM.n+(0,.2) to TOTERM.n+(0,0.4)
658: BELOW: line dashed from TOHOST.s-(0,.2) to TOHOST.s-(0,1.5)
659: SUBJ: circle at HOST-(0,1.5) "subject" "process" rad .5
660: arrow " OS support" <-> from HOST.s to SUBJ.n
661: "host" at SUBJ.s-(0,0.2)
662: "terminal" at TERM.s-(0,1.7)
663: .PE
664: .ce
665: Figure 6. Inter-process communication.
666: .KE
667: .PP
668: Global control in the graphics program lies in a loop that polls the
669: host and user for commands.
670: The following pseudo-code approximates the loop:
671: .P1 0
672: for(;;){ // forever
673: if( mouse activity ){
674: update screen
675: if( remote operation selected )
676: send message to host
677: }
678: if( message from host ){
679: receive from host
680: update screen
681: }
682: if( real-time clock event ){ // see below
683: send message to host
684: }
685: }
686: .P2
687: Global control in the host process lies in a loop in
688: the window package that blocks waiting for messages from the terminal:
689: .P1 0
690: for(;;){
691: read <object, operation, operand> from terminal
692: invoke object->operation(operand)
693: }
694: .P2
695: Usually, an invoked operation in turn causes definitions or redefinitions
696: of objects to be sent to the terminal, to show the user some kind of result.
697: The messages from the host arrive asynchronously with respect to the user's
698: interaction with the graphics.
699: An experienced user need not wait for changes from each operation to be reflected
700: on the screen before invoking another operation.
701: For example, having requested a particular context within a source file to be
702: displayed, the user can select a source line and set a breakpoint on it
703: as soon as that line is visible, even if the host has not finished sending
704: all of the lines needed to fill the window.
705: Some users take advantage of the asynchrony as the natural way to function;
706: others operate as though the communications were half-duplex.
707: .NH
708: Pi's Architecture
709: .PP
710: The debugger is a network of objects as described above.
711: An object of class
712: .CW Process
713: is created to take overall control of the subject process.
714: The
715: .CW Process
716: object creates two major objects to serve it: a symbol table object of class
717: .CW SymTab
718: and a core image access object of class
719: .CW Core .
720: The
721: .CW SymTab
722: is responsible for reading the symbol table as left by the compiler,
723: assembler and loader and providing that information to the rest of the
724: debugger, as discussed below.
725: The
726: .CW Core
727: is responsible for all access to the address space of the subject process and
728: the operating system's control information.
729: Details of the physical processor, operating system and compiler generated code
730: are encapsulated in
731: .CW Core .
732: .KF
733: .PS 5
734: .ft CW
735: .ps -2
736: PROC: circle "Process" rad 0.4
737: CIRC: circle at PROC rad 1.5 invis
738: CORE: circle "Core" at CIRC.w rad 0.4
739: SYMTAB: circle "SymTab" at CIRC.nw rad 0.4
740: BPTS: circle "BreakPts" at CIRC.n rad 0.4
741: ASM: circle "Assembler" at CIRC.ne rad 0.4
742: MEM: circle "Memory" at CIRC.e rad 0.4
743: STACK: circle "CallStack" at CIRC.sw rad 0.4
744: FRAME: circle "Frame" at CIRC.s rad 0.4
745: SIGNALS: circle "Signals" at CIRC.se rad 0.4
746: line from CORE to PROC chop 0.4
747: line from SYMTAB to PROC chop 0.4
748: line from BPTS to PROC chop 0.4
749: line from ASM to PROC chop 0.4
750: line from MEM to PROC chop 0.4
751: line from STACK to CORE chop 0.4
752: line from FRAME to STACK chop 0.4
753: line from SIGNALS to PROC chop 0.4
754: FRAMEN: circle "Frame" at FRAME-(0,1.5) rad 0.4
755: "." "." "." at 1/2 <FRAME.s,FRAMEN.n>
756: line from STACK to FRAMEN chop 0.4
757: EXPR: circle "Expr" at FRAMEN+(1.5,0) rad 0.4
758: EXPRN: circle "Expr" at EXPR+(1.5,0) rad 0.4
759: line from FRAMEN to EXPR chop 0.4
760: ". . ." at 1/2 <EXPR.e,EXPRN.w>
761: SRC: circle "SrcText" at SYMTAB+(0,1.5) rad 0.4
762: SRCN: circle "SrcText" at SRC+(-1.5,0) rad 0.4
763: line from SYMTAB to SRC chop 0.4
764: line from SYMTAB to SRCN chop 0.4
765: ". . ." at 1/2 <SRC.w,SRCN.e>
766: .ft P
767: .ps +2
768: .PE
769: .ce
770: .ft R
771: Figure 7. Pi's object network
772: .KE
773: .PP
774: Of these three classes, only
775: .CW Process
776: opens a window, the Process window, from which the user may then open other
777: windows.
778: To display a callstack, the
779: .CW Process
780: obtains a
781: .CW CallStack
782: object from the
783: .CW Core
784: and extracts each activation record it needs as a
785: .CW Frame
786: object from the
787: .CW CallStack.
788: If a
789: .CW Frame
790: is referenced by the user, it opens a Frame window.
791: As the user creates expressions and derives new ones, each expression is an
792: .CW Expr
793: object which displays itself as a line in its
794: .CW Frame 's
795: window.
796: Figure 7 shows the network.
797: The lines indicate the primary permanent links between objects, but
798: pointers are passed around as needed.
799: .PP
800: It is the
801: .CW Process
802: that monitors the state of subject process.
803: When the subject is running, its state must be polled to see if it reaches a
804: breakpoint or some other exception.
805: The
806: .CW Process
807: therefore periodically executes an operation that reads the current
808: state of the subject from the
809: .CW Core .
810: This operation re-invokes itself by sending to the terminal
811: a message requesting that the terminal invoke it after a specified delay.
812: The invocation returned from the terminal is interleaved with, and
813: indistinguishable from, invocations made directly by the user.
814: The
815: .CW Process
816: can monitor the state of the subject process while the user asynchronously
817: evaluates expressions, sets breakpoints and so on.
818: This technique creates a few bytes per second of extra host-terminal traffic,
819: since it would be possible to use a clock interrupt on the host instead.
820: However, to guarantee that operations are invoked fairly is much simpler if
821: the only source of operations is a single stream coming from the terminal.
822: Also, the terminal is a better place for real-time programming, both in terms
823: of operating system support and expendable processor resources.
824: .NH
825: Symbol Tables
826: .PP
827: A debugger's needs of its symbol table are similar to those of a compiler,
828: for example, to determine the variables in scope at some point in the program.
829: If the symbol tables prepared by the translator suite reflect the data
830: structures used in the compiler,
831: the debugger is much simplified|reference(cardell swat).
832: If the tables have been ``flattened'' by an assembler or loader, the debugger
833: suffers the loss of information.
834: Reconstructing an acceptable data structure can be very time-consuming
835: |reference(beander).
836: Working with the flattened tables complicates those parts of the debugger
837: that make non-trivial use the symbol table|reference(blit debugger spe).
838: .PP
839: For Pi, it seemed likely that versions of the debugger would be used with
840: compilers and assemblers that produced at least two distinct flattened formats.
841: So the first goal was to find a format-independent internal representation
842: that could be built from either format and was well-suited to debugging.
843: Given that the debugger was being written in C++, it seemed a good
844: opportunity to experiment with object-oriented programming.
845: In contrast to the user interface, there was no overall design paradigm guiding the
846: symbol table; the software evolved as different ideas were tried.
847: .PP
848: From the outset, the symbol table was a sub-network of objects.
849: Its structure follows the abstract structure of the subject program \- a tree.
850: The root of the tree is the
851: .CW SymTab
852: object.
853: It reads the file prepared by the loader and builds a tree, as shown in Figure 8.
854: Below the
855: .CW SymTab
856: there is a
857: .CW SrcFile
858: object for each separately compiled source file that contributed to the
859: program.
860: (There is a one-to-one correspondence between the
861: .CW SrcFile s
862: and the
863: .CW SrcText s
864: of Figure 7; a
865: .CW SrcText
866: is created and opens a window when the user decides to examine the source text
867: from the corresponding
868: .CW SrcFile .)
869: Below each
870: .CW SrcFile
871: there is a
872: .CW Function
873: for each function defined in that file.
874: Below each
875: .CW Function
876: there is a
877: .CW Block
878: of arguments and a
879: .CW Block
880: of local variables.
881: Each
882: .CW Block
883: has a list of
884: .CW Variables .
885: Each
886: .CW Function
887: also has a list of
888: .CW Statements ,
889: the source statements in the function.
890: Some symbols can also be accessed directly from a hash table whose entries point
891: into tree's interior.
892: .PP
893: Like any object, a member of the symbol table can receive operations from the user.
894: For example, the object associated with a line of source text in a Source Window
895: is a
896: .CW Statement .
897: To set a breakpoint the user communicates directly with the symbol table.
898: .PP
899: Though not shown in the figure, each node in the tree has four pointers: to its
900: parent, leftmost child and right and left sibling.
901: These make it easy to traverse the tree.
902: C++'s type inheritance is used to capture the common properties of all symbol
903: nodes in a
904: .I base
905: .I class
906: called
907: .CW Symbol
908: from which other classes of symbols are
909: .I derived :
910: .P1 0
911: class Symbol {
912: public:
913: Symbol *parent;
914: Symbol *leftmost_child;
915: Symbol *right_sibling;
916: Symbol *left_sibling;
917: Address addr;
918: char *id;
919: virtual char *text();
920: };
921: .P2
922: .KF
923: .PS 4
924: .ft CW
925: .ps -2
926: SYMTAB: circle "SymTab" rad 0.4
927: SRC2: circle "SrcFile" at SYMTAB-(0,1.2) rad 0.4
928: SRC1: circle "SrcFile" at SRC2-(1.5,0) rad 0.4
929: SRC3: circle "SrcFile" at SRC2+(2,0) rad 0.4
930: arrow from SYMTAB to SRC1 chop 0.4
931: arrow from SRC1 to SRC2 chop 0.4
932: ". . ." at 1/2 <SRC2,SRC3>
933: FUNC2: circle "Function" at SRC2-(0,1.2) rad 0.4
934: FUNC1: circle "Function" at FUNC2-(1.5,0) rad 0.4
935: FUNC3: circle "Function" at FUNC2+(2,0) rad 0.4
936: arrow from SRC2 to FUNC1 chop 0.4
937: arrow from FUNC1 to FUNC2 chop 0.4
938: ". . ." at 1/2 <FUNC2,FUNC3>
939: ARGS: circle "Block" at FUNC2-(0,1.2) rad 0.4
940: LCLS: circle "Block" at ARGS-(0,1.2) rad 0.4
941: arrow from FUNC2 to ARGS chop 0.4
942: arrow from ARGS to LCLS chop 0.4
943: VAR1: circle "Variable" at LCLS+(1.5,0) rad 0.4
944: VAR2: circle "Variable" at VAR1+(1.5,0) rad 0.4
945: arrow from LCLS to VAR1 chop 0.4
946: ". . ." at 1/2 <VAR1,VAR2>
947: STMT2: circle "Statement" at LCLS-(0,1.2) rad 0.4
948: STMT1: circle "Statement" at STMT2-(1.5,0) rad 0.4
949: STMT3: circle "Statement" at STMT2+(1.5,0) rad 0.4
950: arrow from FUNC2 to STMT1 chop 0.4
951: arrow from STMT1 to STMT2 chop 0.4
952: ". . ." at 1/2 <STMT2,STMT3>
953: line dashed "" "\fPlazy\f(CW" from FUNC1-(0,0.6) to FUNC3-(0,0.6)
954: .ft P
955: .ps +2
956: .PE
957: .ce
958: .ft R
959: Figure 8. The symbol table hierarchy
960: .KE
961: The
962: .CW addr
963: and
964: .CW id
965: data members record address information and an identifier for each symbol.
966: The function
967: .CW text()
968: returns a textual representation of the node, which is just the identifier:
969: .P1 0
970: char *Symbol::text()
971: {
972: return id;
973: }
974: .P2
975: There are no instances of class
976: .CW Symbol
977: in the tree; each node of the symbol table is of a type derived from
978: .CW Symbol .
979: For example:
980: .P1 0
981: class Variable : public Symbol {
982: public:
983: Storage storage;
984: DataType type;
985: };
986: .P2
987: As a derived class,
988: .CW Variable
989: inherits all the data and functions of
990: .CW Symbol ;
991: it has two additional data members specific to its needs.
992: In
993: .CW Symbol ,
994: the function
995: .CW text()
996: is declared
997: .I virtual.
998: This means that a derived class may override the base version with its own.
999: .CW Variable
1000: has no need to do this; it is adequately served by the base version that returns
1001: the identifier.
1002: However,
1003: .CW Statement
1004: does define its own
1005: .CW text() :
1006: .P1 0
1007: class Statement : public Symbol {
1008: ...
1009: int line_number;
1010: char *text();
1011: };
1012: .P2
1013: Instead of returning the identifier (which is not used by
1014: .CW Statement ),
1015: .CW Statement::text()
1016: walks up the tree to find its
1017: .CW SrcFile
1018: node and returns a string identifying the statement's source file and line number,
1019: like:
1020: .P1 0
1021: "count.c:9"
1022: .P2
1023: In general, code traversing the tree to extract textual
1024: information does not depend on whether the class of a given node
1025: defines its own version of
1026: .CW text() .
1027: For example,
1028: .CW Statement::text()
1029: applies
1030: .CW text()
1031: to a
1032: .CW SrcFile
1033: pointer to obtain the pathname of the source file to embed in the string being
1034: built; it does not know whether
1035: .CW SrcFile
1036: has defined its own version of
1037: .CW text() .
1038: The choice of implementation of an operation by the object on which the operation
1039: is invoked, rather than the invoker, is common to all object-oriented
1040: programming.
1041: The technique is used throughout Pi.
1042: .NH
1043: Lazy Symbol Table Construction
1044: .PP
1045: If the symbol table as described above were really built it would consume
1046: enormous time and space.
1047: Early versions of Pi did build it and could only be applied to small programs.
1048: Time and space performance was improved dramatically by delaying construction
1049: of the subtree of local symbols below each
1050: .CW Function
1051: node until needed \- ``lazy'' construction.
1052: .PP
1053: When the debugger picks up a process it scans the flattened symbol table
1054: to build the tree only down to the
1055: .CW Function
1056: level \- the part of the tree above the dashed line in Figure 8.
1057: From a
1058: .CW Function
1059: the only public access to its sub-tree is through function members.
1060: The members of
1061: .CW Function
1062: detect that the sub-tree is missing and call on the
1063: .CW SymTab
1064: to build it before returning a pointer to a requested
1065: .CW Block
1066: or
1067: .CW Statement .
1068: Once the sub-tree has been built it remains; pointers into it may have been
1069: passed to, and retained by, other objects.
1070: .PP
1071: Lazy construction allows large symbol tables to be presented to the rest
1072: of the debugger in a manner that is encapsulated naturally and efficiently.
1073: The real-time initialization delay is about one second per thousand lines of source
1074: text, on a VAX-11/750\(dg processor.
1075: .FS
1076: \(dg VAX is a trademark of Digital Equipment.
1077: .FE
1078: The cost of building a sub-tree on demand is negligible and very
1079: few are built.
1080: Local tables are needed for only those functions on the callstack
1081: or visible in a Source window.
1082: It is exceptional to need tables for more than about 15 functions.
1083: When Pi, a 500-function program, is used to debug itself, it typically builds
1084: 1%\-5% of the local tables.
1085: .PP
1086: This style of lazy table construction could be implemented in any programming
1087: language, but reliably only in a language that enforces its data abstraction.
1088: In C++, because the only public access from a
1089: .CW Function
1090: to its sub-tree is through member functions, the lazy operation of the symbol
1091: table does not depend on cooperation from clients.
1092: Very few problems have arisen with this code.
1093: .PP
1094: A similar lazy method is used to defer the construction of the tables of
1095: user-defined types; the savings are comparable.
1096: .NH
1097: Generators that Traverse the Symbol Table
1098: .PP
1099: Clients of the symbol table need to perform various traversals to extract
1100: information.
1101: For example, a menu built by a
1102: .CW Frame
1103: contains the local variables visible from a function.
1104: This might be implemented by a natural traversal of the data structure
1105: in Figure 8.
1106: However, the symbol table can be better encapsulated by providing a class
1107: .CW VisibleVars ,
1108: an instance of which performs such a traversal:
1109: .P1 0
1110: class VisibleVars {
1111: ...
1112: public:
1113: VisibleVars(Block*);
1114: Variable *gen();
1115: };
1116: .P2
1117: The constructor takes an argument pointing to a
1118: .CW Block .
1119: The only public function,
1120: .CW gen() ,
1121: returns a pointer to a different
1122: .CW Variable
1123: on each call, ending with a null pointer.
1124: Client code with a pointer to a
1125: .CW Block
1126: from somewhere:
1127: .P1 0
1128: Block *b;
1129: .P2
1130: creates an instance of
1131: .CW VisibleVars
1132: and iterates through the generated variables:
1133: .P1 0
1134: {
1135: VisibleVars vv(b);
1136: Variable *var;
1137:
1138: while( var = vv.gen() ){
1139: ...
1140: }
1141: }
1142: .P2
1143: This iteration is built on general purpose data abstraction in C++,
1144: rather than a built-in iteration primitive|reference(icon book)
1145: |reference(alphard cacm).
1146: .PP
1147: Parts of Pi use nested iteration through the variables visible from a function.
1148: Nested iteration arises in the code that warns the user of ambiguity when an
1149: identifier occurs more than once in a menu.
1150: To determine if an identifier is non-unique, the menu builder searches
1151: the identifiers of the variables that its generator will produce later in the
1152: iteration by taking a
1153: .I copy
1154: of the generator in its current state and iterating through the copy:
1155: .P1 0
1156: {
1157: VisibleVars vv(b);
1158: Variable *v;
1159:
1160: while( v = vv.gen() ){
1161: ...
1162: VisibleVars copy(0); // initialized with null block
1163: copy = vv;
1164: Variable *w;
1165: while( w = copy.gen() ){
1166: if( strcmp(v->id, w->id) )
1167: ...
1168: }
1169: ...
1170: }
1171: }
1172: .P2
1173: (In this case quadratic running time is acceptable.)
1174: .NH
1175: Debugging Multiple Processes
1176: .PP
1177: The initial design of Pi did not consider letting the user examine
1178: more than a single process at a time.
1179: The
1180: .CW Process
1181: class (Figure 7) had been introduced in order to follow the object-oriented
1182: paradigm uniformly throughout the program.
1183: The intention was to instantiate
1184: .CW Process
1185: only once.
1186: Other parts of the debugger were made a little more complicated by this decision
1187: because they had to fetch data from the
1188: .CW Process
1189: that might otherwise have been stored in global variables.
1190: This version of the debugger did not have a master window or dynamic
1191: binding to processes; the subject process was fixed by a command line
1192: argument.
1193: .PP
1194: Once Pi was working reliably, I realized that with trivial modification
1195: it could instantiate an arbitrary set of
1196: .CW Process
1197: objects to examine an arbitrary set of subject processes.
1198: The user would need only one copy of the debugger, no matter how many processes
1199: were to be examined.
1200: It took only a few days to implement.
1201: A
1202: .CW Master
1203: object creates a
1204: .CW Process
1205: object for each subject process that the user chooses to examine,
1206: as shown in Figure 9.
1207: Each
1208: .CW Process
1209: and its sub-network knows nothing of any others that might exist.
1210: The user interface package sees no qualitative change \- just more objects.
1211: The technique whereby a
1212: .CW Process
1213: polls its subject is also unaffected; the delayed invocations of the
1214: polling operation from each
1215: .CW Process
1216: are interleaved with one another.
1217: None of the problems described in |reference(dbxtool) of implementing and using a
1218: multi-process debugger have been encountered.
1219: .KS
1220: .PS
1221: .ft CW
1222: .ps -2
1223: MAST: circle "Master" rad 0.3
1224: PROCSW: circle "Process" at MAST+(-1,-1) rad 0.3
1225: line from MAST to PROCSW chop 0.3
1226: PROCS: circle "Process" at MAST+(0,-1) rad 0.3
1227: line from MAST to PROCS chop 0.3
1228: PROCSE: circle "Process" at MAST+(1,-1) rad 0.3
1229: line from MAST to PROCSE chop 0.3
1230: .ft P
1231: .ps +2
1232: .PE
1233: .ce
1234: Figure 9. Object network for multi-process debugging.
1235: .KE
1236: .PP
1237: Multiple process debugging could also have been achieved by instantiating
1238: multiple debugger processes rather than multiple
1239: .CW Process
1240: objects within a single debugger.
1241: The advantage of instantiating only a single debugger is the reduced overhead
1242: for both the user and the computers.
1243: With only one instance of the debugger the user has less to manage on the screen.
1244: When multiple processes are debugged the set of debugging windows are the
1245: same whether they are together in one debugger's window or in separate instances
1246: of the debugger.
1247: But when the user wants to treat the debugging environment as a whole, it is
1248: better to deal with a single tool.
1249: For example, removing a single debugger is simpler than removing a set of
1250: debuggers.
1251: Less machine resources on the host and terminal are required to execute
1252: only a single process in each.
1253: In special circumstances (such as debugging a debugger), multiple instances
1254: of the debugger are needed.
1255: .NH
1256: Multiple Target Environments
1257: .PP
1258: The initial design did anticipate versions of Pi that would operate in
1259: different target environments.
1260: Those parts of the debugger dependent on the target processor were encapsulated in
1261: the
1262: .CW Core
1263: and
1264: .CW Assembler
1265: classes, those dependent on the operating system in
1266: .CW Core ,
1267: and those dependent on the external symbol table format in
1268: .CW SymTab .
1269: The original version of Pi was for a VAX processor running the Eighth Edition of
1270: the
1271: .UX
1272: system.
1273: The intention was to tailor versions to different target environments
1274: as the need arose.
1275: The first demand was for a version to debug processes in the DMD 5620 bitmap
1276: terminal: an AT&T WE32000 processor running a virtual terminal multiplexor
1277: called Mux.
1278: .PP
1279: As a further experiment with object-oriented programming, I decided
1280: to build both of these versions as a single program \- so that one instance
1281: of Pi could simultaneously examine processes in both target environments.
1282: For each target-dependent class there must be a base class, with a derived class
1283: for each target environment.
1284: Everywhere a target-dependent object is instantiated it must be of the
1285: appropriate derived class, but its target-independent clients need not know
1286: from which derivation.
1287: The classes derived from
1288: .CW Core
1289: are
1290: .CW HostCore
1291: and
1292: .CW TermCore ,
1293: for the host and terminal, respectively.
1294: The class hierarchy for
1295: .CW Core
1296: is shown in Figure 10.
1297: .KF
1298: .PS
1299: .ft CW
1300: CORE: "Core"
1301: HOSTCORE: "HostCore" at CORE+(-0.75,-0.75)
1302: TERMCORE: "TermCore" at CORE+( 0.75,-0.75)
1303: line from CORE.s-(0,.1) to HOSTCORE.n+(0,.1)
1304: line from CORE.s-(0,.1) to TERMCORE.n+(0,.1)
1305: .ft P
1306: .PE
1307: .ce
1308: Figure 10. Class hierarchy for \f(CWCore\fP.
1309: .KE
1310: .PP
1311: The main process of Pi is still a process in the timesharing host.
1312: To access memory in the terminal, an instance of
1313: .CW TermCore
1314: (executing on the host) communicates with an additional agent
1315: process in the terminal.
1316: (The agent process need not be in the same terminal as the
1317: real-time graphics process, but usually it is.)
1318: This communication is based on remote procedure calls from the host to
1319: the terminal.
1320: The debugger is now three processes altogether: the host process, the real-time
1321: graphics process and the terminal access agent, as shown in Figure 11.
1322: Implementation experience with a previous debugger |reference(blit debugger spe)
1323: indicated that
1324: bandwidth between the host and terminal would limit performance.
1325: This influenced the design of the host/terminal protocol and
1326: satisfactory performance was achieved.
1327: For example, when a
1328: .CW TermCore
1329: requests a callstack traceback from the terminal, the terminal computes the
1330: callstack locally, compares it to the last callstack sent to the host and
1331: transmits the difference \- usually only the deepest activation record has
1332: changed.
1333: .KS
1334: .PS
1335: HOST: circle "Pi and" "window" "package" rad .5
1336: TERM: circle at HOST+(2,0) "real-time" "graphics" rad .5
1337: TOTERM: arc -> cw from HOST.ne to TERM.nw
1338: TOHOST: arc -> cw from TERM.sw to HOST.se
1339: "definitions" at TOTERM.n+(0,.1)
1340: "operations" at TOHOST.s-(0,.1)
1341: LINE: line dashed from TOTERM.n-(0,.1) to TOHOST.s+(0,.1)
1342: ABOVE: line dashed from TOTERM.n+(0,.2) to TOTERM.n+(0,0.4)
1343: BELOW: line dashed from TOHOST.s-(0,.2) to TOHOST.s-(0,1.5)
1344: SUBJ: circle at HOST-(0,1.5) "host" "subject" "process" rad .5
1345: arrow " OS support" <-> from HOST.s to SUBJ.n
1346: PIDOTM: circle at HOST+(-2,0) "terminal" "agent" rad .5
1347: TOPIDOTM: line "remote" "proc call" <-> from HOST.w to PIDOTM.e
1348: TERMSUBJ: circle at PIDOTM-(0,1.5) "terminal" "subject" "process" rad .5
1349: arrow " OS support" <-> from PIDOTM.s to TERMSUBJ.n
1350: UP: line dashed from TOPIDOTM.c+(0,0.2) to TOPIDOTM.c+(0,1)
1351: DOWN: line dashed from TOPIDOTM.c-(0,0.2) to TOPIDOTM.c-(0,2.1)
1352: "host" at SUBJ.s-(0,0.2)
1353: "terminal" at TERM.s-(0,1.7)
1354: "terminal" at TERMSUBJ.s-(0,0.2)
1355: " . . ." at SUBJ.e
1356: " . . ." at TERMSUBJ.e
1357: .PE
1358: .ce
1359: Figure 11. Pi's three processes with two subject processes.
1360: .KE
1361: .PP
1362: How
1363: .CW Core
1364: finds the value of the subject's program counter is a simple example of
1365: inheritance and virtual functions at work.
1366: Consider part of the definition of
1367: .CW Core :
1368: .P1 0
1369: class Core {
1370: ...
1371: public:
1372: virtual int pc_index(); // register number for program counter
1373: virtual long reg_save(int r); // address at which register r saved
1374: virtual long peek_long(long a); // fetch value from memory at address a
1375: virtual long pc(); // fetch value of program counter
1376: ...
1377: };
1378: .P2
1379: The code here has been somewhat simplified to eliminate irrelevant complications;
1380: for example, it doesn't handle errors.
1381: .CW Core::pc()
1382: is target-independent, though it calls the target-dependent functions
1383: .CW pc_index() ,
1384: .CW reg_save() ,
1385: and
1386: .CW peek_long()
1387: to obtain its result:
1388: .P1 0
1389: long Core::pc()
1390: {
1391: return peek_long( reg_save( pc_index() ) );
1392: }
1393: .P2
1394: .CW pc_index() ,
1395: .CW reg_save()
1396: and
1397: .CW peek_long()
1398: must be implemented for each of
1399: .CW HostCore
1400: and
1401: .CW TermCore .
1402: For example, the program counter is register 15 on the VAX:
1403: .P1 0
1404: int HostCore::pc_index()
1405: {
1406: return 15;
1407: }
1408: .P2
1409: .CW reg_save()
1410: and
1411: .CW peek_long()
1412: have the target-dependent code to find the location at which an arbitrary register
1413: has been saved and read the contents of an arbitrary memory location, respectively.
1414: .PP
1415: Note that
1416: .CW Core::pc()
1417: is virtual; the derived classes
1418: .I may
1419: also redefine it.
1420: So, even though
1421: .CW TermCore
1422: could inherit this functionally correct
1423: .CW pc()
1424: from
1425: .CW Core ,
1426: it has its own version.
1427: The base version reads memory every time it needs the value of the program
1428: counter.
1429: For the terminal, this would mean a remote procedure call to the terminal every
1430: time.
1431: As an optimization,
1432: .CW TermCore
1433: keeps a copy of the program counter, updating it each time the state of the
1434: subject process is checked;
1435: .CW TermCore::pc()
1436: simply returns this cached value.
1437: The semantics are slightly different: if the program counter is manually patched
1438: while the program is halted,
1439: .CW TermCore::pc()
1440: will report the old value.
1441: In practice this discrepancy is less significant than the minor differences that
1442: arise from operating system idiosyncrasies.
1443: No user has ever noticed it.
1444: .PP
1445: Finding suitable target-independent base abstractions and implementing
1446: the derived classes took several months; simply building a new version of
1447: Pi specifically for the new target environment would have taken a few weeks.
1448: The
1449: .CW SymTab
1450: class was relatively straightforward, but tedious because of arbitrary
1451: differences in the detailed representation of the symbol tables.
1452: Two hard parts of finding an acceptable inheritance for
1453: .CW Core
1454: were byte ordering and function calling.
1455: The problems encountered with byte ordering are instructive \- the original
1456: scheme did not work on either machine, for reasons that no amount of forethought
1457: (by me) would have revealed.
1458: The scheme is to read memory from the subject process and create objects from
1459: which various types of data (byte, short, long, float, double) can be extracted
1460: later by clients of
1461: .CW Core .
1462: The VAX version failed when it tried to set up arbitrary bit patterns as
1463: candidates for extraction as floating point values; the operand of a floating
1464: move instruction must be a valid floating point number, of which 1 in 256 bit
1465: patterns is not.
1466: The WE32000 version did not work because the processor does not use the same
1467: byte ordering for code and data fetches; a multi-byte constant embedded in code
1468: is not the same bit pattern as that constant in data.
1469: Neither of these problems
1470: was hard to fix, but they indicate the difficulty of finding
1471: machine-independent abstractions for hardware.
1472: Harder was the interface through which the expression evaluator calls a function
1473: in the subject.
1474: The mechanisms for the host and terminal are quite different.
1475: For the host architecture, the debugger arranges that the subject process
1476: execute the function using the user's stack; in the terminal the function is
1477: executed directly by the debugger's agent process in the terminal on its own
1478: stack.
1479: The operation is broken down into a series of steps, each performed by
1480: a member of the respective derived
1481: .CW Core ,
1482: such that
1483: .CW Expr
1484: can detect no difference.
1485: The five steps supplied by
1486: .CW Core
1487: are: save context, allocate argument area, call function,
1488: determine location of returned result, restore context.
1489: .PP
1490: A further derivation from
1491: .CW HostCore
1492: has been added for examining core dumps from the
1493: .UX
1494: kernel on the VAX.
1495: .CW KernelCore
1496: differs very little from
1497: .CW HostCore ;
1498: the major change is that memory fetches must be mapped through the
1499: kernel's page tables.
1500: A derivation of
1501: .CW Core
1502: for S-Net, a multi-processor computer based on the Motorola MC68000,
1503: is being implemented at the time of writing.
1504: The current
1505: .CW Core
1506: hierarchy is shown in Figure 12.
1507: .KS
1508: .PS
1509: .ft CW
1510: CORE: "Core"
1511: HOSTCORE: "HostCore" at CORE+(-0.75,-0.75)
1512: TERMCORE: "TermCore" at CORE+( 0.75,-0.75)
1513: SNETCORE: "SNetCore" at CORE+( 0,-0.75)
1514: line from CORE.s-(0,.1) to HOSTCORE.n+(0,.1)
1515: line from CORE.s-(0,.1) to TERMCORE.n+(0,.1)
1516: line from CORE.s-(0,.1) to SNETCORE.n+(0,.1)
1517: KERNCORE: "KernelCore" at HOSTCORE+(0,-0.75)
1518: line from HOSTCORE.s-(0,.1) to KERNCORE.n+(0,.1)
1519: .ft P
1520: .PE
1521: .ce
1522: Figure 12. Current \f(CWCore\fP hierarchy.
1523: .KE
1524: .PP
1525: A single debugger that handles multiple target environments
1526: has been a success for both the users and the implementer.
1527: The user is guaranteed to see the same interface when debugging in all
1528: environments.
1529: When changes are made to target-independent parts of Pi
1530: they are usually only tested for one target before being installed
1531: \- they almost always work correctly for the others.
1532: This was true of adding a trace history of breakpoints, for example.
1533: More complicated changes, involving target-dependent parts, take some time
1534: before a clean compilation can be achieved, because several derived classes must
1535: be changed consistently.
1536: It often takes days to get an error-free compilation.
1537: It is frustrating to be unable to test new code for machine X because
1538: the code for machine Y is out of date and cannot compile.
1539: The discipline introduced is that thought must be given to all target
1540: environments simultaneously; this results in earlier exposure of
1541: target environment inconsistencies.
1542: .NH
1543: Deficiencies in C++
1544: .PP
1545: Though indispensable in the construction of Pi, C++ is deficient in two respects.
1546: First, derived classes may inherit from only a single base class.
1547: Second, the benefits provided by classes come at the expense of considerable
1548: compilation overhead.
1549: .PP
1550: Though each class derived from
1551: .CW Core
1552: is a single step from its parent in the type hierarchy, the step embodies
1553: several independent changes: the processor, the operating system and the
1554: compiler.
1555: If Pi had to support all four target environments possible with
1556: operating systems A and B on processors P and Q,
1557: the class hierarchy would be that of Figure 13.
1558: As a result, each derived class would contain target-dependent code replicated in
1559: two others.
1560: .KS
1561: .PS
1562: .ft CW
1563: CORE: "Core"
1564: AP: "APCore" at CORE+(-1.5,-1)
1565: BP: "BPCore" at CORE+( -.5,-1)
1566: AQ: "AQCore" at CORE+( .5,-1)
1567: BQ: "BQCore" at CORE+( 1.5,-1)
1568: line from CORE.s-(0,.1) to AP.n+(0,.1)
1569: line from CORE.s-(0,.1) to BP.n+(0,.1)
1570: line from CORE.s-(0,.1) to AQ.n+(0,.1)
1571: line from CORE.s-(0,.1) to BQ.n+(0,.1)
1572: .ft P
1573: .PE
1574: .ce
1575: Figure 13. Multiplicity of Derived Classes.
1576: .KE
1577: .LP
1578: This is a situation in which
1579: .I multiple
1580: .I inheritance
1581: could be used to eliminate replication.
1582: Under multiple inheritance a derived class may inherit from more than
1583: one base class.
1584: The derivation graph could be as shown in Figure 14.
1585: Target-dependent code would be confined to a single appearance in one of
1586: the base classes:
1587: .CW ACore ,
1588: .CW BCore ,
1589: .CW PCore
1590: and
1591: .CW QCore .
1592: The derived classes would need no additional code.
1593: .KF
1594: .PS
1595: .ft CW
1596: ACORE: "ACore"
1597: PCORE: "PCore" at ACORE+(1,0)
1598: BCORE: "BCore" at PCORE+(1,0)
1599: QCORE: "QCore" at BCORE+(1,0)
1600: AP: "APCore" at ACORE+(0,-1)
1601: BP: "BPCore" at PCORE+(0,-1)
1602: BQ: "BQCore" at BCORE+(0,-1)
1603: AQ: "AQCore" at QCORE+(0,-1)
1604: line from ACORE.s-(0,.1) to AP.n+(0,.1)
1605: line from ACORE.s-(0,.1) to AQ.n+(0,.1)
1606: line from BCORE.s-(0,.1) to BP.n+(0,.1)
1607: line from BCORE.s-(0,.1) to BQ.n+(0,.1)
1608: line from PCORE.s-(0,.1) to AP.n+(0,.1)
1609: line from PCORE.s-(0,.1) to BP.n+(0,.1)
1610: line from QCORE.s-(0,.1) to BQ.n+(0,.1)
1611: line from QCORE.s-(0,.1) to AQ.n+(0,.1)
1612: .ft P
1613: .PE
1614: .ce
1615: Figure 14. Multiple Inheritance.
1616: .KE
1617: .PP
1618: No pair of target environments have yet shared a common component,
1619: but time will certainly change that.
1620: Since C++ does not provide multiple inheritance, some other means of factoring
1621: the program must be found to avoid duplicating code.
1622: Of course, the success of multiple inheritance cannot be guaranteed without
1623: practical experience, but it is certainly worth pursuing.
1624: .PP
1625: A more severe problem that has been encountered is the cost of
1626: recompilation triggered by the modification of class declarations.
1627: The declaration of a class,
1628: .CW X ,
1629: places both the public and private components of its interface in
1630: a single syntactic unit.
1631: The declaration is usually stored in a ``header file,''
1632: .CW X.h .
1633: Two compilation problems arise with respect to
1634: .I clients
1635: of
1636: .CW X ,
1637: that is, other classes that depend only on
1638: .CW X 's
1639: public interface.
1640: Before processing the source text of a client the compiler must read the header
1641: file,
1642: .CW X.h .
1643: It therefore reads both the public and private declarations in
1644: .CW X ,
1645: even though the client's source is denied reference to the private declarations.
1646: (At the implementation level, the client might depend on this private information:
1647: to generate client code, the compiler needs to know the
1648: .I size
1649: of the private data in
1650: .CW X ,
1651: if an instance of
1652: .CW X
1653: appears in a client's stack frame.)
1654: If the private declarations in
1655: .CW X.h
1656: in turn depend on other header files, they must also be included, and so on.
1657: Compilation of the client therefore depends on many header files,
1658: even though the client does not need the information from those header files.
1659: This makes client compilation more expensive, because of the additional
1660: header files that must be processed.
1661: Moreover, using conventional Make |reference(feldman make) dependencies,
1662: client source is
1663: frequently recompiled after the modification of private declarations in
1664: classes unreferenced by the client.
1665: The subterfuge that partially overcomes this problem is unworthy of description.
1666: .NH
1667: Conclusion
1668: .PP
1669: Object-oriented programming in C++ has worked very well in Pi.
1670: Pi's ability to examine multiple processes over multiple target environments
1671: follows from the object-oriented model and class inheritance mechanism used in
1672: the implementation.
1673: At the outset the goal was to experiment with the user interface.
1674: Had an object-oriented programming language not been available,
1675: I doubt that Pi would have evolved beyond experiments at that level.
1676: .NH
1677: Acknowledgements
1678: .PP
1679: The success of Pi owes much to the ideas and software of
1680: Bjarne Stroustrup, Tom Killian and Rob Pike.
1681: Thanks also to Brian Kernighan, Doug McIlroy and John Linderman for
1682: their comments on drafts of this paper.
1683: .NH
1684: References
1685: .LP
1686: |reference_placement
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.