bluuebunny/crossref_metadata_2025 huggingface dataset:
A syntax macro processor
Authors: Wodon P. L.
Published: November 2005

Since syntax macros are not new, a few words of justification for still another experiment are necessary. The origin is the following question: “In which language to program the software of electronic telephone exchanges?” Roughly, this is the known problem of choosing a language for software programming, i.e. a language which should be “high-level” to ensure reliability and hardware-oriented to ensure efficiency. Telephone exchanges however, have particularities of their own, two of which are worth mentioning. Firstly, no two exchanges are exactly alike, and this rules out plain assembly code. Secondly, the exchange builders know what they want but seem to have difficulties in expressing it in terms of algorithms. This means that designing at once another special purpose language was out of the question.

Something flexible was needed. To provide for an immediately usable programming tool, a GPM-like macro generator [4] was put into service and is being used for producing software.
Overview of the syntax processor generator SYNPROC
Authors: Fernandez A. , Heliard J. C. , Ichbiah J. D.
Published: November 2005

SYNPROC is a facility for generating syntactic analyzers, implemented on the CII 10070 computer system.

It uses a technique for automatic generation of Floyd-Evans productions which is described in [4]. It also uses bounded-context [3] resolution of identical right-hand sides of syntactic rules. Thus, space optimized analyzers are obtained mechanically for bounded-context (m,1) grammars.

The facility has other practical features which are useful for the construction of compilers for usual programming languages.
Parallel non-deterministic bottom-up parsing
Authors: Lang Bernard
Published: November 2005

The development of translator writing systems and extensible languages has led to a simultaneous development of more efficient and general syntax analyzers, usually for context-free (CF) syntax. Our paper describes a type of parser that can be used with reasonable efficiency for any CF grammar, even one which is ambiguous.

Our parser, like most others, is based on the pushdown automaton model, and thus its generality requires it to be non-deterministic (in the automata theoretic sense). An actual implementation of a non-deterministic automaton requires that we explore every computational path that could be followed by the theoretical automaton. This can be done serially [5], following successively every computational path whenever a choice occurs. It leads to the algorithms described in [1], whose time bounds can be exponential functions of the length of the string to be parsed.

We can also use a parallel implementation which consists in following “simultaneously” all the possible computational paths whenever a non-deterministic choice occurs. Then we can merge paths that have ceased to be different after a certain point. Those mergings reduce drastically the amount of computation. The best known example is the top-down algorithm described in [2]. The algorithm we describe in the first part of our paper is a basic bottom-up parser, similar to [2] in its organization. Both parsers can be shown to work within time bounds which are at most the cube of the length of the input string, and are often a linear function of it. The space bounds are at most the square of that length.

The second part of our paper deals with the optimization of the basic parallel bottom-up algorithm, using the properties of weak precedence relations [3]. The various optimization techniques further reduce the amount of computation required and cause frequent occurrence of a “sparse determinism” phenomenon which allows determination of part of the parse-tree before the non-deterministic analysis is ended. These optimizations also considerably lessen the space requirements. Full details can be found in [6].

The parser is easy to generate for any CF grammar, requiring only the computation of precedence tables. It is slower than most deterministic parsers (on the order of ten times); but all examples we have tried showed it to be more efficient than any other parser having the same generality. We consider that the inefficiency of our parser is reasonable as we intend it as a research tool for the language designer rather than as a part of an industrial compiler.

Languages designers, or extensible languages users, are often more preoccupied with semantics than syntax and fix the syntax of their language in a “nice” form only when they have found what kind of semantics it is to represent. So they can easily come up with ambiguous syntax [4]. Our parser parses ambiguous languages and detects ambiguities in programs, thus enabling the programmer to eliminate them.
An alternative approach to macro processing
Authors: Hammer Michael
Published: November 2005

This paper presents the basic principles of, and the motivation for, an alternative method of processing syntax macros. The inspiration for this work derives from some obvious shortcomings and inefficiencies in conventional macro processing schemes. However, our primary interest is not in designing a faster macro processor; rather it lies in isolating the underlying ideas of syntax macros, realizing their implications, and producing a clean and economical scheme based on these principles.

The compiler model in terms of which we shall couch our discussions is a very familiar one, namely that of the two-pass compilation process. The first pass consists of syntactic and semantic analysis, and converts a source language program into an intermediate language (computation tree) form, which represents the meaning of the program. The second pass is then either an object code selector or an interpreter.
Data types and extensible languages
Authors: Jorrand Philippe
Published: November 2005

