Search

Discusses the use of decision tables in solving large scale programming problems. Construction of an application program through the selection of certain source statements from a predefined file; Ideas behind the other historical approaches of solving programming problems.

Provides algorithms for implementing discrete patterns in SNOBOL4. Applications of discrete recognition systems; Use of the theory of formal languages as basis for the formal study of discrete recognition processes; Properties of SNOBOL4's recognition system.

Studies the use of grammatical inference for designing programming languages. Steps in designing a new language; Methods for the definition of meaning or semantics; Issues to be addressed with the formal definition of a programming language.

Linguistic mechanisms which can be used to protect one subprogram from another's malfunctioning are described. Function-producing functions and various type-tagging schemes are considered. An attempt is made to distinguish between access limitation and authentication. [ABSTRACT FROM AUTHOR]

Most current programming languages treat computation over different classes of objects (e.g. numbers, strings, labels and functions). For correct compilation and execution, the following question then arises: is a program properly constructed so that its operations and operands are compatible? The activity of answering this question is usually called type checking. This paper attempts to isolate the notion of type checking and presents a partial solution to the type checking problem based on the notions of abstraction and application of functions. In particular, a program is mapped into an expression within a decideable subset of the λ-calculus, which characterizes the type relations within the program and eliminates all other information The determination of the type-wise correctness or incorrectness of the program is resolved by reducing its corresponding λ-calculus expression to one of two normal forms, the constant "correct" for a type-wise correct program or the constant "error." An application to type checking in Algol 60 is made, and the attendant problems faced for any notion of type checking are discussed. [ABSTRACT FROM AUTHOR]

The constructs of a simple programming language are introduced and described informally in terms of values and side-effects. A translator is defined which translates the language into flowcharts for a simple machine. The action of the machine in executing a flowchart is defined. A proof is constructed that the effect of translating and executing any program can be expressed solely in terms of the value and side-effect of the program. During the course of constructing the proof, formal definitions of the concepts of value and side-effect are derived in order to make the proof rigorous. Correctness of the implementation involves checking that the definitions derived in the step above are an acceptable formalization of the informal description given in the first step. [ABSTRACT FROM AUTHOR]

A new datatype, called a block, has been implemented for SNOBOL4. A block is a three-dimensional aggregate of characters in the form of a right parallelepiped, best thought of as a three-dimensional extension to a string. (The third dimension is used for overstriking.) Blocks may he printed, concatenated in any of three dimensions, and merged on the basis of program-defined connection points. Some blocks adapt In size and shape to their environment. Blocks and their operations are mainly used for composing printable output. A variety of graphical problems (including flowcharting, bargraphs, logic diagrams, mathematical-equation formation, and text justification and preparation) have been programmed on a printer in what appears to be an easy and natural way. In addition to these somewhat specialized applications, blocks appear to be a good general purpose device-independent output formation mechanism especially suitable for nonnumerical work. The concept of a block is largely language independent. That is, blocks require little in the way of specialized syntax and could readily be absorbed into the external structure of most programming languages. [ABSTRACT FROM AUTHOR]

A modified version of Bell's Boolean matrix method for the computation of linear precedence functions associated with a conflict-free matrix of precedence relations is given. This algorithm not only detects when the precedence functions do not exist, but also provides an indication of why they do not exist, so that corrective action can he taken if possible. Necessary and sufficient conditions for the existence of precedence functions are given. The use of Boolean matrices to prove the existence of precedence functions associated with classes of conflict-free grammars is illustrated through an example. [ABSTRACT FROM AUTHOR]

The system described herein employs the block concept, and that of global and local variables, in addition to the methods applied in most LISP systems. Also, a new means of list representation is used: "local sequential'' for lists created during compilation, and "block level sequential" for those created dynamically. A new garbage collection algorithm has been introduced to make lists as compact as possible; partial garbage collection is performed after each block exit instead of total garbage collection when storage is exhausted. The algorithm does not use the customary flagging procedure. This combination of features has eliminated the need for a free list, and effectively minimizes the number of pages used at any moment. [ABSTRACT FROM AUTHOR]

Presents a notation for describing the semantics of data structures. Implementation facility which could be a part of a programming language; Expression of the semantics of an algorithm; Efficiency of the structures.

A proof is given of the correctness of the algorithm "Find." First, an informal description is given of the purpose of the program and the method used. A systematic technique is described for constucting the program proof during the process of coding it, in such a way as to prevent the intrusion of logical errors. The proof of termination is treated as a separate exercise. Finally, some conclusions relating to general programming methodology are drawn. [ABSTRACT FROM AUTHOR]

Describes a universal two-dimensional data plotting software system, called AMESPLOT, whose syntax is based on the ordering of subroutine modules. Outline of the elements common to all types of data plots; Key features of data plotting; Structuring of plots from multiple, independent, self-contained subplots; Utility software of AMESPLOT.

Describes a dump technique for programs written in ALGOL 60. Intelligible analysis of an unsuccessful computation process in terms of the original source program; Compromises between the completeness of the analysis and the cost in computer time and programming effort; Design of the ALCOR Illinois 7090/7094 Post Mortem Dump.

