bluuebunny/crossref_metadata_2025 huggingface dataset:
Formal development of correct algorithms
Authors: Jones C B
Published: November 2005

This paper contains the formal development of a correct algorithm from an implicit definition of the task to be performed. Each step of the development can be accompanied by a proof of its correctness. As well as ensuring the correctness of the final program, the structured development gives considerable insight into the algorithm and possible alternatives. The example used is a simplified form of the recognition algorithm due to Earley.
METAPI - a language for extensions
Authors: Chandler Gerald D.
Published: November 2005

The METAPI system [1,2] can be considered to be a combination of a translator writing system and an extensible language system. The history and usage of the system should make clear how it functions in both roles.

METAPI grew from the need for a language in which a version of Fortran especially suited for interactive use could be implemented. Originally METAPI consisted of a translator writing system based on the Schorre [3] META II system. It was enhanced during implementation of PIFOR*, our Fortran language. It turned out that METAPI could be incorporated on an equal footing with PIFOR in the interactive system. Thus METAPI became a language for extensions since it was dynamically available. A user of the PI system, which incorporates METAPI and PIFOR can extend his language by writing statements in METAPI and can create any new statement type he wants. It is arbitrary whether these new statement types are considered to be a Fortran type or a METAPI type since in the PI system both languages are so closely intertwined.

The PI implementations are examples of the usual applications of a translator writing system. A simple example of an extension would be a shift operator which can be added to PIFOR with a single short line of METAPI code.
An implementation of ECL data types
Authors: Brosgol Benjamin M.
Published: November 2005

The data-type definition scheme in ECL is designed to furnish its users with a natural notation, in which the composition and behavior of complex objects can be readily described, and which simultaneously produces efficient underlying representations. The purpose of this paper is to discuss how these objectives are met in the implementation of ECL on Harvard's PDP-10.

Section II outlines the fundamentals of data definition in ECL. For a full discussion of the ECL programming system and its language component, the reader is referred to [1], [2], or [4]; an overview of the system is presented in a companion paper by Wegbreit [5]. A complete description of ECL's data extension mechanism is given in [1] and [3].

Section III presents the main features of the implementation of the ECL data definition scheme, discusses the “mode compiler”, analyzes the internal representation chosen for data objects, and describes the efficiencies resulting from this representation.

Finally, section IV deals with some of the interfaces between the data extension mechanism and the rest of the ECL system, and section V proposes some areas where further research would be useful.
Subroutine interface primitives for ETC
Authors: Dickman B. N.
Published: November 2005

Efficient coding for subroutine interfaces often implies, especially for system programmers, the passing of arguments in hardware registers, rather than on a system stack. This is a problem in an extendible compiler that allocates registers for itself and also allows programmers to use hardware registers (as well as memory locations) as variables. There is the added problem of standardizing the subroutine interface to reduce the possibility of using the subroutine incorrectly. This abstract discusses a solution to these problems.

The compiler for which the solution is intended is ETC[1], an extendible, macro-based, infix compiler designed to facilitate the production of very efficient code. Statements in the language may be freely mixed with machine operations, pseudo-operations, and macro calls. The extended language resembles FORTRAN. The base language consists of an assembler with a powerful macro facility [2] and a set of primitives, including operation, function and attribute definition, and limited register allocation.
Problems of PL/I for system programming
Authors: Hopkins Martin
Published: November 2005

A group within the Computer Science Department of the IBM T. J. Watson Research Center is now engaged in the design and development of System/A, an experimental operating system to support a variety of user activities with multiprocessing hardware. PL/I has been chosen as the system implementation language. Work with the language has shown that it is very good for system programming. However, there are problems. A number of minor annoyances can be circumvented rather easily but there are a few more basic problems which often stem from the fundamental concepts of PL/I.
Use of APL in microprogrammable machine modeling
Authors: Bingham Harvey W.
Published: November 2005

APL has long been a versatile language suitable for concise expression of digital processing algorithms. The availability of an interpretive version has permitted creation of executable models of entire soft, firm or hard machines. These APL models can both serve as formal functional descriptions, and as tools for insuring that various hardware realizations are functionally equivalent. A microprogrammable machine model is described. This model provides an easily extended machine that allows a microprogrammer to interactively develop the machine image characterizing his application. He can debug his microinstruction sequences with selective visibility to significant state changes under his control. Statistics gathering is automatic and new statistics are easily added. Examples of APL modeling at various levels are given. This model has been used prior to verification of microcode on actual hardware and for microprogram memory tradeoff analyses. APL has been particularly useful in non-numeric tasks related to software and hardware design.
Dynamically scoped functions as the essence of AOP
Authors: Costanza Pascal
Published: November 2005

