bluuebunny/crossref_metadata_2025_split huggingface dataset:
ALGOL 68 might-have-beens
Authors: van der Meulen S. G. 
Published: November 2005

This paper discusses some language features which might have been in ALGOL68. They would not have complicated the compiler to any considerable extent. They would certainly have contributed to the expressive power of the language. In fact their desirability emerged from the practice of ALGOL68 programming (cf. {4}). “Might-have-beens” are small super-language features and some of them could even be considered as “might-be”s in the sense that they still might be incorporated in existing compilers without (great) difficulty.
A few of these “lost chances” have deeper roots and may contribute to the development of future languages.
'Run-time profiling of Algol 68-R programs using DIDYMUS and SCAMP'
Authors: Brailsford D. F. , Foxley E. , Mander K. C. , Morgan D. J. 
Published: November 2005

Information concerning the run-time behaviour of programs (“program profiling”) can be of the greatest assistance in improving program efficiency. Two software devices have been developed for use on ICL 1900 Series machines to provide such information.
DIDYMUS is probabilistic in approach and uses multitasking facilities to sample the instruction addresses used by a program at run time. It will work regardless of the source language of the program and matches the detected addresses against a loader map to produce a histogram.
SCAMP is restricted to profiling Algol 68-R programs, but provides deterministic information concerning those language constructs that are monitored. Procedure calls to appropriate counting routines are inserted into the source text in a pre-pass prior to compilation. The profile information is printed out at the end of the program run.
It has been found that these two approaches complement each other very effectively.
Direct microprogrammed execution of the intermediate text from a high-level language compiler
Authors: Broca Francois Robert , Merwin Richard E. 
Published: November 2005

Microprogramming commonly executed operations can improve the computational speed of data processing systems. This paper describes how microprogramming may be used to execute directly the intermediate text generated by a high-level language compiler after syntactic and semantic analysis of the input source program.
Direct microprogrammed execution of common forms of intermediate text - i.e.: quadruples, triples, and duos - has been simulated. A comparison is made, in terms of storage requirements and execution time, of this direct microprogrammed system scheme with the present methods which result in machine language representation and execution of the intermediate text. Direct generation of a microprogram from the high-level language statements is also examined.
Timing assumptions for comparative purposes have been based on the IBM 360 MOD 50 system. Simulation and timing estimates for the microprograms have been carried out on a microprogram directed simulator which closely represents the architectural organization of the MOD 50.
Profile guided code positioning
Authors: Pettis Karl , Hansen Robert C. 
Published: November 2005

This paper presents the results of our investigation of code positioning techniques using execution profile data as input into the compilation process. The primary objective of the positioning is to reduce the overhead of the instruction memory hierarchy.
After initial investigation in the literature, we decided to implement two prototypes for the Hewlett-Packard Precision Architecture (PA-RISC). The first, built on top of the linker, positions code based on whole procedures. This prototype has the ability to move procedures into an order that is determined by a “closest is best” strategy.

The second prototype, built on top of an existing optimizer package, positions code based on basic blocks within procedures. Groups of basic blocks that would be better as straight-line sequences are identified as
chains
. These chains are then ordered according to branch heuristics. Code that is never executed during the data collection runs can be physically separated from the primary code of a procedure by a technique we devised called
procedure splitting
.

The algorithms we implemented are described through examples in this paper. The performance improvements from our work are also summarized in various tables and charts.
Two-directional record layout for multiple inheritance
Authors: Pugh William , Weddell Grant 
Published: November 2005

