bluuebunny/crossref_metadata_2025 huggingface dataset:
A language design for vector machines
Authors: Basili V. R. , Knight J. C.
Published: November 2005

This paper deals with a programming language under development at NASA's Langley Research Center for the CDC STAR-100. The design goals for the language are that it be basic in design and able to be extended as deemed necessary to serve the user community, capable of the expression of efficient algorithms by forcing the user to make the maximum use of the specialized hardware design, and easy to implement so that the language and compiler could be developed with a minimum of effort. The key to the language was in choosing the basic data types and data structures. Scalars, vectors, and strings are available data types in the language. Each basic data type has an associated set of operators which consist primarily of the operations provided by the hardware. The only data structure in the language is a restricted form of the array. Only vector and string data types may be stored in arrays, forcing the user to vectorize scalar data when it is necessary to structure it. This permits the most effective use of the machine for entities such as real arrays since the high level vector machine instructions may be used to deal with them directly.
Fortran for the Texas Instruments ASC system
Authors: Wedel Dorothy
Published: November 2005

The ASC Fortran compiler and the methods of optimizing the execution times of compiled programs are described. Language extensions and compiler organization are briefly outlined. Traditional scalar optimization techniques and techniques to detect and generate vector operations from ANS standard Fortran source code are discussed. Emphasis is placed on optimal generation of vector operations and parallel processing. The vector and parallel processing techniques described here are applicable to a wide variety of vector or parallel processing machines. Numerous examples are discussed to demonstrate many of the capabilities and features of the compiler.
Array operations in MU5
Authors: Capon P. C. , Ibbett R. N.
Published: November 2005

In this paper the operation of the machine on code compiled for typical array operations is discussed. The performance of programs written in this straight forward way is compared with the possible gain through using hardware array orders within the MU5 framework. It is necessary to first outline the MU5 order code.
Lexical analysis and parsing techniques for a vector machine
Authors: Donegan Michael K. , Kartzke Stuart W.
Published: November 2005

The use of vector oriented hardware for compilation places a special burden on the compiler writer to make use of vector operations whenever possible. This paper presents various techniques for lexical analysis and parsing using the CDC STAR-100 instruction set. Although the similarity between APL and the STAR is apparent, previous techniques developed by Lincoln and others using APL as a base cannot be used directly on the STAR. Difficulties involved in implementing such methods occur because of the non-uniform treatment of vectors of different types on the STAR as opposed to a very uniform treatment in APL. The relevant features of the STAR-100 are discussed after which techniques are described for performing lexical analysis of a source text. The goal is to reduce the text to a set of tokens of unit length. Finally some parsing methods are suggested.
Problem formulation using array processing techniques
Authors: Evans D. J.
Published: November 2005

This paper outlines the evolution of array processing computational techniques and systems and briefly discusses the important concepts of the software and programming strategies which enable these systems to be used effectively.

For very large problems, the advantages of parallel processing techniques are stressed and the use of a mathematical programming array language outlined for removing some of the arbitrariness from the problem formulation and programming stages of solving partial differential equations. The purpose of the proposed approach is to eliminate errors in the logical formulation early in the design of a large scientific program and hence prevent many of the logical errors that can creep into a program because of its sheer size and complexity. The discussion includes the solution of both boundary and initial value scientific problems using an approach in which APL augments FORTRAN in the problem formulation stage.
The software reliability game
Authors: Davis Ruth M.
Published: November 2005

The meaning of software reliability and the problems involved in attaining reliable software are examined from three perspectives: customer, producer, and user. The impact of reliable software on the public at large is discussed, emphasizing the importance of safeguarding the individual's right to privacy. Finally, the government's contribution to improving software quality is presented.
Guarded commands, non-determinacy and a calculus for the derivation of programs
Authors: Dijkstra Edsger W.
Published: November 2005

So-called “guarded commands” are introduced as a building block for alternative and repetitive constructs that allow non-deterministic program components for which at least the activity evoked, but possibly even the final state, is not necessarily uniquely determined by the initial state. For the formal derivation of programs expressed in terms of these constructs, a calculus will be shown.
The impact of language design on the production of reliable software
Authors: Gannon J. D. , Horning J. J.
Published: November 2005

The language in which programs are written can have a substantial effect on their reliability. This paper discusses the design of programming languages to enhance reliability. It presents several general design principles, and then applies them to particular language constructs. Since we can not logically prove the validity of such design principles, empirical evidence is needed to support or discredit them. Gannon has performed a major experiment to measure the effect of nine specific language design decisions in one context. Analysis of the frequency and persistence of errors shows that several decisions had a significant impact on reliability.
On the problem of uniform references to data structures
Authors: Geschke C. M. , Mitchell J. G.
Published: November 2005