The aspect-oriented programming community devotes lots of energy into the provision of complex static language constructs to reason about eventual dynamic properties of a program. Only the focus on a strongly dynamically-natured language construct reveals a very simple mechanism behind the notions of AOP. This paper shows that dynamically scoped functions, together with a simple additive to access previous function definitions, form the essence of aspect-oriented programming. We present a complete executable one page implementation of this idea.
Scripting the type inference process
Authors: Heeren Bastiaan , Hage Jurriaan , Swierstra S. Doaitse
Published: November 2005

To improve the quality of type error messages in functional programming languages,we propose four techniques which influence the behaviour of constraint-based type inference processes. These techniques take the form of externally supplied type inference directives, precluding the need to make any changes to the compiler. A second advantage is that the directives are automatically checked for soundness with respect to the underlying type system. We show how the techniques can be used to improve the type error messages reported for a combinator library. More specifically, how they can help to generate error messages which are conceptually closer to the domain for which the library was developed. The techniques have all been incorporated in the Helium compiler, which implements a large subset of Haskell.
From Hilbert space to Dilbert space
Authors: Mairson Harry G.
Published: November 2005

We give a tutorial and first-principles description of the
context semantics
of Gonthier, Abadi, and Lévy [5, 4], a computer-science analogue of Girard's
geometry of interaction
[3]. In the spirit of the invited presentation of Tom Knight (see this Proceedings [7]), the semantics is reversible, and supports pseudo-quantum computation via a superposed sharing of terms and evaluation contexts [2].Context semantics provides a mechanism for modelling ?-calculus, and more generally multiplicative-exponential linear logic (MELL); we explain the the call-by-name (CBN) coding of the ?-calculus, and sketch a proof of the correctness of
readback
, where the normal form of a ?-term is recovered from its semantics. This analysis yields the algorithmic correctness of Lamping's optimal reduction algorithm [8]. We relate the context semantics to linear logic types and to ideas from
game semantics
, used to prove full abstraction theorems for PCF and other ?-calculus variants [1, 6, 10]. Readback is essentially a game played by an environment (the Opponent) who wants to discover the
Böhm tree
(normal form) of a term known by a Player. A
type
plays the role---using the games jargon---of an
arena
of possible
moves
, and a
term
of that type provides a
winning strategy
for the Player, permitting the Player to respond correctly to moves made by the Opponent. The interaction between Opponent and Player describes a perfect flow analysis which answers questions like, "can call site a ever call procedure p?" The context semantics provides a low-level coding mechanism for describing such flows, the positions of subexpressions and head variables in Böhm trees, as well as moves in the above described two-player games.
A theory of aspects
Authors: Walker David , Zdancewic Steve , Ligatti Jay
Published: November 2005

This paper define the semantics of MinAML, an idealized aspect-oriented programming language, by giving a type-directed translation from its user-friendly external language to its compact, well-defined core language. We argue that our framework is an effective way to give semantics to aspect-oriented programming languages in general because the translation eliminates shallow syntactic differences between related constructs and permits definition of a clean, easy-to-understand, and easy-to-reason-about core language.The core language extends the simply-typed lambda calculus with two central new abstractions: explicitly labeled program points and first-class advice. The labels serve both to trigger advice and to mark continuations that the advice may return to. These constructs are defined orthogonally to the other features of the language and we show that our abstractions can be used in both functional and object-oriented contexts. The labels are well-scoped and the language as a whole is well-typed. Consequently, programmers can use lexical scoping in the standard way to prevent aspects from interfering with local program invariants.
A sound and complete axiomatization of delimited continuations
Authors: Kameyama Yukiyoshi , Hasegawa Masahito
Published: November 2005

The shift and reset operators, proposed by Danvy and Filinski, are powerful control primitives for capturing
delimited continuations
. Delimited continuation is a similar concept as the standard (unlimited) continuation, but it represents part of the rest of the computation, rather than the whole rest of computation. In the literature, the semantics of shift and reset has been given by a CPS-translation only. This paper gives a direct axiomatization of calculus with shift and reset, namely, we introduce a set of equations, and prove that it is sound and complete with respect to the CPS-translation. We also introduce a calculus with control operators which is as expressive as the calculus with shift and reset, has a sound and complete axiomatization, and is conservative over Sabry and Felleisen's theory for first-class continuations.
An effective theory of type refinements
Authors: Mandelbaum Yitzhak , Walker David , Harper Robert
Published: November 2005