Describes some techniques used in the ALGOL compiler written by the ALCOR group for the IBM 7090. Compiler writing; Organizational details of the compiler; Timing estimates.

Describes PL/C, a diagnostic compiler for a dialect for PL/I programming language. Design objective and implementation; Use of established load-and-go compilation strategies to achieve compilation speed of 10-20,000 source statements per minute.

A method of analyzing statements in a programming language which can tolerate a considerable inaccuracy in their specification is proposed. This method involves principles at present mainly confined to studies in the area of artificial intelligence such as feature extraction, approximate tree matching, and strategy improvement by feedback from the matching process. A pilot program incorporating the principles is described and preliminary operating results are presented. A final section surveys further principles which are currently being investigated. [ABSTRACT FROM AUTHOR]

This paper discusses the multiplication of conformable sequences of row vectors, column vectors, and square matrices. The minimum time required to evaluate such products on ordinary serial computers as well as parallel computers is discussed. Algorithms are presented which properly parse suck matrix sequences subject to the constraints of the machine organization. [ABSTRACT FROM AUTHOR]

A method of incremental compilation is presented which applies especially to programming languages in which statements can be nested (such as Algol and PL/I) The method permits editing of the source language using a general purpose text editor, and incremental processing of changes without frequent recompilation of entire routines. The essential points of the method are: (1) the syntax of the language is restricted insofar as which constructs may occur on lines; (2) an internal data structure (called the skeleton) is maintained to represent the statement structure; (3) the recompilation is partially batched in the sense that recompilation of modified lines does not occur until the last of a set of editing commands has been received; and (4) the parsing and compilation are factored into two parts, that done on individual lines and that done globally to handle the relationships between the lines. [ABSTRACT FROM AUTHOR]

The paper describes a scheme for symbolic manipulation of index expressions which arise as a by-product of the symbolic manipulation of expressions in the matrix calculi described by the authors in a previous paper. This scheme attempts program optimization by transforming the original algorithm rather than the machine code. The goal is to automatically generate code for handling the tedious address calculations necessitated by complicated data structures. The paper is therefore preoccupied with "indexing by position." The relationship of "indexing by name" and "indexing by position" is discussed. [ABSTRACT FROM AUTHOR]

The classical process of partitioning an array into subarrays is extended to a more useful array language operation. Various modes of partitioning are defined for different types of arrays, so that subarrays may vary over the original array in a nearly arbitrary manner. These definitions are motivated with several realistic examples to illustrate the value of partitioning for array languages. Of general interest Is the data structure for partitioning. This consists of dynamic tree structures which are used to derive and maintain the array control information. These are described in sufficient detail to be of value In the design of other array languages. The description presented in this paper is Implemented in a new array language, OL/2, currently under development at the University of lllinois. [ABSTRACT FROM AUTHOR]

An elementary outline of the theorem-proving approach to automatic program synthesis Is given, without dwelling on technical details. The method Is Illustrated by the automatic construction of both recursive and Iterative programs operating on natural numbers, lists, ant frees. In order to construct a program satisfying certain specifications, a theorem induced by those specifications is proved, and the desired program Is extracted from the proof. The same technique is applied to transform recursively defined functions into iterative programs, frequently with a major gain in efficiency. It is emphasized that hi order to construct a program with loops or with recursion, the principle of mathematical Induction must be applied. The relation between the version of the induction rule used and the form of the program constructed is explored in some detail. [ABSTRACT FROM AUTHOR]

Develops a technique for generating almost optimal Floyd-Evans productions given a precedence grammar in programming languages. Graph formulation used for the problem of merging productions; Validity of the technique for weak precedence grammars.

This article focuses on contributions of Edsger Wybe Dijkstra, a noted computer scientist, in science and industry of computing. Dijkstra was the 1972 recipient of the ACM Turing Award, often viewed as the Nobel Prize for computing. He was a member of the Netherlands Royal Academy of Arts and Sciences, a member of the American Academy of Arts and Sciences, and a distinguished fellow of the British Computer Society. He received the 1974 AFIPS Harry Goode Memorial Award, the 1982 IEEE Computer Pioneer Award, the 1989 ACM SIGCSE Award for Outstanding Contributions to Computer Science Education, and the ACM PODC 2002 Influential Paper Award. He received two honorary doctorates, from the Queen's University of Belfast, Northern Ireland in 1976, and Athens University in Athens, Greece 2001. In 2002, the C&C Foundation of Japan recognized Dijkstra for his pioneering contributions to the establishment of the scientific basis for computer software through creative research in basic software theory, algorithm theory, structured programming, and semaphores.

A language, BLISS, is described. This language is designed so as to be especially suitable for use in writing production software systems for a specific machine (the PDP-10): compilers, operating systems, etc. Prime design goals of the design are the ability to produce highly efficient object code, to allow access to all relevant hardware features of the host machine, and to provide a rational means by which to cope with the evolutionary nature of systems programs. A major feature which contributes to the realization of these goals is a mechanism permitting the definition of the representation of all data structures in terms of the access algorithm for elements of the structure. [ABSTRACT FROM AUTHOR]