Search

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]

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 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 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]

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 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.

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]