We develop an explicit two level system that allows programmers to reason about the behavior of effectful programs. The first level is an ordinary ML-style type system, which confers standard properties on program behavior. The second level is a conservative extension of the first that uses a
logic of type refinements
to check more precise properties of program behavior. Our logic is a fragment of intuitionistic linear logic, which gives programmers the ability to reason
locally
about changes of program state. We provide a generic resource semantics for our logic as well as a sound, decidable, syntactic refinement-checking system. We also prove that refinements give rise to an optimization principle for programs. Finally, we illustrate the power of our system through a number of examples.
Polish parsers, step by step
Authors: Hughes R. John M. , Swierstra S. Doaitse
Published: November 2005

We present the derivation of a space efficient parser combinator library: the constructed parsers do not keep unnecessary references to the input, produce online results and efficiently handle ambiguous grammars. The underlying techniques can be applied in many contexts where traditionally backtracking is used.We present two data types, one for keeping track of the progress of the search process, and one for representing the final result in a linear way. Once these data types are combined into a single type, we can perform a breadth-first search, while returning parts of the result as early as possible.
Optimistic evaluation
Authors: Ennals Robert , Jones Simon Peyton
Published: November 2005

Lazy programs are beautiful, but they are slow because they build many thunks. Simple measurements show that most of these thunks are unnecessary: they are in fact always evaluated, or are always cheap. In this paper we describe Optimistic Evaluation --- an evaluation strategy that exploits this observation. Optimistic Evaluation complements compile-time analyses with run-time experiments: it evaluates a thunk speculatively, but has an abortion mechanism to back out if it makes a bad choice. A run-time adaption mechanism records expressions found to be unsuitable for speculative evaluation, and arranges for them to be evaluated more lazily in the future.We have implemented optimistic evaluation in the Glasgow Haskell Compiler. The results are encouraging: many programs speed up significantly (5-25%), some improve dramatically, and none go more than 15% slower.
Confinement of a class of harmful effects of the goto statement
Authors: Hetrick Brian A. , Nberg H. Eise
Published: November 2005

In this paper, it is shown that the dangers resulting from the semantics of the goto statement described by Zoethout and Stein can arise only in a small and easily recognized class of statement sequences, that these effects are broader than described by Zoethout and Stein, and that these effects are intrinsically stochastic. It is also shown that these effects can be exploited for desirable results in certain circumstances.
PL/I program efficiency
Authors: McNeil Michael , Tracz William
Published: November 2005

All PL/I Programmers should be aware of and genuinely concerned about PL/I Program efficiency. This paper addresses the following question:"How do you write a PL/I program which the PL/I Complier will reduce to the smallest and fastest executing machine language module?" The real world payoffs of knowing how the PL/I Optizing Compiler handles different syntactical representations of similar semantic relationships with respect to code generation and storage allocation can increase program runtime efficiency by many orders of magnitude thus saving many hours of CPU time. Research gathered by the authors in this paper deals with several areas within the PL/I programming realm: logical switches, bit string manipulation, character string manipulation, and multiway branching. Time and money did not permit for an exhaustive study of other areas of PL/I coding, but the results of these four areas have been rewarding and in some instances very surprising.
A simple model of distributed programs based on implementation-hiding and process autonomy
Authors: Chandy K. M. , Misra J.
Published: November 2005

This paper presents a model for a network of communicating processes. We extend well known ideas in sequential programming such as procedures, parameter passing and binding, and recursion to distributed programs. We stress the notion of implementation-hiding, i.e. the invoker of a process or procedure has no knowledge of the implementation of the invoked computation.
A comment on "operator identification in ADA" by Ganzinger and Ripken
Authors: Janas Jürgen M.
Published: November 2005

In a recent technical contribution [1], H. Ganzinger and K. Ripken investigate the impacts of the ADA overloading rule for the problem of operator identification; they show that operator identification may be achieved by at most four passes over the expression trees. While this theoretical result is correct, the procedure suggested for traversing the expression trees is insufficient in several ways. A correct version of the algorithm obviously intended by the authors is given below. Thereby the same notation as in [1] is used; in particular, T(v) stands for the type set and O(v) for the operator set associated with a node v in the expression tree.
Data oriented program design
Authors: Sharp John A.
Published: November 2005

The time is ripe for a change from the traditional, von Neumann view of computing. The desire to increase the efficiency of the programmer by providing a more natural programming tool, and also the desire to increase the efficiency of processor, and memory utilisation by allowing for increased concurrency in execution are major motivations for this change.A data oriented approach to program design is presented which, it is contended, satisfies both of these goals. In order to support this approach a model of parallel computation, and the outline of a programming language based on that model are presented.Some short example programs are included, and the question of input and output (which is often ignored) is discussed.
Comments on the suggested implementation of tasking facilities in the "rationale for the design of the ADA programming language"
Authors: Tai Kuo-Chung , Garrard Ken
Published: November 2005

