As an invited contributor to this Festschrift honoring Alain Colmerauer, I feel compelled to give not only an account of his main research contributions, but also of my perspective on the motivations behind them. I hope that this will provide the reader with a glimpse of how a focused, tenacious, rigorous, and inventive mind like Alain's picks research problems and proceeds to solve them. The history of Prolog, the language that remains one of Alain's major accomplishments, is well documented. His paper on the ‘Birth of Prolog,’ co-authored with Philippe Roussel (Colmerauer & Roussel, 1970), is a highly recommended account of the circumstances that led to the development of Prolog. Bob Kowalski (1988) presents his views of the early history of Prolog from the automatic theorem proving perspective. Finally, my own paper on the topic (Cohen, 1988) contains material complementing Alain's and Bob's narratives. Instead of recasting already-available historical material, I have opted to present here a more personal account of Alain's contributions, acknowledging in advance the individual bias inherent in such an accounting of long-past events.

Abstract The paper proposes and describes several tools enabling their user to estimate the efficiency of Pascal or C‐like programs. The approach consists of generating symbolic formulas expressing the efficiency of the programs being analyzed. The formulas are applicable to a variety of compiler‐machine configurations. The actual numeric values of the variables in the symbolic formula are determined using linear programming techniques. The proposed approach reduces considerably the amount of benchmarking needed to analyze programs. Several examples are presented showing the applicability of the tools. The effort necessary to implement them is considerably reduced by the combined usage of Prolog and a symbolic formula manipulation package (Maple).

This paper consists of two parts: the first provides the theoretical foundations for analyzing parallel programs and illustrates how the theory can be applied to estimate the execution time of a class of parallel programs being executed on a MIMD computer. The second part describes a program analysis system, based on the theoretical model, which allows a user to interactively analyze the results of executing (or simulating the execution) of such parallel programs. Several examples illustrating the use of the tool are presented. A novel contribution is the separation (both at the conceptual and the implementation levels) of the machine-independent and the machine-dependent parts of the analysis. This separation enables the users of the system to establish speed-up curves for machines having varying characteristics.

A language is described for specifying program transformations, from which programs can be generated to perform the transformations on sequences of code. The main objective of this work has been to develop a language that would allow the user to quickly and easily specify a wide range of transformations for a variety of programming languages. The rationale for the language constructs is given, as well as the details of an implementation which was prototyped using Prolog. Numerous examples of the language usage are provided.>

The first part of the paper shows that previous theoretical work on the semantics of probabilistic programs (Kozen) and on the correctness of performance annotated programs (Ramshaw) can be used to automate the average-case analysis of simple programs containing assignments, conditionals, and loops. A performance compiler has been developed using this theoretical foundation. The compiler is described, and it is shown that special cases of symbolic simplifications of formulas play a major role in rendering the system usable. The performance compiler generates a system of recurrence equations derived from a given program whose efficiency one wishes to analyze. This generation is always possible, but the problem of solving the resulting equations may be complex. The second part of the paper presents an original method that generalizes the previous approach and is applicable to functional programs that make use of recursion and complex data structures. Several examples are presented, including an analysis of binary tree sort. A key feature of the analysis of such programs is that distributions on complex data structures are represented using attributed probabilistic grammars.

This paper presents the material needed for exposing the reader to the advantages of using Prolog as a language for describing succinctly most of the algorithms needed in prototyping and implementing compilers or producing tools that facilitate this task. The available published material on the subject describes one particular approach in implementing compilers using Prolog. It consists of coupling actions to recursive descent parsers to produce syntax-trees which are subsequently utilized in guiding the generation of assembly language code. Although this remains a worthwhile approach, there is a host of possibilities for Prolog usage in compiler construction. The primary aim of this paper is to demonstrate the use of Prolog in parsing and compiling. A second, but equally important, goal of this paper is to show that Prolog is a labor-saving tool in prototyping and implementing many non-numerical algorithms which arise in compiling, and whose description using Prolog is not available in the literature. The paper discusses the use of unification and nondeterminism in compiler writing as well as means to bypass these (costly) features when they are deemed unnecessary. Topics covered include bottom-up and top-down parsers, syntax-directed translation, grammar properties, parser generation, code generation, and optimizations. Newly proposed features that are useful in compiler construction are also discussed. A knowledge of Prolog is assumed.

A model for the operation of bottom-up parallel parsing using asynchronous processors is proposed. The model is based on an extension of shift-reduce parsers which are able to merge the information they keep on their stacks. The main objective of the paper is to provide estimates of the speedup attainable when using the proposed model. Three programs were written to measure the speedup. The first is a classical simulator which keeps track of the times spent performing the shift, reduce, and merge operations for each processor. The second is a program which generates "typical" strings in a language and simultaneously keeps track of the number of operations needed to parse the generated strings. The third is a program capable of deducing the num-ber of parsing operations by counting the number of selected terminals appearing in an input string. The results, applicable to the paralel parsing of programs written in a Pascal-like language, show how the speedup varies with the number of processors for different ratios of the times to shift, reduce, and merge. Although the speedup falls considerably below that predicted by theory, substantial gains are still attainable by using a fairly large number of parallel processors. With the decreasing costs of processors, parallel parsing and parallel compilation will become increasingly important and should allow considerable gains in speedup.