Much recent work in polymorphic programming languages allows subtyping and multiple inheritance for records. In such systems, we would like to extract a field from a record with the same efficiency as if we were not making use of subtyping and multiple inheritance. Methods currently used make field extraction 3-5 times slower, which can produce a significant overall performance slowdown.
We describe a record layout algorithm that allows us to assign a fixed offset to each field name. This allows field extraction to done just as quickly as in systems that do not provide multiple inheritance. Assigning fixed offsets may require us to leave gaps in some records (and waste space). However, by placing fields at both positive and negative offsets we can drastically reduce the amount of wasted space. Finding an optimal layout is NP-hard, so we propose and analyze heuristic algorithms for producing good two-direction record layouts.
In a trial run, our algorithm produced a fixed layout for the instance variables of the 563 flavors of a Lisp Flavors system; this fixed layout only wastes 6% of the total space consumed by a collection of one instance of each flavor.
Derivation of axiomatic definitions of programming languages from algorithmic definitions
Authors: Allen C David 
Published: November 2005

Language definitions by abstract interpreters are appropriate to the design and development of a language. Axiomatic definitions are more appropriate to proving program properties and verification of compilers. The proof methods of Manna and Ashcroft can be applied to an algorithmic definition in, e.g. the Vienna Definition Language to deduce theorems which constitute an axiomatic definition of precisely the same language.
The process and techniques are explained, and illustrated on a simple language of assignment statements.
Translating recursion schemes into program schemes
Authors: Garland Stephen J. , Luckham David C. 
Published: November 2005

Here and in a further paper [2] we study translations between schemes and related equivalence problems, i.e., problems of determining whether two schemes in a given class are equivalent. In particular, we are concerned with the question of developing methods for attacking these problems. It seems to us that some “general methods” ought to exist or, at least, a general form ought to be given to the existing “tricks”. In these papers we present four methods: applying the theory of formal languages, programming, measuring the complexity of a computation, and “cutting and pasting” (roughly speaking, the application of a method due to Rabin and Scott [8] to bound the search necessary to determine if two schemes will behave differently).
Although a few of the results are true for some general notion of scheme, we have nearly always had in mind, for the sake of illustration, just three specific classes of schemes: program schemes, program schemes augmented with counters, and recursively defined schemes. The greater part of the study is restricted to monadic schemes (i.e., schemes containing only functions and predicates of a single argument), and in the case of recursively defined schemes, we are concerned almost exclusively with the single variable monadic recursion schemes introduced by de Bakker and Scott in [1].
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.
Swamp: a fast processor for Smalltalk-80
Authors: Lewis David M. , Galloway David R. , Francis Robert J. , Thomson Brian W. 
Published: November 2005

A processor for the Smalltalk-80↑ programming language is described. This machine is implemented using a standard bit slice ALU and sequencer, TTL MSI, and NMOS LSI RAMS. It executes an instruction set similar to the Smalltalk-80 virtual machine instruction set. The data paths of the machine are optimized for rapid Smalltalk-80 execution by the inclusion of a context cache, tag checking, and a hardware method cache. Each context is only partly initialized when created, and has no memory allocated for it until a possibly non-LIFO reference to it is created. The machine is microprogrammed, and uses a simple next micro-address prediction strategy to obtain most of the performance of pipelining without the attendant complexity. The machine can execute simple instructions at over 7M bytecodes per second and has a predicted average throughput of 1.9M bytecodes per second.
A processor for the Smalltalk-80↑ programming language is described. This machine is implemented using a standard bit slice ALU and sequencer, TTL MSI, and NMOS LSI RAMS. It executes an instruction set similar to the Smalltalk-80 virtual machine instruction set. The data paths of the machine are optimized for rapid Smalltalk-80 execution by the inclusion of a context cache, tag checking, and a hardware method cache. Each context is only partly initialized when created, and has no memory allocated for it until a possibly non-LIFO reference to it is created. The machine is microprogrammed, and uses a simple next micro-address prediction strategy to obtain most of the performance of pipelining without the attendant complexity. The machine can execute simple instructions at over 7M bytecodes per second and has a predicted average throughput of 1.9M bytecodes per second.
Augmentation of object-oriented programming by concepts of abstract data type theory: the ModPascal experience
Authors: Olthoff Walter G. 
Published: November 2005