This paper points out errors and omissions in the suggested implementation of tasking facilities in the "Rationale for the Design of the Ada Programming Language." Apprehension of these mistakes is vital to the correct implementation of Ada compilers.
The Ada compiler validation capability
Authors: Goodenough John B.
Published: November 2005

The Ada Compiler Validation Capability consists of tests, tools, procedures, and documentation designed to enforce (and encourage) development of compilers that conform to the Ada language Standard. In this paper, we discuss our approach to solving the principal problems faced in developing and using such a capability.
The Charrette Ada compiler
Authors: Rosenberg Jonathan , Lamb David Alex , Hisgen Andy , Sherman Mark
Published: November 2005

The Charrette Ada compiler is a working compiler for a substantial subset of the preliminary Ada language. The Ada source program is translated into an equivalent program in an intermediate implementation language. The result of the compilation process is machine language generated for this intermediate program.This paper provides a brief overview of the compiler with special attention given to the primary translation phase. Emphasis is placed on the transformation of Ada type and subtype information and the representation of objects. The translation of several interesting statement and expression forms is also outlined.
TCOL
Ada
and the "middle end" of the PQCC Ada compiler
Authors: Brosgol Benjamin M.
Published: November 2005

A compiler is traditionally partitioned into a (mostly) machine independent Front End which performs lexical, syntactic, and semantic analysis, and a machine dependent Back End which performs optimization and code generation. In the Ada compiler being implemented at Carnegie-Mellon University in the PQCC project, it is useful to identify a set of phases occurring at the start of the Back End - i.e., "Middle End" - after semantic analysis but before optimization. These phases, known collectively as "CWVM" (an abbreviation for "Compiler Writer's Virtual Machine") make basic representational choices and reflect these in an expanded program tree. This paper describes both TCOL
Ada
- the intermediate language interface produced by the Front End - and the phases comprising CWVM. TCOL
Ada
is a graph structured high level representation of the source program which includes both the symbol table and the program tree. The CWVM phases perform transformations of the TCOL
Ada
graph which fall into three categories: language oriented (e.g., expansion of checking for constructs such as array indexing), virtual machine oriented (e.g., translation of up-level addressing into "display" vector accesses), and actual machine oriented (e.g., expansion of component selection into address arithmetic).
A multi-processing implementation-oriented formal definition of Ada in SEMANOL
Authors: Belz F. C. , Blum E. K. , Heimbigner D.
Published: November 2005

A formal definition of the syntax and semantics of Preliminary Ada has been designed and partially implemented as a metaprogram in the SEMANOL system. The paper describes the design in detail and also presents excerpts of the actual SEMANOL metaprogram. Special attention is paid to the following aspects, lacking in the formal denotational definition of Ada: (1) formal definition of the connection between the concrete and abstract syntax of Ada, a necessary element of a formal definition if it is to be executable; (2) formal definition of the semantics of concurrency in Ada tasking; (3) formal definition of the semantics of exceptions and interrupts. The complete SEMANOL metaprogram will be an executable formal definition. In effect, it defines a multi-processing operating system which accepts an Ada program, as a set of compilation units, together with data, and causes the program to be executed in a concurrent mode in accordance with the semantics of tasks prescribed in the Ada reference manual and rationale.
Effective machine descriptors for Ada
Authors: Bishop Judy M.
Published: November 2005

With the impetus provided by the U.S. Department of Defense's support for Ada, serious attention must once again be given to the design of computer architecture for the efficient execution of structured high level languages. Descriptors are one of the more theoretically popular features in a structured machine, yet in practice they do not come up to expectations. This paper examines the deficiencies of current descriptor implementations, and goes on to propose a new approach to descriptors. The design takes into account the relative usage of scalar and structured data in structured programs, and pays due attention to the efficient representation of descriptors as well as to packing, the question of uninitialised values and the contribution which the compiler makes to range and index checking.
A structured APL preprocessor
Authors: Cook Michael L. , Arnold Mark G.
Published: November 2005

This paper presents a set of structured control statements for APL and a preprocessor to implement them. The preprocessor translates structured APL functions into APL functions using the branch operator to replace the structured statements. The translation is based on finding keywords, such as IF and WHILE, appearing in syntactically valid places in the function. Since no modification of either the APL interpreter or APL syntax is required, the APL editor can be used to modify structured functions. The preprocesor also produces an indented listing that aids in the debugging of programs.
The data flow programming language CAJOLE - an informal introduction
Authors: Hankin C. L. , Glaser H. W.
Published: November 2005