Definition mechanisms for extensible programming languages, in principle, allow variation of the language definition in various directions: data types, operations, control structure and syntax. We will focus our attention here on the definitional capabilities that one might expect from a data type extension mechanism. First, we will define informally what the nature of a data type is, what kind of information it contains. Then, we will discuss the most classical approach for data type definition in extensible languages. Finally, we will sketch a model for a mechanism which would permit to introduce really new data types in a language.
Extensibility in Simula 67
Authors: Ichbiah Jean D.
Published: November 2005

Simula 67 is a general purpose language developed at the Norwegian Computing Center. It evolved from an earlier simultation language called Simula 1 [1]

Dahl and Nygaard however, realized that the problems that had to be solved for the implementation of a simulation language, namely the handling of complex data structures and of quasi-parallelism, were general problems. The language Simula 67 [2,3] was therefore defined as a general purpose language with a mechanism for extensions. The simulation capabilities are thus not defined in the base language Simula 67 but are rather defined by extension. This shows clearly how the language Simula 67, hereafter called Simula, is related to the idea of extensibility.
The control structure facilities of ECL
Authors: Prenner Charles J.
Published: November 2005

ECL is a programming language system currently under development at Harvard University. A general description of the system is given in a companion paper [1]. This paper will describe some of the control structure facilities available in ECL - a complete description will appear as part of the author's Ph.D. thesis.

Most existing programming languages allow for only one path of control. The programmer is presented with an environment in which he may use conditional statements, iteration statements and nested function calls (perhaps called recursively) to modify the flow of control through his program but it is not usually possible to either suspend execution of the current program (control path) and start up another or to set up another control path to execute in parallel with the current one. EL1, as originally proposed in [2], allows for only one path of control. ECL, however, allows for the creation and manipulation of multiple paths of control. These paths may execute in parallel, or act as coroutines or in any other relation desirable. Since the number of paths which can be created to execute in parallel may be greater than the number of processors available on a given machine, some sort of path scheduling must be done. The path scheduler is written in EL1 and is available for redefinition by the programmer.
Conversational systems programming by incremental extension of system configuration
Authors: Krutar Rudolph A.
Published: November 2005

An engineer needs tools for his trade and a laboratory or toolshop in which to store them, sharpen them, and use them. A software engineer needs programming tools and a software laboratory. Input/output routines, lexical analyzers, lexicons, storage allocators, temporary files (stacks queues, sorting files), debugging aids, etc., all are useful tools in any software factory or research house. To set up a shop one needs a program library (with librarian), a linkage convention, and a set of interface languages. In my shop (1) each program in the library must have a calling sequence; (2) the linkage convention is a peculiar coroutine linkage (with each program issuing standard subroutine calls on up to k0 virtual facilities (currently k0=8)); and (3) the interface languages are very simple and few in number. An execution instance of a program is a 'process' and may be 'active' or 'suspended'. An output stream of one process may be specified as an input stream of another.

Those who build systems such as mine (including myself) are often disinterested in providing simple but useful services like formatted output, program libraries, listing controls, etc. Furthermore we must build some facilities which are not really relevant to our goals (e.g. input-output routines, lexical analyzers, recursion mechanisms, storage allocators, syntax recognizers, and so on). If we try to use facilities constructed for other systems, we must steal copies of the source code and modify them extensively ([Ki 69]). Such facilities are almost always superfluous to our goals and should therefore be external to our systems. This externalization is surprisingly easy.
An extensible interpreter
Authors: Schuman Stephen A.
Published: November 2005

The purpose of this brief paper is to propose an alternative approach for the implementation of an extensible language. The idea outlined here will be referred to as an
extensible interpreter
. In this particular case, the term itself constitutes an exceptionally concise description of the basic concept, even though there exists another, equally valid way of viewing the same notion, namely as a strategy for integrating an optimizing compiler into an essentially interpretive system. Regardless of which point of view is preferred, however, both are indicative of the fundamental assumption which underlies the present proposal: that the “semantics” of a programming language must ultimately be defined by means of an interpreter. This is to say that the definition of a given language must finally be formulated in terms of an “abstract machine” which is capable of carrying out, in an appropriate environment, the “unit operations” comprising the semantic primitives that language. Thus, an implementation which reflects the definition of the language in question must necessarily include a realization of this abstract machine, whether it is present implicitly, in the processing performed by the compiler, or whether it appears explicitly. In the latter case, the abstact machine may be represented in the form of a conventional software interpreter, or more directly, by means of a suitable set of micro-instructions, the only distinction being the number of different “layers” of interpretation which are actually interposed between this machine and the supporting hardware.

