bluuebunny/crossref_metadata_2025 huggingface dataset:
Mechanizing the meta-theory of programming languages
Authors: Harper Robert
Published: November 2005

What does it mean for a programming language to exist? Usually languages are defined by an informal description augmented by a reference compiler whose behavior is regarded as normative. This approach works well so long as the one true implementation suffices, but as soon as we wish to have multiple compilers for the same language, we must agree on what the language is independently of its implementations. Most often this is accomplished through social processes such as standardization committees for building consensus.These processes have served us well, and will continue to be important for language design. But they are not sufficient to support the level of rigor required to prove theorems about languages and programs written in them. For that we need a semantics, which provides an objective foundation for such analyses, typically in the form of a type system and an operational semantics. But merely having such a rigorous definition for a language is not enough — it must be validated by a body of meta-theory that establishes its coherence and its consistency with expectations.But how are we to develop and maintain this body of theory? For full-scale languages the task is so onerous as to inhibit innovation and foster stagnation. The way forward is to take advantage of the recent advances in mechanized reasoning. By representing a language definition within a logical framework we may subject it to formal analysis, much as we use types to express and enforce crucial invariants in our programs. I will describe our use of the Twelf implementation of the LF logical framework, and discuss our successes and difficulties in using it as a tool for mechanizing the meta-theory of programming languages.
A logical analysis of aliasing in imperative higher-order functions
Authors: Berger Martin , Honda Kohei , Yoshida Nobuko
Published: November 2005

We present a compositional program logic for call-by-value imperative higher-order functions with general forms of aliasing, which can arise from the use of reference names as function parameters, return values, content of references and parts of data structures. The program logic extends our earlier logic for alias-free imperative higher-order functions with new modal operators which serve as building blocks for clean structural reasoning about programs and data structures in the presence of aliasing. This has been an open issue since the pioneering work by Cartwright-Oppen and Morris twenty-five years ago. We illustrate usage of the logic for description and reasoning through concrete examples including a higher-order polymorphic Quicksort. The logical status of the new operators is clarified by translating them into (in)equalities of reference names. The logic is observationally complete in the sense that two programs are observationally indistinguishable if they satisfy the same set of assertions.
Multiparadigm research
Authors: Placer John
Published: November 2005

Multiparadigm research is a relatively new direction in programming language design. In this paper we discuss several aspects of this research area. We consider some of the ideas that underlie the multiparadigm point of view, we examine some of the motivations behind the work being done and we consider some of the directions within this field of work. Finally we offer a short example that suggests the potential usefulness of combining several paradigms into one linguistic framework.
Toward integrating imperative and logic programming paradigms
Authors: Delrieux Claudio , Azero Pablo , Tohme Fernando
Published: November 2005

This paper presents an integration of imperative and logic programming, implemented on a PROLOG interpreter. The idea is to exploit the interpreter's execution model to support a procedural style of coding, and to imcorporate the notion of state by means of the use of the internal database. Both the coding style and some experimental structured-like programming constructs are discussed. The proposed integration provides hints to achieve an extensible language (i. e. iterative control structures that may be useful when tail recursion optimization is not possible) and also benefits in learning the equivalence between its declarative and operational semantics.
Fortran 90 arrays
Authors: Bernecky Robert
Published: November 2005

Excellent application performance should not require tour de force programming efforts by users. Fortran 90 in an attempt to bring it from a scalar orientation into an array notation, has adopted some of the early concepts of APL, such as array operations. The introduction of these ideas is shown to be inadequate meeting the algorithmic needs of programmers, in terms of expressiveness, consistency, and conciseness. Comparisons with APL show Fortran 90 to be a mongrel, neither scalar- nor array-oriented, unable achieve the levels of productivity, performance, reliability, and maintainability required by computer users in the 1990s.
O.LISP theoretical basis and description
Authors: Lieu Choun Tong , Sarni Djamil
Published: November 2005

We describe, in this article, O. LISP: a functional language based on the manipulation of expressions issued from the syntax of lambda-calculus on occurrence (λ()-caculus [8]). In this theoretical framework, the functions are constructed without variables, we essentially use indexes of occurrences and basic terms.In O. LISP new primitives, like SUBO or UNSUBO, realize, respectively, a substitution (without variable, by creating links between numbers of occurrences and arguments) and a locking on some of these links.A first version of O. LISP has been implemented on a LISP interpret We present, at the end of this article, some examples which are extracted from this implementation.
Generation and recognition of formal languages by modifiable grammars
Authors: Burshteyn Boris
Published: November 2005