Object-oriented programming and abstract data type (ADT) theory have emerged from the same origin of computer science: the inability to deal efficiently with 'programming in the large' during the early seventies. Each of the approaches has led to significant practical and theoretical results resp. Nevertheless it is still unsatisfactory that up to now the mutual influence seems to be limited to more or less syntactical issues (e.g. the provision of packages, clusters, forms).
In this paper we report on the object-oriented language ModPascal that was developed as part of the Integrated Software Development and Verification (ISDV) Project. We show how the essence of concepts of ADT theory as algebraic specifications, enrichments, parameterized specifications or signature morphisms as well as their semantics can be consistently integrated in an imperative object-oriented language. Furthermore, as the experience of using ModPascal as target language of the ISDV System has shown, we claim that without similar support of theoretical concepts techniques like formal specification of programs or algebraic verification loose their power and even applicability.
The management of changing types in an object-oriented database
Authors: Skarra Andrea H. , Zdonik Stanley B. 
Published: November 2005

We examine the problem of type evolution in an object-oriented database environment. Type definitions are persistent objects in the database and as such may be modified and shared. The effects of changing a type extend to objects of the type and to programs that use objects of the type. We propose a solution to the problem through an extension of the semantic data model.
A change in the interface defined by a type may result in errors when programs use new or old objects of the type. Through the use of an abstraction of the type over time, timestamping and error handling mechanisms provide support for the type designer in creating compatible versions of the type. The mechanisms are incorporated into the behavior defined by the type and are inherited via the type-lattice.
Register windows vs. register allocation
Authors: Wall D. W. 
Published: November 2005

A large register set can be exploited by keeping variables and constants in registers instead of in memory. Hardware register windows and compile-time or link-time global register allocation are ways to do this. A measure of the effectiveness of any of these register management schemes is how thoroughly they remove loads and stores. This measure must also count extra loads and stores executed because of window overflow or conflicts between procedures.
By combining profiling, instrumentation, and in-line simulation, we measured the effectiveness of several register management schemes. These included compile-time and link-time schemes for allocating registers, and register window schemes using fixed-size or variable-sized windows. Link-time allocation based on profile information was the clear winner in some cases and did about as well as windows in the rest. Even link-time allocation based on an estimated profile was about as good as windows. Variable-sized windows sometimes did better than fixed-sized windows, but the difference was usually small.
Register windows require extra logic in the data path, which may slow the machine cycle slightly, and often use more chip real estate for additional registers. Proponents of windows suppose that they trade these drawbacks for a reduction in the number of memory references they must make. Our results show that this tradeoff should be made the other way. Keep the hardware simple, because a link-time register allocator can nearly duplicate the improvement in memory reference frequency. Then the cycle time can be as small as possible, resulting in faster programs overall.
Multiprocessor Smalltalk: a case study of a multiprocessor-based programming environment
Authors: Pallas J. , Ungar D. 
Published: November 2005

We have adapted an interactive programming system (Smalltalk) to a multiprocessor (the Firefly). The task was not as difficult as might be expected, thanks to the application of three basic strategies: serialization, replication, and reorganization. Serialization of access to resources disallows concurrent access. Replication provides multiple instances of resources when they cannot or should not be serialized. Reorganization allows us to restructure part of the system when the other two strategies cannot be applied.
We serialized I/O, memory allocation, garbage collection, and scheduling, we replicated the interpreter process, software caches, and a free-list, and we reorganized portions of the scheduling system to deal with some deep-seated assumptions. Our changes yielded a fairly low static overhead. We attribute our success to the choice of a small, flexible operating system, a set of constraints which simplified the problem, and the versality of the three strategies for dealing with concurrency. The current system has a moderate amount of overhead when parallelism is being used—25% to 65%. It is acceptable, but we believe it can be improved.
ACM SIGPLAN history of programming languages conference PL/I language summary
Authors: Rosin Robert F. 
Published: November 2005

