bluuebunny/crossref_metadata_2025 huggingface dataset:
Jungloid mining
Authors: Mandelin David , Xu Lin , Bodík Rastislav , Kimelman Doug
Published: November 2005

Reuse of existing code from class libraries and frameworks is often difficult because APIs are complex and the client code required to use the APIs can be hard to write. We observed that a common scenario is that the programmer knows what type of object he needs, but does not know how to write the code to get the object.In order to help programmers write API client code more easily, we developed techniques for synthesizing
jungloid
code fragments automatically given a simple query that describes that desired code in terms of input and output types. A jungloid is simply a unary expression; jungloids are simple, enabling synthesis, but are also versatile, covering many coding problems, and composable, combining to form more complex code fragments. We synthesize jungloids using both API method signatures and jungloids
mined
from a corpus of sample client programs.We implemented a tool,
prospector
, based on these techniques.
prospector
is integrated with the Eclipse IDE code assistance feature, and it infers queries from context so there is no need for the programmer to write queries. We tested
prospector
on a set of real programming problems involving APIs;
prospector
found the desired solution for 18 of 20 problems. We also evaluated
prospector
in a user study, finding that programmers solved programming problems more quickly and with more reuse when using
prospector
than without
prospector
.
Essential language support for generic programming
Authors: Siek Jeremy G. , Lumsdaine Andrew
Published: November 2005

Concepts
are an essential language feature for generic programming in the large. Concepts allow for succinct expression of constraints on type parameters of generic algorithms, enable systematic organization of problem domain abstractions, and make generic algorithms easier to use. In this paper we present the design of a type system and semantics for concepts that is suitable for non-type-inferencing languages. Our design shares much in common with the type classes of Haskell, though our primary influence is from best practices in the C++ community, where concepts are used to document type requirements for templates in generic libraries. Concepts include a novel combination of associated types and same-type constraints that do not appear in type classes, but that are similar to nested types and type sharing in ML.
Semantic type qualifiers
Authors: Chin Brian , Markstrum Shane , Millstein Todd
Published: November 2005

We present a new approach for supporting user-defined type refinements, which augment existing types to specify and check additional invariants of interest to programmers. We provide an expressive language in which users define new refinements and associated type rules. These rules are automatically incorporated by an
extensible typechecker
during static typechecking of programs. Separately, a
soundness checker
automatically proves that each refinement's type rules ensure the intended invariant, for all possible programs. We have formalized our approach and have instantiated it as a framework for adding new type qualifiers to C programs. We have used this framework to define and automatically prove sound a host of type qualifiers of different sorts, including pos and neg for integers, tainted and untainted for strings, and nonnull and unique for pointers, and we have applied our qualifiers to ensure important invariants on open-source C programs.
Permission-based ownership
Authors: Krishnaswami Neel , Aldrich Jonathan
Published: November 2005

Today's module systems do not effectively support information hiding in the presence of shared mutable objects, causing serious problems in the development and evolution of large software systems. Ownership types have been proposed as a solution to this problem, but current systems have ad-hoc access restrictions and are limited to Java-like languages.In this paper, we describe System F

own

, an extension of System F with references and ownership. Our design shows both how ownership fits into standard type theory and the encapsulation benefits it can provide in languages with first-class functions, abstract data types, and parametric polymorphism. By looking at ownership in the setting of SystemF, we were able to develop a design that is more principled and flexible than previous ownership type systems, while also providing stronger encapsulation guarantees.
Code placement for improving dynamic branch prediction accuracy
Authors: Jiménez Daniel A.
Published: November 2005

Code placement techniques have traditionally improved instruction fetch bandwidth by increasing instruction locality and decreasing the number of taken branches. However, traditional code placement techniques have less benefit in the presence of a trace cache that alters the placement of instructions in the instruction cache. Moreover, as pipelines have become deeper to accommodate increasing clock rates, branch misprediction penalties have become a significant impediment to performance. We evaluate
pattern history table partitioning
, a feedback directed code placement technique that explicitly places conditional branches so that they are less likely to interfere destructively with one another in branch prediction tables. On SPEC CPU benchmarks running on an Intel Pentium 4, branch mispredictions are reduced by up to 22% and 3.5% on average. This reduction yields a speedup of up to 16.0% and 4.5% on average. By contrast, branch alignment, a previous code placement technique, yields only up to a 4.7% speedup and less than 1% on average.
Garbage collection without paging
Authors: Hertz Matthew , Feng Yi , Berger Emery D.
Published: November 2005

