bluuebunny/crossref_metadata_2025_split huggingface dataset:
Inductive methods for proving properties of programs
Authors: Manna Zohar , Ness Stephen , Vuillemin Jean 
Published: November 2005

We have two main purposes in this paper. First, we clarify and extend known results about computation of recursive programs, emphasizing the difference between the theoretical and practical approaches. Secondly, we present and examine various known methods for proving properties of recursive programs. We discuss in detail two powerful inductive methods, computational induction and structural induction, illustrating their applications by various examples. We also briefly discuss some other related methods.
Our aim in this work is to introduce inductive methods to as wide a class of readers as possible and to demonstrate their power as practical techniques. We ask the forgiveness of our more theoretical-minded colleagues for our occasional choice of clarity over precision.
Decision problems in computational models
Authors: Paterson Michael S. 
Published: November 2005

Some of the assertions about programs which we might be interested in proving are concerned with correctness, equivalence, accessibility of subroutines and guarantees of termination. We should like to develop techniques for determining such properties efficiently and intelligently wherever possible. Though theory tells us that for a realistic programming language almost any interesting property of the behaviour is effectively undecidable, this situation may not be intolerable in practice. An unsolvability result just gives us warning that we may not be able to solve all of the problems we are presented with, and that some of the ones we can solve will be very hard.
In such circumstances it is very reasonable to try and determine necessary or sufficient conditions on programs for our techniques to be assured of success; however, in this paper we shall discuss a more qualitative, indirect, approach. We consider a range of more or less simplified computer models, chosen judiciously to exemplify some particular feature or features of computation. A demonstration of unsolvability in such a model reveals more accurately those sources which can contribute to unsolvability in a more complicated structure. On the other hand a decision procedure may illustrate a technique of practical use. It is our thesis that this kind of strategy of exploration can and will yield insight and practical advances in the theory of computation. Provided that the model retains some practical relevance, the dividends are the greater the nearer the decision problem lies to the frontier between solvability and unsolvability.
On a laboratory for the study of automating programming
Authors: Cheatham T. E. , Wegbreit Ben 
Published: November 2005

At the present time there is considerable interest in the general question of “automating programming:” there are a number of people actively doing research concerned with various aspects of the question and even a few projects exploring various practical issues via experimental implementations. The area encompassed by “automating programming” is a very broad one, particularly if one understands “programming” to include the entire spectrum of activities concerned with producing algorithms which are correct and effective in terms of certain design specifications. It is therefore to be expected that comparison of various techniques and integration of those techniques and the experimental facilities developed in a variety of institutions will be difficult and expensive unless there is some coordinated effort to provide a common framework to support such activities. We would note that at present it is relatively expensive just to construct sufficient programs to permit the investigation of and experimentation with some proposed technique of program automation; because of this many studies in the general area of programming automation are primarily “paper studies”.
It is the purpose of this note to provide an overview of the project currently under way at Harvard's Center for Research in Computing Technology, directed toward the implementation of a laboratory for the study of programming automation techniques. A more detailed discussion of our approach is provided in [1]. In the four sections which follow we will discuss briefly our view of the use of a program automation laboratory, the basis for and basic components of the facility currently being implemented, and finally, suggest that there are a variety of research areas which are strongly related to the question of automating programming in which the laboratory might be employed as a research tool.
The implementation of ALGOL N
Authors: Suzuki N. , Fujisaki T. , Kakehi K. , Wada E. , Simauti T. 
Published: November 2005

Recent expansion of new techniques invented a great number of application areas in which computers are used in the ways which have not been dreamed of a decade ago. Since the usage of computers was controlled by programs stored in computers, the production of programs has been increasing in enormous rate. In order to ease programming efforts, many programming devices have been invented and organized to become an operating system and a programming system. Nowadays the operating system serves as an interface between the hardware and the programming system or a programmer. They are designed as a multipurpose program so as to be able to handle any usage of the computer. The programming system is, on the other hand, the tool for the programmer to make a program. It serves as an interface between a programmer and the operating system or the hardware. Since there are peculiar notions in each application area, different programming languages are invented for each application area so that programs become short and easy to write. The nucleus of the programming system is the language processor, so the programming system is expanding in terms of language processors. It now becomes necessary to find an easy way to create programming systems which can be expanded easily.
There are three main approaches to resolving this problem. The first approach is to make a universal language and to write all programs in this language. Only one language processor is necessary for one computer. But this has never been realized. PL/I is supposed to serve as a higher programming language version of a universal language. The second approach is to make one compiler-compiler and to generate all compilers for different programming languages by that compiler-compiler. Strong tools for defining the syntax of the language already exist, but it is still not easy to define semantics. So it is very difficult to generate a good compiler with a good optimization facility. The third approach, now becoming more attractive, is the attempt to make a language extensible. An extensible language is the language which can introduce new syntax, practically in the form of operators, and new data structures. So if a programmer wants special operators and data structures, he can declare them before the program and can program in terms of them. This approach is promising since the programmer can make a program constructively.
Grammatical inference for defining extensions
Authors: Reghizzi S. Crespi 
Published: November 2005