Data Flow represents a radical departure from the conventional approach to computer organisation. Rather than a centralised control unit that controls the sequencing of operations, the scheduling of instructions for execution is controlled by the flow of data between operations. In this way the control is distributed and several operations may be executed concurrently. This new approach has major implications for computer architecture and several "data flow" machines have been proposed in the literature.In this paper we present a low level graphical programming language that can be used to represent data flow programs. We also introduce a high level textual language, CAJOLE, that reflects the data flow philosophy. The notations used are simple and elegant in contrast to "fat and flabby" Von Neumann languages.With the advent of fast and cheap microprocessors, we are likely to see a vast increase in the number of tightly-coupled microprocessor systems (a system where several processors cooperate in executing a single task). In this sort of system it is essential to distribute as much as possible the functions that have traditionally been performed by the central control unit. Data flow provides an elegant conceptual basis for this.
Full LR(1) parser generation
Authors: Spector David
Published: November 2005

Full LR(1) parser generation is discussed and shown to be useful and practical, in contrast to current widespread misconception.
The "simplest functional programming language" is neither simple nor functional
Authors: Fehr Elfriede
Published: November 2005

This note is a discussion on David Spector's paper: "The Simplest Functional Programming Language" (SIGPLAN NOTICES18.1 (1983)). It is shown that neither syntax nor semantics of the referred language $ is simpler than that of the pure λ-calculus, and furthermore, this language does not meet the requirement of substitutivity of equivalence, which is essential for functional languages.
Is Pascal suitable for GKS?
Authors: Antoy Sergio , Dettori Giuliana
Published: November 2005

The compatibility between the Pascal programming language and the graphics standard GKS is considered, Both the access of GKS from a Pascal program and the implementation of GKS in Pascal language are analyzed. Various problems arise which do not seem to have simple solution.
Messages vs. remote procedures is a false dichotomy
Authors: Scott Michael Lee
Published: November 2005

This paper discusses some of the major design decisions that distiguish recent language proposals for concurrent programming, It is argued that the classification of languages as "procedure-based" or "message-based" is misleading, in that it confuses two independent issues. It is further argued that these issues are best left undecided by the language designer.
An alternative to current looping syntax
Authors: Taylor David
Published: November 2005

There has been a lot of discussion lately about the drawbacks of various language structures [2] and the lack of the same structures in older programming languages (Fortran) [1]. In this brief paper I propose a modest alteration to programming languages and present a simple pre-processor written in Fortran that implements the alteration.
On the cost of mixed language programming
Authors: Vouk Mladen A.
Published: November 2005

A simple model for estimating the cost of mixed language programming (MLP) is considered. It is based on the empirical information concerning the expense of learning and practically using inter-language communication facilities available in commercial high-level language compiler environments and some static models for inter and intra-language conversion costs and the cost of producing new software. Calculations show that MLP can be very cost effective and compiler manufacturers should be encouraged to incorporate good (and perhaps standardized) inter-language communication facilities into new versions of their high-level language environments.
Prettyprinting styles for various languages
Authors: Leavens Gary T.
Published: November 2005

There are three basic styles of prettyprinting in current usage. I present a simple hypothesis that governs which style is commonly found for any given language, based on the observation of several programming languages.
Error free code
Authors: Mamone Salvatore
Published: November 2005

Much has been written about error free code; what it is, and how to attain it. Given that error free code is desirable and worth striving for, can it ever be realized in the majority of our code? I believe that the answer regrettably, is no. If one were to disregard the every day simple applications; like our 50th update program, or simple reports, error free code in large systems is not attainable. There are a number of reasons for that pessimistic statement, such as the following: multiplicity of design methodologies, non use of reusable code, time constraints, user misunderstanding, and testing. The following is an examination of each of the previous reasons.
Experiences porting Pascal source from a micro computer to a Vax
Authors: Mayer Herbert
Published: November 2005

In March 1984, I ported a good sized Pascal project from an Intel 8086-based micro computer to a Vax11/780. The Pascal compilers on both systems had been implemented long before the Pascal standard [2] was accepted in 1983; consequently neither compiler adheres exactly to the standard. The "Pascal-86" compiler on the Intel micro computer is a user friendly, multipass implementation with various extensions over the standard. Tne Vax Pascal compiler is the Berkeley "PC" implementation running under Unix, version 4.2.I anticipated this task with great pleasure, because I expected that I would be replacing a slow development machine with a fast runner. Also this was an opportunity to test my main design goal which was the writing of software that can be rehosted and retargeted with no effort. By "no effort", I mean that the software can be reconstructed from existing programs with less than 1% of the time of rewriting it altogether.My main goal was successful. In this article, I describe the porting project and list a few surprises encountered along the way. This report was inspired by Sites, who describes a rehosting effort similar to mine in [1].
Applying traits to the smalltalk collection classes
Authors: Black Andrew P. , Schärli Nathanael , Ducasse Stéphane
Published: November 2005