In this article the formal definitions of modifiable grammars are presented, and the equivalence between classes of modifiable grammars and Turing machines is proved. Some criteria for reducing modifiable grammars to context-free grammars are provided. A lazy LR(1) algorithm for context-free grammars and an algorithm for constructing a LR(1) parser for modifiable grammars are discussed.
Does Modula-2 generate racehorses?
Authors: Dotzel Günter
Published: November 2005

A simple example serves to demonstrate the code quality generated by two different Modula-2 compilers. In this paper the two compilers are called the Zürich/Hamburger and the Erlanger.
Two models for integrating persistence and lazy functional languages
Authors: McNally David J. , Davie Antony J. T.
Published: November 2005

A new programming system --- STAPLE (Statically Typed Applicative Persistent Language Environment) --- which integrates a lazy functional programming language and a persistent store is described. The motivation for introducing orthogonal persistence into a functional setting is given. Two models for achieving this integration are then described together with a discussion of the way laziness interacts with persistence and the benefits resulting from this interaction. In the first model, a system of persistent modules allows the programmer to create persistent values by naming them in a module. In the second model, a combination of stream I/O and a dynamic type allows functional programs to manipulate values already in the persistent store and to allow dynamically created values to become persistent.
Shallow binding makes functional arrays fast
Authors: Baker Henry G.
Published: November 2005

Access and update for random elements of arrays in imperative programming languages are O(1) operations. Implementing functional programming languages to achieve equivalent efficiency has proved difficult. We show how the straight-forward application of shallow binding to functional arrays automatically achieves O(1) update for single-threaded usage.
A retargetable compiler for ANSI C
Authors: Fraser Christopher W.
Published: November 2005

lcc is a new retargetable compiler for ANSI C. Versions for the VAX, Motorola 68020, SPARC, and MIPS are in production use at Princeton University and at AT&T Bell Laboratories. With a few exceptions, little about lcc is unusual --- it integrates several well engineered, existing techniques --- but it is smaller and faster than most other C compilers, and it generates code of comparable quality, lcc's target-independent front end performs a few simple, but effective, optimizations that contribute to good code; examples include simulating register declarations and partitioning switch statement cases into dense tables. It also implements target-independent function tracing and expression-level profiling.
An object-oriented specification for compiler
Authors: Wu Pei-Chi , Wang Feng-Jian
Published: November 2005

In this paper, we present an object-oriented approach to compiler specification. Our method treats grammar symbols as templates which instantiate nodes of parse tree for object-oriented semantic analysis. To have better classification and inheritance for semantic description, it uses
restricted
CFG to specify grammar rules. The semantic specification is done based on a class hierarchy generated from the restricted CFG. Besides, that a path expression is booted to describe the possible receivers of a message releases the restriction on the specification of message (value) propagations in attribute grammar methods.
Integrating destructive assignment and lazy evaluation in the multiparadigm language G-2
Authors: Placer John
Published: November 2005

In order to design a broadly multiparadigm language, i.e., a language that directly supports several diverse programming paradigms, one must integrate a number of seemingly incompatible paradigmatic attributes. Among the most formidable of these antagonists are the time-independent and the time-dependent features of the diverse paradigms that are to be integrated into the language design. Although at some level these antagonists are inherently irreconcilable, finding an appropriate level of integration for such diverse elements can be a significant contribution to a broadly multiparadigm language design. In order to demonstrate this, we first briefly introduce the language G-2, the latest version of the multiparadigm language G. We focus on a new linguistic feature, called a
block
, that was introduced into G-2 in order to reconcile the facilities of destructive assignment and lazy evaluation. Finally we examine how the
block
supports many of the paradigms included in G-2 in a simple and direct manner.
Proxy: an interpreter for rapid prototyping
Authors: Leavenworth Burt
Published: November 2005

Proxy is an interpreter for a rapid prototyping language with C/C++ like syntax based on modelling software using data structures such as sets, maps, sequences, and objects. It allows the developer to make incremental changes to a design and test them immediately."The hardest single part of building a software system is deciding precisely what to build" - Fred Brooks [3].
A quick introduction to the programming language MIKE
Authors: Coolsaet K.
Published: November 2005

MIKE is a new programming language developed by the author as a base language for the development of algebraic and symbolic algorithms. It is a structured programming language with a MODULA-2-like syntax supporting special features such as transparent dynamic memory management, discriminated union types, operator overloading, data abstraction and parametrized types. This text gives an overview of the main features of the language as of version 2.0.
Scanning regular languages by dual finite automata
Authors: Wu Pei-Chi , Wang Feng-Jian , Young Kai-Ru
Published: November 2005