The cost of a change to a large software system is often primarily a function of the size of the system rather than the complexity of the change. One reason for this is that programs which access some given data structure must operate on it using notations which are determined by its exact representation. Thus, changing how it is implemented may necessitate changes to the programs which access it. This paper develops a programming language notation and semantic interpretations which allow a program to operate on a data object in a manner which is dependent only on its logical or abstract properties and independent of its underlying concrete representation.
Organizing tests during software evolution
Authors: Cicu A. , Maiocchi M. , Polillo R. , Sardoni A.
Published: November 2005

This paper describes the structure and expounds the underlying motivations of the 'Testing System' which is presently being designed and experienced in testing the Honeywell GCOS Level 62 operating system. TS is a hierarchical system in which two main levels are individuated: tests and 'testing structures'. The former are automatic 'system exercisers' - either 'testing programs' and 'testing units' at JCL level; the latter are hierarchically organized 'catalogues', allowing the management of testing activities through the use of automatic tools.
Automated generation of testcase datasets
Authors: Miller E. F. , Melton R. A.
Published: November 2005

Software quality enhancement can be achieved in the near term through use of a systematic program testing methodology. The methodology attempts to relate functional software testcases with formal software specifications as a means to achieve correspondence between the software and its specifications. To do this requires generation of appropriate testcase data.

Automatic testcase generation is based on
a priori
knowledge of two forms of internal structure information: a representation of the tree of subschema automatically identified from within each program text, and a representation of the iteration structure of each subschema. This partition of a large program allows for efficient and effective automatic testcase generation using straightforward backtracking techniques.

During backtracking a number of simplifying, consolidating, and consistency analyses are applied. The result is either (1) early recognition of the impossibility of a particular program flow, or (2) efficient generation of input variable specifications which cause the testcase to traverse each portion of the required program flow.

A number of machine output examples of the backtracking facility are given, and the general effectiveness of the entire process is discussed.
New assertion concepts for self-metric software validation
Authors: Stucki Leon G. , Foshee Gary L.
Published: November 2005

Automated tools and structured programming techniques are in use on a variety of scientific and business application programming projects within the McDonnell Douglas Corporation. An examination of the resulting programs reveals certain development and maintenance characteristics that suggest new and very interesting applications for automated tools.

An extension of PET (a currently operational McDonnell Douglas validation tool for FORTRAN) to include a user embedded assertion capability offers a step in the direction of automatically verifying the dynamic execution of programs. A user-oriented local and global assertion capability is introduced and its implementation is discussed.

Application of these tools within a well-conceived structured programming environment offers a positive step forward in the development of more reliable software systems.
Some experience with automated aids to the design of large-scale reliable software
Authors: Boehm B. W. , McClean R. K. , Urfrig D. B.
Published: November 2005

This paper summarizes some recent experience in analyzing and eliminating sources of error in the design phase of large software projects. It begins by pointing out some of the significant differences in software error incidence between large and small software projects. The most striking contrast, illustrated by project data, is the large preponderance of design errors over coding errors on large-scale projects, not only with respect to numbers of errors, but also with respect to the relative time and effort required to detect them and correct them.

The paper next presents a taxonomy of software error causes, and some analyses of the design error data, performed to obtain a better understanding of the nature of large-scale software design errors and to evaluate alternative methods of preventing, detecting, and eliminating them.

Based on this analysis of observational data, a hypothesis was derived regarding the potential cost-effectiveness of an automated aid to detecting inconsistencies between assertions about the nature of inputs and outputs of the various elements (functions, modules, data bases, data sources, etc.) of the software design. This hypothesis was tested by developing a prototype version of such an aid, the Design Assertion Consistency Checker (DACC), using TRW's Generalized Information Management (GIM) system, and using it on a large-scale software project with 186 elements and 967 assertions about their inputs and outputs.

Of the 121,000 possible mismatches between input and output assertions, DACC found 818, at a cost in computer time of $30. Most of the mismatches resulted from shortfalls in the initial version of DACC or the initial data preparation, such as a lack of a synonym capability and a lack of a explicit statements about external inputs and outputs. However, a number of serious mismatches were exposed at a time when they were easy to correct, and a most useful work-list generated of items needing resolution before allowing the design effort to proceed to further detail.