In the context of an extensible language, one can immediately identify the natural instruction set for such an abstract machine: it corresponds to the repertoire of primitive operations provided by the base language. Since it is axiomatic to extensibility that new linguistic elements are constructed by systematic composition of previously defined and/or primitive constructs, the “meaning” of every operation in any subsequent extended language is ultimately defined by its derivation in terms of the operations belonging to the base language. Given that it is, conceptually, the
definition
of the language which is expected to evolve as a consequence of extension, there are strong motivations for explicitly representing the definition itself in any implementation of that language. The logical point of departure, therefore, is to implement an interpreter for the base language, thereby providing a direct realization of the underlying abstract machine.
Extensible languages
Authors: Duby J. J.
Published: November 2005

The purpose of this paper is to describe a computer user's concern about what extensible languages will do for him, and how they will do it. It may in some respects sound a little demagogic, by considering users requirements as priority requirements. However, as Lenin said, “facts are stubborn”, and if users have been used to certain performance characteristics of usual programming languages, they will want to get at least the same performance from extensible languages, and in fact much more - otherwise why switch?
A hierarchy of high order languages for systems programming
Authors: Lyle Don M.
Published: November 2005

The programming of systems software in higher level languages has been a subject of much interest and debate. At Burroughs the debatability of the issue has long since ceased to exist since both the operating system and the compilers for the B5500 were successfully implemented in variants of ALGOL 60. The low manpower requirements and the ease of maintenance and modification have caused all concerned with the project to accept this approach without question. This technique has the added benefit of producing more reliable software due to the greatly reduced number of lines of code required.

When the decision to produce a successor to the B5500 was made, there was no controversy over the use of high level languages but considerable debate over how high a level the languages should be. B5500 ESPOL (Executive System Problem Oriented Language), the operating system implementation language, contained many “unsafe” constructs, for example, the ability to directly address memory through a subscripted reference to an array known, strangely enough, as MEMORY. This allowed coding errors to produce undesirable side effects on the system. Examination of the algorithms used in most operating systems indicated that surprisingly few routines actually require such “unsafe” tools leading to the conclusion that the proper approach to the coding of the overall systems software might be a hierarchical set of systems programming languages with varying degrees of “safety.”
Object serialization analysis and comparison in Java and .NET
Authors: Hericko Marjan , Juric Matjaz B. , Rozman Ivan , Beloglavec Simon , Zivkovic Ales
Published: November 2005

This article compares binary and XML object serialization on Java and Microsoft .NET platforms from the performance and size perspective. It uses three different types of objects and different number of objects to make a comparison which reflects real-world circumstances. The article has the following contributions: (1) it compares binary and XML serialization between Java and .NET to compare the efficiency of both platforms; (2) it compares binary and XML serialization within the platforms to compare the differences between the two serialization types; (3) it studies the reasons for performance differences and provides possible performance optimizations.
Value reuse optimization
Authors: Kumar K. V. Seshu
Published: November 2005

Value reuse technique eliminates the redundant evaluation of expressions, using the support of hardware at runtime to eliminate them. The potential performance of a value reuse mechanism not only depends on the number of instances it has eliminated, but as well as on the time spent in detecting the instance to be eliminated. In order to have better value reuse, we move from instruction level reuse to function reuse, so that one can detect more eliminative instances with reasonable effort. This removes the extra time spent on detecting the possibility of instruction execution elimination. The results of the mathematical library functions evaluated can be reused. Since they can be treated as instructions, i,e. functions which do not have side-effects with the application, one can eliminate the function call itself. In this paper, we propose a Technique to re-use the evaluated values for math library functions. Execution time is decreased up to 6%. Reduction in the number of calls due to instrumentation of code for function reuse for math library routines is up to 99% at a particular call-site in the application
Conservation of information
Authors: Knight Thomas
Published: November 2005

Microscopic physics is entirely reversible, yet almost all computation is done using irreversible processes. Adding two numbers together, for example, destroys information, unless one of the numbers is retained. Over the past few years, some advantages of taking reversible computation seriously have emerged -- first in the context of saving energy, through the development of dissipationless logic, and then in the promise of quantum computation, which is necessarily also reversible and dissipationless.The necessary conservation of information in these systems raises the question of how we can best capture this strong constraint from an abstract point of view. Already ideas such as linear logic can be applied, but the full implementation of conservative logic ideas will require language and architectural innovation and a rethink of our computational models.
An extension of HM(X) with bounded existential and universal data-types
Authors: Simonet Vincent
Published: November 2005