Garbage collection offers numerous software engineering advantages, but interacts poorly with virtual memory managers. Existing garbage collectors require far more pages than the application's working set and touch pages without regard to which ones are in memory, especially during full-heap garbage collection. The resulting paging can cause throughput to plummet and pause times to spike up to seconds or even minutes. We present a garbage collector that avoids paging. This
bookmarking collector
cooperates with the virtual memory manager to guide its eviction decisions. Using summary information ("bookmarks") recorded from evicted pages, the collector can perform in-memory full-heap collections. In the absence of memory pressure, the bookmarking collector matches the throughput of the best collector we tested while running in smaller heaps. In the face of memory pressure, it improves throughput by up to a factor of five and reduces pause times by up to a factor of 45 over the next best collector. Compared to a collector that consistently provides high throughput (generational mark-sweep), the bookmarking collector reduces pause times by up to 218x and improves throughput by up to 41x. Bookmarking collection thus provides greater utilization of available physical memory than other collectors while matching or exceeding their throughput.
Demystifying on-the-fly spill code
Authors: Aletà Alex , Codina Josep M. , Gonzàlez Antonio , Kaeli David
Published: November 2005

Modulo scheduling is an effective code generation technique that exploits the parallelism in program loops by overlapping iterations. One drawback of this optimization is that register requirements increase significantly because values across different loop iterations can be live concurrently. One possible solution to reduce register pressure is to insert spill code to release registers. Spill code stores values to memory between the producer and consumer instructions.Spilling heuristics can be divided into two classes: 1)
a posteriori
approaches (spill code is inserted after scheduling the loop) or 2)
on-the-fly
approaches (spill code is inserted during loop scheduling). Recent studies have reported obtaining better results for spilling
on-the-fly
. In this work, we study both approaches and propose two new techniques, one for each approach. Our new algorithms try to address the drawbacks observed in previous proposals. We show that the new algorithms outperform previous techniques and, at the same time, reduce compilation time. We also show that, much to our surprise,
a posteriori
spilling can be in fact slitghtly more effective than
on-the-fly
spilling.
DART
Authors: Godefroid Patrice , Klarlund Nils , Sen Koushik
Published: November 2005

We present a new tool, named DART, for automatically testing software that combines three main techniques: (1)
automated
extraction of the interface of a program with its external environment using static source-code parsing; (2) automatic generation of a test driver for this interface that performs
random
testing to simulate the most general environment the program can operate in; and (3) dynamic analysis of how the program behaves under random testing and automatic generation of new test inputs to
direct
systematically the execution along alternative program paths. Together, these three techniques constitute
Directed Automated Random Testing
, or
DART
for short. The main strength of DART is thus that testing can be performed
completely automatically
on any program that compiles -- there is no need to write any test driver or harness code. During testing, DART detects standard errors such as program crashes, assertion violations, and non-termination. Preliminary experiments to unit test several examples of C programs are very encouraging.
Shangri-La
Authors: Chen Michael K. , Li Xiao Feng , Lian Ruiqi , Lin Jason H. , Liu Lixia , Liu Tao , Ju Roy
Published: November 2005

Programming network processors is challenging. To sustain high line rates, network processors have extremely tight memory access and instruction budgets. Achieving desired performance has traditionally required hand-coded assembly. Researchers have recently proposed high-level programming languages for packet processing, but the challenges of compiling these languages into code that is competitive with hand-tuned assembly remain unanswered.This paper describes the Shangri-La compiler, which accepts a packet program written in a C-like high-level language and applies scalar and specialized optimizations to generate a highly optimized binary. Hot code paths identified by profiling are mapped across processing elements to maximize processor utilization. Since our compilation target has no hardware caches, software-controlled caches are generated for frequently accessed application data structures. Packet handling optimizations significantly reduce per-packet memory access and instruction counts. Finally, a custom stack model maps stack frames to the fastest levels of the target processor's heterogeneous memory hierarchy.Binaries generated by the compiler were evaluated on the Intel IXP2400 network processor with eight packet processing cores and eight threads per core. Our results show the importance of both traditional and specialized optimization techniques for achieving the maximum forwarding rates on three network applications,
L3-Switch, MPLS
and
Firewall
.
Threads cannot be implemented as a library
Authors: Boehm Hans-J.
Published: November 2005

In many environments, multi-threaded code is written in a language that was originally designed without thread support (e.g. C), to which a library of threading primitives was subsequently added. There appears to be a general understanding that this is not the right approach. We provide specific arguments that a pure library approach, in which the compiler is designed independently of threading issues, cannot guarantee correctness of the resulting code.We first review why the approach almost works, and then examine some of the surprising behavior it may entail. We further illustrate that there are very simple cases in which a pure library-based approach seems incapable of expressing an efficient parallel algorithm.Our discussion takes place in the context of C with Pthreads, since it is commonly used, reasonably well specified, and does not attempt to ensure type-safety, which would entail even stronger constraints. The issues we raise are not specific to that context.
PADS
Authors: Fisher Kathleen , Gruber Robert
Published: November 2005