Extensions to a language need be defined by a grammar, or by any conceivable method which is apt to discriminate valid from unwanted extensions and to provide efficient parsing and translation.
Context-free grammars - a traditional choice - have a major drawback with respect to practical use. Namely, the unsophisticated user of an extensible system would find it hard to formulate an appropriate BNF definition of the constructions he wants.
Transition functions
Authors: Leavenworth B. M. 
Published: November 2005

Syntactic extension methods (see, for example (5)) usually involve the following steps:
(1) recognize a syntactic pattern in the program and find its (string) parameters
(2) call the appropriate string function, substituting actual for formal parameters
(3) execute the result of the string function
The specification of syntactic extensions results in modifying the translator incrementally. We will not be further concerned with syntactic extensions in this paper.
Interpreter/compiler integration in ECL
Authors: Holloway Glenn H. 
Published: November 2005

As mentioned in [1], a primary design objective of the ECL programming system [2, 3] has been to maximize the flexibility afforded its user, particularly during the design and debugging of his programs, without sacrificing the efficiency of his final product. The programmer is given the facility first to tailor the system to his needs, then to shed unneeded variability in exchange for increased efficiency.
To this end, ECL includes both an interpreter and a compiler for the language EL1. The integration of two compatible language processors in a single system is achieved with a minimum of duplicate syntactic or semantic analysis.
Application of extensible languages to specialized application languages
Authors: Sammet Jean E. 
Published: November 2005

It is becoming increasingly clear that one of the major thrusts of the programming language field is in the direction of specialized application languages - sometimes called special purpose languages. These specialized application languages have already been developed for such diverse fields as civil engineering, electrical engineering, computer assisted instruction, systems programming, equipment checkout, movie animation, etc. Of the roughly 165 languages currently in use in the United States, approximately 85 of them might be classified as specialized. (See the list in Reference 1.) For description and illustration of many of these, see Chapter 9 in Reference 2.
All languages are applications oriented. In fact, this is probably the best way to categorize the set of programming languages. However, some application areas are obviously larger than others, e.g., scientific computation (numeric and non-numeric) and business data processing. The main concern here is with the more specialized languages. While each person may have a different idea of what the categories of specialization should be, there can be little dispute about the wide diversity and large number of them.
PPL - an extensible language that failed
Authors: Standish Thomas A. 
Published: November 2005

PPL, a conversational extensible language, has been running on the DEC PDP-10 for over a year now. Its applications have included: matrix, vector, polynomial, rational and complex arithmetic; formula, list, string, tree and graph manipulation; significant programs in real-time radar air traffic control simulation and parser generation for context-free languages; and a host of useful conversational tasks in population biology, algebra word problems and optimization of programs. Indeed, the parser for another extensible language(ECL) was generated in PPL(using the De Remer algorithm). PPL is now used by over 450 students in Harvard's introductory programming course. Needless to say, for me and a number of others, PPL is the preferred medium for writing programs and serves as an important and enjoyable tool of thought. To me, PPL is rich, highly versatile and easy to use As is the case for most other languages, PPL evokes both adoring remarks from its proponents and the usual scorn from its detractors. In analogy to the process of stellar evolution, if there is such a thing as a “main sequence” for the life of programming languages, PPL seems well launched on it (though programming languages probably die by fizzling out, not by exploding).
Yet PPL is a failure. A few years ago, the vision of extensible languages held by some was that users could rapidly and cheaply extend the base of an extensible language to encompass the data, the operations, the notation and the control natural to many diverse application areas. In short, one was supposed to be able to manufacture personalized languages of reasonable efficiency and substantial utility with great ease just by applying some easily learned extension techniques. It was thought that just as programmers decree the organization of processes (by defining and calling subroutines),they should also decree appropriate organizations for data and for notation, in order to attain more clarity and efficiency.
Inferred syntax and semantics of PL/S
Authors: Wiederhold Gio , Ehrman John 
Published: November 2005