A regular language is generally accepted by a single finite automaton. An approach of dual finite automata is presented here. An input string is scanned by two deterministic finite automata (DFA's): reading from the string's head and tail respectively. One of them accepts the regular language itself; the other accepts the language's reversal. Whether a string is accepted depends on the states of both automata, when their reading heads meet. Dual finite automata can be applied in compiler generation and parallel computing.
Exploratory language design
Authors: Ipser Edward A.
Published: November 2005

Exploratory language design is an iterative process of language refinement the purpose of which is to define a language that closely fits a given domain of applications. First, choose a domain of applications and a language starting point. Then iteratively choose an application in the domain, write the solution to the application in the language, and fit the language to the application until satisfied.
A globalizing transformation for attribute grammars
Authors: Räihä K. J. , Tarhio Jorma
Published: November 2005

A transformation is presented for replacing conventional local attribute references in attribute grammars by upward remote references. The purpose of the transformation is to enhance readability of the grammar and to facilitate easy storage optimization.
Discovering machine-specific code improvements
Authors: Kessler Peter B.
Published: November 2005

I have designed and built a compiler construction tool that automates much of the case analysis necessary to exploit special purpose instructions on a target machine. Given a suitable description of the target machine, my analysis identifies instruction sequences that are equivalent to single instructions. During code generation, these equivalences can be used to avoid inefficient instruction sequences in favor of more efficient instructions.

I present a working prototype of the instruction set analyzer needed in the framework outlined by [Giegerich 83]. In contrast to the work presented in [Davidson and Fraser 80, 84], I analyze machine descriptions during compiler construction, rather than analyzing instruction sequences that occur during code generation. [R Kessler 84] describes a system which analyzes machine descriptions during compiler construction, but which which is limited to discovering instructions that are equivalent to instruction sequences of length 2. The techniques presented here can identify instruction sequences of arbitrary length that are equivalent to single instructions.

I have applied this analysis to the descriptions of two machines, and used the results to replace hand-written case analysis routines in an otherwise table-driven code generator [Henry 84].
An abstract machine design for lexically scoped parallel Lisp with speculative processing
Authors: Yuen C. K.
Published: November 2005

An abstract machine is designed to support the data environment requirements of BaLinda Lisp, a parallel Lisp dialect which permits speculative processing of conditional modules. Logically, the machine provides multiple stacks connected into an environment tree, with lexically visible sections pointed to by display registers. Physically, stack sections are stored as separate objects and access is established by the use of a dynamic stack recording the chain of function calls, and a set of lexical display registers pointing at visible objects. This arrangement allows parts of the environment of a function to be retained or garbage-collected as appropriate after exit. By making copies of visible ancestral stack sections, side effects of speculative parallel tasks are handled in accordance with language semantics. The architecture is generic and may be realized in a variety of forms, depending on whether BaLinda Lisp is implemented on a conventional machine, stack machine, or dataflow machine.
MANEVRO
Authors: Mijanovic Srdjan
Published: November 2005

Manevro is a class based programming language designed primarily for system programming. Using FORTH-like environment, compiler produces extremely efficient code. One of the main goals of the project was to create machine independent compiler thus increasing portability of code.
Debugging optimized code with dynamic deoptimization
Authors: Hölzle Urs , Chambers Craig , Ungar David
Published: November 2005

SELF's debugging system provides complete source-level debugging (
expected behavior
) with globally optimized code. It shields the debugger from optimizations performed by the compiler by dynamically
deoptimizing
code on demand. Deoptimization only affects the procedure activations that are actively being debugged; all other code runs at full speed. Deoptimization requires the compiler to supply debugging information at discrete
interrupt points
; the compiler can still perform extensive optimizations between interrupt points without affecting debuggability. At the same time, the inability to interrupt between interrupt points is invisible to the user. Our debugging system also handles
programming changes
during debugging. Again, the system provides expected behavior: it is possible to change a running program and immediately observe the effects of the change. Dynamic deoptimization transforms old compiled code (which may contain inlined copies of the old version of the changed procedure) into new versions reflecting the current source-level state. To the best of our knowledge, SELF is the first practical system providing full expected behavior with globally optimized code.
A customizable substrate for concurrent languages
Authors: Jagannathan Suresh , Philbin Jim
Published: November 2005

We describe an approach to implementing a wide-range of concurrency paradigms in high-level (symbolic) programming languages. The focus of our discussion is STING, a dialect of Scheme, that supports lightweight threads of control and virtual processors as first-class objects. Given the significant degree to which the behavior of these objects may be customized, we can easily express a variety of concurrency paradigms and linguistic structures within a common framework without loss of efficiency.

