bluuebunny/crossref_metadata_2025 huggingface dataset:
Array processing on an array processor
Authors: Erickson David B.
Published: November 2005

Central memory is distributed across several processing elements on the ILLIAC-IV and similar array processors. This causes memory to appear two dimensional and raises special problems in the handling of arrays. Assignment of arrays to storage, and development of efficient array mapping functions and accessing techniques are all much more difficult than on conventional machines with “linear” memories. This paper discusses these problems as they relate to IVTRAN, a Fortran-like compiler for the ILLIAC-IV. Alternate solutions, useful in a different environment, are also explored.

We shall start by giving a brief overview of the pertinent features of the ILLIAC-IV. The paper then describes IVTRAN constructs which may be used in expressing parallelism and the implications that these constructs have for array storage. Next, array mapping formulas are developed and the array packing problem is treated. Finally, argument passage and Fortran COMMON and EQUIVALENCE statements are discussed.
The principle of sufficient reason
Authors: Geller Dennis P. , Weinberg Gerald M.
Published: November 2005

To a large extent, the design of languages for parallel processing machines seems to be a problem merely because of the historical precedence of von Neumann machines. We have grown up professionally in a serial computing environment, so that many of the habits we have acquired are related to that seriality and yet are so deeply ingrained thay we do not recognize seriality as the reason for doing them. Instead they seem like 'natural' laws, sometimes so 'natural' that we don't even notice their existence. In many cases then, we can arrive at the proper design of languages for parallel processing simply by forgetting what we 'know' about programming languages — but forgetting is not an easy thing to do without specific guidelines. One such guideline is the Principle of Sufficient Reason, which states: “parallel is more natural than serial, unless proved otherwise.”
PACOL
Authors: Barta Ben Zion
Published: November 2005

An Extended Parallel Program Scheme (EPPS) and a higher level Parallel Control Language (PACOL) are defined. They are suitable for describing and programming parallel programs, intended for execution by a LSI modular, highly parallel processing system. PACOL provides for the definition of the sequencing of task-executions and of the related data transfers. To define the computations associated with the tasks, however, any one of the usual programming languages has to be used. These program statements are interwoven with the PACOL statements, to form a complete parallel program. PACOL uses ternary control variables but, for convenience, the task entry-functions are “quasi boolean”. It allows for very flexible sequencing schemes, including reentrant and recursive executions, lock, unlock and waiting actions. A programming example and the description of a part of the PACOL-semantics follow the definitions of its syntax and of the EPPS.
DMAP-a COBOL extension for associative array processors
Authors: Resnick Harold K. , Larson Arvid G.
Published: November 2005

This paper defines a high-level programming language for a generalized associative array processor (AP). In particular, a data management language for APs, known as DMAP, is developed for use with a representative AP model. This development model, containing both an associative processing section and a sequential processing section, which may operate concurrently, follows current AP design technology[1]. DMAP fully exploits the capabilities available in current AP technology by extending ANSI COBOL [2,3] to support data management functions in an AP environment.

There exists general agreement that the use of a high-level language can significantly facilitate the AP programming process in many applications [4,5]. However, a search of the literature suggests that few attempts at high-level language implementation, or even definition, have been made to date [6,7]. The several additional and unique difficulties associated with application-oriented programming of parallel processors in general, and APs in particular, mandates a high-level language capability to produce cost-effective utilization of their processing resources. This paper considers one approach, a first step, toward this development of a high-level language capability to provide some alleviation of immediate programming difficulties as well as provide a tool for further exploration of AP technology.
CFD — A FORTRAN-like language for the ILLIAC IV
Authors: Stevens K. G.
Published: November 2005

A FORTRAN-like language, CFD, is described as it relates to the parallel hardware of ILLIAC IV. Included are the basic goals of the authors of CFD and some of the author's own experiences during the evolution of the language. CFD was developed for the ILLIAC IV to provide programmers with a language similar to commonly used versions of FORTRAN. Many of the deviations from FORTRAN found in CFD were dictated by the parallel hardware architecture of ILLIAC IV.
Removal of invariant statements from nested-loops in a single effective compiler pass
Authors: Neel D. , Amirchahy M.
Published: November 2005