We propose a conservative extension of HM(
X
), a generic constraint-based type inference framework, with bounded existential (a.k.a. abstract) and universal (a.k.a. polymorphic) data-types. In the first part of the article, which remains abstract of the type and constraint language (i.e. the logic
X
), we introduce the type system, prove its safety and define a type inference algorithm which computes principal typing judgments. In the second part, we propose a realistic constraint solving algorithm for the case of structural sub-typing, which handles the non-standard construct of the constraint language generated by type inference: a form of bounded universal quantification.
CDuce
Authors: Benzaken Véronique , Castagna Giuseppe , Frisch Alain
Published: November 2005

We present the functional language CDuce, discuss some design issues, and show its adequacy for working with XML documents. Distinctive features of CDuce are a powerful pattern matching, first class functions, overloaded functions, a very rich type system (arrows, sequences, pairs, records, intersections, unions, differences), precise type inference for patterns and error localization, and a natural interpretation of types as sets of values. We also outline some important implementation issues; in particular, a dispatch algorithm that demonstrates how static type information can be used to obtain very efficient compilation schemas.
.
Global abstraction-safe marshalling with hash types
Authors: Leifer James J. , Peskine Gilles , Sewell Peter , Wansbrough Keith
Published: November 2005

Type abstraction is a key feature of ML-like languages for writing large programs. Marshalling is necessary for writing distributed programs, exchanging values via network byte-streams or persistent stores. In this paper we combine the two, developing compile-time and run-time semantics for marshalling, that guarantee abstraction-safety between separately-built programs. We obtain a namespace for abstract types that is global, i.e. meaningful between programs, by hashing module declarations. We examine the scenarios in which values of abstract types are communicated from one program to another, and ensure, by constructing hashes appropriately, that the dynamic and static notions of type equality mirror each other. We use singleton kinds to express abstraction in the static semantics; abstraction is tracked in the dynamic semantics by coloured brackets. These allow us to prove preservation, erasure, and coincidence results. We argue that our proposal is a good basis for extensions to existing ML-like languages, pragmatically straightforward for language users and for implementors.
A user-centred approach to functions in Excel
Authors: Jones Simon Peyton , Blackwell Alan , Burnett Margaret
Published: November 2005

We describe extensions to the Excel spreadsheet that integrate user-defined functions into the spreadsheet grid, rather than treating them as a "bolt-on". Our first objective was to bring the benefits of additional programming language features to a system that is often not recognised as a programming language. Second, in a project involving the evolution of a well-established language, compatibility with previous versions is a major issue, and maintaining this compatibility was our second objective. Third and most important, the commercial success of spreadsheets is largely due to the fact that many people find them more usable than programming languages for programming-like tasks. Thus, our third objective (with resulting constraints) was to maintain this usability advantage.Simply making Excel more like a conventional programming language would not meet these objectives and constraints. We have therefore taken an approach to our design work that emphasises the cognitive requirements of the user as a primary design criterion. The analytic approach that we demonstrate in this project is based on recent developments in the study of programming usability, including the Cognitive Dimensions of Notations and the Attention Investment model of abstraction use. We believe that this approach is also applicable to the design and extension of other programming languages and environments.
Disjunctive normal forms and local exceptions
Authors: Beffara Emmanuel , Danos Vincent
Published: November 2005

All classical ?-terms typable with disjunctive normal forms are shown to share a common computational behavior: they implement a local exception handling mechanism whose exact workings depend on the tautology. Equivalent and more efficient control combinators are described through a specialized sequent calculus and shown to be correct.
FreshML
Authors: Shinwell Mark R. , Pitts Andrew M. , Gabbay Murdoch J.
Published: November 2005

FreshML extends ML with elegant and practical constructs for declaring and manipulating syntactical data involving statically scoped binding operations. User-declared FreshML datatypes involving binders are concrete, in the sense that values of these types can be deconstructed by matching against patterns naming bound variables explicitly. This may have the computational effect of swapping bound names with freshly generated ones; previous work on FreshML used a complicated static type system inferring information about the 'freshness' of names for expressions in order to tame this effect. The main contribution of this paper is to show (perhaps surprisingly) that a standard type system without freshness inference, coupled with a conventional treatment of fresh name generation, suffices for FreshML's crucial correctness property that values of datatypes involving binders are operationally equivalent if and only if they represent a-equivalent pieces of object-level syntax. This is established via a novel denotational semantics. FreshML without static freshness inference is no more impure than ML and experience with it shows that it supports a programming style pleasingly close to informal practice when it comes to dealing with object-level syntax modulo a-equivalence.
Why a Lisp-based command language?
Authors: Levine John
Published: November 2005