In general, the data confirmed the hypothesis about the general utility of a DACC capability for large software projects. However, a number of additional features should be considered to compensate for current deficiencies (in areas such as manuscript preparation) and to fully take advantage of having the software design in machine-readable form.
Structured programming in a production programming environment
Authors: Baker F. T.
Published: November 2005

This paper discusses how structured programming methodology has been introduced into a large production programming organization using an integrated but flexible approach. It next analyzes the advantages and disadvantages of each component of the methodology and presents some quantitative results on its use. It concludes with recommendations based on this generally successful experience, which could be useful to other organizations interested in improving reliability and productivity.
A many-state Markov model for the estimation and prediction of computer software performance parameters
Authors: Trivedi Ashok K. , Shooman Martin L.
Published: November 2005

A many-state Markov model has been developed for the purpose of providing various performance criteria for computer software. The software system under consideration is assumed to be fairly large, of the order of 10
5
words of code, so that statistical deductions become meaningful, and is assumed to initially contain an unknown number of unknown bugs. The model provides estimates and predictions of the most probable number of errors that will have been corrected at a given time t in the operation of this software package based on preliminary modeling of the error occurrence rate λ as well as the error correction policy μ. The model also provides predictions for the availability A(t) and for the reliability R(t) of the system. The differential equations corresponding to the Markov model are solved for the case when λ and μ are constant using an exact (closed-form) solution. The numerical solution is also obtained for this case for verification and demonstrative purposes. The more interesting and important case, from an applications point of view, is that when λ and μ are not constant, but rather functions of the state of debugging achieved. This case is solved numerically only, since the exact solution is cumbersome. It is also demonstrated that the numerical solution is superior to the so-called exact solution. Finally, some extensions and modifications of the basic Markov model are briefly discussed.
Reliability experience with Chi/OS
Authors: Lynch W. C. , Langner J. W. , Schwartz M. S.
Published: November 2005

The Chi/OS operating system, the latest large scale software effort of Chi Corporation, has had an excellent reliability record since its installation in November, 1973. Although the system design is vital to the reliability of Chi/OS, several environmental factors are equally vital. After a brief presentation of the substantial work load supported by Chi/OS, this paper deals with those environmental factors which contribute to the reliability of the software.
Structured specification of a Security Kernel
Authors: Walter K. G. , Schaen S. I. , Ogden W. F. , Rounds W. C. , Shumway D. G. , Schaeffer D. D. , Biba K. J. , Bradshaw F. T. , Ames S. R. , Gilligan J. M.
Published: November 2005

Certifying an entire operating system to be reliable is too large a task to be practicable. Instead, we are designing a Security Kernel which will provide information security. The kernel's job is to monitor information flow in order to prevent compromise of security.

Sound design is encouraged by using a technique called
Structured Specification
, in which successively more detailed models of the Security Kernel are developed. The initial model, M
0
, is an abstract description which formalizes governmental security applied to computer systems.

Subsequent levels of modeling provide increasingly more detail, and gradually the models begin to resemble a particular system (Multics in this case). The second model, M
1
, defines a tree-structured file system, and an interagent communication system while M
2
adds details concerning segmentation in a dynamic environment.

It is intended that the final level of modeling will specify the primitive commands for the kernel of a Multics-like system and will enumerate precisely those assertions which must be proved about the implementation in order to establish correctness.
The purpose of concurrent Pascal
Authors: Hansen Per Brinch
Published: November 2005

This is the first of three papers that describe a new programming language for structured programming of computer operating systems [1, 2, 3]. It extends the sequential programming language Pascal with concurrent programming tools called processes and monitors. These concepts are explained informally by means of pictures that illustrate a hierarchical design of a simple spooling system. The main contribution of Concurrent Pascal is to extend the monitor concept with an explicit hierarchy of access rights to shared data structures that can be stated in the program text and checked by a compiler.

[1]Brinch Hansen, P. The purpose of Concurrent Pascal. Information Science, California Institute of Technology, November 1974.

[2]Brinch Hansen, P. The use of Concurrent Pascal. Information Science, California Institute of Technology, November 1974.

[3]Brinch Hansen, P. Job control in Concurrent Pascal. Information Science, California Institute of Technology. November 1974.
Constructing correct and efficient concurrent programs
Authors: Sintzoff Michel , Lamsweerde Axel Van
Published: November 2005

