bluuebunny/crossref_metadata_2025_split huggingface dataset:
Programming without pointer variables
Authors: Kieburtz Richard B. 
Published: November 2005

The presence of pointer variables in high level programming languages constitutes an artifact originally introduced to support the representation of recursive data structures. Programming practice has come to rely on pointer variables for their originally intended use, and for several others as well. Their use adds to the complexity of stating algorithms by forcing one to conceptualize data representations in which storage addressing is made manifest. In addition, the use of pointer variables allows one to refer to a common data object by a multiplicity of names, a phenomenon we call the alias variable problem, Alias variables make the verification of program behavior substanially more difficult, and frustrate the goals of modular decomposition.
In this paper, we consider alternatives to the use of pointer variables in programming. One of these alternatives is the inclusion of a class of data abstractions based on recursively defined data types. The representational power of the proposed data types is characterized formally, and some issues of implementation and efficiency of programs are discussed.
Correctness of data representations (Extended Abstract)
Authors: Berry D. M. , Erlich Z. , Lucena C. J. 
Published: November 2005

At present, there is considerable debate whether, in light of what is being learned about construction of reliable software, pointers are desirable in high level programming languages. One side [Hoa73, Hoa75] maintains that
1) Pointers are like the goto in that they are an invitation to create spaghetti in one's program [Hoa75].
2) In some languages, e.g., PL/1 [Wlk71], the use of pointers can lead to serious type violations, for example, the compiler believes that a given pointer will be pointing to an integer when in fact, it will be pointing to a real.
3) The indiscriminate use of pointers may confound the attempts of hardware pipelining and use of cache memory to speed up computations [Hoa73, Hoa75].
4) A pointer may be left dangling, that is, a pointer may point to a variable or other datum which has been deallocated [Bry71, CDMPS73, Bry74].
DIAM II
Authors: Senko Michael E. 
Published: November 2005

The notion of dividing complex problems into hierarchic levels of abstraction has a long history. Recently this approach under the name, structured programming, has been used in a pragmatic way to simplify the structure of procedural programs. The notion has also been used in the data base area - notable early papers include those of Madnick (1) and Meltzer (2). In these early papers, level structures (for example, involving logical and physical levels) were also relatively pragmatic creations.
One new aspect of the DIAM I architecture (3) was that it defined a detailed, relatively formal basis for four levels of abstraction and the mappings between these levels. Each level had a small set of primitive generalized building blocks, each with its own small permanent set of parameters. By specifying values for these parameters, the user could define essentially any reasonable data structure and file organization he wished for his stored information.
SCRATCHPAD
Authors: Griesmer James H. , Jenks Richard D. 
Published: November 2005

SCRATCHPAD is an interactive system for algebraic manipulation available under the CP/CMS time-sharing system at Yorktown Heights. It features an extensible declarative language for the interactive formulation of symbolic computations. The system is a large and complex body of LISP programs incorporating significant portions of other symbolic systems.
Here we present a capsule view of SCRATCHPAD, its language and its capabilities. This is followed by an example which illustrates its use in an application involving the solution of an integral equation.
Babel, an application of extensible compilers
Authors: Scowen R. S. 
Published: November 2005

The normal approach in providing an extensible programming language seems to be to design and implement a base language which has facilities enabling the programmer to define and use extensions. This paper discusses a solution using an alternative approach in which extensions are made by changing the compiler. Of course, in theory, any compiler can be altered (it is only a computer program); in practice it is probably not so easy since difficulties will arise if the compiler has been designed for one fixed standard language on one particular computer. If a compiler is to be altered, it must possess various properties; there should be no danger of accidentally invalidating an existing program, and it must be clear what changes are required to make a desired extension. It is also desirable that only a small number of changes should be required to make an extension.
The method of writing compilers which is described below satisfies these conditions and has been adopted in three different applications:-
(1) Babel, a conventional high level programming language.
(2) SOAP, a program which documents and edits an ALGOL 60 program.
(3) PL516, a high level assembly language for the Honeywell DDP516 computer.
A short presentation of the main features of AEPL - an extensible programming language
Authors: Katzenelson J. , Milgrom E. 
Published: November 2005

AEPL is a programming system designed as a tool for the implementation of problem-oriented languages. It is based on a small number of simple but powerful concepts described briefly below.
The AEPL system is not yet implemented at the present time; it has been used, however, to define - on paper - a language for the manipulation of graphs. The extensibility of the system stems from the ability to create new data types and from the ability to modify some of the language structures dynamically (syntax and associated semantic as well as some control structures).
Syntax translation with context macros or macros without arguments
Authors: Grant Charles A. 
Published: November 2005