This document presents how one of the most important optimizations that a program may undergo is dealt with by means of attributes [7]. A semantic formalization of the classical method which consists of removing all loop-independent statements from the articulation blocks of a loop is given. The method is equally well applicable to algebraic languages or their intermediate code : in a high level language even very well constructed programs quite often contain in their intermediate code version invariant loop expressions where address evaluations are concerned. Whatever the level of nested-loop structure, the method proposed here would not require more than a single real compiler pass in contrast with classical methods which proceed from the innermost loop and shift the invariant statements just one level at each successive pass. Finally an interesting algorithm to determine the articulation blocks of a program is given in the annexe. This method has been so conceived as to take into account the evaluation of attributes by the system DELTA [6]. In this phase of the compiler possibilities of parallel execution are offered as the evaluation program is data oriented. The rigour of formalization attained together with a certain minimization of risks of erroneous optimization applications which it involves render this method indubitably efficient.
Program optimization - theory and practice
Authors: Loveman David B. , Faneuf Ross A.
Published: November 2005

The conventional program optimization techniques employed by the ILLIAC FORTRAN compiler are general purpose, effective, and efficient. The underlying theory is applicable to FORTRAN and to other high level languages. A unique approach to the gathering of global set and use information about variables as well as careful software engineering of the algorithms has led to the construction of an effective source-to-source optimizer which performs constant propagation, constant computation, common subexpression elimination, reduction in strength, and invariant code motion.

We will first consider the type of information which must be gathered about a program, and how this information is used to perform optimization. Then we shall state the algorithm for globally computing the set and use information for program variables. Having discussed the science of optimization we shall turn to the engineering aspects and consider such topics as representation of programs, order of optimization transformations, and efficient computation of global use and set information.
A stream processing network
Authors: Morris D. , Treleaven P. C.
Published: November 2005

This paper is concerned with a programming system based on the notion of
stream
operands. These are sequences of scalar operands in which only the current member of the stream can be accessed at any one time and after that only the next member. The language discussed is aimed initially at a system consisting of a network of microprocessors. It has a fairly conventional appearance and the new facilities are introduced mainly as procedure calls. Once the semantic characteristics have been established a more appropriate syntax will be developed. The long term goal is a style of high level language that will lead away from conventional systems, for large problems which lend themselves to
streaming
.
A parallel approach to code generation for Fortran like compilers
Authors: Krohn Howard E.
Published: November 2005

It has been shown by Lincoln and others that vector operations can be used to perform lexical analysis of FORTRAN source code. This paper presents techniques for code generation using parallel programming methods developed on the CDC STAR-100.

Methods are presented for handling arithmetic assignment statements, DO loops, IF statements, and parenthetical expressions. A CO-NO table syntactical analysis is performed using the numeric vector from lexical analysis to produce output code for arithmetic expressions. Code for DO loops and IF statements is then merged into the object code vector.
Specification techniques for data abstractions
Authors: Liskov Barbara , Zilles Stephen
Published: November 2005

The main purposes in writing this paper are to discuss the importance of formal specifications and to survey a number of promising specification techniques. The role of formal specifications both in proofs of program correctness, and in programming methodologies leading to programs which are correct by construction, is explained. Some criteria are established for evaluating the practical potential of specification techniques. The importance of providing specifications at the right level of abstraction is discussed, and a particularly interesting class of specification techniques, those used to construct specifications of data abstractions, is identified. A number of specification techniques for describing data abstractions are surveyed and evaluated with respect to the criteria. Finally, directions for future research are indicated.
Knowledge about programs
Authors: Gerhart Susan L.
Published: November 2005

Dijkstra suggests in his “Notes on Structured Programming” that program schema and theorems about their correctness may describe the way that programmers understand programming. This paper follows up his suggestion by describing a general model for domains of programming knowledge in terms of schema, transformations, and derivation rules. The model is illustrated by the results of a case study of the knowledge about 10 programs which use arrays. The model and case study illustrate a methodology for constructing and proving correct programs based on knowledge which is independently expressed and partially proved in an abstract form and which can be applied in a stepwise way.
Programming-in-the large versus programming-in-the-small
Authors: DeRemer Frank , Kron Hans
Published: November 2005

We distinguish the activity of writing large programs from that of writing small ones. By large programs we mean systems consisting of many small programs (modules), possibly written by different people.

We need languages for programming-in-the-small, i.e. languages not unlike the common programming languages of today, for writing modules. We also need a “module interconnection language” for knitting those modules together into an integrated whole and for providing an overview that formally records the intent of the programmer(s) and that can be checked for consistency by a compiler.

We explore the software reliability aspects of such an interconnection language. Emphasis is placed on facilities for information hiding and for defining layers of virtual machines.
Automated aids fob reliable software
Authors: Reifer Donald J.
Published: November 2005