A method is presented for programming correct and efficient cooperation in a set of sequential modules, on the basis of an invariant assertion, by means of formal and static deductions. For each sequential module, the pre- and post-assertions are computed from the invariant. Whereas the pre-assertion gives the synchronizing condition required before execution in order to preserve the invariant, the post-assertion expresses the “contribution” of this execution. Other assertions, called firing conditions, are derived which connect that contribution to the needs of waiting processes as expressed in their synchronizing conditions. A sequential module and its synchronizing and firing conditions are then integrated in a high-level synchronizing construct close to conditional critical regions, but allowing explicit control over the synchronizing conditions to be reevaluated at the exit for process resumption. Three levels of static elimination of useless condition reevaluations are then presented. These eliminations essentially use the information contained in firing conditions; they are shown to preserve partial correctness. The combined use of the notation and of the techniques proposed is illustrated through three examples.
How to write correct programs and know it
Authors: Mills Harlan D.
Published: November 2005

There is no foolproof way to ever know that you have found the last error in a program. So the best way to acquire confidence that a program has no errors is never to find the first one, no matter how much it is tested and used. It is an old myth that programming must be an error-prone, cut-and-try process of frustration and anxiety. The new reality is that you can learn to consistently write programs which are error free in their debugging and subsequent use. This new reality is founded in the ideas of structured programming and program correctness, which not only provide a systematic approach to programming but also motivate a high degree of concentration and precision in the coding subprocess.
The effect of certain modular design principles on testability
Authors: Edwards N. P.
Published: November 2005

This paper is a nonprogrammers view of design principles which are considered essential to testability of complex structures. The principles are related to the programming problem.

The basic problems in verifying the function of any complex structure derive from: inadequate specification of function, the very large number of possible structures (most of which are “mistakes”) and the very large number of possible outputs for specified and unspecified inputs.

Present trends in programming techniques are towards various forms of controlled modularity. If modularity is controlled so that the function of a module is independent of the source of its input, the destination of its output, and the past history of use of the module, the difficulty of testing the modules and structures assembled from the modules is greatly reduced. Multilevel modularity also powerfully reduces the complexity of modules and structures. Controlled modularity requires that the separation of certain variables be rigorously maintained. Controlled branching also reduces complexity and testing requirements. These are examined with mathematical examples and it is concluded that if the proper principles of controlled modularity are observed, it should be technically feasible to design software to achieve specified function and that under certain conditions it should be economically feasible to test software so designed to practical levels of accuracy and reliability.
Verifying programs which operate on data structures
Authors: Laventhal Mark S.
Published: November 2005

In order to prove the correctness of a computer program, one must be able to characterize the data in the program. Proofs by the inductive assertion method require the construction of concise, precise assertions to describe the data. This paper presents some techniques for characterizing data structures which can be used to build adequate assertions. New primitive relations are introduced for describing intra-structural relationships. These primitives form the basis for two important concepts: The invariant of a structure is a concise characterization of a structural class. A representation function is a mapping from a structure to a corresponding abstract data object; this concept provides a means for expressing relationships between a structure and other data, and among the values of a structure over time. By means of verification lemmas, these concepts can be integrated into proofs of correctness, and the proofs as well as the assertions can be dramatically simplified. An example program is presented which demonstrates the use of these concepts in constructing the assertions, and the resulting proof of correctness is outlined.
Proving structured programs correct, level by level
Authors: Infante R. , Montanary U.
Published: November 2005

Structured programs are developed and documented using levels of “virtual machines”. Problem-oriented data structures and primitives, at each level, are programmed in terms of those at the immediately lower level, until available programming constructs are reached. We suggest to extend this technique to assertions by expanding the involved predicates level by level. Using some “level axioms” We want to be able to prove any given level correct without looking at any further expansion of the primitive predicates at that level. The advantages are: i) The programmer may use problem-oriented predicates in the assertions; ii) the demand posed on the theorem prover (if any) is very limited; iii) it is possible to replace the levels not yet programmed with functionally different routines, provided the predicates are also expanded consistently
.
System structure for software fault tolerance
Authors: Randell B.
Published: November 2005

The paper presents, and discusses the rationale behind, a method for structuring complex computing systems by the use of what we term “recovery blocks”, “conversations” and “fault-tolerant interfaces”. The aim is to facilitate the provision of dependable error detection and recovery facilities which can cope with errors caused by residual design inadequacies, particularly in the system software, rather than merely the occasional malfunctioning of hardware components.
Design of self-checking software
Authors: Yau S. S. , Cheung R. C.
Published: November 2005