Unlike parallel systems that rely on operating system services for managing concurrency, STING implements concurrency management entirely in terms of Scheme objects and procedures. It, therefore, permits users to optimize the runtime behavior of their applications without requiring knowledge of the underlying runtime system.

This paper concentrates on (a) the implications of the design for building asynchronous concurrency structures, (b) organizing large-scale concurrent computations, and (c) implementing robust programming environments for symbolic computing.
Prototyping Fortran-90 compilers for massively parallel machines
Authors: Chen Marina , Cowie James
Published: November 2005

Massively parallel architectures, and the languages used to program them, are among both the most difficult and the most rapidly-changing subjects for compilation. This has created a demand for new compiler prototyping technologies that allow novel style of compilation and optimization to be tested in a reasonable amount of time.

Using formal specification techniques, we have produced a data-parallel Fortran-90 subset compiler for Thinking Machines' Connection Machine/2 and Connection Machine/5. The prototype produces code from initial Fortran-90 benchmarks demonstrating sustained performance superior to hand-coded Lisp and competitive with Thinking Machines' CM Fortran compiler. This paper presents some new specification techniques necessary to construct competitive, easily retargetable prototype compilers.
Relaxing SIMD control flow constraints using loop transformations
Authors: v. Hanxleden Reinhard , Kennedy Ken
Published: November 2005

Many loop nests in scientific codes contain a parallelizable outer loop but have an inner loop for which the number of iterations varies between different iterations of the outer loop. When running this kind of loop nest on a SIMD machine, the SIMD-inherent restriction to single program counter common to all processors will cause a performance degradation relative to comparable MIMD implementations. This problem is not due to limited parallelism or bad load balance, it is merely a problem of control flow.

This paper presents a loop transformation, which we call
loop flattening
, that overcomes this limitation by letting each processor advance to the next loop iteration containing useful computation, if there is such an iteration for the given processor. We study a concrete example derived from a molecular dynamics code and compare performance results for flattened and unflattened versions of this kernel on two SIMD machines, the CM-2 and the DECmpp 12000. We then evaluate loop flattening from the compiler's perspective in terms of applicability, cost, profitability, and safety. We conclude with arguing that loop flattening, whether performed by the programmer or by the compiler, introduces negligible overhead and can significantly improve the performance of scientific codes for solving irregular problems.
A safe approximate algorithm for interprocedural aliasing
Authors: Landi William , Ryder Barbara G.
Published: November 2005

During execution, when two or more names exist for the same location at some program point, we call them
aliases
. In a language which allows arbitrary pointers, the problem of determining aliases at a program point is ρ-space-hard [Lan92]. We present an algorithm for the Conditional May Alias problem, which can be used to safely approximate Interprocedural May Alias in the presence of pointers. This algorithm is as precise as possible in the worst case and has been implemented in a prototype analysis tool for C programs. Preliminary speed and precision results are presented.
Compiler support for garbage collection in a statically typed language
Authors: Diwan Amer , Moss Eliot , Hudson Richard
Published: November 2005

We consider the problem of supporting compacting garbage collection in the presence of modern compiler optimizations. Since our collector may move any heap object, it must accurately locate, follow, and update all pointers and values derived from pointers. To assist the collector, we extend the compiler to emit tables describing live pointers, and values derived from pointers, at each program location where collection may occur. Significant results include identification of a number of problems posed by optimizations, solutions to those problems, a working compiler, and experimental data concerning table sizes, table compression, and time overhead of decoding tables during collection. While gc support can affect the code produced, our sample programs show no significant changes, the table sizes are a modest fraction of the size of the optimized code, and stack tracing is a small fraction of total gc time. Since the compiler enhancements are also modest, we conclude that the approach is practical.
APL arrays and their editor
Authors: Gfeller W
Published: November 2005

APL arrays can be perceived to consist of several
parts
. This concept is extended and rationalized. Together with
keyed indexing
, it allows to treat all entities in an APL system as arrays. The human interface to such a system is a recursive
array editor
(
ae
), which is isomorphic to the APL language.Finally, a design of such an editor for a workstation with bitmapped display is presented.
An analysis of length equation using a dynamic approach
Authors: Chen T Y , Kwan S C
Published: November 2005

This paper is to compare the dynamic and static approaches towards the analysis of the length equation, which is the most fundamental and important equation in the theory of software science. In addition to intuition, our empirical results give further support to the claim that dynamic approach is more appropriate than the static approach towards the theory of software science.
ALBA
Authors: Hernández J. , de Miguel P. , Barrena M. , Martínez J. M. , Polo A. , Nieto M.
Published: November 2005