PADS is a declarative data description language that allows data analysts to describe both the physical layout of ad hoc data sources and semantic properties of that data. From such descriptions, the PADS compiler generates libraries and tools for manipulating the data, including parsing routines, statistical profiling tools, translation programs to produce well-behaved formats such as Xml or those required for loading relational databases, and tools for running XQueries over raw PADS data sources. The descriptions are concise enough to serve as "living" documentation while flexible enough to describe most of the ASCII, binary, and Cobol formats that we have seen in practice. The generated parsing library provides for robust, application-specific error handling.
Composing security policies with polymer
Authors: Bauer Lujo , Ligatti Jay , Walker David
Published: November 2005

We introduce a language and system that supports definition and composition of complex run-time security policies for Java applications. Our policies are comprised of two sorts of methods. The first is
query
methods that are called whenever an untrusted application tries to execute a security-sensitive action. A query method returns a
suggestion
indicating how the security-sensitive action should be handled. The second sort of methods are those that perform state updates as the policy's suggestions are followed.The structure of our policies facilitates composition, as policies can query other policies for suggestions. In order to give programmers control over policy composition, we have designed the system so that policies, suggestions, and application events are all first-class objects that a higher-order policy may manipulate. We show how to use these programming features by developing a library of policy combinators.Our system is fully implemented, and we have defined a formal semantics for an idealized subset of the language containing all of the key features. We demonstrate the effectiveness of our system by implementing a large-scale security policy for an email client.
Efficient application migration under compiler guidance
Authors: Zhang Kun , Pande Santosh
Published: November 2005

Mobile computing based upon wireless technology as the interconnect and PDAs, Web-enabled cell phones etc. as the end devices provide a rich infrastructure for anywhere, anytime information access. Wireless connectivity also poses tough problems [11, 12]. Network nodes may be mobile and the connectivity could be sporadic. In many cases, application mobility involving migration from one network node to another could provide interesting possibilities. However, the migration process is expensive in terms of both time and power overheads. To minimize the migration cost, an efficient strategy must decide which parts of the program should migrate to continue execution and at which program point the migration should take place.In this work we develop a compiler framework to achieve the above two goals. First, the potential migration points are decided by analyzing the call chains in the code. Then the compiler determines what parts of the program are dead at these points. At run time, using the current context of the call chain, a decision on whether to migrate now or later is taken. Such a decision depends mainly upon the cost of migration involved at the current program point vs. at a later potential migration point. Our experiments with multimedia applications show that both the migration state and the latency are significantly reduced by our techniques over the base case of migration with full state in the absence of any compiler guidance. Thus, the key contribution of the paper is to provide an efficient migration methodology removing barriers to application mobility.
Composable code generation for distributed giotto
Authors: Henzinger Thomas A. , Kirsch Christoph M. , Matic Slobodan
Published: November 2005

We present a compositional approach to the implementation of hard real-time software running on a distributed platform. We explain how several code suppliers, coordinated by a system integrator, can independently generate different parts of the distributed software. The task structure, interaction, and timing is specified as a Giotto program. Each supplier is given a part of the Giotto program and a timing interface, from which the supplier generates task and scheduling code. The integrator then checks, individually for each supplier, in pseudo-polynomial time, if the supplied code meets its timing specification. If all checks succeed, then the supplied software parts are guaranteed to work together and implement the original Giotto program. The feasibility of the approach is demonstrated by a prototype implementation.
Transparent distribution of real-time components based on logical execution time
Authors: Farcas Emilia , Farcas Claudiu , Pree Wolfgang , Templ Josef
Published: November 2005

This paper introduces the notion of transparent distribution of real time software components. Transparent distribution means that (1) the functional and temporal behavior of a system is the same no matter where a component is executed, (2) the developer does not have to care about the differences of local versus distributed execution of components, and (3) the components can be developed independently. We present the design and implementation of a component model for real time systems that is well suited for transparent distribution. The component model is based on logical execution time, which abstracts from physical execution time and thereby from both the execution platform and the communication topology.
System-wide compaction and specialization of the linux kernel
Authors: Chanet Dominique , De Sutter Bjorn , De Bus Bruno , Van Put Ludo , De Bosschere Koen
Published: November 2005