This paper discusses different techniques for constructing a piece of self-checking software for systems where ultra-reliability is required. Self-checking software can be designed to detect software errors, to locate and to stop the propagation of software errors, to assist in the recovery from errors and to verify the integrity of the system. Self-checking techniques can be implemented in the program to check the function, the control sequence and the data of a process. The functional aspects of a process can be monitored to detect infinite loops, incorrect loop terminations, illegal branches and wrong branches. The validity of data of a process can be assured by performing checks on the integrity of data values, the integrity of data structures and the nature of data values. These self-checking capabilities should be implemented during the initial stage of program development. The cost-effectiveness of each technique in the particular operating environment should be evaluated. Only the most cost-effective techniques should be retained and overhead can be reduced considerably by implementing these techniques in hardware.
Some transformations for developing recursive programs
Authors: Burstall R. M. , Darlington John
Published: November 2005

The paper describes a system of rules for transforming programs, the programs being in the form of recursion equations. The idea is to start with a very simple, lucid and hopefully correct program, then to transform it into a more efficient one by altering the recursion structure. Illustrative examples of program transformations are given, and a tentative implementation is described. We hope to throw some light on the alternative structures for programs, also to indicate a possible initial phase for an automatic or semi-automatic program manipulation system.
Toward a theory of test data selection
Authors: Goodenough John B. , Gerhart Susan L.
Published: November 2005

This paper examines the theoretical and practical role of testing in software development. We prove a fundamental theorem showing that properly structured tests are capable of demonstrating the absence of errors in a program. The theorem's proof hinges on our definition of test reliability and validity, but its practical utility hinges on being able to show when a test is actually reliable. We explain what makes tests unreliable (for example, we show by example why testing all program statements, predicates, or paths is not usually sufficient to insure test reliability), and we outline a possible approach to developing reliable tests. We also show how the analysis required to define reliable tests can help in checking a program's design and specifications as well as in preventing and detecting implementation errors.
Data reliability
Authors: Hoare C.A. R.
Published: November 2005

This paper surveys the problems of achieving data reliability, and finds them more severe than those of program reliability. It then outlines some of the conceptual and methodological tools which are available for the solution of these problems, including the concept of type, direct product, union, sequence, recursion and mapping. It touches on the topdown design of data and programs, and argues that references or pointers are to be avoided. It concludes with an annotated bibliography for further reading.
Correctness concerns and, among other things, why they are resented
Authors: Dijkstra Edsger W.
Published: November 2005

According to Webster's definition of a tutorial: “a paper and esp. a technical paper written to give practical information about a specific subject”, this paper is
not
worthy of the name “tutorial”, because I would never describe what I intend to do as “giving practical information”. On the contrary: I intend to give as little “practical information” as I possibly can. I am not going to enumerate facts, results and theories, for those you can find—in abundance, I am tempted to add—in the published literature. What I do hope to achieve, however, is helping you to understand and evaluate those facts, results and theories when you encounter them in the literature. I intend to do so by providing you with a historical perspective, be it—in more than one sense—a partial one. It is a lucky circumstance that the amateur historian, like myself, can always come away with very few facts: the fewer the facts, the greater our freedom of interpretation, and it is that freedom that I intend to enjoy.

For a short while we have to go back to the scientific climate at the beginning of this century, for there we seem to find the roots of the philosophical opinions that prevailed a few decades later. And these philosophical opinions, in turn, seem to be the source of today's tacit assumptions. By being tacit, these assumptions tend to escape being challenged and that is bad, because they are third-generation off-spring of scientific hopes that, in the mean time, have been shown to have been unjustified, they express everyman's image of a goal that, in the mean time, has been proved to be unattainable.
Gypsy
Authors: Ambler Allen L. , Good Donald I. , Browne James C. , Burger Wilhelm F. , Cohen Richard M. , Hoch Charles G. , Wells Robert E.
Published: November 2005

An introduction to the Gypsy programming and specification language is given. Gypsy is a high-level programming language with facilities for general programming and also for systems programming that is oriented toward communications processing. This includes facilities for concurrent processes and process synchronization. Gypsy also contains facilities for detecting and processing errors that are due to the actual running of the program in an imperfect environment. The specification facilities give a precise way of expressing the desired properties of the Gypsy programs. All of the features of Gypsy are fully verifiable, either by formal proof or by validation at run time. An overview of the language design and a detailed example program are given.
Efficient implementation and optimization of run-time checking in PASCAL
Authors: Fischer Charles N. , LeBlanc Richard J.
Published: November 2005