In this paper, ALBA, A parallel Language Based on Actors, is introduced. ALBA [15] is a new programming language designed to take advantage of highly parallel architectures that use message passing as the fundamental low-level interaction primitive. ALBA is being developed as implementation language for the QUATRO parallel Database machine [5] in order to facilitate its portability and permit a homogeneous description of the QUATRO system to every multiprocessor machine.ALBA is a strong-typed language, and is oriented towards the development of both parallel and distributed applications. The actor paradigm in ALBA presents new characteristics such as the use of broadcast methods; dynamic actor allocations permitting the programmer to distribute actors on the machine, in a load-balancing way, on both a specific set of virtual processors or on all of the processors of the machine; different communication and synchronization mechanisms among actors, and others that are presented in this papcr.The ALBA programming language and the QUATRO Database Machine are being developed under the HELIOS operating system for a transputer machine.
Anonymous routine-texts
Authors: Stolz Otto
Published: November 2005

Hanspeter Mössenböck has proposed [7] a language construct for treating statement sequences as block objects that can be passed to procedures as parameters. As these blocks are nothing else but parameterless procedures, a more orthogonal solution to Mössenböck's set of problems has long been available: in the programming language Algol 68, a routine-text can be specified, anonymously, in the place of an argument.The present contribution presents Mössenböck's example in Algol 68 notation, and demonstrates the versatility of anonymous routine-texts by transforming the given example to a neater solution.
PIDL/Pascal
Authors: Baowen Xu
Published: November 2005

This paper introduces a Pascal-oriented program interface description language, PIDL/Pascal, which is designed to specify the interface reformation between program units so as to remedy the weakness of some design tools. We will also discuss its design ideas, program structure and facilities, applications, and checking tools.
History of the Icon programming language
Authors: Griswold Ralph E. , Griswold Madge T.
Published: November 2005

The Icon programming language, which was conceived in 1977, was strongly influenced by the earlier SNOBOL languages and the subsequent SL5. This paper concentrates primarily on the early development of Icon, but also discusses subsequent versions. The motivation, design philosophy, and environmental factors that shaped Icon are emphasized in this paper.
The evolution of Lisp
Authors: Steele Guy L. , Gabriel Richard P.
Published: November 2005

Lisp is the world's greatest programming language—or so its proponents think. The structure of Lisp makes it easy to extend the language or even to implement entirely new dialects without starting from scratch. Overall, the evolution of Lisp has been guided more by institutional rivalry, one-upsmanship, and the glee born of technical cleverness that is characteristic of the “hacker culture” than by sober assessments of technical requirements. Nevertheless this process has eventually produced both an industrial-strength programming language, messy but powerful, and a technically pure dialect, small but powerful, that is suitable for use by programming-language theoreticians.

We pick up where McCarthy's paper in the first HOPL conference left off. We trace the development chronologically from the era of the PDP-6, through the heyday of Interlisp and MacLisp, past the ascension and decline of special purpose Lisp machines, to the present era of standardization activities. We then examine the technical evolution of a few representative language features, including both some notable successes and some notable failures, that illuminate design issues that distinguish Lisp from other programming languages. We also discuss the use of Lisp as a laboratory for designing other programming languages. We conclude with some reflections on the forces that have driven the evolution of Lisp.
Array privatization for shared and distributed memory machines (extended abstract)
Authors: Tu Peng , Padua David
Published: November 2005

Memory related anti- and output-dependences can limit the potential parallelism in ordinary programs. In a distributed memory system, improper partition and distribution of data involved in memory related dependences may incur unnecessary communications and load imbalance. In this extended abstract, we present an overview of our work on using array privatization to enhance inherent parallelism and reduce communications.
Fail-safe programming in compiler optimization
Authors: Schilling Jonathan L.
Published: November 2005

Compiler internal errors usually result in the immediate termination of a compilation. However, in the case of internal errors involving optimization, it may instead be possible to proceed with a less-optimized but otherwise correct compilation. A technique is presented that accomplishes this goal. The compiler contexts in which it may be used, and the benefits resulting from it, are discussed.
Two-level grammars are more expressive than Type 0 grammars
Authors: Grune Dick
Published: November 2005

Under some simple conditions, two-level grammars can generate languages with unbounded numbers of terminal symbols; Type 0 grammars cannot.
How does PASCAL-XSC compare to other programming languages with respect to the IEEE standard?
Authors: Janssens Pascal , Cuyt Annie
Published: November 2005

In this report we investigate a number of popular programming languages, when used for scientific computation or computational mathematics. The main aim is to investigate the XSC-philosophy that has been launched in the last few years and has resulted in a number of XSC-extensions of existing programming languages. We also focus on details of the IEEE standard which, although a standard, is never followed completely.
Five principles for the formal validation of models of software metrics
Authors: Ejiogu Lem O.
Published: November 2005