Recent investigations on the use of automation to realize the twin objectives of cost reduction and reliability improvement for computer programs developed for the U. S. Air Force are reported. The concepts of reliability and automation as they pertain to software are explained. Then, over twenty automated tools and techniques (aids) identified by this investigation are described and categorized. Based on the information reviewed, an assessment of the state of the technology is made. Finally, specific recommendations which try to give direction to future efforts are offered.
Towards automatic debugging of programs
Authors: Katz Shmuel , Manna Zohar
Published: November 2005

We present the germ of an idea for automatically correcting logical errors in programs by manipulating the invariants of the program. An invariant tree is defined, and we show how it can be used to change the program in order to guarantee correctness.

Debugging could be incorporated into a verification system which would first try to prove the correctness of the program. If the attempt is unsuccessful, two alternative approaches are suggested and compared. In the first, we try directly to correct the invariants and - through these - the statements, taking the calculated risk of modifying an already correct program. In the second approach, we initially prove incorrectness, and only then try to correct the program, by invalidating this proof.
A methodology for verifying programs
Authors: von Henke F. W , Luckham D. C.
Published: November 2005

The paper investigates methods for applying an online interactive verification system designed to prove properties of PASCAL programs. The methodology provides techniques for developing a debugged and verified version starting from an incomplete program
.
Finding Invariant assertions for proving programs
Authors: Caplain Michel
Published: November 2005

We attempt to extract from any program loop its “Most General Invariant” in order to either prove its correctness, including termination, or disprove it and propose corrections.
A system for reliable engineering software
Authors: Culpepper L. M.
Published: November 2005

Much of the software developed to support engineering design calculations is produced by persons whose primary job skill is not that of computer scientist. Software validation techniques suitable for use by these engineer-programmers have been under investigation by the Navy as part of a project designed to increase the reliability, usability, and portability of engineering design software. The results of the project are summarized and a software validation tool is described.
The Mythical Man-Month
Authors: Brooks Fred P.
Published: November 2005

The book, The Mythical Man-Month, Addison-Wesley, 1975 (excerpted in Datamation, December 1974), gathers some of the published data about software engineering and mixes it with the assertion of a lot of personal opinions. In this presentation, the author will list some of the assertions and invite dispute or support from the audience. This is intended as a public discussion of the published book, not a regular paper.
“Software reliability in online real time environment”
Authors: Miyamoto Isao
Published: November 2005

This paper discusses actual software reliability data obtained in an on line real time environment. The measures used are the reliability function R(t) and the mean time between software errors MTBSE. How to measure the operational data of R(t) or MTBSE and to analyze the measurement results are described, presenting collected reliability data. This paper proposes some quantitative models which can be used to measure, manage and predict the level of perfection of software during the test stage. The error model used in this paper is based on Shooman's work1), and the number of errors remaining in a software program is modeled in terms of the number of errors corrected, the additional errors because of erroneous debugging, and observed number of errors detected. Also the assumption is made that the software error rate is proportional to the number of remaining errors. The major problems to be met during system development are readjusted.
A reliability model for Markov structured software
Authors: Littlewood B.
Published: November 2005

A system is considered in which switching takes place between sub-systems according to a continuous parameter Markov chain. Failures may occur in Poisson processes in the sub-systems, and in the transitions between sub-systems. All failure processes are independent. The overall failure process is described exactly and asymptotically for highly reliable sub-systems. An application to process-control computer software is suggested.
Finite state modelling in program development
Authors: Henderson Peter
Published: November 2005

A technique is presented whereby a significant amount of program validation can be done simply by exercising the program components in a model environment provided by a finite state machine, specially built to characterise the real environment of that component. The tools necessary to support such a technique are characterised and the merits and demerits of the technique are discussed.
A new approach to program testing
Authors: King James C.
Published: November 2005

The current approach for testing a program is, in principle, quite primitive. Some small sample of the data that a program is expected to handle is presented to the program. If the program produces correct results for the sample, it is assumed to be correct. Much current work focuses on the question of how to choose this sample. We propose that a program can be more effectively tested by executing it "symbolically." Instead of supplying specific constants as input values to a program being tested, one supplies symbols. The normal computational definitions for the basic operations performed by a program can be expanded to accept symbolic inputs and produce symbolic formulae as output. If the flow of control in the program is completely independent of its input parameters, then all output values can be symbolically computed as formulae over the symbolic inputs and examined for correctness. When the control flow of the program is input dependent, a case analysis can be performed producing output formulae for each class of inputs determined by the control flow dependencies. Using these ideas, we have designed and implemented an interactive debugging/testing system called EFFIGY.
Quantitative aspects of software validation
Authors: Rubey Raymond J.
Published: November 2005