The limited built-in configurability of Linux can lead to expensive code size overhead when it is used in the embedded market. To overcome this problem, we propose the application of link-time compaction and specialization techniques that exploit the
a priori
known, fixed run-time environment of many embedded systems. In experimental setups based on the ARM XScale and i386 platforms, the proposed techniques are able to reduce the kernel memory footprint with over 16%. We also show how relatively simple additions to existing binary rewriters can implement the proposed techniques for a complex, very unconventional program such as the Linux kernel. Finally, we pinpoint an important code size growth problem when compaction and compression techniques are combined on the ARM platform.
Scalable precision cache analysis for preemptive scheduling
Authors: Staschulat Jan , Ernst Rolf
Published: November 2005

Accurate timing analysis is key to efficient embedded system synthesis and integration. Caches are needed to increase the processor performance but they are hard to use because of their complex behavior especially in preemptive scheduling. Current approaches use simplified assumptions or propose exponentially complex analysis algorithms to bound the cache related preemption delay at a context switch. Existing approaches consider only direct mapped caches or propose non conservative approximation for set associative caches.In this paper we propose a novel cache related preemption delay analysis for set-associative instruction caches where the designer can adjust the analysis precision by scaling the problem complexity. Furthermore, this precise preemption delay analysis is integrated into a scheduling analysis to determine the response time of tasks accurately. In experiments we evaluate this tradeoff between analysis precision and analysis time. The results show an improvement of 22%-71% in analysis precision of cache related preemption delay and 5%-21% in response time analysis compared to previous conservative approaches.
Feedback EDF scheduling exploiting hardware-assisted asynchronous dynamic voltage scaling
Authors: Zhu Yifan , Mueller Frank
Published: November 2005

Recent processor support for dynamic frequency and voltage scaling (DVS) allows software to affect power consumption by varying execution frequency and supply voltage on the fly. However, processors generally enter a sleep state while transitioning between frequencies/voltages. In this paper, we examine the merits of hardware/software co-design for a feedback DVS algorithm and a novel processor capable of executing instructions during frequency/voltage transitions. We study several power-aware feedback schemes based on earliest-deadline-first (EDF) scheduling that adjust the system behavior dynamically for different workload characteristics. An infrastructure for investigating several hard real-time DVS schemes, including our feedback DVS algorithm, is implemented on an IBM PowerPC 405LP embedded board. Architecture and algorithm overhead is assessed for different DVS schemes. Measurements on the experimentation board provide a quantitative assessment of the potential of energy savings for DVS algorithms as opposed to prior simulation work that could only provide trends. Energy consumption, measured through a data acquisition board, indicates a considerable potential for real-time DVS scheduling algorithms to lower energy up to 64% over the naïve DVS scheme. Our feedback DVS algorithm saves at least as much and often considerably more energy than previous DVS algorithms with peak savings of an additional 24% energy reduction. To the best of our knowledge, this is the first comparative study of real-time DVS algorithms on a concrete micro-architecture and the first evaluation of asynchronous DVS switching.
Revisiting an automatic program inverter for Lisp
Authors: Glück Robert , Kawabe Masahiko
Published: November 2005

We reformulate the Korf-Eppstein method for automatic inversion of
first-order functional programs using a structural operational
semantics and compare it with the program inversion method
described by Gries. We analyze the method and suggest possible
extensions. The method is noteworthy in that it was used to
construct the first automatic program inverter described in the
literature. The key features of the Korf-Eppstein method are the
simultaneous inversion of an injective system of functions, an
equation-oriented transformation, and the use of postcondition
inference heuristics.
An approach to automatic testing exception handling
Authors: Jiang Shujuan , Zhang Yongping , Yan Dashun , Jiang Yuanpeng
Published: November 2005

Exception handling mechanism can increase the reliability of the system and improve the robustness of the software. But the exception handling code that is used to respond to exceptional conditions tends to be the source of the systems failure. It is difficult to test the exception handling by usual methods. This paper proposes an approach to automatic testing of exception handling based on analyzing the problems encountered during testing exception handling. The method of testing exception handling is efficient through combining the structure of exception handling with "assertion violation". It also gives the supporting tool that has been designed for the method.
The anatomy of a loop
Authors: Shivers Olin
Published: November 2005

Writing loops with tail-recursive function calls is the equivalent of writing them with goto's. Given that loop packages for Lisp-family languages have been around for over 20 years, it is striking that none have had much success in the Scheme world. I suggest the reason is that Scheme forces us to be precise about the scoping of the various variables introduced by our loop forms, something previous attempts to design ambitious loop forms have not managed to do.I present the design of a loop package for Scheme with a well-defined and natural scoping rule, based on a notion of control dominance that generalizes the standard lexical-scope rule of the λ-calculus. The new construct is powerful, clear, modular and extensible.The loop language is defined in terms of an underlying language for expressing control-flow graphs. This language itself has interesting properties as an intermediate representation.
An expressive language of signatures
Authors: Ramsey Norman , Fisher Kathleen , Govereau Paul
Published: November 2005