Everyone now agrees that there is a major programmer productivity crisis in the computing industry today. Reports in Computerworld suggest that within a few years data processing will surpass vegetable farming as the U.S.'s most labor-intensive industry. Clearly, any development that promises to improve programmer productivity substantially is of great importance.One important development has been the growth of programmable system command languages. Since every user needs to learn about the command language in order to use a computer system at all, the more work that can be done at the command language level, the less programming in conventional languages will be required.
Towards a compiler front-end for Ada
Authors: Goos Gerhard , Winterstein Georg
Published: November 2005

This paper discusses the current development of a compiler front-end for Ada at the University of Karlsruhe. The front-end is independent of the target-machine and will compile Ada into an intermediate language AIDA, essentially an attributed structure tree. The front-end is written in its own language using Ada-0 and LIS as preliminary compilers for the bootstrap. The compiler in its present form relies heavily on the formal definition of Ada which is under development at CII and IRIA.
A runtime representation for Ada variables and types
Authors: Hisgen Andy , Lamb David Alex , Rosenberg Jonathan , Sherman Mark
Published: November 2005

The type and subtype facilities of the Ada programming language permit some subtype information to be determined dynamically. This subtype information requires a runtime representation, and its dynamic nature influences the representation of variables. In this paper, we first review Ada's types and subtypes to identify some of those aspects which affect runtime representation. We then present the particular representation scheme which is used in the CHARRETTE Ada implementation. The scheme is straightforward and consistent in that a variable is represented the same way independently of where it appears, whether it is on the stack, on the heap, or a component of another variable. The design treats Ada's discriminants and discriminant constraints as a form of parameterized types, where the parameterization permits different instances of a type to have different variants and different sizes for array fields. Composition of such parameterized types is supported. We explain how several Ada operations are handled by our particular representation. We briefly discuss some alternative approaches to Ada representation, comparing them to our design.
An Ada code generator for VAX 11/780 with Unix
Authors: Sherman Mark , Hisgen Andy , Lamb David Alex , Rosenberg Jonathan
Published: November 2005

This paper describes the final phase of an Ada compiler which produces code for the VAX 11/780 running the Unix operating system. Problems encountered in the implementation of subprogram calls, parameter passing, function return values, and exception handling and discussed and their solutions outlined.An underlying requirement for the code generator has been speed of implementation consistent with being a test bed for an Ada implementation. To accomplish this, a common model for the target environment has been assumed. The assumptions include: the VAX is a stack machine, a single address space is used, only the general case is implemented (no optimization of special cases), the hardware does as much work as possible, run time routines for lengthy code sequences are acceptable, and the conventions given in the VAX architecture, hardware, and software manuals are used.The code generator has been running on PDP-10 with Tops-10, producing a VAX assembly language source program as output. it has been available to local users since the beginning of 1980.
Generics and verification in Ada
Authors: Young William D. , Good Donald I.
Published: November 2005

This paper explores the restrictions a mechanism in the style of the Ada generics facility would have to satisfy in order to be amenable to existing verification techniques. "Generic verification" is defined and defended as the appropriate goal for any such facility. Criteria are developed for generic verification to be possible and then Ada is evaluated with respect to these criteria. An example of the application of these techniques to an Ada unit is presented to show that generic verification is possible at least on a subclass of Ada generic units. Finally some potential applications of verified generic units are presented.
Ada as a software transition tool
Authors: Filipski Gary L. , Moore Donald R. , Newton John E.
Published: November 2005

Our agency plans to use the Ada programming language as a vehicle to transport a locally written inquiry system from Burroughs' equipment to another vendor's hardware. This is being done in the following manner. A bootstrap Ada translator has been written in Pascal to generate Burroughs' ALGOL. The Ada translator will be rewritten into Ada from ALGOL and executed on the current Burroughs' machine. When the new hardware is selected, the Ada translator will be retargeted to generate an efficient language on that machine, thereby transporting the inquiry system. The Ada translator will be discarded for an Ada compiler on the new system.
Source-to-source translation
Authors: Albrecht Paul F. , Garrison Philip E. , Graham Susan L. , Hyerle Robert H. , Ip Patricia , Krieg-Brückner Bernd
Published: November 2005

An implementation of translators between Ada and Pascal is described. The method used is to define subsets of each language between which there is a straightforward translation and to translate each source program to its respective sublanguage by program transformations. A common internal tree representation is used. The underlying organization of the translators is described, and some of the difficulties we have confronted and solves are discussed.
The NYU Ada translator and interpreter
Authors: Dewar Robert B. K. , Fisher Gerald A. , Schonberg Edmond , Froehlich Robert , Bryant Stephen , Goss Clinton F. , Burke Michael
Published: November 2005

