Interactive Programming at Carnegie Tech

A H Bond

1968

Artificial Intelligence 3

From September 1966 to September 1967 Bob Hopgood took a sabbatical at Carnegie Tech having completed the main part of the Atlas Algol System with Alex Bell. At Carnegie he shared an office with Alan Bond and had Tom Calvert as his next door neighbour. All three were involved in interactive graphics on the Bendix G21. Bob Hopgood also implemented a machine independent version of the Brooker-Morris compiler compiler. Robin Kerr, the author of the Atlas Algol Compiler had by then moved to General Electric in Schenectady and Bob collaborated with Robin in getting a version of the Brooker-Morris compiler compiler working on the GE range of machines. Alan Bond. on return to the UK, became an Atlas user. Tom Calvert went on to be a leading figure in the area of computer-aided dance systems after he moved to Simon Fraser University.

1. PROLOGUE-THE RELATIONSHIP OF CONVENTIONAL COMPUTING SCIENCE RESEARCH TO ARTIFICIAL INTELLIGENCE

Ernst and Newell (1967) have discussed programming languages as problem solvers. An ALGOL program solves a certain restricted class of problems. The program is constructed using the primitive control structures and primitive data structures of ALGOL. An artificial intelligence program also solves a class of problems in an analogous way. It has a heuristic control structure rather than one which is straightforwardly deterministic, but Newell and Ernst thought this an unimportant distinction. One might consider an artificial intelligence program as a choice of data structure and control structure which could have been a choice of language. They did not consider the design of a language for artificial intelligence, but it seems to me that such programs are so diverse that an extendable language with suitable primitive structures would be appropriate.

Second, an interesting paper by Simon (see Simon, 1967) compares the central nervous system to a time-sharing monitor program. He argues that processing in the human brain must be serial, and that given the multiple needs of the organism in an unpredictable environment, one is led to a monitor-like control structure with hierarchies of goals which are motivations, and an interrupt mechanism which leads him to a theory of emotion. Certainly one would like a control structure which can serve a multiplicity of motives simultaneously, as opposed to the dogged, weakly contextual control of most problem-solving programs.

2. INTRODUCTION

In this paper I try to describe the current state of interactive programming in so far as I have been concerned with it at Carnegie-Mellon. I describe the graphics system on the G-21, the main computer at present. The graphic monitor and special procedures in ALGOL and Formula ALGOL provide a software system for writing programs with human-program interaction. Some of the difficulties of system programming and of the design of languages which have well-defined semantics during interaction and which provide the needed facilities are discussed. Examples of programs which have been written to interact graphically are described.

3. THE G-21 GRAPHICS SYSTEM

3.1. Hardware

As shown in figure 1, the G- 21 is a 64K computer with two central processors, which runs a card and teletype queue and a teletype servicing monitor. There is a general filing system called AND. There are three very advanced scopes (see Quatse, 1966), also serviced by a special auxiliary 'scope monitor'. Rather than using a special satellite computer, we have an auxiliary 8K module of core which is switchable, i.e. it can be switched, by a G-21 machine order, to be addressable by the G-21 central processor, at which time it replaces a normal module. The entire normal core consists of eight modules. Programs can run using 32K or 64K and they can interact with the switchable module. The module contains code which receives interrupts and performs actions under control of the human scope user; it also contains display material which is a sequence of scope opcodes which is acted upon by the scope scanner. The scope scanner is a separate processor which displays the display material on the screens and enables display material to be entered by human action at the scopes. Thus, the scope module is used by two separate processors; one which interprets the bit patterns as G-21 machine orders, and the other which interprets them as display commands. I suppose any autonomous I/O unit is similar in this respect. It conjures up the idea of a large computer with several processors, some doing computing-setting up I/O material-and others performing the I/O operations. One can enter characters (a large set is provided) or lines, but no curves (these have to be fabricated from lines), and the scanner will also perform certain editing operations on the display material, like clearing a display region or deleting or inserting an element. The display material is broken into a chain of linked modules which the scanner constantly scans. Each module is headed by a delimit scope opcode saying on which scope( s) the display is to be shown. Each scope can have four separate display modules, called its pages; they are of arbitrary length and can be displayed or superimposed visually at will at the console.

Figure 1: The G-21 and H-module

3.2. The scope monitor