Current languages allow a programmer to describe an interface only by enumerating its parts, possibly including other interfaces wholesale. Such languages cannot express relationships between interfaces, yet when independently developed software components are combined into a larger system, significant relationships arise.To address this shortcoming, we define, as a conservative extension of ML, a language for manipulating interfaces. Our language includes operations for adding, renaming, and removing components; for changing the type associated with a value; for making manifest types abstract and vice versa; and for combining interfaces. These operations can express useful relationships among interfaces. We have defined a formal semantics in which an interface denotes a group of four sets; we show how these sets determine a subtyping relation, and we sketch the elaboration of an interface into its denotation.
Dynamic optimization for functional reactive programming using generalized algebraic data types
Authors: Nilsson Henrik
Published: November 2005

A limited form of dependent types, called Generalized Algebraic Data Types (GADTs), has recently been added to the list of Haskell extensions supported by the Glasgow Haskell Compiler. Despite not being full-fledged dependent types, GADTs still offer considerably enlarged scope for enforcing important code and data invariants statically. Moreover, GADTs offer the tantalizing possibility of writing more efficient programs since capturing invariants statically through the type system sometimes obviates entire layers of dynamic tests and associated data markup. This paper is a case study on the applications of GADTs in the context of Yampa, a domain-specific language for Functional Reactive Programming in the form of a self-optimizing, arrow-based Haskell combinator library. The paper has two aims. Firstly, to explore what kind of optimizations GADTs make possible in this context. Much of that should also be relevant for other domain-specific embedded language implementations, in particular arrow-based ones. Secondly, as the actual performance impact of the GADT-based optimizations is not obvious, to quantify this impact, both on tailored micro benchmarks, to establish the effectiveness of individual optimizations, and on two fairly large, realistic applications, to gauge the overall impact. The performance gains for the micro benchmarks are substantial. This implies that the Yampa API could be simplified as a number of "pre-composed" primitives that were there mainly for performance reasons are no longer needed. As to the applications, a worthwhile performance gain was obtained in one case whereas the performance was more or less unchanged in the other.
A step-indexed model of substructural state
Authors: Ahmed Amal , Fluet Matthew , Morrisett Greg
Published: November 2005

The concept of a "unique" object arises in many emerging programming languages such as Clean, CQual, Cyclone, TAL, and Vault. In each of these systems, unique objects make it possible to perform operations that would otherwise be prohibited (e.g., deallocating an object) or to ensure that some obligation will be met (e.g., an opened file will be closed). However, different languages provide different interpretations of "uniqueness" and have different rules regarding how unique objects interact with the rest of the language.Our goal is to establish a common model that supports each of these languages, by allowing us to encode and study the interactions of the different forms of uniqueness. The model we provide is based on a substructural variant of the polymorphic λ-calculus, augmented with four kinds of mutable references: unrestricted, relevant, affine, and linear. The language has a natural operational semantics that supports deallocation of references, strong (type-varying) updates, and storage of unique objects in shared references. We establish the strong soundness of the type system by constructing a novel, semantic interpretation of the types.
Simple, partial type-inference for System F based on type-containment
Authors: Rémy Didier
Published: November 2005

We explore partial type-inference for System F based on type-containment. We consider both cases of a purely functional semantics and a call-by-value stateful semantics. To enable type-inference, we require higher-rank polymorphism to be user-specified via type annotations on source terms. We allow implicit predicative type-containment and explicit impredicative type-instantiation. We obtain a core language that is both as expressive as System F and conservative over ML. Its type system has a simple logical specification and a partial type-reconstruction algorithm that are both very close to the ones for ML. We then propose a surface language where some annotations may be omitted and rebuilt by some algorithmically defined but logically incomplete elaboration mechanism.
Scrap your nameplate
Authors: Cheney James
Published: November 2005

Recent research has shown how
boilerplate
code, or repetitive code for traversing datatypes, can be eliminated using generic programming techniques already available within some implementations of Haskell. One particularly intractable kind of boilerplate is
nameplate
, or code having to do with names, name-binding, and fresh name generation. One reason for the difficulty is that operations on data structures involving names, as usually implemented, are not regular instances of standard
map
,
fold
, or
zip
operations. However, in
nominal abstract syntax
, an alternative treatment of names and binding based on swapping, operations such as α-equivalence, capture-avoiding substitution, and free variable set functions are much better-behaved.In this paper, we show how nominal abstract syntax techniques similar to those of FreshML can be provided as a Haskell library called
FreshLib
. In addition, we show how existing genericmprogramming techniques can be used to reduce the amount of nameplate code that needs to be written for new datatypes involving names and binding to almost nothing—in short, how to
scrap your nameplate
.
Scrap your boilerplate with class
Authors: Lämmel Ralf , Jones Simon Peyton
Published: November 2005