A conceptually language independent macro facility with the following properties is described here:
1)Each macro gathers its own arguments from the text in which the call is embedded (the context).
2) A macro may modify its context an arbitrary distance from the actual string which represents the call.
3) A macro may specify the precise point from which scanning is to continue after the macro returns.
The objective of this work is to define a simple user facility for conveniently and powerfully modifying the syntax of programming languages.
A syntax macro processor
Authors: Wodon P. L. 
Published: November 2005

Since syntax macros are not new, a few words of justification for still another experiment are necessary. The origin is the following question: “In which language to program the software of electronic telephone exchanges?” Roughly, this is the known problem of choosing a language for software programming, i.e. a language which should be “high-level” to ensure reliability and hardware-oriented to ensure efficiency. Telephone exchanges however, have particularities of their own, two of which are worth mentioning. Firstly, no two exchanges are exactly alike, and this rules out plain assembly code. Secondly, the exchange builders know what they want but seem to have difficulties in expressing it in terms of algorithms. This means that designing at once another special purpose language was out of the question.
Something flexible was needed. To provide for an immediately usable programming tool, a GPM-like macro generator [4] was put into service and is being used for producing software.
Overview of the syntax processor generator SYNPROC
Authors: Fernandez A. , Heliard J. C. , Ichbiah J. D. 
Published: November 2005

SYNPROC is a facility for generating syntactic analyzers, implemented on the CII 10070 computer system.
It uses a technique for automatic generation of Floyd-Evans productions which is described in [4]. It also uses bounded-context [3] resolution of identical right-hand sides of syntactic rules. Thus, space optimized analyzers are obtained mechanically for bounded-context (m,1) grammars.
The facility has other practical features which are useful for the construction of compilers for usual programming languages.
Parallel non-deterministic bottom-up parsing
Authors: Lang Bernard 
Published: November 2005

The development of translator writing systems and extensible languages has led to a simultaneous development of more efficient and general syntax analyzers, usually for context-free (CF) syntax. Our paper describes a type of parser that can be used with reasonable efficiency for any CF grammar, even one which is ambiguous.
Our parser, like most others, is based on the pushdown automaton model, and thus its generality requires it to be non-deterministic (in the automata theoretic sense). An actual implementation of a non-deterministic automaton requires that we explore every computational path that could be followed by the theoretical automaton. This can be done serially [5], following successively every computational path whenever a choice occurs. It leads to the algorithms described in [1], whose time bounds can be exponential functions of the length of the string to be parsed.
We can also use a parallel implementation which consists in following “simultaneously” all the possible computational paths whenever a non-deterministic choice occurs. Then we can merge paths that have ceased to be different after a certain point. Those mergings reduce drastically the amount of computation. The best known example is the top-down algorithm described in [2]. The algorithm we describe in the first part of our paper is a basic bottom-up parser, similar to [2] in its organization. Both parsers can be shown to work within time bounds which are at most the cube of the length of the input string, and are often a linear function of it. The space bounds are at most the square of that length.
The second part of our paper deals with the optimization of the basic parallel bottom-up algorithm, using the properties of weak precedence relations [3]. The various optimization techniques further reduce the amount of computation required and cause frequent occurrence of a “sparse determinism” phenomenon which allows determination of part of the parse-tree before the non-deterministic analysis is ended. These optimizations also considerably lessen the space requirements. Full details can be found in [6].
The parser is easy to generate for any CF grammar, requiring only the computation of precedence tables. It is slower than most deterministic parsers (on the order of ten times); but all examples we have tried showed it to be more efficient than any other parser having the same generality. We consider that the inefficiency of our parser is reasonable as we intend it as a research tool for the language designer rather than as a part of an industrial compiler.
Languages designers, or extensible languages users, are often more preoccupied with semantics than syntax and fix the syntax of their language in a “nice” form only when they have found what kind of semantics it is to represent. So they can easily come up with ambiguous syntax [4]. Our parser parses ambiguous languages and detects ambiguities in programs, thus enabling the programmer to eliminate them.
An alternative approach to macro processing
Authors: Hammer Michael 
Published: November 2005