This paper discusses the need for quantitative descriptions of software errors and methods for gathering such data. The software development cycle is reviewed and the frequency of the errors that are detected during software development and independent validation are compared. Data obtained from validation efforts are presented, indicating the number of errors in 10 categories and three severity levels; the inferences that can be drawn from this data are discussed. Data describing the effectiveness of validation tools and techniques as a function of time are presented and discussed. The software validation cost is contrasted with the software development cost. The applications of better quantitative software error data are summarized.
On attaining reliable software for a secure operating system
Authors: Robinson Lawrence , Levitt Karl N. , Neumann Peter G. , Saxena Ashok R.
Published: November 2005

This paper presents a general methodology for the design, implementation, and proof of large software systems, each described as a hierarchy of abstract machines. The design and implementation occur in five stages as described in this paper. Formal proof may take place at each stage. We expect the methodology to simplify the proof effort in such a way as to make proof a feasible tool in the development of reliable software. In addition to the anticipated advantages in proof, we feel that the methodology improves a designer's ability to formulate and organize the issues involved in the design of large systems, with additional benefits in system reliability. These advantages remain even if proof is not attempted.

We are currently applying this methodology to the design and proof of a secure operating system. Each level in the system acts as a manager of all objects of a particular type (e .g ., directories, segments, linkage sections), and enforces all of the protection rules involved in the manipulation of these objects. In this paper we illustrate the methodology by examining three of the system levels, including specifications, for a simplified version of these levels. We also demonstrate some proofs of security-related properties and of correctness of implementation.
A verifiable protection system
Authors: Popek Gerald J. , Kline Charles S.
Published: November 2005

This paper reports on the design and implementation of the UCLA Virtual Machine System, a multiuser operating system base that has been developed to provide ultra high reliability protection and security. Details are presented of the UCLA-VM system, a prototype of which now exists. Concepts which have influenced its structure are discussed, including program verification, security kernels, virtual machines, virtual memory, and the need for flexible information sharing facilities. A new mechanism, capability faulting, is developed in order to remove much of the virtual memory support from the security kernel. Flexible, reliable control of sharing is obtained by extensions to several of these concepts, especially through the use of levels of kernels.
A structured specification of a hierarchical operating system
Authors: Saxena Ashok R. , Bredt Thomas H.
Published: November 2005

This paper applies the concepts of hierarchical levels of abstraction and structured programming to the design of a large program system. An operating system for a multi-processor installation is specified that supports a large number of concurrently active processes and provides a virtual store for them. The specification is in an extended version of PASCAL, a high-level language.
An analysis of errors and their causes in system programs
Authors: Endres Albert
Published: November 2005

Program errors detected during internal testing of the operating system DOS/VS form the basis for an investigation of error distributions in system programs. Using a classification of the errors according to various attributes, conclusions can be drawn concerning the possible causes of these errors. The information thus obtained is applied in a discussion of the most effective methods for the detection and prevention of errors.
Analysis of error processes in computer software
Authors: Schneidewind Norman F.
Published: November 2005

A non-homogeneous Poisson process is used to model the occurrence of errors detected during functional testing of command and control software. The parameters of the detection process are estimated by using a combination of maximum likelihood and weighted least squares methods. Once parameter estimates are obtained, forecasts can be made of cumulative number of detected errors. Forecasting equations of cumulative corrected errors, errors detected but not corrected, and the time required to detect or correct a specified number of errors, are derived from the detected error function. The various forecasts provide decision aids for managing software testing activities. Naval Tactical Data System software error data are used to evaluate several variations of the forecasting methodology and to test the accuracy of the forecasting equations. Because of changes which take place in the actual detected error process, it was found that recent error observations are more representative of future error occurrences than are early observations. Based on a limited test of the model, acceptable accuracy was obtained when using the preferred forecasting method.
The influence of software structure on reliability
Authors: Parnas D. L.
Published: November 2005

This paper assumes software structure to be characterized by the interfaces between subsystems or modules. Reliability is considered to be a measure of the extent to which the system can be expected to deliver usable services when those services are demanded. It is argued that reliability and correctness (in the sense used in current computer literature) are not synonyms. The differences suggest techniques by which the reliability of software can be improved even while the production of correct software remains beyond our reach. In general, the techniques involve considering certain unpleasant facts of life at an early stage in the design process, the stage where the structure is determined, rather than later. An appendix gives some specific examples of questions which, if they are thoughtfully considered early in the design, can lead to more reliable systems.
Implementation of the Alpha-6 programming system
Authors: Buda A. O. , Granovaky A. A. , Ershov A. P.
Published: November 2005