Complete run-time checking of programs is an essential tool for the development of reliable software. A number of features of the programming language PASCAL (arrays, subranges, pointers, record variants (discriminated type unions), formal procedures, etc.) can require some checking at run-time as well as during compilation. The problem of efficiently implementing such checking is considered. Language modifications to simplify such checking are suggested. The possibility of optimizing such checking is discussed.
A study of protection in programming languages
Authors: Ambler Allen L. , Hoch Charles G.
Published: November 2005

The concept of “protection” in programming languages refers to the ability to express directly in the language the desired access control relationships for all objects defined in the language. The use of such mechanisms as
data types, scope, parameter passing
mechanisms,
routines as parameters, abstract data types,
and
capabilities
in Pascal, Concurrent Pascal, Euclid, Clu, and Gypsy are explored via a simple example which embodies many protection problems. The usefulness of language defined and enforced protection mechanisms to the process of formal verification is discussed.
Static determination of dynamic properties of generalized type unions
Authors: Cousot Patrick , Cousot Radhia
Published: November 2005

The classical programming languages such as PASCAL or ALGOL 68 do not provide full data type security. Run-time errors are not precluded on basic operations. Type safety necessitates a refinement of the data type notion which allows subtypes. The compiler must also be able to ensure that basic operations are applicable. This verification consists in determining a local subtype of globally declared variables or constants. This may be achieved by improved compiler capabilities to analyze the program properties or by language constructs which permit the expression of these properties. Both approaches are discussed and illustrated by the problems of access to records via pointers, access to variants of record structures, determination of disjoint collections of linked records, and determination of integer subrange. Both approaches are complementary and a balance must be found between what must be specified by the programmer and what must be discovered by the compiler.
Language features for process interaction
Authors: Andrews Gregory R. , McGraw James R.
Published: November 2005

Languages for parallel programming should meet four goals: expressiveness, data integrity, security, and verifiability. This paper presents a set of language features for describing processes and process interaction, gives examples of their use, and briefly discusses their relation to the goals. Two constructs, resources and protected variables, are introduced as the mechanisms for describing interaction. Resources are extensions of the monitor concept of Hoare; protected variables are global variables which can only be accessed by one process at a time. Two types of access control are introduced: restrictions on scope rules for static access, and capabilities for dynamic access. Examples include the interface to machine devices, files and virtual devices, readers/writers, device scheduling, device reservation, and buffer allocation.
Process structuring, synchronization, and recovery using atomic actions
Authors: Lomet D. B.
Published: November 2005

This paper explores the notion of an atomic
action
as a method of process structuring. This notion, first introduced explicitly by Eswaren et al [6] in the context of data base systems, reduces the problem of coping with many processes to that of coping with a single process within the atomic
action
. A form of process synchronization, the
await
statement, is adapted to work naturally with atomic actions. System recovery is also considered and we show how atomic actions can be used to isolate recovery action to a single process. Explicit control of recovery is provided by a
reset
procedure that permits information from rejected control paths to be passed to subsequent alternative paths.
Abstraction and verification in Alphard
Authors: Shaw Mary , Wulf Wm A. , London Ralph L.
Published: November 2005

The Alphard
form
provides the programmer with a great deal of control over the implementation of abstract data types. In this paper we extend the abstraction techniques from simple data representation and function definition to the
iteration statement
, the most important point of interaction between data and the control structure of the language itself. We introduce a means of specializing Alphard's loops to operate on abstract entities without explicit dependence on the representation of those entities. We develop specification and verification techniques that allow the properties of the
generators
for such iterations to be expressed in the form of proof rules. We obtain results for common special cases of these loops that are essentially identical to the corresponding constructs in other languages. We also provide a means of showing that a generator will terminate.
Graph attribution with multiple attribute grammers
Authors: Rohrich J.
Published: November 2005

Attributed graphs are well suited to represent structured sets of data objects. A multiple attribute grammar (MTAG) consists of several attribute grammars that describe an attributed graph as a union of attributed trees. Thus, from an MTAG one can automatically generate attribute evaluators for graphs. Dependency analysis at generation time of the attribute evaluator leads to fast attribute evaluation, and to significant space savings due to attribute overlay.
Editing IDL data structures
Authors: Persch G.
Published: November 2005

We describe an editing facility influenced by programming languages and abstract data types which allows to inspect and manipulate arbitrary data structures. Starting from a graph-like data model, the editor has a powerful command language which allows to iterate over subgraphs or subsets of the nodes. The editor has been successfully used for rapid tool construction and user friendly debugging of several large data structures, including the intermediate language DIANA and the project library of our Ada compiler.
Relationship between IDL and structure editor generation technology
Authors: Feiler P. H.
Published: November 2005