This paper presents the basic principles of, and the motivation for, an alternative method of processing syntax macros. The inspiration for this work derives from some obvious shortcomings and inefficiencies in conventional macro processing schemes. However, our primary interest is not in designing a faster macro processor; rather it lies in isolating the underlying ideas of syntax macros, realizing their implications, and producing a clean and economical scheme based on these principles.
The compiler model in terms of which we shall couch our discussions is a very familiar one, namely that of the two-pass compilation process. The first pass consists of syntactic and semantic analysis, and converts a source language program into an intermediate language (computation tree) form, which represents the meaning of the program. The second pass is then either an object code selector or an interpreter.
Extensibility in Simula 67
Authors: Ichbiah Jean D. 
Published: November 2005

Simula 67 is a general purpose language developed at the Norwegian Computing Center. It evolved from an earlier simultation language called Simula 1 [1]
Dahl and Nygaard however, realized that the problems that had to be solved for the implementation of a simulation language, namely the handling of complex data structures and of quasi-parallelism, were general problems. The language Simula 67 [2,3] was therefore defined as a general purpose language with a mechanism for extensions. The simulation capabilities are thus not defined in the base language Simula 67 but are rather defined by extension. This shows clearly how the language Simula 67, hereafter called Simula, is related to the idea of extensibility.
The control structure facilities of ECL
Authors: Prenner Charles J. 
Published: November 2005

ECL is a programming language system currently under development at Harvard University. A general description of the system is given in a companion paper [1]. This paper will describe some of the control structure facilities available in ECL - a complete description will appear as part of the author's Ph.D. thesis.
Most existing programming languages allow for only one path of control. The programmer is presented with an environment in which he may use conditional statements, iteration statements and nested function calls (perhaps called recursively) to modify the flow of control through his program but it is not usually possible to either suspend execution of the current program (control path) and start up another or to set up another control path to execute in parallel with the current one. EL1, as originally proposed in [2], allows for only one path of control. ECL, however, allows for the creation and manipulation of multiple paths of control. These paths may execute in parallel, or act as coroutines or in any other relation desirable. Since the number of paths which can be created to execute in parallel may be greater than the number of processors available on a given machine, some sort of path scheduling must be done. The path scheduler is written in EL1 and is available for redefinition by the programmer.
Conversational systems programming by incremental extension of system configuration
Authors: Krutar Rudolph A. 
Published: November 2005

An engineer needs tools for his trade and a laboratory or toolshop in which to store them, sharpen them, and use them. A software engineer needs programming tools and a software laboratory. Input/output routines, lexical analyzers, lexicons, storage allocators, temporary files (stacks queues, sorting files), debugging aids, etc., all are useful tools in any software factory or research house. To set up a shop one needs a program library (with librarian), a linkage convention, and a set of interface languages. In my shop (1) each program in the library must have a calling sequence; (2) the linkage convention is a peculiar coroutine linkage (with each program issuing standard subroutine calls on up to k0 virtual facilities (currently k0=8)); and (3) the interface languages are very simple and few in number. An execution instance of a program is a 'process' and may be 'active' or 'suspended'. An output stream of one process may be specified as an input stream of another.
Those who build systems such as mine (including myself) are often disinterested in providing simple but useful services like formatted output, program libraries, listing controls, etc. Furthermore we must build some facilities which are not really relevant to our goals (e.g. input-output routines, lexical analyzers, recursion mechanisms, storage allocators, syntax recognizers, and so on). If we try to use facilities constructed for other systems, we must steal copies of the source code and modify them extensively ([Ki 69]). Such facilities are almost always superfluous to our goals and should therefore be external to our systems. This externalization is surprisingly easy.
A hierarchy of high order languages for systems programming
Authors: Lyle Don M. 
Published: November 2005

The programming of systems software in higher level languages has been a subject of much interest and debate. At Burroughs the debatability of the issue has long since ceased to exist since both the operating system and the compilers for the B5500 were successfully implemented in variants of ALGOL 60. The low manpower requirements and the ease of maintenance and modification have caused all concerned with the project to accept this approach without question. This technique has the added benefit of producing more reliable software due to the greatly reduced number of lines of code required.
When the decision to produce a successor to the B5500 was made, there was no controversy over the use of high level languages but considerable debate over how high a level the languages should be. B5500 ESPOL (Executive System Problem Oriented Language), the operating system implementation language, contained many “unsafe” constructs, for example, the ability to directly address memory through a subscripted reference to an array known, strangely enough, as MEMORY. This allowed coding errors to produce undesirable side effects on the system. Examination of the algorithms used in most operating systems indicated that surprisingly few routines actually require such “unsafe” tools leading to the conclusion that the proper approach to the coding of the overall systems software might be a hierarchical set of systems programming languages with varying degrees of “safety.”
An experience with a Prolog-based object-oriented language
Authors: Fukunaga Koichi , Hirose Shin-ichi 
Published: November 2005