The implementation of a large compiler system is described, and conclusions are drawn about organization, time scales and the quality achieved.
Software design validation tool
Authors: Carpenter Loren C. , Tripp Leonard L.
Published: November 2005

DECA is a computer program which is used in conjunction with a top-down dominated design methodology. The program organizes, validates, and produces a document depicting the design of a software system. The use of DECA significantly enhances the quality of the software design. The quality of the design in turn significantly benefits the quality of the implemented software system.
Provable programming
Authors: Good Donald I.
Published: November 2005

Techniques are presented for the design of computer programs that are proved to meet stated specifications. The design strategy is the simultaneous step-wise refinement of both the program and its proof so that at each step the program constructed so far is proved. At each step, the specifications for a single program unit are given, the unit is designed, and then proved, by automatically supportable methods, before going on to successive steps. The proof i) shows that the program unit meets its specifications, ii) exhibits any assumptions the unit makes about the problem domain, and iii) defines the specifications for units to be designed in later steps. The design process is based on the refinement of operational and data abstractions in both the program and its specifications. These abstractions are what allow the proof at each step to be supported by automatic, or interactive, program proving systems. The abstractions also keep the proofs of the individual units at an appropriate level of abstraction and also largely independent, thus significantly reducing the size of the complete proof of the entire program. These techniques of provable programming are illustrated by two examples.
Fault-tolerance and fault-intolerance
Authors: Avižienis Algirdas
Published: November 2005

Two complementary methods whìch are employed in order to assure relìable computing are fault-intolerance and fault-tolerance. Fault-intolerance depends on the elìmìnatìon of the causes of unreliability prior to the start of the computing process while fault-tolerance employs protective redunuancy during the computing process in order to detect and to correct unreliable functìoning. A balanced allocation of reliability resources between the two methods appears to offer the best practical solution. The paper reviews current fault-tolerance practices in system architecture and discusses their relevance to software systems.
An interactive program verification system
Authors: Good Donald I. , London Ralph L. , Bledsoe W. W.
Published: November 2005

This paper is an initial progress report on the development of an interactive system for verifying that computer programs meet given formal specifications. The system is based on the conventional inductive assertion method: given a program and its specifications, the object is to generate the verification conditions, simplify them, and prove what remains. The important feature of the system is that the human user has the opportunity and obligation to help actively in the simplifying and proving. The user, for example, is the primary source of problem domain facts and properties needed in the proofs. A general description is given of the overall design philosophy, structure, and functional components of the system, and a simple sorting program is used to illustrate both the behavior of major system components and the type of user interaction the system provides.
On the connections between range of variable and control structure testing
Authors: Kopetz Hermann
Published: November 2005

This paper discusses the subject of systematic program testing from a software engineering point of view. A number of different software error types are defined to facilitate the analysis of the error detection capability of a software module. It is found that many practical programs are, at best, conditionally Correct. Consequently it is not possible to establish the correctness of such a program even by an exhaustive test of the control structure. Keeping those insights in mind, some applicable techniques for the construction, error treatment and test of practical software systems are presented.
A view of program verification
Authors: London Ralph L.
Published: November 2005

One person's perspectives of program verification and its relation to some aspects of reliable software are presented. The main verification method of inductive assertions is illustrated with several variations of one detailed example; a second example shows a surprisingly simple inductive assertion proof of an iterative tree traversal example. Briefly discussed also are the implicit assumptions of most verifications, proving termination, the creating of assertions, and languages in which to write assertions. An abstract overview is given of existing program verification systems together with a sample list of verified programs. A short bibliography is included.
Notes on the design of Euclid
Authors: Popek G. J. , Horning J. J. , Lampson B. W. , Mitchell J. G. , London R. L.
Published: November 2005

Euclid is a language for writing system programs that are to be verified. We believe that verification and reliability are closely related, because if it is hard to reason about programs using a language feature, it will be difficult to write programs that use it properly. This paper discusses a number of issues in the design of Euclid, including such topics as the scope of names, aliasing, modules, type-checking, and the confinement of machine dependencies; it gives some of the reasons for our expectation that programming in Euclid will be more reliable (and will produce more reliable programs) than programming in Pascal, on which Euclid is based.
Restricted data types, specification and enforcement of invariant properties of variables
Authors: Buckle Normand
Published: November 2005