The goal of software metrics is the improvement of the software process. Five principles are fundamental to the formal validation of models of software metrics:--
Attribute Type
--what attribute(s) of software behavior are we measuring?;
The mathematical postulates of a measure function
--a model must have the utility for comparison; this unique criterion must be passed by every effective model of measure;
Metrical Vindication
--applying the model directly to measure actual software module(s); how consistent and reliable are the results of the measures?;
Feedback Effect
--how does the metric help us to identify faults and errors (of design) or improve testing and maintenance; what is a metric if it is just a number?;
Units of Measure
--what are we measuring with respect to dimensions: size, length/depth, extent, degree of variation, degradation, etc.?; a measure without unit(s) is like a building without a roof.Without principles, there is nothing to validate. Every good science is a body of relevant principles. Some worked examples on some of these principles are presented. Some of these examples in a way, expose the failures or frustrations resulting from the applications of some models of measure presently being used in industry and science. Not every mathematical function can be used as a model of measurement.
Detection and recovery of endangered variables caused by instruction scheduling
Authors: Adl-Tabatabai Ali-Reza , Gross Thomas
Published: November 2005

Instruction scheduling re-orders and interleaves instruction sequences from different source statements. This impacts the task of a symbolic debugger, which attempts to present the user a picture of program execution that matches the source program. At a breakpoint
B
, if the value in the run-time location of a variable
V
may not correspond to the value the user expects
V
to have, then this variable is
endangered
at
B
. This paper describes an approach to detecting and recovering endangered variables caused by instruction scheduling. We measure the effects of instruction scheduling on a symbolic debugger's ability to recover source values at a breakpoint. This paper reports measurements for three C programs from the SPEC suite and a collection of programs from the Numerical Recipes, which have been compiled with a variant of a commercial C compiler.
Abstract debugging of higher-order imperative languages
Authors: Bourdoncle François
Published: November 2005

Abstract interpretation is a formal method that enables the static determination (i.e. at compile-time) of the dynamic properties (i.e. at run-time) of programs. We present an abstract interpretation-based method, called
abstract debugging
, which enables the static and formal debugging of programs, prior to their execution, by finding the origin of potential bugs as well as necessary conditions for these bugs not to occur at run-time. We show how
invariant assertions
and
intermittent assertions
, such as termination, can be used to formally debug programs. Finally, we show how abstract debugging can be effectively and efficiently applied to higher-order imperative programs with exceptions and jumps to non-local labels, and present the
Syntox
system that enables the abstract debugging of the
Pascal
language by the determination of the range of the scalar variables of programs.
Implementing type classes
Authors: Peterson John , Jones Mark
Published: November 2005

We describe the implementation of a type checker for the functional programming language Haskell that supports the use of
type classes
. This extends the type system of ML to support overloading (ad-hoc polymorphism) and can be used to implement features such as equality types and numeric overloading in a simple and general way.

The theory of type classes is well understood, but the practical issues involved in the implementation of such systems have not received a great deal of attention. In addition to the basic type checking algorithm, an implmenentation of type classes also requires some form of program transformation. In all current Haskell compilers this takes the form of dictionary conversion, using functions as hidden parameters to overloaded values. We present efficient techniques for type checking and dictionary conversion. A number of optimizations and extensions to the basic type class sytems are also described.
The essence of compiling with continuations
Authors: Flanagan Cormac , Sabry Amr , Duba Bruce F. , Felleisen Matthias
Published: November 2005

In order to simplify the compilation process, many compilers for higher-order languages use the continuation-passing style (CPS) transformation in a first phase to generate an intermediate representation of the source program. The salient aspect of this intermediate form is that all procedures take an argument that represents the rest of the computation (the “continuation”). Since the nai¨ve CPS transformation considerably increases the size of programs, CPS compilers perform reductions to produce a more compact intermediate representation. Although often implemented as a part of the CPS transformation, this step is conceptually a second phase. Finally, code generators for typical CPS compilers treat continuations specially in order to optimize the interpretation of continuation parameters.

A thorough analysis of the abstract machine for CPS terms show that the actions of the code generator
invert
the nai¨ve CPS translation step. Put differently, the combined effect of the three phases is equivalent to a source-to-source transformation that simulates the compaction phase. Thus, fully developed CPS compilers do not need to employ the CPS transformation but can achieve the same results with a simple source-level transformation.
Load/store range analysis for global register allocation
Authors: Kolte Priyadarshan , Harrold Mary Jean
Published: November 2005