The scope monitor (see Bond, 1967) manages the core available space and performs managerial operations on request by the human user or a G-21 program in 'lower core'. It time-shares the three scopes and has a simple, variable increment, interrupt stack for each scope. The various facilities provided by the scope monitor are demanded by twenty interrupt buttons, the meanings of the buttons being shown in an explanatory display (like a menu). The operations are arranged in groups called states, and one changes state by interrupt also in a hierarchical fashion. We think that the commands available form quite a comprehensive set (some are listed in figure 2), and we are trying to make it easy for ordinary users to use the scopes using ordinary ALGOL and Formula ALGOL programs.

Figure 2

3.3. Writing interactive programs

The way one writes an interactive program is simply by using commands very similar to the interrupt commands. Each of these corresponds to a monitor user routine, which we call B routines. A list of B routines is given in figure 3.

Figure 3

By a succession of B routine calls in a program one can set up display or read in display from the scope face. In ALGOL, a procedure called B is provided, whose first argument BNUM is the number of the B routine being called. The procedure B performs all the necessary module switching, checking, memory protection, etc. The means available for human-program interaction are as follows:

1. each displays text to be read by the other;
2. each displays a general display of lines and text;
3. various hardware attachments:
   1. two 'analog knobs' with values in [0,63] can be set by humans and read by program;
   2. the cursor can be set and read by both;
   3. eight switches can be set and read by both;
4. the use of interrupts
   1. compare interrupt on a certain (set of) character( s) on a certain page;
   2. memory full interrupt;
   3. button interrupts, numbered 1-19.

Figure 4 also lists a library of ALGOL routines written using the procedure B, giving a fairly comprehensive set. Note that input and output of card images in the CMU implementation can use an ALGOL array as buffer, and so the scope I/O has the full formatting and conversion facilities of the ALGOL-20 I/O language.

1. INTEGER PROCEDURE LOC(N);
2. B(BNUM, R52, R53, R54, R55, R56);
3. HEADER (X,Y);
4. VECTOR(X,Y,SG);
5. CHA2STR(C1, C2, C3, SG1, SG2, SG3);
6. NUM(X,Y,N);
7. LINE(X1,Y1,X2,Y2);
8. CURVE(X,Y,T,DT,TA,TB);
9. SCALEX(X); SCALEY(Y);
10. READPAGE(N,RBUFF);
11. PRINTONPAGE(N,WBUFF,X,Y);
12. BUTTIN(ENT,CONSW,INTNO,SCOPENO,COMPCHAR);
13. COMEIN (X,Y,CHAR,PAGENO,ENT);

Figure 4

3.4. Permission to interact and interaction with more than one scope

Before any B procedure can be called, B (-1) must be called. This announces the user program to the scope monitor which allows interaction provided the program was submitted from the scope, and not from some other medium, and that the job card corresponds to the user logged-in on the scope. The program also checks, just before, that the scope monitor is indeed present by checking a clobber word in the scope monitor core area. If a program wishes to interact with more than one scope, it sets a variable (a register) when calling the B routine. This will lead to an error unless the human at that scope has first instructed the scope monitor, by means of an interrupt, that it will allow the program submitted from scope N to interact. The program can display and read from scopes for which permission has been given. When an interrupt is generated by the human, the scope monitor passes the number of the interrupting scope to the program.

4. USER INTERRUPTS

The program can define certain points to be entered on interrupt. The scope monitor, of course, processes all interrupts, and recognizes those destined to be processed by the user program and passes control at an appropriate point together with useful information. The compare interrupt is set by putting a special scanner opcode in the module of core corresponding to a given page. Any subsequent attempt to type in a character, of the type designated only, on that page will cause the scanner to generate an interrupt and place the recognized character in a fixed location to be read by the scope monitor. User interrupts of this type can occur in any state; however, the button interrupts are defined by the menus until the monitor is in the user program interaction state. When these interrupts are first defined and the entry points declared to the scope monitor, the user program also passes certain integer arguments which are locations of variables in the user program, i.e. the user program essentially declares some variables for communication with the scope monitor. On interrupt, the scope monitor places all the information, like interrupt number, scope number, etc., in the agreed locations and passes control to the user. To prevent multiple interrupt problems, it was found unsatisfactory to use the hardware control register of the G-2l which prevents any interrupts occurring, as this was too powerful. Instead, one of the declared variables is a user interrupt control switch and is consulted by the scope monitor before passing control. If the switch is set, the scope monitor 'remembers' the interrupt (it does not queue multiple interrupts, however) and keeps inspecting the switch. Thus, one has a shared ALGOL variable, which if used foolishly could cause havoc. For example, the interruption of the evaluation of an expression involving the scope number might have one value for it in one part and another in another part of the evaluation; however, this mechanism, if used sensibly, can be advantageous.