This paper discusses observed commonalities and differences between IDL and structure editor generation technologies. IDL (Interface Description Language) is technology for generation of tool intercommunication support with roots in compiler generation. Structure editor generation technology has its roots in syntax-directed editors. It produces environments for interactive viewing and manipulation of formally specified structures. Both technologies use a formal notation for structural and constraint descriptions. From these descriptions both generation tools automatically produce software for reading, writing, and manipulating instances of the described structures, as well as for checking specified constraints on information contained in the structures. The IDL technology emphasizes generation of batch---oriented applications while the structure editor generation technology is tailored to supporting interactive applications. Structure editor generation technology has been applied to itself, i.e., to building an interactive structure editor generation environment.
Benchmark semantics
Authors: Ponder Carl G.
Published: November 2005

Be careful when interpreting benchmark measurements that compare two languages or two implementations of the same language. A program expressed in two different languages rarely computes the exact same function in both cases. The same goes for a program run on two different implementations of the same language. The implementation details ultimately affect the language semantics as well as the benchmark performance. Here are some simple examples of this effect.
Approximations for the Halstead software science software error rate and project effort estimators
Authors: Schneider Victor
Published: November 2005

Experimental estimators are presented relating the expected number of software errors (B) in a software development project tothe overall reported months of programmer effort for the project (E)the number of subprograms (n)the count of thousands of coded source statements (S)These estimators areB ≈ 7.6 E
0.667
S
0.333
andB ≈ n ((S/n)/.047)
1.667
These estimators are shown to be consistent with data obtained from the air force Rome air development center, the naval research laboratory, and Fujitsu corporation. It is suggested here that more data is needed to refine these estimators further.
MS-DOS Prolog implementations revisited
Authors: Berghel Hal , Rankin Richard , Bhatia Sanjiv
Published: November 2005

In an earlier article [11] we proposed a taxonomy for classification of PROLOG implementations. This analysis has been used by ourselves [1], [3], [11] and others [6] in evaluation of current microcomputer-based products. However, it has become out of date for several reasons. First, PROLOG has matured to the point where the language kernels have become comparable in functionality. Thus, many of the features which distinguished products a few years ago no longer do so. Conversely, increasing attention is being paid to extra-and metalogical support, so that there are now features which are distinguishing which were not, only a few years back. It is now quite reasonable to expect a PROLOG implementation to support graphics, virtual memory, modularization, and so forth. Thus, we offer a revision which is more in keeping with the current PROLOG offerings.
Clarify function!
Authors: Anand N.
Published: November 2005

The biggest obstacle in understanding large software systems is the sheer quantity of information that has to be explicitly remembered by a programmer. Our ability to understand a system directly determines the ease with which it can be modified, maintained or extended; programmers are hence in need of techniques which, when applied, result in systems that can be understood quickly and effectively. In this paper, some practical techniques for constructing such "highly understandable" systems are presented. The paper starts with an analysis of how we humans understand a system --- it is demonstrated that we do so by identifying the functions of various entities in it. On the basis of this important observation, the argument for naming entities by the function that they perform is developed. Some concrete rules for naming procedures, variables, pointers, etc. are subsequently suggested and the reasons why these rules should obviate the need to remember are explored. We further argue why inability to name according to the given criteria should be interpreted as an indication of poor quality of the system. Thus, we conclude that the way to construct systems that can be understood quickly and effectively is to name entities in the system by the function that they perform.
Spreadsheet language level: how high is it?
Authors: Kokol Peter
Published: November 2005

In this paper we briefly describe most important features of the spreadsheet software. Then we present an algorithm for measuring its Halstead's language level. Finaly we analyse the obtained measures.
Issues and solutions
Authors: Klee Karl J.
Published: November 2005

With the advent of the World Wide Web, my teaching and my students' learning have become more interdisciplinary. In teaching the computer literacy course at Jamestown Community College, we include researching on the Internet. An assignment that I require of students is a short term paper on a computer-related topic, using references
only
from the Web. Recent topics that students have chosen include: computer security, computer viruses, computers and the disabled, computers in the medical field, configuring a computer system, and artificial intelligence. Students have found this assignment to be very useful relative to researching topics for their other courses. They were particularly impressed by how up-to-date the information was on the Web (verses books) and the ease with which they could extend their searches with the use of the hypertext links.
Computer skills
Authors: Janik Kathleen
Published: November 2005