This paper presents an experience with a programming language SPOOL which is based on the combination of object-oriented programming and logic programming. This language inherits the capability of knowledge base organization from object-oriented programming and its expressive power from logic programming.
The experience of the application of SPOOL to the program annotation system showed that this combination was quite useful to formalize domain knowledge into declarative data types and make them reusable in different contexts. It also showed the need for further study such as better linguistic support to exploit the full power of this combination.
The history of FORTRAN I, II, and III
Authors: Backus John 
Published: November 2005

Before 1954 almost all programming was done in machine language or assembly language. Programmers rightly regarded their work as a complex, creative art that required human inventiveness to produce an efficient program. Much of their effort was devoted to overcoming the difficulties created by the computers of that era: the lack of index registers, the lack of built- in floating point operations, restricted instruction sets (which might have AND but not OR, for example), and primitive input- output arrangements. Given the nature of computers, the services which “automatic programming” performed for the programmer were concerned with overcoming the machine's shortcomings. Thus the primary concern of some “automatic programming” systems was to allow the use of symbolic addresses and decimal numbers (e.g., the MIDAC Input Translation Program [Brown and Carr 1954]).
But most of the larger “automatic. Programming” systems (with the exception of Laning and Zierler's algebraic system [Laning and Zierler 1954] and the A-2 compiler [Remington Rand 1953; Moser 1954]) simply provided a synthetic “computer” with an order code different from that of the real machine. This synthetic computer usually had floating point instructions and index registers and had improved input-output commands; it was therefore much easier to program than its real counterpart.
The early history and characteristics of PL/I
Authors: Radin George 
Published: November 2005

Source material for a written history of PL/I has been preserved and is available in dozens of cartons, each packed with memos, evaluations, language control logs, etc. A remembered history of PL/I is retrievable by listening to as many people, each of whom was deeply involved in one aspect of its progress. This paper is an attempt to gather together and evaluate what I and some associates could read and recall in a few months. There is enough material left for several dissertations.
The exercise is important, I think, not only because of the importance of PL/I, but because of the breadth of its subject matter. Since PL/I took as its scope of applicability virtually all of programming, the dialogues about its various parts encompass a minor history of computer science in the middle sixties. There are debates among numerical analysts about arithmetic, among language experts about syntax, name scope, block structure, etc., among systems programmers about multi-tasking, exception handling, I/O, and more.
Systematic protection mechanism design
Authors: Jones Douglas W. 
Published: November 2005

This work describes an attempt to systematically design a hardware resource protection mechanism when given the requirements of a particular language as a target. The design process is formalized as a structured walk through the multidimensional computer design space towards a hypothetical class of optimal machines. Each step in this walk involves a change in the distribution of work between the compiler and run-time system but no change in the source language semantics. The starting point for this walk is the result of a semantic analysis of the language to be implemented; typically, this produces a very high level machine where the compiler, if any, is trivial. The walk ends when no changes result in a net improvement. This does not guarantee that the result is even locally optimal, since the changes tried depend on the ingenuity and persistence of the designer.
This design approach has been used to arrive at a practical, general purpose protection mechanism oriented towards the needs of the Ada language (preliminary version). This architecture was evaluated by comparing it with the PDP-11/45. For the purpose of this comparison, the protection mechanism was incorporated into a partially specified PDP-11 like instruction set. The number of bits making up the processor state and the number of operations involved in address computation were evaluated. On this basis, the result appears to be competitive and worth further investigation.
Supporting ada memory management in the iAPX-432
Authors: Pollack Fred J. , Cox George W. , Hammerstrom Dan W. , Kahn Kevin C. , Lai Konrad K. , Rattner Justin R. 
Published: November 2005

In this paper, we describe how the memory management mechanisms of the Intel iAPX-432 are used to implement the visibility rules of Ada. At any point in the execution of an Ada® program on the 432, the program has a protected address space that corresponds exactly to the program's accessibility at the corresponding point in the program's source. This close match of architecture and language did not occur because the 432 was designed to execute Ada—it was not. Rather, both Ada and the 432 are the result of very similar design goals.
To illustrate this point, we compare, in their support for Ada, the memory management mechanisms of the 432 to those of traditional computers. The most notable differences occur in heap-space management and multitasking. With respect to the former, we describe a degree of hardware/software cooperation that is not typical of other systems. In the latter area, we show how Ada's view of sharing is the same as the 432, but differs totally from the sharing permitted by traditional systems. A description of these differences provide some insight into the problems of implementing an Ada compiler for a traditional architecture.