Abstract Dbxtool is a window‐ and mouse‐based debugger for C, Pascal and FORTRAN programs running on Sun workstations. Its use of the mouse as the primary input mechanism eliminates the need to type variables, line numbers, breakpoints and most commands. Its multiple windows provide several qualitatively different perspectives on the debugging problem. Compared to the Unix 4.2 BSD dbx from which it is derived, it has been extended with the abilities to debug multiple‐process programs, already‐running processes, and the Sun Operating System kernel.

A new approach to data flow analysis of procedural programs and programs with recursive data structures is described. The method depends on simulation of the interpreter for the subject programming language using a retrieval function to approximate a program's data structures.

Two different methods of flow analysis are discussed, one a significant generalization of the other. It is shown that the two methods have significantly different intrinsic computational complexities. As an outgrowth of our observations it is shown that a feature of the programming language used by Dijkstra in A Discipline of Programming makes it unsuitable for compile-time type checking, thus suggesting that flow analysis is applicable to the design of programming languages, as well as to their implementation. It is also shown that program verification by the method of inductive assertions is very likely to lead to assertions whose lengths and proofs are not polynomially bounded in the size of the program being verified, even for very simple programs. This last observation casts further doubt on the practicality and relevance of mechanized verification of arbitrary programs.

In [12] the authors introduced the concept of binding time optimization and presented a series of data flow analytic methods for determining some of the binding time characteristics of programs. In this paper we extend that work by providing methods for determining the class of shapes which an unbounded data object may assume during execution of a LISP-like program, and describe a number of uses to which that information may be put to improve storage allocation in compilers and interpreters for advanced programming languages.We are concerned chiefly with finding, for each program point and variable a finite description of a set of graphs which includes all the shapes of values the variable could assume at that point during the execution of a program. If this set is small or regular in structure, this information can be used to optimize the program's execution, mainly by use of more efficient storage allocation schemes.In the first part we show how to construct from a program without selective updating a tree grammar whose nonterminals generate the desired sets of graphs; in this case they will all be trees. The tree grammars are of a more general form than is usually studied [8, 19], so we show that they may be converted to the usual form. The resulting tree grammar could naturally be viewed as a recursive type definition [11] of the values the variables may assume. Further, standard algorithms may be employed to test for infiniteness, emptiness or linearity of the tree structure.In the second part selective updating is allowed, so an alternate semantics is introduced which more closely resembles traditional LISP implementations, and which is equivalent to the tree model for programs without selective updating. In this model data objects are directed graphs. We devise a finite approximation method which provides enough information to detect cell sharing and cyclic structures whenever they can possibly occur. This information can be used to recognize when the use of garbage collection or of reference counts may be avoided.The work reported in the second part of this paper extends that of Schwartz [17] and Cousot and Cousot [7]. They have developed methods for determining whether the values of two or more variables share cells, while we provide information on the detailed structure of what is shared. The ability to detect cycles is also new. It also extends the work of Kaplan [13], who distinguishes only binary relations among the variables of a program, does not handle cycles, and does not distinguish selectors (so that his analysis applies to nodes representing sets rather than ordered tuples).

In order to study the effects of recurston on the complexity of program analysis, a fimte memory machme wtth recurstve calls is defined, as well as two parameter passmg mechamsms whmch extend the power of the language Close upper and lower bounds on the complexity of determmmg whether a program accepts the empty language are gtven for each of the three program models It ts shown that such questtons as acceptance of the empty set, eqmvalence, and so on are retractable even for these relatively simple programs

A simple programming language which corresponds in computational power to the class of generalized sequential machines with final states is defined. It is shown that a variety of questions of practical programming interest about the language are of nondeterministic linear space complexity. Extensions to the language are defined (adding arithmetic and array data structures) and their complexity properties are explored. It is concluded that questions about halting, equivalence, optimization, and so on are intractable even for very simple programming languages.

A new approach to the design of a programming language and its processor is proposed and some of the techniques necessary to realize the design are investigated. The language would have a precisely specified syntax and semantics, with both designed to provide the programmer maximal expressive power and to be as easily understood as possible. The semantics would be based on extremely late binding times, which provide great power to the programmer and are consistent with ease of understanding of the execution process. It would be the responsibility of the processor to implement each program in the most efficient manner consistent with its being correctly executed. Implications of this design philosophy and some of the techniques to be used are discussed in greater detail, focusing particularly on data types and storage allocation.

The computational complexity properties of a hierarchy of classes of subrecursive schemata are investigated. The schemata are derived from the multiple recursive operators of Peter. Concrete complexity measures based on specific computation rules and an underlying random-access stored-program machine (RASP) model are defined and the complexity properties induced by certain structural features are studied. It is shown to be undecidable whether two schemata have identical complexity. Upper bounds for the complexity of schemata are then given in terms of a hierarchy of multiple recursive function classes and lower bounds are given which demonstrate that multiple recursion is a thoroughly unfeasible computational tool in practice. Specifically, it is shown that a pure multiple recursive schema capable of defining nonprimitive recursive functions must have at least exponential complexity in terms of its arguments for all interpretations. We also show it undecidable whether a schema has the minimal complexity of the class to which it belongs. Finally, we raise a number of open questions arising from this work.

It has long been known that most questions of interest about the behavior of programs are recursively undecidable. These questions include whether a program will halt, whether two programs are equivalent, whether one is an optimized form of another, and so on. On the other hand, it is possible to make some or all of these questions decidable by suitably restricting the computational ability of the programming language under consideration. The Loop language of Meyer and Ritchie [MR], for example, has a decidable halting problem, but undecidable equivalence. Restricting the computational ability still further, virtually all of these questions are decidable for finite automata and generalized sequential machines (except that Griffiths [Gri] has shown equivalence undecidable for nondeterministic gsms).A natural question to ask is how hard it is to solve these problems for programming languages for which they are decidable, and it is with this area that we are concerned in this paper. In particular we describe a programming language modeled on current higher-level languages which has exactly the computational power of deterministic finite state transducers with final states, and analyze the space and time required to decide various questions of programming interest about the language. We find that questions about halting, equivalence, and optimization are already intractable for this very simple language. We also study extensions to the language such as simple arithmetic capabilities, arrays, and recursive subroutines with both call-by-value and call-by-name parameter passing mechanisms, some of which extend the capabilities of the language and/or increase the complexity of its decidable problems. In one case, that of recursion with call-by-name, the previously decidable questions are seen to become undecidable.

The study of program schemata and the study of subrecursive programming languages are both concerned with limiting program structure in order to permit a more complete analysis of algorithms while retaining sufficiently rich computing power to allow interesting algorithms. In this paper we combine these approaches by defining classes of subrecursive program schemata and investigating their equivalence problems. Since the languages are all subrecursive, any scheme written in any one of them must halt (as long as we assume the basic functions and predicates are all total). Hence equivalence of schemes is the first question of interest we can ask about these languages.