In today's business world everyone needs computer skills. I was a Political Science major at Gettysburg College, and when I graduated this past spring I found that may computer proficiency was one of my most marketable skills.
Parallel processing
Authors: Fisher Joseph A. , Ellis John R. , Ruttenberg John C. , Nicolau Alexandru
Published: November 2005

Multiprocessors and vector machines, the only successful parallel architectures, have coarse-grained parallelism that is hard for compilers to take advantage of. We've developed a new fine-grained parallel architecture and a compiler that together offer order-of-magnitude speedups for ordinary scientific code.
Compiler prototyping using formal semantics
Authors: Pleban Uwe F.
Published: November 2005

The descriptive techniques of formal semantics can be used for the generation of complete prototype compilers. First, we review the essential characteristics of such semantics implementation systems, and discuss our experience with two existing experimental systems. Then, we show how to derive a complete conventional compiler for a small language from its denotational semantics. The compiler is specified in three phases consisting of a front-end (parser, tree builder, and semantic checker), a translator from syntax trees to prefix code, and a code generator which converts the prefix code into IBM/370 style assembly code. The translator component is obtained by modifying the standard semantics of the language in two steps: first, the semantic domains and the equations are rewritten in a straight forward way to achieve a normal form, and then the auxiliary semantic functions are interpreted as instructions for a prefix code machine. The entire three part specification has been implemented with the help of Paulson's semantics processing system.
Incremental compilation in Magpie
Authors: Schwartz Mayer D. , Delisle Norman M. , Begwani Vimal S.
Published: November 2005

Magpie is an interactive, integrate programming environment that supports the development of Pascal programs a powerful, single-user workstation. Incremental compilation techniques are used to provide quick feedback on static errors and to ensure that a program is always ready for execution even while it is being edited. Magpie performs syntax and static semantic analysis with the unit of incrementality of a single character. Magpie uses incremental compilation to achieve performance levels that allow Pascal to be used interactively and as its own debugging language.
Incremental data flow analysis in a structured program editor
Authors: Zadeck Frank Kenneth
Published: November 2005

For many years, the generally accepted methods for solving global data flow analysis problems (GDFAPs) have relied on the
bit vector paradigm
[Alle 70] [Kenn 81]. In these algorithms, the information for each variable is represented as a position in a bit vector. These vectors are propagated from node to node during the analysis of the program.This paper investigates a different paradigm for solving GDFAPs. In this strategy, the data flow solution for each variable is computed independently. A new algorithm for solving some GDFAPs is presented here. While it is expected that this algorithm will run slower in the batch compiling environment, there are conditions under which this algorithm can be expected to be superior to those in the bit vector class.
An approach to incremental compilation
Authors: Reiss Steven P.
Published: November 2005

This paper describes an approach to incremental compilation that allows a complete incremental compiler to be generated from a simple language description. This description is in two parts. The first consists of an abstract syntax annotated with a powerful language for specifying the local semantics. The second consists of separate specifications detailing the uses of symbols, data types and expressions in the language. The approach operates in two stages. The first stage builds a local model of the semantics. The second propagates local changes into a global semantics. This approach has been used as part of the PECAN system for generating program development environments at Brown University.
A semantic prototyping system
Authors: Wand Mitchell
Published: November 2005

We have written a set of computer programs for testing and exercising programming language specifications given in the style of denotational semantics. The system is built largely in Scheme 84, a dialect of LISP that serves as an efficient lambda-calculus interpreter. The system consists of:• a syntax-directed transducer, which embodies the principle of compositionality,• a type checker, which is extremely useful in debugging semantic definitions, and• an interface to the
yacc
parser-generator, which allows the system to use concrete syntax rather than the often cumbersome abstract syntax for its programs.In this paper, we discuss the design of the system, its implementation, and discuss its use.
Register allocation by priority-based coloring
Authors: Chow Frederick , Hennessy John
Published: November 2005

The classic problem of global register allocation is treated in a heuristic and practical manner by adopting the notion of priorities in node-coloring. The assignment of priorities is based on estimates of the benefits that can be derived from allocating individual quantities in registers. Using the priorities, the exponential coloring process can be made to run in linear time. Since the costs involved in register allocation are taken into account, the algorithm does not over-allocate. The algorithm can be parameterized to cater to different fetch characteristics and register configurations among machines. Measurements indicate that the register allocation scheme is effective on a number of target machines. The results confirm that, using priority-based coloring, global register allocation can be performed practically and efficiently.