OEDIPUS(ID:5626/oed001)Bell Labs interpretive algebraic systemfor Operating Environment with Dynamlc storage allocation, Input-output, Public pushdown List, Unhurried diagnostics, and Symbolic snaps !!!! Interpretive environment for algebraic manipulation, built as an extension to ALPAK on the way towards ALPAKB Places Related languages
References: DOI Extract: Oedipus intro OEDIPUS is a computer programming system which can serve as an operating environment for' programs and programming systems requiring dynamic storage allocation and/or recursion A detailed technical description of this system is given in [1]. The name is an acronym (Operating Environment with Dynamic storage allocation, Input-output, Public pushdown list, Unhurried diagnostics, and Symbolic snaps) which outlines the main features of the system and also the sections of this paper. OE: Operating Environment OEDIPUS is an outgrowth of the experience of programming ALPAK, a system for the symbolic manipulation of rational functions of several variables [2]. This experience involved the solution of several interesting mathematical problems, and also suggested many more. However, it became apparent at art early stage that the mathematical problems were overshadowed by a mountain of programming problems including dynamic allocation of storage for contiguous blocks of unpredictable size, communication and bookkeeping for subroutines including some which are recursive, input and output for a hierarchy of data types, and debugging. Simple examples are given in the appropriate sections below. It seems obvious that these problems are not unique to ALPAK, and that adequate general solutions would be useful for the implementation of a wide variety of systems having similar requirements. We were thus led to the concept of an operating environment, an extension of a conventional monitor system to provide the services needed by higher level programming systems such as ALPAK. Of course we hope anti expect that these services will be provided in one form or another within future monitor systems. If so, both the implementors and the users will profit substantially. The dynamic storage allocation orders (see Section D) make it possible to obtain contiguous blocks of storage of arbitrary size as needed (provided that sufficient space is available) and to return idle space to the system. This type of storage allocation is clearly required for dynamic own arrays in ALGOL [4] and for the ALLOCATE and FREE statements of NPL [5]. The input-output facilities (see Section I) assume that all data structures, both on cards and in core, are self-identifying. A data structure on cards must begin with an identifying control card. A data structure in core must have an identifying code number in its heading. An executive input routine, READ, picks up the control card and calls the appropriate special-purpose input subroutine. An executive output routine, PRINT or PUNCH, fetches the code number and calls the appropriate special-purpose output subroutine. The use of a public pushdown list for subroutine storage (see Section P) makes recursive programming automatic. That is, a subroutine can call itself without taking special measures to preserve its arguments and intermediate results. The difficulty of programming subroutines, whether recursive or not, is substantially lessened by a rudimentary compiler which assumes the burden of incrementing and restoring the public-pushdown-list pointer, transmitting arguments, clearing temporaries, and so forth, leaving the programmer free to concentrate on essentials. OEDIPUS is based on the premise that debugging is a central problem, perhaps the central problem, in the implementation and in the operation of any large programming system. Furthermore, conventional debugging aids (octal snaps and post mortems) are hopelessly inadequate in the face of dynamic storage allocation and recursion. The debugging aids in OEDIPUS provide a unique combination of three features. (1) The decision on whether or not to terminate a run and initiate a post mortem can be delayed until well after the trouble has been discovered and all necessary information has been saved (see Section U). (2) In a run-time or post-mortem snap the computer assumes the burden of finding and analyzing subroutine storage sections in the public pushdown list and data structures in the data buffer (see Section S). (3) The data structures which are printed during a run-time or post-mortem snap can be printed symbolically (that is, in source language) by user-provided printing subroutines. This feature is vitally important for any system which deals with large and complex data structures. Its implementation requires an executive printing routine (see Section I). OEDIPUS has been implemented within the BE-SYS-7 monitor system on the IBM 7094 computer, but its language and concepts are machine independent. In its present form it consists of a macro compiler and two sets of subroutines. The latter were compiled with the aid of the former, and occupy approximately 3600 (decimal) words of storage. The entire project including research, development and documentation required approximately three man-years of effort. The following notational conventions apply to model instructions throughout: lower-case italic and upper-ease roman letters represent substitutable and non-substitutable items respectively. Macro parameters which are to be interpreted literally are boldface. All others are addresses of the arguments for which they are named. If the argument is a dynamically allocated data structure (see Section D), then the corresponding macro parameter is the address of its pointer. Finally, optional parameters are enclosed in brackets, and parameters which may represent lists or sets of' sub-parameters are enclosed in parentheses. D: Dynamic Storage Allocation For efficiency ALPAK represents a non-scalar polynomial as an array of coefficients and exponents, and stores this array in a contiguous block of memory locations. During a typical computation many polynomials come and go, and their sizes are for all practical purposes completely unpredictable. Clearly the allocation of blocks of storage for all of these polynomials cannot be done in advance, so it must be done as the need arises. Furthermore, the active blocks must occasionally be packed together to prevent the free storage from breaking apart into uselessly small fragments. The higher order data types in ALPAK include formal products represented as lists of scalars or polynomials, truncated power series represented as lists of scalars or polynomials or formal products, and matrices represented as arrays of scalars or polynomials or formal products or truncated power series. All of these can be viewed as rooted directed treks whose terminal nodes are scalars and polynomials. Therefore, the storage allocator must be able to handle trees as well as blocks. In OEDIPUS the terminal nodes of a tree are represented as blocks of data, while the remaining nodes are represented as blocks of pointers. Every main program which uses OEDIPUS directly or indirectly must begin with an initialization order whose functions include reserving a block of working space, to be called the data buffer. Since blocks may be moved without warning, each block has a fixed heading, which always maintains its current location and length. The user refers to a block by giving the symbolic address of a single word, called a pointer, containing tile address of the heading. Since there may be several pointers to a given block, as in the example of Figure 1, the heading also contains a reference count. All blocks and their headings are located in the data buffer, which is partitioned into three sections as illustrated in Figure 2. The blocks are at the beginning in locations AA through BB -. 1; the headings are at the end in locations CC through DD - 1; and the free space is in the middle in locations BB through CC - 1. Initially BB = AA and CC = DD. When a block is to be created, an idle heading is found in the heading region (or if none exists a new heading is created just before CC), the block itself is created just after BB, and BB and CC are updated appropriately. When a block is to be destroyed, its heading is marked idle and the link from the heading to the block is broken. Whenever there is not enough free space for a desired block, the garbage collector is automatically called. This subroutine repacks the active blocks at the beginning of the data buffer, thereby restoring any idle blocks to free space, and updates BB accordingly. To obtain a block b of length lng, the user writes MAKBL b, lng This is a macro instruction with substitutable parameters b and lng, which represent the symbolic addresses of a pointer and of a length respectively. MAKBL (MAKe BLock) creates a block and a heading for B as described above, and fills in the pointer with the address of the heading. MAKBL also has an optional third argument, which can be used to specify the identification word (see below), and an optional overflow exit (see the discussion of failure exits in Section P). Once a block b has been created, the user can locate it by writing FIND b, (xr), (adr) where xr is a list of index registers to be loaded with the length of b and adr is a list; of addresses to be filled with the address of b. A simple example may help to clarify the role of FIND. Suppose we have two equal-length blocks A and B, and we wish to copy the contents of B into A. First we locate the two blocks by writing: FIND A, 2, AX FIND B, , BX Index register 2 now contains the length, while AX and BX contain the BES addresses of A and B respectively. To copy the contents of B into A we now write: BX CLA **, 2 AX STO **, 2 TIX BX, 2, 1 When a block b is no longer needed, the user can release it by writing CLEAR b or he can reuse its pointer as an output of MAKBL MAKBL b, lng or of some other OEDIPUS-compiled subroutine. In the latter case the subroutine (e.g., MAKBL) clears it and then fills in its pointer with the address of a new heading (see the discussion of normal exits in Section P). When called from outside of itself, the CLEAR subroutine replaces the pointer of its argument by zero. If the reference count in the heading reveals the existence of other pointers, then it is reduced by one. Otherwise the heading is marked idle and the link from it to the block is broken. Every active heading contains an identification word whose principal purpose is to identify the block for the benefit of the executive output routines (see Section I). The block may or may not be a block of pointers, and the identification word may or may not contain a pointer. The four cases are distinguished by the tree indicator, which is a part of the identification word. When CLEAR is applied to a block of pointers or to a block whose identification word contains a pointer, the attached structures must be cleared before the given block is released. Thus CLEAR is a recursive subroutine. Its algorithm in abbreviated form is: (1) reduce reference count; or (2) clear any attached structures, mark the heading idle, break the link from the heading to the block, and if CLEAR was called front outside of itself zero the pointer. There are two subroutines for copying. CPYPT (CoPY PoinTer) copies the pointer and increments the reference count. COPY makes a new block, and increments the reference counts of any attached blocks. Similarly there are two subroutines for exchanging. XCHPTS (eXCHange PoinTerS) exchanges the pointers, leaving the headings untouched, while XCHHDS (eXCHange HeaDingS) exchanges the headings except for their reference counts, and leaves the pointers untouched. A block can be extended contiguously in either direction, or cut; from either end, at run time. The extension algorithm in abbreviated form is: (1) extend the block into adjacent space; or (2) make art extended copy at the beginning of free space (after collecting garbage if necessary); or (3) open a gap between the given block and its neighbor, and extend into the gap. Finally a block may contain one or more disjoint subblocks, each of which may in turn contain one or more disjoint subblocks, and so forth to arbitrary depth. Like any other block, a subblock has a heading and one or more pointers. Every heading contains a subblock indicator, which tells whether or not it is a parent block and whether or not it is a subblock. When a parent block which is not itself a subblock is cleared, its first-generation subblocks cease to be subblocks, so their subblock indicators are changed accordingly. Similarly when a subblock is cleared, its parent may cease to be a parent, and if so its subblock indicator must be updated. I: Input-Output It is evident that the routine which receives an ALPAK user's request for input or output of a polynomial must be able to handle a scalar, since a scalar is a special case of a polynomial. However it is inconvenient to represent a scalar, either on cards or in core, as a polynomial in some particular set of variables, having exactly one term in which all of the exponents are zero. Therefore a scalar, whether on cards or in core, must be marked in such a way that it can be distinguished from a nonscalar polynomial before any conversion is attempted. Similarly the routine which receives an ALPAK user's request for input or output of a data structure of the highest type must be able to handle any data structure of lower type, and every data structure must be labeled to indicate the lowest data type to which it belongs. We are thus led to the concept of a single executive reading routine, henceforth called READ, whose function is to discover the lowest data type of the structure on cards and call an appropriate special-purpose reading subroutine. Now the special-purpose subroutine for reading polynomials will not have to be able to read scalars, since READ will divert all scalars to the scalar reading subroutine. Similarly we are led to the concept of executive printing and punching routines, to be called PRINT and PUNCH respectively. Since the purpose of output is to provide information, and not to alter the flow of control, these have no error returns, instead, each provides as much information as possible about its argument and then returns control to its calling program. Since these executive input and output routines fulfil a need which exists whenever a system deals with data structures of several types some of which are special cases of others, it seems clear that they should be a part of ALPAK's operating environment, OEDIPUS, and not a part of ALPAK itself. This can be accomplished by adopting conventions for labeling data structures with their data types and for describing the correspondence between labels and special-purpose input arid output subroutines. For each distinct data type the OEDIPUS user must adopt a three-letter generic name and a small non-negative integral code number. He must also supply reading, printing and punching subroutines, arid tables to inform OEDIPUS of the correspondences between generic times, code numbers, subroutines and control cards (see below), these tables can be generated by a single macro call. A data structure on cards always begins with a control card containing its generic name, and usually ends with a control card containing its generic name concatenated to "END". The latter may be omitted if no ambiguity results. READ examines the name card, finds the name in a table, arid calls the corresponding special-purpose reading subroutine. This subroutine is expected to read and convert all subsequent, cards up to the end card, if any, and to store the resulting structure in the data buffer. The reading may be terminated by a signal within the data or by a look ahead at the next, control card. In the latter ease the control card may be an end card for the current data structure or a name card for the following structure. Upon regaining control, READ processes the end card, if any, and returns control to its calling program. It is important to realize that a special-purpose reading subroutine may itself make one or more recursive calls to READ. This possibility may be clarified by a simple ALPAK example. The following is a set of input cards for a formal product (PRD) of two polynomials (POL) and a scalar (SCL). Optional end cards are bracketed, and the numerical data cards are replaced by dots. PRD POL . . . [POLEND] POL . . . [POLEND] SCL . . . [SCLEND] PRDEND When READ is called, it examines the PRD card arid calls the special-purpose subroutine for formal products. This subroutine calls READ three times, once for each of the factors. Before each of these recursive calls it looks ahead at the name card to verify that a legal factor is coming. When it sees that PRDEND is not the name card of a fourth factor, it returns control the outer READ, which processes the PRDEND card and exits. We remark that either END or an end-of-file condition is recognized as a control card and terminates all levels of READ. Also, any card with an asterisk in column 1 is treated as a remark card. Remark cards printed if the PIO switch is on, but are otherwise ignored. The PIO switch may be turned on or off by the user. When it is on, all cards which are read and all data structures which are punched are also printed. Every data structure in core has a heading which contains its code number. An executive output routine, PRINT or PUNCH, finds the code number and calls the corresponding special-purpose output: subroutine, which is expected to convert and print or punch the entire structure. If the code number is illegal, a special-propose output subroutine within OEDIPUS prints or punches the structure in octal. If the structure is a tree, the special-purpose output subroutine may call PRINT or PUNCH recursively to take care of the sub-trees. If a given sub-tree is encountered more than once (luring the output of a tree (for example the sub-tree rooted at E in Figure 3), then on all encounters after' the first, only the heading address, which provides a back reference, and a suitable comment or control card are printed or punched. P: Public Pushdown List A subroutine which can call itself', either directly or indirectly, is called recursive. In order to automate the bookkeeping associated with recursion, Om)Ir, Vs provides a public pushdown list for subroutine storage sections. Although we borrowed the idea from LISP [3], we shall explain it here in order to keep the paper self-contained. When control passes into a subroutine, ENTER (see below) adds a storage section for it to the public pushdown list. When the subroutine has completed its task, EXIT (see below) removes the storage section, thereby restoring the public pushdown list, to its prior state. In the meantime if the subroutine calls another subroutine, a storage section for the latter will be added temporarily during its execution. With this mechanism a subroutine which is idle at, a given moment has no storage, section at all, while one which is recursively active has several - one for each level. Clearly this use of space is very economical. Furthermore in our implementation the cost in time is negligible, since a subroutine can access a location in its storage section directly with the aid of a reserved index register which always marks the end of the public pushdown list. When one undertakes to write a subroutine as a part of a larger system, it often seems that the "trivial" problems of communication and bookkeeping are more than half of the battle. Furthermore as the system grows, any change in the method of performing these tasks tends to become progressively more difficult, until eventually even the most minor change may be considered impossible. To alleviate these difficulties OEDIPUS in(dudes a compiler for sub- routines, hi our implementation this compiler is the 7094 FAP assembly program, augmented by a set of macro definitions. An OEDIPUS-compiled subroutine is called by a macro instruction of the same name, which is defined with the aid of the macro instruction MACDEF. For example, the subroutine COPY is called by the macro instruction: COPY a, b, [ovf] This replaces a by a copy of b or transfers to ovf if space is insufficient. The brackets indicate that the parameter ovf is optional. The arguments are a and b, and the failure exit is ovf. The macro definition is produced by: MAC, DEF COPY, ((A), (B)), ((OVF)) A subroutine begins with a set of declarations, which specify its calling sequence and other characteristics. For example, COPY begins with the declarations: BEGSUB (A, B), (OVF), (ID, LNG), (2) INOUT (B), (A) PTDCL (A, B) The BEGSUB (BEGin SUBroutine) declaration specifies that A and B are (internal names for) the arguments, OVF is the failure exit, ID and LNG are temporaries, and index register 2 must be saved and restored. The INOUT (INputs and OUTputs) declaration specifies that B is the input and A is the output. The PTDCL (PoinTer DeCLaration) declaration specifies that A and B are dynamically allocated data structures (see Section D), whereas [1) and LNG are simply data words. These declarations completely determine the action which must be taken at, each entry point and at each exit point. At an entry point the programmer writes sb ENTEIR where sb is the name of the entry point,. This compiles an ENTRY card, some information for PRTREM and SSNAP (see Sections U and S respectively), and a calling sequence for an enter subroutine, whose functions are: (1) suppress any remark which has been set (see Section U) ; (2) initiate a post mortem if time has run out (see Section S) ; (3) append an appropriate storage section to the public pushdown list; (4) bring in the inputs; and (5) save the required index registers. At a normal exit the programmer writes: EXIT This compiles a transfer to an exit subroutine whose functions are: (1) clean those temporaries mentioned in the PTDCL declaration; (2) restore index registers; (3) pass out the outputs (after first clearing those external structures which are being replaced by arguments mentioned in the PTDCL declaration); (4) remove the storage section from the public push-down list; and (5) transfer to the first instruction following the calling sequence. At a failure exit the programmer writes EXIT f where f is one of the failure exits mentioned in the BEGSUB declaration. This compiles a one line calling sequence for a failure-exit subroutine, whose functions are: (1) verify that a remark has been set (see SETREM in Section U) ; (2) flag both outputs and temporaries for clearing if and when the remark is suppressed (see OFFREM in Section U) ; (3) restore index registers; (4) remove the storage section from the public push-down list; and (5) transfer to the proper line of the calling sequence. Finally a subroutine ends with the instruction ENDSUB which causes the assembly of the euter and exit subroutines and also the failure-exit subroutine if necessary. U: Unhurried Diagnostics When art overflow or error is detected in any program within OEDIPUS (using OEDIPUS), it sets (should set) a remark describing the situation. It may then: (1.) print the remark and terminate the job; (2) print the remark and proceed by an alternative route; (3) suppress the remark and proceed by an alternative route; or (4) if it is not the main program, take a failure exit to its calling program, which will then have the same four options. A remark consists of an appropriate diagnostic and a snap of the subroutine nesting list, the principal machine registers, and several key OEDIPUS parameters. For an example see the first nine lines of' Figure 4. The novelty of this procedure lies in the possibility of using option (4). The subroutine which first detects an overflow or error prepares the remark, including both a diagnostic and a snap, but the decision on what action if any should be taken cat, be passed up the line to some higher level subroutine or even to the main program. The handling of overflows and errors in a programming system using OEDIPUS is analogous to the handling of problems in a large corporation. When an employee detects a problem, he will almost certainly make some notes concerning the circumstances of the case. He may then (1) write a normal memorandum and close the case; (2) write a formal memorandum and take some new initiative; (3) throw away his notes and take some new initiative; or (4) if he is not the president, place his notes on the desk of his supervisor, who will then have the same four options. The advantages which accrue to the corporation from the existence of option (4) are evident. There are three basic orders for implementing the procedure which we have described namely SETREM (SET REMark), PRTREM (PRinT REMark), and OFFREM (OFF REMark). In addition, there is a remark switch, which tells at any given time whether or not a remark is set, and if so whether or not it has been printed. To set a remark the user writes SETREM bss, lng where bss is the first word of the diagnostic and lng is its length. SETREM saves these parameters, the contents of the principal machine registers, and several key OEDIPUS parameters, and then turns on the remark switch. If the remark switch is on when SETREM is entered, SETREM calls OFFREM before setting the remark. To print a remark the user writes: PRTREM If the remark switch is on, the remark which has been set is printed and the remark switch is set to its midway position indicating that a remark is set and has been printed. If the remark switch is off or in its midway position , PRTREM does nothing. PRTREM, may also be called by typEND (see Section S). To suppress a remark the user writes: OFFREM This turns off the remark switch and clears any data structures which have been flagged during failure exits (see Section P) since the remark was set. S: Symbolic Snaps The symbolic snapping facility in OEDIPUS permits symbolic printing (by routines belonging not to OEDIPUS but to the system, such as ALPAK, for which OEDIPUS is the operating environment) of the inputs to all subroutines on the public pushdown list, as well as octal printing of the storage sections of these subroutines and of all headings and blocks in the data buffer. Both runtime and post-mortem symbolic snaps are permitted. To take a symbolic snap at runtime, the programmer writes SSNAP i, s, d where each of the parameters is and d is 0 or 1. First the following information is printed for each subroutine on the public pushdown list,: (1) the location from which it was called; (2) its name; (3) if i is 1, its inputs (see. INOUT in Section P), using PRINT (which calls the appropriate special purpose printing subroutine, as explained in Section 1) for those which are pointers (see PTDCL in section P); and (4) if s or d is 1, its storage section in octal, separated into arguments, temporaries, and index registers. Then if d is 1, each active block in the data buffer is printed in is printed in octal together with its heading and appropriate labeling. An OEDIPUS post-mortem consists of a remark (See Section U), if any has been set, and a symbolic snap if one has been requested. […] To request a post-mortem symbolic snap, the user writes typ SSNAP i, s, d at the beginning of his in main program. Then if his run is terminated by a call to typEND (see below), it (typEND) will call SSNAP i, s, d after printing the location and type of its call, and after printing any remark which has been set. To initiate a post mortem, the user writes typEND where type is AOK (normal), OVF (OVerFlow), or DED (error). AOKEND should be used at any place where the job might end if everything goes according to plan, and OVFEND or DEDEND at any other place where it could conceivably end. It, is usually wise to see that a remark has been set, (see Section U) before OVFEND or DEDEND is called. OVFEND should be used whenever the job demands an excessive amount of space or time or produces an excessive amount, of output. DEDEND should be used whenever a programming error is implied. Of course, not every job will end at one of the places where AOKEND, OVFEND or DEDEND has been provided. Nevertheless the benefits of a post, mortem are available to almost all jobs except those which transfer accidentally or deliberately to the job termination subroutine in the monitor. This is accomplished by having the monitor give control to a special OEDIPUS subroutine whatever it interrupts a job for almost any reason. This courtesy is offered only once, and the amounts of time and output available for the post mortem are limited. in [ACM] CACM 8(06) June 1965 view details OEDIPUS Now let us discuss briefly some of the programming problems which were encountered in the implementation of ALPAK. In the first place polynomials and rational functions must be put somewhere inside the computer, and this is clearly the sort of problem that the ALPAK user'should not have to think about. The amount of space required for a particular expression cannot usually be predicted in advance, and space must also be found for intermediate expressions whose existence the user may not even be aware of. This problem is solved by writing a dynamic storage allocator which finds and frees blocks of space on request. The storage allocator must also be able to handle lists and trees, since our data structures--e.g., products of polynomials--are often fairly complicated. A second problem is that many algebraic procedures are recursive. For example, to divide two polynomials in n variables, it is necessary to call a procedure for dividing polynomials in n-1 variables. If n > l, the second procedure is the same as the first, which therefore must be able to call itself. A third problem is that the introduction of complex data structures, dynamic storage allocation, and recurslon has necessitated a new approach to the problem of post mortem analysis. When a run is terminated because of insufficient space or time or because of a programming error, how can we get the computer to tell us in a problem oriented way what it thinks it was trying to do, where it was, and how it got there? Finally there is the ever present problem of book- keeping for subroutines. The facilities for dynamic storage allocation, recurslon, and post mortem analysis impose so many requirements on the writer of a subroutine that he needs the help of a computer to survive. These problems are all more general than ALPAK, and they led us to develop an operating environment called OEDIPUS (Operating E__nvironment with D_ynamlc Storage Allocation, I_nput-Output, Public Pushdown List, U_nhurried Diagnostics, and Symbolic Snaps). This serves as a foundation for ALPAKB, a new version of ALPAK, and can also be used to implement other systems having similar requirements. in [ACM] CACM 9(08) August 1966 view details |