The interruption of programs written in high-level languages has its problems. In machine or assembly code one can simply pass control anywhere; the only errors are those to do with the interruption of a printing command, in which further printing is attempted. This leads to a machine halt from the printer on our machine. If data is overwritten by the new control, in particular return marks, then one assumes the programmer knows what he is doing; he must save any information as it enters the interrupt entry point. In ALGOL, first of all, note that we always use integer variables which are locations of variable, i.e. the address of where the value of the variable is stored. This needs the library procedure LOC. I believe something like this has been proposed in ALGOL x, and is defined in CPL. Normally, the user's interrupt entry point is to his own interrupt service routine; we shall call this the UISR. It makes decisions about what to do next. If it wishes to return to the interrupted computation, then one has to be careful. If it is a simple procedure or simply nested set of procedures without gotos then one can simply return through the UISR return mark to the monitor and thence back to the interrupted computation; this is arranged by the scope monitor. If one has wandered further afield using gotos then a B routine is provided to allow it to return to the interrupted computation. The interrupted computation can then continue provided no damage has been done. In genuine recursive ALGOL, the return marks of all routines will be all right; in non-recursive implementations, not so. A call on a monitor routine (the normal monitor, not the scope monitor) which is overwritten by a similar call in the UISR will lead to trouble. Printing in the UISR will upset NAME lists in the ALGOL printing routines, and indeed it can be said that if a return to the interrupted computation is envisaged, the UISR must not print or communicate with the monitor. In most programs the UISR does not return, however, and usually initiates some entirely new task.

Something more powerful than ALGOL, like Formula ALGOL (FORML for short), is another matter entirely. The implementation at Carnegie-Mellon has two features which interest us here. First, it compiles code which is heavily dependent on (non-recursive) run-time routines. Second, all marks and values and printing pointers are stacked in a communal historian stack. The VISR has to be restricted to a very small subset of FORML; in fact, simple arithmetic expressions and assignments, and local backward gotos only, to avoid disturbing the historian.

The typical program is usually happy to wait in a passive loop looking at a switch and then to act accordingly. One only really wants to interrupt if one sees one's program on a long, worthless task and wishes to terminate this action prematurely. Usually one issues a command and waits for completion before issuing the next command. It is interesting to observe that interactive programs must take on more of a monitor structure than normal programs, also that flow-charting of such programs can sometimes be tricky with control lines appearing out of nowhere, and presumably also going to nowhere, viz. the monitor. Whether sophisticated interactive programs will have to worry about queueing of interrupts or priorities of interrupts is not clear. An advantage of interrupts is that they do tend to give a quick response to the human. Before going on to discuss interactive programs, I shall first describe briefly the other type of interactive user system, viz. the user submonitor and also the modular version of the monitor.

5. THE MODULAR VERSION OF THE SCOPE MONITOR AND USER SUBMONITORS

In the new version, close to completion, the scope monitor has been restructured as a small resident part, about 1000 (decimal) words and a set of relocatable modules of code which swap as required from the disc.

Any user can write a submonitor consisting of an indefinite number of linked modules. These are declared, i.e. assigned logical numbers, by the human. They may be on scope files or AND files, on the disc, and they are used in the same way as system modules. In this way it is now possible to extend the scope monitor indefinitely in modular form, assembling and debugging individual modules only. The assembly of suitable modular code is achieved by a small set of macros, and any assembly program can be so converted. Unfortunately we do not have base registers, so we use a relocation algorithm to relocate the modules at run-time. No high-level language is available for writing this kind of system, but the macro assembler, SPITE, is quite nice. We now have the situation of one large available space, and modules of system code, user code, data, or display material all being allocated space. A text editor submonitor has been written by M. Coleman, which provides extra text manipulation facilities, actuated by graphical commands.

6. CONTINUOUS OPERATIONS AND CONTINUOUS CONSTRAINTS