This is an attempt to describe a language developed and used by IBM Corporation to support the writing of system programs. It is a PL/1-like language specifically oriented towards the kind of operations required In writing operating systems.
The language was referred to originally as BSL, and is now called PL/S. By March 1971 development had proceeded to a version numbered 12.11. I t is this and shortly preceding versions that are described here.
Detecting conflicts between structure accesses
Authors: Larus J. R. , Hilfinger P. N. 
Published: November 2005

Two references to a record structure conflict if they access the same field and at least one modifies the location. Because structures can be connected by pointers, deciding if two statements conflict requires knowledge of the possible aliases for the locations that they access.
This paper describes a dataflow computation that produces a conservative description of the aliases visible at any point in a program. The data structure that records aliases is an alias graph. It also labels instances of structures so that the objects referenced at different points in a program can be compared. This paper shows how alias graphs can be used to detect potential conflicts.
The European side of the last phase of the development of ALGOL 60
Authors: Naur Peter 
Published: November 2005

In preparing this account of some of the developments leading to ALGOL 60 I have primarily sought to present such relevant information that is readily available to myself, but not otherwise accessible or well known. In addition I have tried to answer the specific questions formulated by the organizers of the Conference on the History of Programming Languages. The notes fall in three freely intermixed groups: those that relate to existing documents, those that reflect my own reasoning as a participant in the development, and those that try to answer the organizers' questions. Where the proper support has been lacking I have left open holes in the presentation. Otherwise I have tried to be specific, giving names, dates, and reasons, as far as I have them available.
While this manner of presentation seems to me the best way to support more penetrating historical research into the period, it is also bound to give rise to controversy. First, it is openly one-sided, in the manner that any autobiography is. Further, by being specific the presentation will offer sensitive points of attack to those who see the same development from a different angle and with different eyes. When these circumstances are combined with real events that involved differences of opinion and interest, strong reactions are bound to be provoked. This emerged clearly in the remarks from the reviewers of the draft of the paper.
BASIC
Authors: Kurtz Thomas E. 
Published: November 2005

Dartmouth College is a small university dating from 1769, and dedicated “... for the education and instruction of Youth of the Indian Tribes in this Land in reading, writing and all parts of learning... and also of English Youth and any others.” (Wheelock 1769.) The undergraduate student body (now nearly 4000) outnumbers all graduate students by more than 5 to 1, and majors predominantly in the Social Sciences and the Humanities (over 75 percent).
In 1940 a milestone event, not well remembered until recently (Loveday 1977), took place at Dartmouth. Dr. George Stibitz of the Bell Telephone Laboratories demonstrated publicly for the first time, at the annual meeting of the American Mathematical Society, the remote use of a computer over a communications line. The computer was a relay calculator designed to carry out arithmetic on complex numbers. The terminal was a Model 26 Teletype.
A brief description of JOVIAL
Authors: Cheatham T. E. 
Published: November 2005