The NYU-Ada project is engaged in the design and implementation of a translator-interpreter for the Ada language. The objectives of this project are twofold: a) to provide an executable semantic model for the full Ada language, that can be used for teaching, and serve as a starting point for the design of an efficient Ada compiler; b) to serve as a testing ground for the software methodology that has emerged from our experience with the very-high level language SETL. In accordance with these objectives, the NYU-Ada system is written in a particularly high-level, abstract SETL style that emphasizes clarity of design and user interface over speed and efficiency. A number of unusual design features of the translator and interpreter follow from this emphasis. Some of these features are described below. We also discuss the question of semantic specification of programming languages, and the general methodology of "Software Prototyping" of which the NYU-Ada system is a sizeable example.
Completeness of many-sorted equational logic
Authors: Goguen J. A. , Meseguer J.
Published: November 2005

The rules of deduction which are usually used for many-sorted equational logic in computer science, for example in the study of abstract data types, are not sound. Correcting these rules by introducing explicit quantifiers yields a system which, although it is sound, is not complete; some new rules are needed for the addition and deletion of quantifiers. This note is intended as an informal, but precise, introduction to the main issues and results. It gives an example showing the unsoundness of the usual rules; it also gives a completeness theorem for our new rules, and gives necessary and sufficient conditions for the old rules to agree with the new.
Optional, repeatable, and varying type parameters
Authors: Ford Gary , Hansche Brian
Published: November 2005

Parameter passing mechanisms are developed for optional, repeatable, and varying type parameters. For optional parameters, a programmer-defined default value is passed when the actual parameter is not present; in addition, the called procedure may determine whether the actual parameter is present. An arbitrary number of actual parameters may be passed by binding them to an array-like structure in the called procedure. Syntax similar to Algol 68's union type is proposed to allow passing parameters of varying types. These mechanisms are suggested as useful extensions to Pascal-like languages.
Minimal overhead garbage collection of complex list structure
Authors: Spector David
Published: November 2005

A method is described for keeping track of list cells and other objects so that they may be returned to free storage when they are no longer referenced. The method uses only one bit per reference and no searching.
Automatic assessment aids for Pascal programs
Authors: Rees Michael J.
Published: November 2005

Practical programming courses in the Pascal Language inevitably include the need to assess programs submitted by the students. Part of this assessment usually involves awarding marks for the style of the program listing. The philosophy behind a program designed to asses the style of Pascal programs and award marks automatically is presented. The results obtained on actual student courses are discussed, and some extensions which could lead to further assessment aids are suggested.
Implementing data abstractions and monitors in UCSD Pascal
Authors: Boddy David E.
Published: November 2005

Numerous modern programming languages provide constructs for implementing data abstractions and monitors. This paper discusses practical techniques for realizing these programming constructs in the UCSD dialect of Pascal. Although the Pascal language as defined by Wirth [Jen74] is not amenable to the use of these programming constructs, the extensions provided by the UCSD dialect [Cla82] provide an excellent basis for implementing both data abstractions and monitors.
Semaphores outside the kernel
Authors: Gait Jason
Published: November 2005

We present three new implementations of semaphores for V7 UNIX. None require kernel modifications. The canonical UNIX semaphore method uses link O in a spin loop. The first new method replaces the canonical spin loop with a software trap mechanism, the second provides additional enhancements in the form of a pool of semaphores and explicit quene management, and the third is a distributed protocol extending to the ability for synchronizing in network environments.
Defining dynamic variables and abstract data types in Pascal
Authors: Price Ana M. de A.
Published: November 2005

The definition of dynamic variables in Pascal and in many other hiqh level programming languages involves the use of pointers. This paper introduces a new type for describing dynamic variables so that they can be referred to directly by their names. Programming involving dynamic variables is usually complex and error prone. It can be facilitated if the concept of abstract data types is applied. A data type for describing abstract data types is proposed. The inclusion of the proposed features in Pascal is suggested through the implementation of a preprocessor.
Screen-oriented highlevel debugger (SHD) for Pascal
Authors: Garg Vijay Kumar
Published: November 2005

There are certain golden maxims in programming. One of them is, that no matter how meticulous a programmer is, he spends major portion of his software development time on debugging. In such wise, we must have good debuggers to reduce debugging time. As Lauesen[1] puts it, the superiority of a debugger lies in helping user catch more bugs in given time. Accordingly, power of a debugger is the sole yardstick for goodness of it. Power in this context mean both, functionality and convenience. Other factors, such as, extra information it requires from compiler, its bigger size etc. are irrelevant so long as it is extra powerful. The compexity of the debugger, in terms of efforts required to program it should not be a prohibiting factor either. A debugger is used, as often as, if not more than the compiler itself. Conventional Debuggers[2] which call themselves 'High Level Debugger' are no doubt better than 'Dumpers' but are still too primitive to help user in any substantial manner. Most of them are confined to setting up of breakpoints and examination of unstructured variables. SHD strives to match its level of commands with the thought process of the user for maximum efficiency in detecting bugs.
Language-independent aspect-oriented programming
Authors: Lafferty Donal , Cahill Vinny
Published: November 2005