Traits are a programming language technology that promote the reuse of methods between unrelated classes. This paper reports on a refactoring of the Smalltalk collections classes using traits. The original collection classes contained much duplication of code; traits let us remove all of it. We also found places where the protocols of the collections lacked uniformity; traits allowed us to correct these non-uniformities
without
code duplication.Traits also make it possible to reuse fragments of collection code
outside
of the existing hierarchy; for example, they make it easy to convert other collection-like things into true collections. Our refactoring reduced the number of methods in the collection classes by approximately 10 per cent. More importantly, understandability maintainability and reusability of the code were significantly improved.
HydroJ
Authors: Lee Keunwoo , LaMarca Anthony , Chambers Craig
Published: November 2005

In an evolving software system, components must be able to change independently while remaining compatible with their peers. One obstacle to independent evolution is the
brittle parameter problem
: the ability of two components to communicate can depend on a number of
inessential
details of the types, structure, and/or contents of the values communicated. If these details change, then the components can no longer communicate, even if the
essential
parts of the message remain unaffected.We present HydroJ, an extension of Java that addresses this problem. In HydroJ, components communicate using self-describing, semi-structured messages, and programmers use pattern matching to define the handling of messages. This design stems from two central ideas: first, that self-describing messages reduce dependence on inessential message format details; and second, that object-oriented pattern matching naturally focuses on the essential information in a message and is insensitive to inessential information.We have developed these ideas in the context of Rain, a distributed, heterogeneous messaging system for ubiquitous computing. To evaluate the design, we have constructed a prototype HydroJ compiler, implemented some Rain services in HydroJ, studied the evolution of an existing Rain service over time, and formalized HydroJ's key features in a core language.
Connectivity-based garbage collection
Authors: Hirzel Martin , Diwan Amer , Hertz Matthew
Published: November 2005

We introduce a new family of connectivity-based garbage collectors (
Cbgc
) that are based on potential object-connectivity properties. The key feature of these collectors is that the placement of objects into partitions is determined by performing one of several forms of connectivity analyses on the program. This enables partial garbage collections, as in generational collectors, but without the need for any write barrier.The contributions of this paper are 1) a novel family of garbage collection algorithms based on object connectivity; 2) a detailed description of an instance of this family; and 3) an empirical evaluation of
Cbgc
using simulations. Simulations help explore a broad range of possibilities for
Cbgc
, ranging from simplistic ones that determine connectivity based on type information to oracular ones that use run-time information to determine connectivity. Our experiments with the oracular
Cbgc
configurations give an indication of the potential for
Cbgc
and also identify weaknesses in the realistic configurations. We found that even the simplistic implementations beat state-of-the-art generational collectors with respect to some metrics (pause times and memory footprint).
Lazy modular upgrades in persistent object stores
Authors: Boyapati Chandrasekhar , Liskov Barbara , Shrira Liuba , Moh Chuang-Hue , Richman Steven
Published: November 2005

Persistent object stores require a way to automatically upgrade persistent objects, to change their code and storage representation. Automatic upgrades are a challenge for such systems. Upgrades must be performed in a way that is efficient both in space and time, and that does not stop application access to the store. In addition, however, the approach must be modular: it must allow programmers to reason locally about the correctness of their upgrades similar to the way they would reason about regular code. This paper provides solutions to both problems.The paper first defines
upgrade modularity conditions
that any upgrade system must satisfy to support local reasoning about upgrades. The paper then describes a new approach for executing upgrades efficiently while satisfying the upgrade modularity conditions. The approach exploits object encapsulation properties in a novel way. The paper also describes a prototype implementation and shows that our upgrade system imposes only a small overhead on application performance.
On the construction of effective vocabularies for information retrieval
Authors: Salton G. , Yu Clement T.
Published: November 2005

Natural language query formulations exhibit advantages over artificial language statements since they permit the user to approach the retrieval environment without prior training and without using intermediaries. To obtain adequate retrieval output, it is however necessary to emphasize the good terms and to deemphasize the bad ones. The usefulness of the terms in a natural language vocabulary is first characterized in terms of their frequency distribution over the documents of a collection. The construction of "good" natural language vocabularies is then described, and methods are given for improving the vocabulary by transforming terms that operate poorly for retrieval purposes into better ones.
A note on some limits of the algebraic specification method
Authors: Jones Douglas W.
Published: November 2005

If the algebraic method for the specification of abstract data types and programming languages is to be of general utility, it must be possible to define any data type along with the operations on it. An algebraic definition for a data type previously posed as being undefinable by that method is presented, and questions about the utility of the result are considered.
An investigation into the effects of the counting method used on software science measurements
Authors: Elshoff James L.
Published: November 2005