When defining a data type, it is often useful to specify restrictions on the permitted values of that type.

Pascal's subrange type declaration, a special case of this kind of constraint definition, has already proved itself to be quite useful. Restricted data types allow more complex constraints to be defined and checked; for example, a variable could be declared of type “odd integer” or the day field of a “date” type variable could be checked for consistency with the year and month fields.

A simple mechanism is proposed, allowing the formulation of such constraints and their association with data types; the behaviour of a restricted type variable is described. The effects of the use of such a mechanism on program reliability, readability and efficiency are discussed.
Software reliability
Authors: Melliar-Smith P. M. , Randell B.
Published: November 2005

The paper discusses the basic concepts underlying the issue of software reliability, and argues that programmed exception handling is inappropriate for dealing with suspected software errors. Instead it is shown, using an example program, how exception handling can be combined with the recovery block structure. The result is to improve the effectiveness with which problems due to anticipated faulty input data, hardware components, etc., are dealt with, while continuing to provide means for recovering from unanticipated faults, including ones due to residual software design errors.
Exception handling in PL/I
Authors: MacLaren M. Donald
Published: November 2005

The PL/I language's facilities for handling exceptional conditions are analyzed. The description is based on the new PL/I standard. Special attention is given to fine points which are not well known. The analysis is generally critical. It emphasizes problems in regards to implementation and structured programming. A few suggestions for future language design are offered.
An experimental investigation of the effect of program structure on program understanding
Authors: Love Tom
Published: November 2005

A within-subjects experimental design was used to test the effect of two variables on program understanding. The independent variables were complexity of control flow and paragraphing of the source code. Understanding was measured by having the subjects memorize the code for a fixed time and reconstruct the code verbatim. Also some subjects were asked to describe the function of the program after completing their reconstruction. The two groups of subjects for the experiment were students from an introductory programming class and from a graduate class in programming languages.

The major findings were that paragraphing of the source had no effect for either group of subjects but that programs with simplified control flow were easier for the computer science students to understand as measured by their ability to reconstruct the programs. The dependent variable, rated accuracy of their description of the programs functions, did not differ as a function of either independent variable.

The paper is concluded with a description of the utility of this experimental approach relative to improving the reliability of software and a discussion of the importance of these findings.
Abstraction mechanisms in CLU
Authors: Liskov Barbara , Snyder Alan , Atkinson Russell , Schaffert Craig
Published: November 2005

CLU is a new programming language designed to support the use of abstractions in program construction. Work in programming methodology has led to the realization that three kinds of abstractions, procedural, control, and especially data abstractions, are useful in the programming process. Of these, only the procedural abstraction is supported well by conventional languages, through the procedure or subroutine. CLU provides, in addition to procedures, novel linguistic mechanisms that support the use of data and control abstractions.

This paper provides an introduction to the abstraction mechanisms in CLU. By means of programming examples, we illustrate the utility of the three kinds of abstractions in program construction and show how CLU programs may be written to use and implement abstractions. We also discuss the CLU library, which permits incremental program development with complete type-checking performed at compile-time.
An experimental evaluation of data types on programming reliability
Authors: Gannon J. D.
Published: November 2005

The language in which programs are written can have a substantial effect on the reliability of the resulting programs. This paper discusses an experiment that compares the programming reliability of subjects using a statically-typed language and a “typeless” language. Analysis of the number of errors and the number of runs containing errors shows that, at least in one environment, the use of a statically-typed language can increase programming reliability. Detailed analysis of the errors made by the subjects in programming solutions to reasonably small problems shows that the subjects had difficulty manipulating the representation of data.
Determining path feasibility for commercial programs
Authors: Coward P. David
Published: November 2005

Paths are often used as a basis for the testing of programs. The identification of feasible and infeasible paths is central to a path-based approach to testing. Linear optimizers have been used for determining path feasibility by using the path predicates as constraints of an optimization problem. Commercial programs have been identified as amenable to the linear optimizer approach but the occurrence of alphanumeric literals poses a problem as they cannot be submitted to a numerical optimizer. It is suggested that this problem can be surmounted easily. Two approaches are briefly described. The first substitutes numeric tokens for alphanumeric literals. The second segregates the alphanumeric predicates from the numeric predicates and deals with them independently. The first approach appears to be a practical solution while the second appears to be less useful.
Pascal-FC: a language for teaching concurrent programming
Authors: Burns A. , Davies G.
Published: November 2005