The term aspect-oriented programming (AOP) has come to describe the set of programming mechanisms developed specifically to express crosscutting concerns. Since crosscutting concerns cannot be properly modularized within object-oriented programming, they are expressed as aspects and are composed, or woven, with traditionally encapsulated functionality referred to as components.Many AOP models exist, but their implementations are typically coupled with a single language. To allow weaving of existing components with aspects written in the language of choice, AOP requires a language-independent tool.
Partial behavioral reflection
Authors: Tanter Éric , Noyé Jacques , Caromel Denis , Cointe Pierre
Published: November 2005

Behavioral reflection is a powerful approach for adapting the behavior of running applications. In this paper we present and motivate
partial behavioral reflection
, an approach to more efficient and flexible behavioral reflection. We expose the
spatial
and
temporal
dimensions of such reflection, and propose a model of partial behavioral reflection based on the notion of
hooksets
. In the context of Java, we describe a reflective architecture offering appropriate interfaces for
static
and
dynamic
configuration of partial behavioral reflection at various levels, as well as Reflex, an open reflective extension for Java implementing this architecture. Reflex is the first extension that fully supports partial behavioral reflection in a portable manner, and that seamlessly integrates load-time and runtime behavioral reflection. The paper shows preliminary benchmarks and examples supporting the approach. The examples, dealing with the observer pattern and asynchronous communication via transparent futures, also show the interest of partial behavioral reflection as a tool for open dynamic Aspect-Oriented Programming.
Automatic detection and repair of errors in data structures
Authors: Demsky Brian , Rinard Martin
Published: November 2005

We present a system that accepts a specification of key data structure consistency constraints, then dynamically detects and repairs violations of these constraints, enabling the program to continue to execute productively even in the face of otherwise crippling errors. Our experience using our system indicates that the specifications are relatively easy to develop once one understands the data structures. Furthermore, for our set of benchmark applications, our system can effectively repair inconsistent data structures and enable the program to continue to operate successfully.
A first-class approach to genericity
Authors: Allen Eric , Bannet Jonathan , Cartwright Robert
Published: November 2005

This paper describes how to add first-class generic types---including mixins---to strongly-typed OO languages with nominal subtyping such as Java and C#. A generic type system is "first-class" if generic types can appear in any context where conventional types can appear. In this context, a mixin is simply a generic class that extends one of its type parameters,
e.g.
, a class C that extends T. Although mixins of this form are widely used in Cpp (via templates), they are clumsy and error-prone because Cpp treats mixins as macros, forcing each mixin instantiation to be separately compiled and type-checked. The abstraction embodied in a mixin is never separately analyzed.Our formulation of mixins using first-class genericity accommodates sound local (class-by-class) type checking. A mixin can be fully type-checked given symbol tables for each of the classes that it directly references---the same context in which Java performs incremental class compilation. To our knowledge, no previous formal analysis of first-class genericity in languages with nominal type systems has been conducted, which is surprising because nominal subtyping has become predominant in mainstream object-oriented programming languages.What makes our treatment of first-class genericity particularly interesting and important is the fact that it can be added to the existing Java language without any change to the underlying Java Virtual Machine. Moreover, the extension is backward compatible with legacy Java source and class files. Although our discussion of a practical implementation strategy focuses on Java, the same implementation techniques could be applied to other object-oriented languages such as C# or Eiffel that support incremental compilation, dynamic class loading, and nominal subtyping.
Lightweight confinement for featherweight java
Authors: Zhao Tian , Palsberg Jens , Vitek Jan
Published: November 2005

Confinement properties impose a structure on object graphs which can be used to enforce encapsulation properties essential to certain program optimizations, modular reasoning, and software assurance. This paper formalizes the notion of
confined type
in the context of Featherweight Java. A static type system that mirrors the informal rules of Grothoff et al [17] is proven sound. The definition of confined types is extended to confined instantiation of generic classes. This allows for confined collection types in Java and for classes that can be confined
post hoc
. Confinement type rules are given for Generic Featherweight Java, and proven sound.
Dynamic metrics for java
Authors: Dufour Bruno , Driesen Karel , Hendren Laurie , Verbrugge Clark
Published: November 2005