The 'Scrap your boilerplate' approach to generic programming allows the programmer to write generic functions that can traverse arbitrary data structures, and yet have type-specific cases. However, the original approach required all the type-specific cases to be supplied at once, when the recursive knot of generic function definition is tied. Hence, generic functions were
closed
. In contrast, Haskell's type classes support
open
, or extensible, functions that can be extended with new type-specific cases as new data types are defined. In this paper, we extend the 'Scrap your boilerplate' approach to support this open style. On the way, we demonstrate the desirability of abstraction over type classes, and the usefulness of recursive dictionarie.
A plea for readable pleas for a readable Prolog programming style
Authors: Kaplan Randy M.
Published: November 2005

Writing a plea for a readable Prolog programming style is not like writing most pleas. In writing a plea for a readable Prolog programming style in particular, one could possibly bring forth many results. This means that
special care
must be taken when writing a plea for a readable Prolog programming style. Not only must the plea be readable, it must also be written in such a way as to make clear the process of writing well-styled Prolog programs.Plea writing makes use of a set of rules to specify how a certain task might be accomplished. In general, if these rules are written without attention to their meaning, there is no telling how the style of a particular Prolog program will be affected. It is from this aspect of plea writing both the power and danger of plea writing arise.We will attempt to discuss ways in which pleas for a readable Prolog programming style may be written so that they may be clearly understood and applied to make Prolog programs more readable. We will also give an example of the application of plea writing rules by writing a plea and then applying this plea to excerpts of Prolog code.
Turtle walk through functional language
Authors: Zoran Putnik , Zoran Budimac , Mirjana Ivanovic
Published: November 2005

In this paper implementation and usage of a turtle graphics in (pure) functional programming language - LispKit Lisp is described. With all basic graphics functions available, implementation of a turtle graphics is enabled. Since turtle graphics is second most common way of using graphics, this implementation is a significant improvement of LispKit Lisp abilities. All necessary functions of a turtle graphics are implemented in LispKit Lisp, and they simply should be appended to any program which uses them.
Automated generation of code using backtracking parsers for attribute grammars
Authors: Keller Wolfgang
Published: November 2005

Code generation with the Graham Glanville scheme can be improved, using backtracking parsers for attribute grammars. This eliminates semantic and syntactic blocking during code selection and guarantees the cheapest code possible, if desired. Multipass translation allows the use of nontrivial register allocation strategies. The code generator generator system BECC is a LALR(1) based backtracking parser generator for a derivate of S-attributed grammars which provides several interpreters that differ in their abilities and performance.
Universal editor unattainable
Authors: Yovev C. S.
Published: November 2005

A universal editor problem has been formulated, based on a notion of editability specified by a class of formal text-manipulation models - T-spaces, for which editability is equivalent to computability.Unlike the superficially similar universal Turing machine problem, the universal editor problem and its complement are not r.e., so the ultimate universal editor is an unattainable goal.Thus the bad news is that we cannot manipulate all editable languages in all possible ways. Nevertheless, there are good news as well: we can still manipulate all r.e. languages in some ways.
Preliminary ideas of a conceptual programming language
Authors: Zhai Cheng-xiang
Published: November 2005

This paper presents the preliminary ideas of a relational conceptual programming language CONPL (CONceptual Programming Language). CONPL allows users to use their own concepts instead of computer-related concepts to construct the program. It can also be used as a knowledge representation language. The paper gives the formal description of CONPL and discusses some implementation issues. The paper also explores its potential applications.
Object oriented programming techniques to replace software components on the fly in a running program
Authors: Stadel Manfred
Published: November 2005

Many systems, e. g. embedded systems, process control systems, or telecommunication switching systems cannot be stopped running to modify and extend their software. It must be possible to replace software components on the fly by new versions while the program is running. It is shown how object oriented programming techniques can help do design and implement a software system such that its components are dynamically replaceable at run time.
GCODE
Authors: Joy Mike , Axford Tom
Published: November 2005

The data structures used in the authors' functional language graph reduction implementations are described, together with a standard notation for representing the graphs in a textual format. The data structures employed are tailored to the intermediate functional language FLIC. The textual format is designed to be transmittable easily across networks. This document details the changes in the notation that have evolved since the previous specification [1] was published.
The IL programming language
Authors: Kaplan Randy M.
Published: November 2005