Professor Maurice Halstead of Purdue University first defined a set of properties of algorithms in 1972. The properties are defined in terms of the number of unique operators, unique operands, total operators, and total operands used to express the algorithm. Since 1972, independent experiments have measured various sets of algorithms and have supported Halstead's theories concerning these properties. Also, new properties have been defined and experiments performed to study them.This paper reports a study in which different methods of counting operators and operands are applied to a fixed set of 34 algorithms written in PL/I. Some properties of the algorithms vary significantly depending on the counting method chosen; other properties remain stable. Although no one counting method can be shown to be best, the results do indicate the importance of the counting method to the overall measurement of an algorithm. Moreover, the results provide a reminder of how sensitive some of the measurements are and of how careful researchers must be when drawing conclusions from software science measurements.
An approach to efficient, fault tolerant programming
Authors: Pflasterer David C.
Published: November 2005

In the past software reliability has sometimes been accomplished by an interpreter. The benefits of an interpretive approach have been it's susceptibility to fault tolerance, i.e. it's error detecting and correcting capabilities, Interpreters historically are too slow to be used as the execution complex in a production environment, however.An interpretive based mecharism is proposed in this paper to allow 1) fault tolerance within both the testing and production environment (i.e. the interpreter continues to provide at least a minimum of services even within a hostile environment), and 2) suitable efficiency within a production environment.
The universal compiling system
Authors: Gyllstrom H. C. , Knippel R. C. , Ragland L. C. , Spackman K. E.
Published: November 2005

The Universal Compiling System (UCS) is a unified compiling system for a set of languages and architectures. The integrated implementation discipline of UCS results in reduced development and maintenance costs and increased reliability and efficiency. The key to the UCS design is the strict separation of the source language dependent processes from the architecture dependent processes. This is made possible through the use of an intermediate text and dictionary (symbol table) which is both language independent and architecture independent.
An integrated data base language
Authors: Prakash Naveen , Sharma Y. K.
Published: November 2005

In this document, a language, HYPOL is described. HYPOL represents efforts towards arriving atan integrated language, unified from the points of view of computation, data base definition/manipulation and access control. In arriving at this language the capability concept, as it exists in operating systems, has been used to define access control requirements of a user. Further, the relation has been treated as a sequentisl file of records with appropriste operations defined on it. The type data submodel of HYPOL defines, in a unified manner, the part of the data base seen by a user as well as his access rights over it. Facilities exist to dynamically create new data submodels or to destroy existing ones. Care has been taken to ensure that the language HYPOL helps in writing structured programs.
Brevity and clarity in command languages
Authors: Malcolm James A.
Published: November 2005

An example from Ellis[4] is used to demonstrate the possibilities for greater clarity of expression in a command language which is separate from, rather than embedded in, a programming language.
Los Angeles SIGSPACE/SIGSOFT/SIGPLAN December meeting
Authors: Bixler David C.
Published: November 2005

Have you ever heard of an AN/UYK-41 or an AN/UYK-49? How about MIL-STD-1750A or MIL-STD-1862? Or Nebula? Do they incorporate innovative techniques as supportive targets for modern HOLs? Will they impact the practices and environments in which we develop computer systems? Well, all of these are new computer systems or computer architecture specifications for DoD; so if you design systems or program computers for military projects, you'll be living with them for the next ten years! Find out what they are, how they came about, and what impact these computer standards will have on you in the future.
Some comments on ADA as a real-time programming language
Authors: Mahjoub Ahmed
Published: November 2005

This note contains comments on some of the aspects of the High Order Language ADA which are relevant to real-time programming. Design as well as implementation issues related to the construction of distributed real-time systems are addressed. The comments contained in this note are based on the ADA report printed in the June 1979 issue of the SIGPLAN Notices.
On the synchronization mechanism of the ADA language
Authors: Silberschatz Abraham
Published: November 2005

The synchronization mechanism of the Ada Language is intended to provide a facility for tasks to synchronize their actions. Accept and select statements are the two main features of the language that deal with the issue of synchronization This paper points out one major problem that arises in connection with these features and proposes a possible solution to it.
Isolation of machine dependencies in Euclid
Authors: Aseltine Edward G. , Spencer Henry
Published: November 2005

The programming language Euclid was designed for programming such software as operating system kernels, I/O routines, and storage allocators. These applications require access to low level machine details. Euclid makes a serious effort to limit machine dependencies and to isolate them in readily identifiable sections of code. This paper surveys the machine dependencies of Euclid and assesses the effectiveness of the isolation mechanisms.
On the need for fewer restrictions in changing compile-time environments
Authors: Parnas David L. , Shore John E. , Elliott W. David
Published: November 2005