The scope monitor provides various continuous operations for the human user on request. It will continuously sample a selected area of core and display an octal dump. Using the analog knobs, one can select any area in the G-21 for display. One can request a rotation mode in which a rotation of an analog knob rotates the vectors on a selected page. One can request a curve drawing mode in which the scope monitor puts in line elements as the cursor is moved.

No continuous operations are provided for a user program at the moment, but we feel that some continuous monitor capability could be provided. The user could specify some condition and the monitor could continually check it and interrupt when necessary. This is similar to the PL/I operation ON, but is provided by the monitor rather than being part of the user program. Hardware interrupts can be used to monitor access of, or storage into, flagged locations.

7. INTERACTION WITH TYPEWRITERS

Although some provision is available in the main monitor for interaction with a teletype, no one has yet used this facility in a user program. The routines are used by a desk calculator program, similar to JOSS, which is a part of the monitor, and available on line to any teletype user. The assembler SPITE does have provision for error correction by human intervention at assembly time using a teletype; however, this involves reinitiation of the assembly by job-card.

8. INTERACTIVE PROGRAMS

1. Brooker Morris Compiler-Compiler. This has been implemented on the G-21 by F.R.A.Hopgood (1967). We simply added graphical input-output. Input cards are typed on one page and cleared as they are processed. The last few lines of line printer output are displayed on another page. The response time is imperceptible.
2. The GRASP System. This is a graphic service program written by E.M. Thomas (1966,1967) in ALGOL for the G-21. It is a model building language whose format is like a series of procedure calls. It can also be used as an outer block to an ALGOL program, in which case the procedure calls can be freely incorporated into ALGOL statements. It differs from Sketchpad in several ways, and it does not have constraint satisfaction built in.
3. GRANIS. A graphical inference program written in Formula ALGOL by L. S. Coles (1967). It reads in a picture from the scope face and a statement and decides whether the statement is true or false about the picture.
4. A Pattern Recognition Heuristic Program, by T. W. Calvert (1967). It allowed some human intervention, but mainly for the purpose of gaining insight into its behaviour rather than for a man-machine production system.
5. A graph drawing, interactive iterative and curve fitting system in ALGOL is under development by the present author. Its purpose is to experiment with a very intense interaction between a human and a set of functions.

A typical layout of an interactive program is given in figure 5.

Figure 5: Control structure of interactive system

9. THE FUTURE

In the coming year our two new computers, a Univac 1108 and an IBM 360/67, will take over the main computing load. Some conversational compilers are provided, and we will write some systems ourselves. The LCC project by Perlis, Van Zoren, and Mitchell is a modified conversational ALGOL with a delightful dynamical structure. It is being implemented on the 360. There will be graphics on both machines, but it is not yet clear what hardware will be suitable or what software will be available. The G-21 will gradually become used mainly for graphics. There are several application programs being written in ALGOL for oil mining analysis, structural stress analysis, electrocardiogram recognition, architectural design, etc. Also, there are a few artists beginning to try to use the computer as an artistic medium or artistic aid. Eventually the main monitor will be altered to allow the three scope programs, one from each scope, to monopolize the machine with a swapping system. In the coming year we hope to get some experience with ordinary users writing interactive graphical programs in the usual high level languages.

REFERENCES

Bond, A.H. (1967), Scope user manual. CIT document, CIT.

Calvert, T. W. (1967), Ph.D. thesis. Department of Electrical Engineering, CIT.

Coles, L.S. (1967), Ph.D. thesis. Department of Computer Science, CIT.

Ernst, G. W. & Newell, A. (1967), Generality and GPS. CIT document, CIT.

Hopgood, F.R.A. (1967), The machine independent implementation of the Brooker-Morris compiler compiler.

Quatse, J.T. (1966), A visual display system suitable for time shared use. CIT publication, CIT.

Simon, H.A. (1967), Motivational and emotional controls of cognition. Psycho I. Rev.74,29.

Thomas, E. M. (1966), GRASP user manual. CIT document, CIT.

Thomas, E.M. (1967), GRASP- a graphic service program. Proceedings 22nd A.C.M. National Conference, p. 395. London: Academic Press.

Lorraine Hopgood, Tom Calvert, Malcolm Bird, Barbara Hopgood, Lorna Calvert, Paul Hopgood