IL
is a language for developing mouse-driven interactive applications. It is an example of a "little language" as described by Jon Bentley (1986). We conceived
IL
as a tool for building interactive applications based on an event-driven model. When an event occurs, the systems performs one or more specified actions. By supporting this interactive model the programmer can concentrate on the details of the interactive application as opposed to the details of a specific interaction.
Lucinda—an overview
Authors: Butcher Paul , Zedan Hussein
Published: November 2005

This document describes the courting of Linda (a coordination language) by Russell (a computation language), and the subsequent conception of their child Lucinda. Mother and baby are both doing well.A number of disadvantages with current Linda implementations are discussed, and a new language, Lucinda, is proposed to overcome them. Lucinda provides multiple, typed tuple spaces, polymorphism, and a novel approach to data structuring and storage.
Semantic correctness of structural editing
Authors: Gruźlewski Tadeusz , Weiss Zbigniew
Published: November 2005

Typical structural editor provides for syntax correctness of an edited text. In this paper some problems are discussed that arise when the semantic analysis is to be included in the tasks of a structural editor. The solution to these problems, already implemented in Modelang editor, is presented. It is based on the concept of multistage editing operations and application of default values. Several examples are given to show how the editor should deal with basic Pascal constructs in order to preserve full semantic accuracy. Additionally, two solutions are proposed to the problem of name maintenance within the structural editor. Structural editing versus conditional compilation is also considered.
A theory of organization
Authors: von Issendorff Hermann
Published: November 2005

A theory of organization has been presented last year in the August and September issue of SIGPLAN Notices. Meanwhile some errors and several additional transformation rules were discovered. They are listed below following the order of the paper.
SNOOPS
Authors: Craske Noel
Published: November 2005

The OOP paradigm developed from a desire to provide an environment within which data and procedures could be easily represented homogeneously. The OOPLs developed under this paradigm achieved the goal by representing everything using the same basic structure called an
object
.All OOPLs provide the ability to define objects, classes, and to manipulate them. However, they do not provide a means for introducing newly created classes of objects and previously existing classes without editing the methods on those objects. SNOOPS, an extension to the Scheme Object System --- SCOOPs, was developed to provide this facility as part of a language [Craske, 1988]. Initial research was aimed at developing an ITS that had the ability to select dynamically an appropriate Student Model, Tutor Model, Interface and lesson structure as determined by the interaction with individual students [Craske and Richards, 1988a, 1988b]. It soon became apparent that managing the complexity of the system required a means to simplify the addition of new objects. Our approach was to let the software itself assume responsibility for its' own structure by creating
Intelligent Manager Objects
(meta-objects). Instances
Manager
had the ability to redirect messages to any object, including instances of newly created classes. Thus maintenance in a system built from SNOOPS is centred on instances of class
Manager
.
Analysis and refutation of the LCAS
Authors: Kahan W.
Published: November 2005

A Language Compatible Arithmetic Standard (LCAS) has been proposed as International Standard ISO/IEC 10967:1991 for
Language Compatible Arithmetic
, Project JTC. 22.28, Version 3.1 (1 March 1991), by Drs. Mary Payne and Brian Wichmann. An earlier version appeared in both ACM SIGNUM and ACM SIGPLAN 25 1 (Jan. 1990). The following remonstrance has been sent to ANSI X3-T2, the American committee in charge of the proposal:This proposed Language Compatible Arithmetic Standard is so severely flawed that the computing world must reject it.
Edison, a Unix and C friendly Rete based production system
Authors: Thirion Bernard
Published: November 2005

This document introduces the architecture and the implementation of a rule based system especially devised to be integrated in the C and UNIX world. Built around the Edison knowledge description language and its translator, the environment features an inference engine using the Rete algorithm as well as a trace mechanism and a debugger. The who set can be used in full autonomy to design an expert system, or it can be integrated into a wider application as a software component. We shall describe the Edison language, its translation, the development environment and the performances of our production system.
Computing A*B (mod N) efficiently in ANSI C
Authors: Baker Henry G.
Published: November 2005

The modular product computation A*B (mod N) is a bottleneck for some public-key encryption algorithms, as well as many exact computations implemented using the Chinese Remainder Theorem. We show how to compute A*B (mod N) efficiently, for single-precision A, B, and N, on a modern RISC architecture (Intel 80860) in ANSI C. On this architecture, our method computes A*B (mod N) faster than ANSI C computes A%N, for unsigned longs A and N.
Arrays and pointers considered harmful
Authors: Ince D. C.
Published: November 2005