JOVIAL (Jules' Own Version of the International Algebraic Language) was one of the first programming languages developed primarily to aid in programming large complex real time systems. Today it remains a major language for these applications and versions of JOVIAL have been implemented on dozens of different computers. The language and its compilers have been developed primarily by the Systems Development Corporation.
JOVIAL was based on Algol-58 but includes numerous features not in Algol (58 or 60) which make it particularly useful for programming large scale systems. The most important of these is the COMPOOL (communications POOL), a central repository of data descriptions which permits programmers to reference data items without concerns as to how they are represented on some particular computer.
The development of JOVIAL
Authors: Schwartz Jules I. 
Published: November 2005

The time was late 1958. Computers that those who were involved with the first JOVIAL project had been using included the JOHNNIAC (built at Rand Corporation), the IBM AN/FSQ-7 (for SAGE), 701, and 704. A few had worked with board wired calculators. Some had never programmed. For those using IBM, the 709 was the current machine. There were various other manufacturers at the time, some of whom do not exist today as computer manufacturers.
The vacuum tube was still in vogue, Very large memories, either high speed direct access or peripheral storage, didn't exist, except for magnetic tape and drums on some computers.
ACM SIGPLAN history of programming languages conference SIMULA language summary
Authors: Franta W. R. 
Published: November 2005

SIMULA was conceived in the early sixties by Ole-Johan Dahl and Kristen Nygaard of the Norwegian Computing Center [3 ]. The most prevalent version of the language today is SlMULA-67 [1].
SIMULA was designed for system description and system simulation. A system in this case is a collection of interdependent elements with a common goal [4]. A natural way to simulate a system is to describe the life cycle scenarios of its elements. This approach combines the local attributes of elements and the protocols for inter-element communication into a single structure. Elements may exist for the duration of the simulation or be created and destroyed during its course.
Hardware/software cooperation in the iAPX-432
Authors: Rattner Justin 
Published: November 2005

The Intel iAPX-432 is an object-based microcomputer system with a unified approach to the design and use of its architecture, operating system, and primary programming language. The concrete architecture of the 432 incorporates hardware support for data abstraction, small protection domains, and language-oriented run-time environments. It also uses its object-orientation to provide hardware support for dynamic heap storage management, interprocess communication, and processor dispatching.
We begin with an overview of the 432 architecture so readers unfamiliar with its basic concepts will be able to follow the succeeding discussion without the need to consult the references. Following that, we introduce the various forms of hardware/software cooperation and the criteria by which a function or service is selected for migration. This is followed by several of the more interesting examples of hardware/software cooperation in the 432. A comparison of cooperation in the 432 with several contemporary machines and discussions of development issues, past and future, complete the paper.
The 801 minicomputer
Authors: Radin George 
Published: November 2005

This paper provides an overview of an experimental system developed at the IBM T. J. Watson Research Center. It consists of a running hardware prototype, a control program and an optimizing compiler. The basic concepts underlying the system are discussed as are the performance characteristics of the prototype. In particular, three principles are examined:
system orientation towards the pervasive use of high level language programming and a sophisticated compiler,
a primitive instruction set which can be completely hard-wired,
storage hierarchy and I/O organization to enable the CPU to execute an instruction at almost every cycle.
Empirical analysis of the mesa instruction set
Authors: Sweet Richard E. , Sandman James G. 
Published: November 2005

This paper describes recent work to refine the instruction set of the Mesa processor. Mesa [8] is a high level systems implementation language developed at Xerox PARC during the middle 1970's. Typical systems written in Mesa are large collections of programs running on single-user machines. For this reason, a major design goal of the project has been to generate compact object programs.
The computers that execute Mesa programs are implementations of a stack architecture [5]. The instructions of an object program are organized into a stream of eight bit bytes. The exact complement into of instructions in the architecture has changed as the language and machine micro architecture have evolved.
In Sections 3 and 4, we give a short history of the Mesa instruction set and discuss the motivation for our most recent analysis of it. In Section 5, we discuss the tools and techniques used in this analysis. Section 6 shows the results of this analysis as applied to a large sample of approximately 2.5 million instruction bytes. Sections 7 and 8 give advice to others who might be contemplating similar analyses.
An analysis of a mesa instruction set using dynamic instruction frequencies
Authors: McDaniel Gene 
Published: November 2005

The Mesa architecture is implemented on a variety of processors, and dynamic instruction frequency data for two programs is used to analyze the architecture in an implementation independent fashion.
The Mesa compiler allocates variables in an order based upon their static frequency of use, and measurements are provided that show that these static predictions predict run time usage as well. We provide an evaluation of the advantages and costs of Mesa's compact byte encoding, its reliance upon an evaluation stack, and its use of memory.
The Mesa language has evolved over time in a hardware environment oriented around 16-bit quantities with growing use of and accommodations to 32-bit quantities. The cost of emulating 32-bit data paths on a 16-bit machine is identified for a program that heavily exploits longer values.
Several potential areas for improving the execution speed of a Mesa processor with special purpose hardware are identified.
Dynamic system specification
Authors: Balzer Robert M. 
Published: November 2005

Our group is perhaps unique in that our approach to modeling dynamic systems has a strong heritage from all three fields represented at this workshop. Each of the fields has contributed four major concepts to our modeling approach.
From the Data Base field, we have adopted the idea of a single global model (data base) which defines the state of the system. Fully associative relations among typed atomic objects (no internal structure) constitute the entire state description. An information model (query language) is defined for extracting information from the state (such as one or all objects satisfying some description, or the truthfulness of some proposition). Finally, the model is updated via transactions, so that either the entire operation is completed successfully, or the state is unchanged.