Pascal-FC is an extension of one of Wirth's simple Pascals. The added features allow processes to be specified and executed concurrently. Moreover communication and synchronisation primitives have been added to support semaphores, monitors and the CSP/occam type rendezvous. The language is used to give computer science students practical experience of a range of concurrency models.
Turing Plus: a comparison with C and Pascal
Authors: Perelgut S. , Cordy James R.
Published: November 2005

It is desirable to do systems programming in a high-level language. C is attractive since it yields efficient machine code without placing many restrictions on the programmer. This lack of restrictions and language-supported checking, however, can make C code unreadable and unmaintainable. Pascal is attractive since it provides strong type checking in a relatively elegant package but Pascal compilers don't produce efficient code. Turing Plus offers the advantages of both these languages, including efficient machine code and strong type checking. It also has a number of other features that make it a very attractive alternative. For example, Turing Plus offers controlled access to machine-dependencies, type checked separate compilation, linkage to external routines, language-specified concurrency and exception handling. Portable compilers with replaceable code generators (allowing easy access to cross-compilation) are available and a Turing Plus to C translator is under construction to allow fast portability to all systems supporting C compilers.
PS-Algol's device-independent output statement
Authors: Philbrow P. C. , Armour I. , Atkinson M. P. , Livingstone J.
Published: November 2005

We describe a language-level approach to device-independent output. The paper moves from an abstract discussion through to the provision of destinations for PS-algol's

print

statement. Some feedback from programmers is presented, and conclusions drawn.
How (not) to code a finite state machine
Authors: Jones D. W.
Published: November 2005

The standard advice for those coding a finite state machine is to use a while loop, a case statement, and a state variable. This is usually bad advice! The reasons for this are explored here, and better advice is formulated.
A perspective from industry
Authors: Christiaanse Vance
Published: November 2005

In Sun Microsystems' view of the future, embedded Java will run in everything from your personal computer to your alarm clock. Java's support for network communication would allow your hair dryer to warn your toaster to start breakfast. Will it happen? Will Java code be running all your household appliances someday or will it end up only in the trash compactor? Nobody knows, but here are some reasons to give it a look:
Code generation by coagulation
Authors: Karr Michael
Published: November 2005

This paper describes a new approach to code-generation. The central tenet is that there must be a more intimate coupling between register allocation and instruction selection than exists in present-day technology. This is achieved by generating code in very small regions and gradually coalescing the part of the program that is "compiled".
Sub-protocol-evaluators for attribute grammars
Authors: Farrow Rodney
Published: November 2005

This paper presents a new strategy for evaluating attribute grammars,
sub-protocol attribute evaluation,
and gives an algorithm for constructing sub-protocol-evaluators. Sub-protocol-evaluators can be built for any non-circular attribute grammar; this paper describes how to construct them for absolutely noncircular grammars [4]. Sub-protocol-evaluators are most easily understood as a simple optimization of another evaluator we call the
protocol-evaluator
. The protocol-evaluator has elements in common with the
tree-walk evaluator
of Kennedy-Warren [4] and with Nielson's
direct evaluator
[6]; it can be viewed as a refinement of each of these. Furthermore, the
uniform
AGs, proposed by Warren [9], and the
ordered
AGs, proposed by Kastens [3], are both subclasses of grammars for which especially efficient protocol-evaluators can be built.
Strongly non-circular attribute grammars and their recursive evaluation
Authors: Jourdan Martin
Published: November 2005

This paper is devoted to the construction of recursive evaluators for strongly non-circular attribute grammars. This class of attribute grammars is very large and includes every practical example ; testing strong non-circularity can be done in polynomial time. To each synthesized attribute, a function is associated, which takes as parameters a derivation tree and the values of some inherited attributes, and returns the value of that attribute at the root of the tree. These functions are mutually recursive according to the structure of the full parse tree. This method implements a dynamic "evaluation by need", reducing the number of attributes computed to those necessary to get the "semantic value" of the full tree. A Lisp implementation allowing automatic efficient storage management is also presented, together with some applications. Our work is closely related to those of Kennedy and Warren, Saarinen and Katamaya, but our method is more efficient and has a better theoretical basis.
Automatic generation of peephole optimizations
Authors: Davidson Jack W. , Fraser Christopher W.
Published: November 2005

This paper describes a system that automatically generates peephole optimizations. A general peephole optimizer driven by a machine description produces optimizations at compile-compile time for a fast, pattern-directed, compile-time optimizer. They form part of a compiler that simplifies retargeting by substituting peephole optimization for case analysis.
Analyzing and compressing assembly code
Authors: Fraser Christopher W. , Myers Eugene W. , Wendt Alan L.
Published: November 2005