Formal methods of software development are becoming important topics in software engineering as evidenced by the fact that three important publications
IEEE Transactions on Software Engineering, IEEE Software
and
IEEE Computer
were recently devoted to this topic. This paper looks at the effect that current problems with formal methods might have on language design. The paper describes what a formal method of software development is, provides an example of a mathematical specification and then, by examining the problems involved in formal data refinement, puts forward the proposition that we should now regard the array and the pointer in the same way that we regarded the goto statement during the seventies.
A FORTRAN IV to QuickBASIC translator
Authors: Caringal Rizaldo B. , Dung Phan Minh
Published: November 2005

This paper describes the design and implementation of an automatic translator from standard FORTRAN IV to QuickBASIC, a structured form of the programming language BASIC. The translator makes two passes on the input program before finally generating the translated program. The converter not only performs lexical, syntactic and limited forms of semantic analyses on the source program, but it also recovers from any errors encountered. It was implemented using the C programming language in the Disk Operating System (DOS) environment and was successfully ported to UNIX. Furthermore, the contingencies to cope with other dialects of the source language have been defined, and the problems encountered in the implementation process are discussed.
Optimal chaining in expression trees
Authors: Bernstein David , Boral Haran , Pinter Ron Y.
Published: November 2005

Chaining is the ability to pipeline two or more vector instructions on Cray-1 like machines. We show how to optimally use this feature to compute (vector) expression trees, in the context of automatic code-generation. We present a linear-time scheduling algorithm for finding an optimal order of evaluation for a machine with a bounded number of registers.
Generation of run-time environments
Authors: Kaiser Gail E.
Published: November 2005

Attribute grammars have been used for many years for automated compiler construction. Attribute grammars support the description of semantic analysis, code generation and some code optimization in a formal declarative style. Other tools support the automation of lexical analysis and parsing. However, there is one large part of compiler construction that is missing from our toolkit: run-time environments. This paper introduces an extension of attribute grammars that supports the generation of run-time environments. The extension also supports the generation of interpreters, symbolic debugging tools, and other execution-time facilities.
Interprocedural optimization: eliminating unnecessary recompilation
Authors: Cooper Keith D. , Kennedy Ken , Torczon Linda
Published: November 2005

While efficient new algorithms for interprocedural data flow analysis have made these techniques practical for use in production compilation systems, a new problem has arisen: collecting and using interprocedural information in a compiler introduces subtle dependences among the procedures of a program. If the compiler depends on interprocedural information to optimize a given module, a subsequent editing change to
another
module in the program may change the interprocedural information and necessitate recompilation. To avoid having to recompile every module in a program in response to a single editing change to one module, we must develop techniques to more precisely determine which compilations have actually been invalidated by a change to the program's source. This paper presents a general
recompilation test
to determine which procedures must be compiled in response to a series of editing changes. Three different implementation strategies, which demonstrate the fundamental tradeoff between the cost of analysis and the precision of the resulting test, are also discussed.
Transformations of denotational semantics in semantics directed compiler generation
Authors: Royer Veronique
Published: November 2005

In semantics-directed compiler generation one is faced with the problem of how to translate a source semantic definition of a programming language into on equivalent target semantics closer to an implementation. Most of the existing works solve this problem in a non constructive way : a target semantics is exhibited first and then only proved correct against the source. We try to show that target semantics can be derived from source semantics in a constructive way and so that some correctness ideas are automatically preserved. The framework is denotational semantics.
Effectiveness of a machine-level, global optimizer
Authors: Johnson Mark S. , Miller Terrence C.
Published: November 2005

We present an overview of the design of a machine-code-level, global (intraprocedural) optimizer that supports several front-ends producing code for the Hewlett-Packard Precision Architecture family of machines. The basic optimization strategy is described, including information about the division of responsibilities between various components of the compiler. Optimization algorithms are described, including a discussion of the dataflow information they require. Measurements showing the collective and individual effects of various optimizer components are presented.

The performance data presented here was collected using a preliminary version of the optimizer. Development is continuing and further improvements are expected.
Data flow analysis for `intractable' system software
Authors: Johnson Harold
Published: November 2005

We describe, and give experience with, a new method of intraprocedural data flow analysis on reducible flow-graphs[9]. The method is advantageous in imbedded applications where the added value of improved performance justifies substantial optimization effort, but extremely powerful data flow analysis is required due to the code profile.

The method is unusual in that (1) various kinds of forward data flow analysis are done simultaneously, so that benefit is derived from informative interactions (e.g. between constant propagation[7] and alias analysis[8]) and (2) we abandon insistence on reaching a least fixed point, allowing us to handle extremely broad classes of information (e.g., inequality of array indices, which implies non-aliasing in array references).

We argue that the gain from using a very rich framework more than offsets the loss due to non-minimal fixed points, and justify this with a 'thought experiment' and practical results.