Live range splitting techniques improve global register allocation by splitting the live ranges of variables into segments that are individually allocated registers. Load/store range analysis is a new technique for live range splitting that is based on reaching definition and live variable analyses. Our analysis localizes the profits and the register requirements of every access to every variable to provide a fine granularity of candidates for register allocation. Experiments on a suite of C and FORTRAN benchmark programs show that a graph coloring register allocator operating on load/store ranges often provides better allocations than the same allocator operating on live ranges. Experimental results also show that the computational cost of using load/store ranges for register allocation is moderately more than the cost of using live ranges.
Improving the performance of runtime parallelization
Authors: Leung Shun-Tak , Zahorjan John
Published: November 2005

When the inter-iteration dependency pattern of the iterations of a loop cannot be determined statically, compile time parallelization of the loop is not possible. In these cases, runtime parallelization [8] is the only alternative. The idea is to transform the loop into two code fragements: the
inspector
and the
executor
. When the program is run, the inspector examines the iteration dependencies and constructs a parallel schedule. The executor subsequently uses that schedule to carry out the actual computation in parallel.

In this paper, we show how to reduce the overhead of running the inspector through its parallel execution. We describe two related approaches. The first, which emphasizes inspector efficiency, achieves nearly linear speedup relative to a sequential execution of the inspector, but produces a schedule that may be less efficient for the executor. The second technique, which emphasizes executor efficiency, does not in general achieve linear speedup of the inspector, but is guaranteed to produce the best achievable schedule. We present these techniques, show that they are correct, and compare their performance to existing techniques using a set of experiments.

Because in this paper we are optimizing inspector time, but leaving the executor unchanged, the techniques we present have most dramatic effect when the inspector must be run for each invocation of the source loop. In a companion paper [3], we explore techniques that build upon those developed here to also improve executor performance.
Non-concurrency analysis
Authors: Masticola Stephen P. , Ryder Barbara G.
Published: November 2005

Non-concurrency analysis is a set of techniques for statically identifying pairs (or sets) of statements in a concurrent program which can never happen together. This information aids programmers in debugging and manually optimizing programs, improves the precision of data flow analysis, enables optimized translation of rendezvous, facilitates dead code elimination and other automatic optimizations, and allows anomaly detection in explicitly parallel programs. We present a framework for non-concurrency analysis, capable of incorporating previous analysis algorithms [CS88, DS92] and improving upon them. We show general theoretical results which are useful in estimating non-concurrency, and examples of non-concurrency analysis frameworks for two synchronization primitives: the Ada rendezvous and binary semaphores. Both of these frameworks have a low-order polynomial bound on worst-case solution time. We provide experimental evidence that static non-concurrency analysis of Ada programs can be accomplished in a reasonable time, and is generally quite accurate. Our framework, and the set of refinement components we develop, also exhibits dramatic accuracy improvements over [DS91], when the latter is used as a stand-alone algorithm, as demonstrated by our experiments.
Procs and locks
Authors: Morrisett J. Gregory , Tolmach Andrew
Published: November 2005

We have built a portable platform for running Standard ML of New Jersey programs on multiprocessors. It can be used to implement user-level thread packages for multiprocessors
within
the ML language with first-class continuations. The platform supports experimentation with different thread scheduling policies and synchronization constructs. it has been used to construct a Modula-3 style thread package and a version of Concurrent ML, and has been ported to three different multiprocessors running variants of Unix. This paper describes the platform's design, implementation, and performance.
Attribute propagation by message passing
Authors: Demers Alan , Rogers Anne , Zadeck Frank Kenneth
Published: November 2005

The goal of our work is to use the paradigms of syntax-directed editing to perform very sophisticated semantic checking, for example, to check flow-sensitive properties such as whether a variable is necessarily defined before it is used. Semantic checking of this power is much more important than syntax checking because it relieves the programmer of the need to keep track of numerous details as the program grows in complexity.

There has been a great deal of recent work on syntax-directed editing. This work primarily serves the needs of novice programmers: making the task of entering and editing programs easier and less error prone. Most syntax-directed editors guarantee that the program fragment under construction is syntactically correct at all times. Many of them also detect simple semantic errors such as undeclared variables or type errors. Few, however, attempt to perform more semantic analysis than a typical (non-optimizing) compiler.
A semantic editor
Authors: Dybvig R. Kent , Smith Bruce T.
Published: November 2005

We describe an interactive tool for program development and transformation, a
semantic editor.
The domain of the semantic editor is Backus's FP programming language. The editor facilitates manipulation of FP program schemas by the meaning-preserving transformations of FP's algebra of programs. The semantic editor aids program development, program optimization and equivalence proofs. It also serves as a tool for investigating the algebra of programs itself.