This paper describes the application of a general data compression algorithm to assembly code. The system is retargetable and generalizes cross-jumping and procedural abstraction. It can be used as a space optimizer that trades time for space, it can turn assembly code into interpretive code, and it can help formalize and automate the traditionally ad hoc design of both real and abstract machines.
A specification language for one-pass semantic analysis
Authors: Koskimies Kai
Published: November 2005

A new language is introduced for the specification of semantic analysis of programming languages. The language is based on the concept of one-pass attribute grammars. Various extensions of this basic formalism are incorporated in the language, including disciplined global variables, facilities for symbol processing, and features supporting semantic error detection and recovery. To encourage the writing of declarative specifications the language is nonterminal-oriented, in contrast to the production-oriented languages traditionally used in compiler writing systems.
Tree transformation techniques and experiences
Authors: Keller S. E. , Perkins J. A. , Payton T. F. , Mardinly S. P.
Published: November 2005

A formal description technique for describing transformations from one well-defined language to another is introduced. A TT-grammar contains context-free grammars for describing the syntax of both languages. The transformation between the languages is described by a relationship of productions from the grammars. The TT-grammar is supported by an automated tool. SSAGS -- a translator writing system based on attribute grammars -- has been extended to support certain classes of TT-grammars. SSAGS analyzes TT-grammars and automatically generates Ada source programs implementing the transformation specified by the TT-grammar. Experience with two different restricted forms of TT-grammars is described with respect to their practical application. The experience demonstrates the readability, ease of development, and additional verification available through the use of TT-grammars.
An efficient implementation of visibility in Ada
Authors: Blower M. I.
Published: November 2005

This paper discusses the efficient implementation of Ada's visibility requirements. A scope stack and an unstructured name space are used to facilitate separate compilation and ensure that each Ada declaration takes a constant unit of time. Visibility issues affect practically every aspect of semantic analysis in Ada: declarations, statements, expressions, and separate compilation. The design of the symbol table package is, thus, a critical one. In this paper, I discuss the design goals of the symbol table for the Ada Integrated Environment (AIE) bootstrap compiler front end, and how they were influenced by the Ada language. Since the compiler is being heavily used by the AIE project, we have ample data with which to measure symbol table performance.
The Java syntactic extender (JSE)
Authors: Bachrach Jonthan , Playford Keith
Published: November 2005

The ability to extend a language with new syntactic forms is a powerful tool. A sufficiently flexible macro system allows programmers to build from a common base towards a language designed specifically for their problem domain. However, macro facilities that are integrated, capable, and at the same time simple enough to be widely used have been limited to the Lisp family of languages to date. In this paper we introduce a macro facility, called the Java Syntactic Extender (JSE), with the superior power and ease of use of Lisp macro sytems, but for Java, a language with a more conventional algebraic syntax. The design is based on the Dylan macro system, but exploits Java's compilation model to offer a full procedural macro engine. In other words, syntax expanders may be implemented in, and so use all the facilities of, the full Java language
Efficient subtyping tests with PQ-encoding
Authors: Zibin Yoav , Gil Joseph Yossi
Published: November 2005

Subtyping test
, i.e., determining whether one type is a subtype of another, are a frequent operation during the execution of object-oriented programs. The challenge is in encoding the hierarchy in a small space, while simulataneously making sure that subtyping tests have efficient implmentation. We present a new scheme for encoding multiple and single inheritance hierarchies, which, in the standardized hierarchies, reduces the footprint of all previsously published schemes. The scheme is called
PQ-encoding
after
PQ-trees
, a data structure previously used in graph theory for finding the orderings that satisfy a collection of constraints. In particular, we show that in the traditional object layout model, the extra memory requirement for single inheritance hierarchies is zero. In the PQ-encoding subtyping tests are constant time, and use only two comparisons. Other than PQ-trees, PQ-encoding uses several novel optimization techniques. These techniques are applicable also in improving the performance of otehr, previously published, encoding schemes.
Efficient implementation of Java interfaces
Authors: Alpern Bowen , Cocchi Anthony , Fink Stephen , Grove David
Published: November 2005

Single superclass inheritance enables simple and efficient table-driven virtual method dispathc. However, virtual method table dispatch does not handle multiple inheritance and interfaces. This complication has led to a widespread misimpression that interface method dispatch is inherently inefficient. This paper argues that with proper implementation techniques, Java interfaces need
not
be a source of significant performance degradation.