September 1969 - Vol. 12 No. 9
Features
On multiprogramming, machine coding, and computer organization
The author feels that the interrupt feature which is available in most modern computers is a potent source of programming pitfalls and errors, and that it therefore may heavily contribute to the unreliability of programs making use of it. A programming scheme is presented which avoids the concept of the interrupt and permits the specification of concurrent (or pseudoconcurrent) activities in a supposedly more perspicuous manner. It is intended to serve as a basis for the construction of operating systems, which are prime examples of programs with concurrent activities. The scheme includes a set of basic instructions for the generation, termination, and synchronization of parallel processes. A set of routines representing these instructions and thereby simulating a hypothetical machine organization has been implemented and tested on the IBM System/360. Two programs using these instructions, written in PL360, are presented.
Compact list representation: definition, garbage collection, and system implementation
Compact lists are stored sequentially in memory, rather than chained with pointers. Since this is not always convenient, the Swym system permits a list to be chained, compact, or any combination of the two. A description is given of that list representation and the operators implemented (most are similar to those of LISP 1.5). The system garbage collector attempts to make all lists compact; it relocates and rearranges all of list storage using temporary storage. This unique list-compacting garbage collection algorithm is presented in detail. Several classes of the macros used to implement the system are described. Finally, consideration is given to those design factors essential to the success of a plex processing system implementation.
A base for a mobile programming system
An algorithm for a macro processor which has been used as the base of an implementation, by bootstrapping, of processors for programming languages is described. This algorithm can be easily implemented on contemporary computing machines. Experience with programming languages whose implementation is based on this algorithm indicates that such a language can be transferred to a new machine in less than one man-week without using the old machine.
An algorithm for finding a fundamental set of cycles of a graph
A fast method is presented for finding a fundamental set of cycles for an undirected finite graph. A spanning tree is grown and the vertices examined in turn, unexamined vertices being stored in a pushdown list to await examination. One stage in the process is to take the top element v of the pushdown list and examine it, i.e. inspect all those edges (v, z) of the graph for which z has not yet been examined. If z is already in the tree, a fundamental cycle is added; if not, the edge (v, z) is placed in the tree. There is exactly one such stage for each of the n vertices of the graph. For large n, the store required increases as n2 and the time as n&ggr; where &ggr; depends on the type of graph involved. &ggr; is bounded below by 2 and above by 3, and it is shown that both bounds are attained.
In terms of storage our algorithm is similar to that of Gotlieb and Corneil and superior to that of Welch; in terms of speed it is similar to that of Welch and superior to that of Gotlieb and Corneil. Tests show our algorithm to be remarkably efficient (&ggr; = 2) on random graphs.
On simulating networks of parallel processes in which simultaneous events may occur
The following resolutions were passed at the ASA X3.4 Common Programming Languages Subcommittee during the thirty-third meeting held February 20, 1964 at CEIR, Beverly Hills, California.