The semantic editor does not depend on the existence of normal forms for FP programs. Instead, a history of all program transformations is retained in the system in the form of a congruence relation. The user is free to step through the congruence classes to see different but equivalent versions of his programs. A program equivalence is applied to a program schema by unifying one side of the equivalence with a sub-program, then labeling it congruent to the other side if the unification is successful. A congruence closure algorithm is applied to find any new congruence relations in expressions containing these program schemas.

The program schemas are represented internally by a directed, acyclic graph (
dag
) with identical sub-programs occupying the same sub-graph. The semantic editor uses the Patterson and Wegman unification algorithm and the Nelson and Oppen congruence closure algorithm. Both employ the
dag
representation. The system is implemented in Scheme, a dialect of Lisp.
Relations and attributes
Authors: Horwitz Susan , Teitelbaum Tim
Published: November 2005

The ability to generate language-based editors depends on the existence of a powerful, language-independent model of editing. A model is proposed in which programs are represented as attributed abstract-syntax trees with an associated relational database. Relations can depend on the state of the attributed tree, and attributes can depend on the values in relations, provided there are no circular dependencies.

The power and the limitations of relational operations are demonstrated with respect to the support of static-semantic checking, anomaly detection, an interrogation facility, and the ability to define alternate views of a program. The advantages of the hybrid system over both the purely relational and purely attribute-based systems are presented, and a prototype implementation of an editor generator is discussed. New algorithms are given for query evaluation and incremental view updating motivated by the efficiency requirements of interactive editing under the defined model.
Towards a theory of packages
Authors: Agnarsson Snorri , Krishnamoorthy M. S.
Published: November 2005

A model for packages is introduced, along with operations for their manipulation. The model is based on the unifying principle that programs should be represented by trees, and packages by substitutions on trees. Operations are defined on packages, that allow the construction of any package from a collection of basic packages. A programming environment, based on this model, would allow manipulations and operations that are not possible in current languages. Information hiding and encapsulation are automatically supported by the model. A typing mechanism is presented, which allows polymorphic types. The typing does not affect the typeless aspect of the model.
Structured Editor Support for Modularity and Data Abstraction
Authors: Caplinger Michael
Published: November 2005

Language facilities for data abstraction and modularity have traditionally involved extensions to the declaratory syntax of the languages. Batch compiler technology forces the separation of the editing of this syntax from its being checked by the compiler, making programming more difficult.

We discuss an alternate method of supporting such features in a language-based structured editor. Rather than adding syntax to the language, we simply use the editor to restrict uses of names. In order to specify the restrictions, we provide a language-independent notion of
names
and
scopes
in our abstract syntax tree.
Using ABC to prototype VDM specifications
Authors: Kans Aaron , Hayton Clive
Published: November 2005

ABC is a high-level, easy-to-use imperative language, designed originally as a replacement for BASIC. Although intended primarily as a teaching language, it has many powerful attributes that make it suitable as a language for the rapid prototyping of formal specifications. This paper illustrates how ABC was used to prototype specifications written in the formal specification language of VDM.
Inheritance of interface specifications (extended abstract)
Authors: Leavens Gary T.
Published: November 2005

Four alternatives for the semantics of inheritance of specifications are discussed. The information loss and frame axiom problems for inherited specifications are also considered.
Application of OOP type theory
Authors: Eifrig Jonathan , Smith Scott , Trifonov Valery , Zwarico Amy
Published: November 2005

Important strides toward developing expressive yet semantically sound type systems for object-oriented programming languages have recently been made by Cook, Bruce, Mitchell, and others. This paper focusses on how the theoretical work using F-bounded quantification may be brought more into the realm of actual language implementations while preserving rigorous soundness properties. We simultaneously address three of the more significant problems: adding a notion of global state, proving type-checking is decidable, and integrating the more widely implemented view that subclasses correspond to subtypes with the F-bounded view.
Virtual images
Authors: Vion-Dury Jean-Yves , Santana Miguel
Published: November 2005

In spite of growing needs in many areas, there is a lack of powerful graphical interfaces for interacting with large and complex sets of objects. Debugging, management and monitoring tools for object-oriented distributed systems or databases, for instance, need new interfaces that allow high quality visualization and interaction.

We propose to use 3D interactive animations for representing large numbers of objects, complex relationships, and dynamic execution of concurrent activities. These innovative graphical representations, that we call
virtual images
, provide a consistent and intuitive solution for integrating various functionalities, considerably increasing the amount of information processed by the user. This technique has been successfully applied without specific hardware, demonstrating the feasibility of such interfaces on non specialized workstations.