Compilers for current programming languages enforce rigid restrictions on changes, during the compilation of a statement, in the set of associations between names and declarations, that is, on changes in the compile-time environment of the statement. These restrictions inhibit the writing of well-structured, modular programs, because such programs tend to require frequent switching between the environments associated with different modules. With current compilers, arbitrary switching of environments must be handled by means of macros at compile time or deferred until run time. Conventional macros are difficult to use in situations where it is desirable that the macro writer and the macro user be ignorant about each other's programs. When deferred until run time, frequent switching of environments becomes costly owing to the overhead associated with subroutine calls. In order to encourage the compartmentalization of program information and at the same time to allow efficient code generation, we propose the relaxation of present restrictions on changes in the compile-time environment. Specifically, we propose that a group of declarations can be defined as an environment and that arbitrary pieces of program text can state within which environment they are to be compiled. With such a mechanism, program text can be intermixed by means of macros without having to make the relevant declarations global or having to repeat the declarations in places other than the environment's definition.
Extensions to SNOBOL4 in the SNOBAT implementation
Authors: Silverston Stefan M.
Published: November 2005

SNOBAT is a batch processor for the SNOBOL4 language, developed by the author for the IBM 360. The latest version of SNOBAT, Version 1.9, was released in June, 1976.SNOBAT incorporates a number of extensions to the standard version of SNOBOL4, as set forth by Griswold, Poage, and Polonsky (1). These extensions are described here, and the motivations for their inclusion in SNOBAT are discussed. Some of them are original with the author and his associates, to the best of his knowledge, while some were first suggested by others, as noted. A detailed exposition of SNOBAT extensions to SNOBOL4 appears in the SNOBAT 1.9 Manual (2).
The hierarchical language system
Authors: Terashima Nobuyoshi
Published: November 2005

The Hierarchical Language System HLS is presented. HLS consists of the structured programming language SPL and the extensible programming language EPL which is built upon SPL layer and provides statement and expression extention facilities, and provides to automate top down programming as much as possible by the following means.(1) To describe each breakdown process in the programming languages EPL and SPL, in order to eliminate ambiguity of each breakdown representations which are in general written in natural languages.(2) To generate the whole system which runs in the actual programming environment by this system.This paper describes HLS concepts and language specifications of its components.HLS effectiveness is to be presented in the near future.
The switching reverse polise algorithm
Authors: Witty Robert W.
Published: November 2005

The classical Reverse Polish Algorithm is examined to see why it does not produce optimal evaluation order Reverse Polish. A new algorithm, the Switching Reverse Polish Algorithm, is derived which optimises or improves the evaluation order but retains the simplicity and serial input-output of the classical algorithm. The supermultiply operator is introduced to facilitate strength reduction.
A proposal for a Fortran loop construct
Authors: Brainerd Walt
Published: November 2005

The block IF, ELSE IF, ELSE, and END IF statements [1] have been added during revision of the draft proposed ANS FORTRAN [2]. There have been several suggestions to add new looping constructs, such as DO WHILE or DO UNTIL. There are at least two reasons for not adopting these proposals at this time:1. The DO statement is already available in FORTRAN. Although the syntax may not be elegant by current standards, it is possible to construct loops and leave them using the GO TO statement.2. The constructs proposed only handle special cases of what is needed: a convenient way of leaving from any point in a loop and leaving any level of nesting of loops.Presumably, control structures will be one of the first items discussed when and if work is begun on another revision of the FORTRAN standard. The purpose of this note is to generate some discussion and perhaps some implementations, so that decisions to include other control structures will be based on more experience than is available now. Only loop constructs will be discussed.
Fortran 77 input-output seems out of touch
Authors: Shapiro Michael D.
Published: November 2005

The input-output section of the proposed Fortran 77 is compared to the services provided by the Mass Storage Control System required to support standard Cobol and is found wanting.
An intermediate systems language for the PDP-11
Authors: Karasz Peter
Published: November 2005

In this paper we describe Version 2 of Intermediate Systems Language (ISL/V2), a general purpose software implementation language developed at the B. F. Goodrich Company. The particular implementation we discuss here is for the PDP-11 family of minicomputers that use the 11/40 instruction set.ISL has a FORTRAN like syntax with a number of added features to make it a versatile software development tool. It is the implementation language of IDMS-11, a CODASYL-type Data Base Management System (DBMS) for the PDP-11.The language puts a minimal amount of constraint on the programmer. Top down logic design and modular programming are encouraged but not enforced by the compiler. The ISL compiler produces an assembly program that very closely approaches hand-written code both in appearance and quality. A compile time option is provided for the generation of re-entrant programs. In-line assembler language statements may be inserted into the ISL source program.