Let S be the set of all strings of length n generated by a given context-free grammar. A uniform random generator is one which produces strings from S with equal probability. In generating these strings, care must be taken in choosing the disjuncts that form the right-hand side of a grammar rule so that the produced string will have the specified length. Uniform random generators have applications in studying the complexity of parsers, in estimating the average efficiency of theorem provers for the propositional calculus, in establishing a measure of ambiguity of a grammar, etc. Two methods are presented for generating uniform random strings in an unambiguous context-free language. The first method will generate a random string of length n in linear time, but must use a precomputed table of size $O(n^{r + 1} )$, where r is the number of nonterminals in the grammar used to specify the language. The second method precomputes part of the table and calculates the other entries as they are called for. It requires only linear space, but uses $O(n^2 (\log n)^2 )$ time to generate each string. Both methods generate strings by leftmost derivations where the probability that a given production will be used depends on the history of the derivation. It is also shown that, in the special cases of finite-state or linear languages, the generation can be performed in linear time with constant space.

The relative efficiencies of four compactors of varisized cells are estimated by constructing their timeformulas.These are symbolic formulas expressing execution times as functions of the time to perform common, elementary operations such as assignment, addition, subscripting, and loop overhead.By binding the variables to numeric values corresponding to a specific machine one can estimate program execution times without resorting to empirical tests.The first of the compactors (Lisp 2) requires additional storage for pointer readjustment.The second (based on the work of Haddon and Waite) attempts to reduce these storage requirements at the expense of processing time.The last two (Morris' and Jonkers') are recently proposed compactors that require minimal additional storage and that update pointers by first threading them into linear lists.The paper provides unified descriptions of the algorithms and presents curves expressing the relative efficiencies of the compactors when run on a specific machine (PDP-10).It is straightforward to modify the given formulas to estimate compactors' efficiencies when run on other computers.

article Free Access Share on Upper Bounds for Speedup in Parallel Parsing Authors: Jacques Cohen Computer Science Program, Brandeis University, Waltham, MA Computer Science Program, Brandeis University, Waltham, MAView Profile , Timothy Hickey Mathematics Department, University of Chicago, Chicago, IL Mathematics Department, University of Chicago, Chicago, ILView Profile , Joel Katcoff Kaye, Scholer, Fierman, Hays and Handler, 425 Park Avenue, New York, NY Kaye, Scholer, Fierman, Hays and Handler, 425 Park Avenue, New York, NYView Profile Authors Info & Claims Journal of the ACMVolume 29Issue 2April 1982 pp 408–428https://doi.org/10.1145/322307.322316Published:01 April 1982Publication History 26citation413DownloadsMetricsTotal Citations26Total Downloads413Last 12 Months17Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Determining volumes of convex n-dimensional polyhedra defined by a linear system of inequalities is useful in program analysis Two methods for computing these volumes are proposed (1) summing the volumes of stmphces which form the polyhedron, and (2) summing the volumes of (increasingly smaller) paralleleplpeds which can be fit into the polyhedron Assuming that roundoff errors are small, the first method is analytically exact whereas the second one converges to the exact solution at the expense of addmonal computer time Examples of polyhedra whose volumes were computed by programs representing the algorithms are also provided

Program transformation is used to show the correspondence between two known algorithms for translating parenthesized expressions into their polish counterparts. The first algorithm is a syntax-directed translator which produces output upon the recognition of predefined syntactic rules. The second one, suggested by Dijkstra, is of empirical nature: it performs the translation by simulating the operation of a railyard shunt. The second algorithm is more efficient than the first, but less general. This work enables one 1) to assert the correctness of the empirical algorithm, 2) to compare the relative efficiencies of the two algorithms, and 3) to gain insight into the circumstances in which syntax-directed translation may be improved by generalizing the ideas involved in Dijkstra's algorithm.

Time formulas are symbolic formulas which express the execution time of a program as a function of its input data and of variables representing the time to execute individual operations (e.g., push, pop, transfer, etc.). It is shown that in many cases the time formulas for recursive descent parsers may be generated automatically by a simple inspection of the parser code. These time formulas are instrumental in estimating the gains attained by various types of optimizations. Several of these optimizations are presented and their efficiency gains are estimated. A parser for a simple programming language is generated, optimized, and evaluated using the proposed techniques.

Abstract This paper describes a language for studying the behaviour of programs, based upon the data collected while these programs are executed by a computer. Besides being a useful tool in debugging, the language is also valuable in the experimental evaluation of the complexity of algorithms, in studying the interdependence of conditionals in a program and in determining the feasibility of transporting programs from one machine to another. The program one wishes to analyse is written in an Algol 60‐like language; when the program is executed it automatically stores, in a data base, the information needed to answer general questions about computational events which occurred during execution. This information consists (basically) of the list of labels passed while the program is being executed, and the current values of the variables. Since the list of labels is describable by regular expressions, these expressions can also be used to identify specific subparts of the list and therefore allow access to the values of the variables. This constitutes the basis for the design of the inquiry language. The user's questions are automatically answered by a processor which inspects the previously generated data base. The paper also presents examples of the use of the language and describes the implementation of its processor.

An interactive computer program which has some capability for solving systems of finite difference equations is described.Although this capability is limited to linear systems, a knowledgeable user can, with the help of the program, solve a wider class of equations.Over 100 examples, covering a variety of cases, have been solved by using the program.Some representative examples are presented.Additional features which would improve the versatility of the program are also discussed.

Abstract The author describes some of his experience gained by working in the area of syntax‐directed compilers and parser generating systems during the past ten years. His most recent work in this area was designing and supervising the implementation of a conversational parser generator which has been operational for about two years. The paper describes this generator, its implementation, usage and the characteristics which make it practical to use. The author's main conclusion is that althouth it is relatively easy to implement nuclei of parser generating systems which are of educational value, the implementation of a practical system requires a major programming effort.

The ordering of grammar rules in the syntactical analysis of context-free languages (as utilized in syntax-directed compilers) plays an important role in the parsing efficiency. No theoretical treatment of the optimum ordering is currently available. This paper presents a practical approach to this problem whereby reordering of rules is adjusted to optimize the analysis of input string samples.