PL/I was developed in two distinct stages. First the language NPL was conceived by a joint user-IBM committee. IBM alone then developed PL/I by clarifying and refining the rather incomplete specification of NPL. This overview describes the major features of PL/I, and George Radin's paper makes clear the distinctions between these two languages.
The characteristics of PL/I were strongly influenced by two factors; what was known (in 1964-65) about commercial, scientific, real-time and system programming applications, and the features of FORTRAN, COBOL, and ALGOL which were useful in implementing those applications. The result is a language of great expressive power, which occasionally requires the programmer to manage great complexity.
The operating system and language support features of the BELLMAC
TM
-32 microprocessor.
Authors: Berenbaum Alan D. , Condry Michael W. , Lu Priscilla M. 
Published: November 2005

The BELLMAC-32 microprocessor is a 32-bit microprocessor, implemented with CMOS technology, designed to support operating system functions and high level languages efficiently. The architecture was designed with the following objectives in mind:
• High performance.
• Enhanced operating system support capabilities.
• High level language support.
• High reliability, availability and maintainability.
On a general property of memory mapping tables
Authors: Reed Karl 
Published: November 2005

The paper shows that memory mapping tables can be used to implement the display registers used in providing architectural support for block-structured languages such as Algol 60. This allows full lexical level addressing to be implemented on so-called von-Neuman machines.
The problems of fragmentation of the paged address space are explored, and machines with memory mapping schemes capable of supporting the proposals identified.
Attention is drawn to the similarity between segmented and paged schemes, and it is suggested that the latter may be used to support the former.
A multi-microprocessor architecture with hardware support for communication and scheduling
Authors: Ahuja Sudhir R. , Asthana Abhaya 
Published: November 2005

We describe a multiprocessor system that attempts to enhance the system performance by incorporating into its architecture a number of key operating system concepts. In particular:
— the scheduling and synchronization of concurrent activities are built in at the hardware level,
— the interprocess communication functions are performed in hardware, and,
— a coupling between the scheduling and communication functions is provided which allows efficient implementation of parallel systems that is precluded when the scheduling and communication functions are realized in software.
Associating types with domains of relational data bases
Authors: Lacroix Michel , Pirotte Alain 
Published: November 2005

In the DB field, there are two
interpretations
(or perceptions or schools of thought)
concerning the relational model
:

(a) one interpretation considers that the relational model contribution to the DB field essentially consists in the presentation of a clear and simple notion of (flat) file, and that many users will be very satisfied to describe their data structures as tables;
(b) another interpretation considers the relational model as a (reasonable) support for a (weak) entity relationship model.
MoDE: a UIMS for Smalltalk
Authors: Shan Yen-Ping 
Published: November 2005

While the Model-View-Controller (MVC) framework has contributed to many aspects of user interface development in Smalltalk, interfaces produced with MVC often have highly coupled model, view, and controller classes. This coupling and the effort required to use MVC make user interface creation a less effective aspect of Smalltalk.
The Mode Development Environment (MoDE) is a user interface management system (UIMS) which addresses the above issues. MoDE is composed of two major components: the Mode framework and the Mode Composer. The Mode framework accommodates an orthogonal design which decouples the user interface components and increases their reusability. The Mode Composer reduces the effort of using MoDE by providing a direct-manipulation user interface to its users. This paper discusses the importance of orthogonality and illustrates its incorporation into the design of MoDE. A comparison of the Mode framework and the MVC framework is included.
OOP in the real world
Authors: DeNatale Rick , Irby Charles , LaLonde John , Leathers Burton , Phillips Reed 
Published: November 2005

Some advocates of OOP have promised that it will make all code reusable, shorten development cycles, remove the applications backlog, cure the common cold and plug the hole in the ozone layer.
How well does actual experience bear this out?
Success stories are published much more often than failures and false starts. This is very unfortunate since the former two are often much more instructive.
This panel will attempt to bring the less successful experiences to light, and hopefully, will provide lessons on how to do better.