In order to perform meaningful experiments in optimizing compilation and run-time system design, researchers usually rely on a suite of benchmark programs of interest to the optimization technique under consideration. Programs are described as
numeric
,
memory-intensive
,
concurrent
, or
object-oriented
, based on a qualitative appraisal, in some cases with little justification. We believe it is beneficial to quantify the behaviour of programs with a concise and precisely defined set of metrics, in order to make these intuitive notions of program behaviour more concrete and subject to experimental validation. We therefore define and measure a set of unambiguous, dynamic, robust and architecture-independent metrics that can be used to categorize programs according to their dynamic behaviour in five areas: size, data structure, memory use, concurrency, and polymorphism. A framework computing some of these metrics for Java programs is presented along with specific results demonstrating how to use metric data to understand a program's behaviour, and both guide and evaluate compiler optimizations.
Effectiveness of cross-platform optimizations for a java just-in-time compiler
Authors: Ishizaki Kazuaki , Takeuchi Mikio , Kawachiya Kiyokuni , Suganuma Toshio , Gohda Osamu , Inagaki Tatsushi , Koseki Akira , Ogata Kazunori , Kawahito Motohiro , Yasue Toshiaki , Ogasawara Takeshi , Onodera Tamiya , Komatsu Hideaki , Nakatani Toshio
Published: November 2005

This paper describes the system overview of our Java Just-In-Time (JIT) compiler, which is the basis for the latest production version of IBM Java JIT compiler that supports a diversity of processor architectures including both 32-bit and 64-bit modes, CISC, RISC, and VLIW architectures. In particular, we focus on the design and evaluation of the cross-platform optimizations that are common across different architectures. We studied the effectiveness of each optimization by selectively disabling it in our JIT compiler on three different platforms: IA-32, IA-64, and PowerPC. Our detailed measurements allowed us to rank the optimizations in terms of the greatest performance improvements with the smallest compilation times. The identified set includes method inlining only for tiny methods, exception check eliminations using forward dataflow analysis and partial redundancy elimination, scalar replacement for instance and class fields using dataflow analysis, optimizations for type inclusion checks, and the elimination of merge points in the control flow graphs. These optimizations can achieve 90% of the peak performance for two industry-standard benchmark programs on these platforms with only 34% of the compilation time compared to the case for using all of the optimizations.
Mostly concurrent garbage collection revisited
Authors: Barabash Katherine , Ossia Yoav , Petrank Erez
Published: November 2005

The
mostly concurrent garbage collection
was presented in the seminal paper of Boehm et al. With the deployment of Java as a portable, secure and concurrent programming language, the mostly concurrent garbage collector turned out to be an excellent solution for Java's garbage collection task. The use of this collector is reported for several modern production Java Virtual Machines and it has been investigated further in academia.In this paper, we present a modification of the mostly concurrent collector, which improves the throughput, the memory footprint, and the cache behavior of the collector without foiling the other good qualities (such as short pauses and high scalability). We implemented our solution on the IBM production JVM and obtained a performance improvement of up to 26.7%, a reduction in the heap consumption by up to 13.4%, and no substantial change in the (short) pause times. The modified algorithm was subsequently incorporated into the IBM production JVM.
Declaring and checking non-null types in an object-oriented language
Authors: Fähndrich Manuel , Leino K. Rustan M.
Published: November 2005

Distinguishing non-null references from possibly-null references at the type level can detect null-related errors in object-oriented programs at compile-time. This paper gives a proposal for retrofitting a language such as C# or Java with non-null types. It addresses the central complications that arise in constructors, where declared non-null fields may not yet have been initialized, but the partially constructed object is already accessible. The paper reports experience with an implementation for annotating and checking null-related properties in C# programs.
Object equality profiling
Authors: Marinov Darko , O'Callahan Robert
Published: November 2005

We present
Object Equality Profiling
(OEP), a new technique for helping programmers discover optimization opportunities in programs. OEP discovers opportunities for replacing a set of equivalent object instances with a single representative object. Such a set represents an opportunity for automatically or manually applying optimizations such as hash consing, heap compression, lazy allocation, object caching, invariant hoisting, and more. To evaluate OEP, we implemented a tool to help programmers reduce the memory usage of Java programs. Our tool performs a dynamic analysis that records all the objects created during a particular program run. The tool partitions the objects into equivalence classes, and uses collected timing information to determine when elements of an equivalence class could have been safely collapsed into a single representative object without affecting the behavior of that program run. We report the results of applying this tool to benchmarks, including two widely used Web application servers. Many benchmarks exhibit significant amounts of object equivalence, and in most benchmarks our profiler identifies optimization opportunities clustered around a small number of allocation sites. We present a case study of using our profiler to find simple manual optimizations that reduce the average space used by live objects in two SpecJVM benchmarks by 47% and 38% respectively.