2,199 papers · page 109 of 110
A new algorithm for global flow analysis on reducible graphs is presented. The algorithm is shown to treat a very general class of function spaces. For a graph of e edges, the algorithm has a worst case time bound of 0(e log2e) function operations. In programming terms, the numbe…
Work on PLANNER-73 and actors has led to the development of a basis for semantics of programming languages. Its value in describing programs with side-effects, parallelism, and synchronization is discussed. Formal definitions are written and explained for sequences, cells, and a …
This paper extends the relational algebra of data bases, presented by Codd [4] and others, in four areas. The first is the use of selector names to remove order dependencies from the columns of a relation. This use of selector names enables us to define a more general class of op…
In this paper we derive upper bounds on the complexity of LR(k) testing both when k is considered to be a fixed integer and also when k is considered to be a parameter of the problem. In the latter case, we show that the lower bounds on the running time of such algorithms depend …
It is shown that both the upper and the lower bounds on the time complexity of the circularity test for Knuth's attribute grammars are exponential functions of the size of the grammar description. This result implies the "intractability" of the circularity test in the sense that …
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, …
A new approach to global program data flow analysis which constructs a for the control flow graph is discussed and a simple algorithm which uses a node listing to determine the live variables in a program is presented. This algorithm combined with a fast node listing constructor …
Petri nets are used to define a path and process notation which is more general in its ability to express synchronization than previous path notations. The Petri net classes corresponding to the path notation prove to be interesting in their own right and have demonstrable proper…
A class of program schemas with concurrency is defined as a natural extension of the standard notion of sequential flow-chart-like schemas. The question is considered as to whether such a program schema may reach a premature termination (or "hangup") for some interpretation. It i…
A framework for validating surface properties of programming language constructs, composed of proof rules (akin to those of Hoare) and supporting hypotheses, is constructed using the mathematical semantics of Scott and Strachey. The following approach to language design is then c…
When proving that a system of processes has a given property it is often convenient to assume that a routine is uninterruptible, i.e. that the routine cannot be interleaved with the rest of the system. Here sufficient conditions are obtained to show that the assumption that a rou…
This paper describes a system being developed to bridge the gap between an application program and a user inexperienced in the ways of computers. The user explores the characteristics of the available programs by a natural language dialogue with the system. The dialogue is suppor…
Some social aspects of programming are illuminated through analogies with similar aspects of mathematics and natural languages. The split between pure and applied mathematics is found similarly in programming. The development of natural languages toward flexionless, word-order ba…
SETL is a set-theoretically oriented language of very high level whose repertoire of semantic objects includes finite sets, ordered n-tuples, and sets of ordered n-tuples useable as mappings. This paper sets forth techniques for the logical analysis and optimization of SETL progr…
NO ABSTRACT SUPPLIED
Article Free Access Share on An algebraic model for string patterns Author: Glenn F. Stewart I.P. Sharp Associates Limited, Toronto, Ontario, Canada I.P. Sharp Associates Limited, Toronto, Ontario, CanadaView Profile Authors Info & Claims POPL '75: Proceedings of the 2nd ACM SIGA…
This paper contains a suggestion for a calculus for constructing 'flowchartable' algorithms. The calculus is a generalization of an Algol-like calculus, and hence maintains some discipline over the algorithms constructible with it.The essence of the great 'go to' debate seems to …
We consider methods of describing the syntax of programming languages in ways that are more flexible and natural than conventional BNF descriptions. These methods involve the use of ambiguous context-free grammars together with rules to resolve syntactic ambiguities. We show how …
This paper proposes axioms to define a sequence of language-classes; the most general is that of "programming language", the most restricted has some simple and attractive properties. Here "language" is used in its traditional sense as referring to a set of interpreted expression…
In order to define the semantics of PL/I in a form which is both precise and readable, a method of definition has been developed which employs an abstract machine operating on tree-structured data. The classes of trees involved are defined by formal grammars, while the algorithms…