bluuebunny/crossref_metadata_2025 huggingface dataset:
A systematic approach to multiple inheritance implementation
Authors: Templ J.
Published: November 2005

Multiple inheritance is commonly believed to increase the expressive power of a programming language, but to slow down efficiency of message sends even in case of single inheritance. This paper shows that none of these arguments hold. First, a technique to express the effect of multiple inheritance in terms of single inheritance is described. Based on this technique an efficient implementation of multiple inheritance is constructed. The resulting implementation does not slow down single inheritance and, in case of multiple inheritance, is more efficient than widely used implementations.
And/Or parallel execution of logic programs
Authors: Yuhua Zheng , Honglei Tu , Li Xie
Published: November 2005

This paper proposes a new And/Or parallel execution model (FORDAP) for logic programs which can not only exploit full Or- and independent And-parallelism, but also can exploit dependent And-parallelism with a limited increment of runtime cost. A synchronization mechanism is constructed on a shared variable between its producer and its consumers and a consumer with a large granularity is decomposed further to let its subgoals independent to that producer to execute without delay. A granularity computation algorithm is presented for the control of a goal's decomposition.
The birth of Prolog
Authors: Colmerauer Alain , Roussel Philippe
Published: November 2005

The programming language, Prolog, was born of a project aimed not at producing a programming language but at processing natural languages; in this case, French. The project gave rise to a preliminary version of Prolog at the end of 1971 and a more definitive version at the end of 1972. This article gives the history of this project and describes in detail the preliminary and then the final versions of Prolog. The authors also felt it appropriate to describe the Q-systems since it was a language which played a prominent part in Prolog's genesis.
The early history of Smalltalk
Authors: Kay Alan C.
Published: November 2005

Most ideas come from previous ideas. The sixties, particularly in the ARPA community, gave rise to a host of notions about “human-computer symbiosis” through interactive time-shared computers, graphics screens and pointing devices. Advanced computer languages were invented to simulate complex systems such as oil refineries and semi-intelligent behavior. The soon to follow paradigm shift of modern personal computing, overlapping window interfaces, and object-oriented design came from seeing the work of the sixties as something more than a “better old thing”. That is, more than a better way: to do mainframe computing; for end-users to invoke functionality; to make data structures more abstract. Instead the promise of exponential growth in computing/$/volume demanded that the sixties be regarded as “almosta new thing” and to find out what the actual “new things” might be. For example, one would compute with a handheld “Dynabook” in a way that would not be possible on a shared mainframe; millions of potential users meant that the user interface would have to become a learning environment along the lines of Montessori and Bruner; and needs for large scope, reduction in complexity, and end-user literacy would require that data and control structures be done away with in favor of a more biological scheme of protected universal cells interacting only through messages that could mimic any desired behavior.

Early Smalltalk was the first complete realization of these new points of view as parented by its many predecessors in hardware, language and user interface design. It became the exemplar of the new computing, in part, because we were actually trying for a qualitative shift in belief structures—a new Kuhnian paradigm in the same spirit as the invention of the printing press—and thus took highly extreme positions which almost forced these new styles to be invented.
A history of C++
Authors: Stroustrup Bjarne
Published: November 2005

This paper outlines the history of the C++ programming language. The emphasis is on the ideas, constraints, and people that shaped the language, rather than the minuitiae of language features. Key design decisions relating to language features are discussed, but the focus is on the overall design goals and practical constraints. The evolution of C++ is traced from C with Classes to the current ANSI and ISO standards work and the explosion of use, interest, commercial activity, compilers, tools, environments, and libraries.
Kernel-control parallel versus data parallel
Authors: Pratt Terrence W.
Published: November 2005

The
dusty deck problem
is the problem of how to automatically transform large existing serial/vector codes into a form suitable for efficient execution on new parallel architectures.
Kernel-control parallel
(KCP) methods provide a promising approach to solving the dusty deck problem for MIMD distributed memory machines. This paper is a status report on a project to develop this technology into a full-scale prototype for running large Fortran 77 codes on the Intel iPSC/860. Space limits preclude a full description of the methods. Instead, we sketch the approach and then use a series of questions to explore some of the key differences between this new technology and existing data parallel methods, which are similar but better known.
Optimal evaluation of array expressions on massively parallel machines (extended abstract)
Authors: Chatterjee Siddhartha , Gilbert John R. , Schreiber Robert , Teng Shang-Hua
Published: November 2005

We investigate the problem of optimal evaluation of Fortran-90 style array expressions on a massively parallel distributed-memory machine. On such machines, an elementwise operation can be performed in unit time for arrays whose corresponding elements are in the same processor. If the arrays are not aligned in this manner, the cost of alignment is part of the cost of expression evaluation. The choice of where to perform the operation then affects this cost. We demonstrate how a dynamic programming technique can be applied to solve this problem efficiently for a wide variety of interconnection schemes, including multidimensional grids and rings, hypercubes, and fat-trees. We also consider the variant where the operations may change the shape of the arrays, and show that our approach extends naturally to handle this case.
Library for architecture-independent development of structured grid applications
Authors: Lemke Max , Quinlan Daniel
Published: November 2005

P++ is an innovative user environment that simplifies the development of efficient, parallel programs for large scale scientific applications. It permits portability across the widest variety of computer architectures. The target machines are distributed memory computers with different types of node architectures (scalar, vector, or superscalar), but the requirements of shared memory computers are also addressed. Unfortunately, robust, architecture-independent and efficient software environments have been notable to date primarily by their absence. Such a simplifying environment for the development of software is sorely needed to take advantage of the current and future developments in advanced computational hardware. The P++ environment does this using a standard language, C++, with absolutely no modification of the compiler. For parallel communication it employs existing widely portable communications libraries. Such an environment allows existing C++ language compilers to be used to develop software in the preferred serial environment, and such software to be efficiently run, unchanged, in all target environments.The explicit goal of P++ is the support of advanced computational methods for the solution of large-scale computational problems. For efficiency reasons and also for simplification, the use of P++ is restricted to the large class of structured grid methods for partial differential equations. Applications using P++ can selectively exploit the added degree of freedom presented by parallel processing by use of an optimization module within the array language interface. A collection of defaults ensures deterministic behavior. In this way, complicated optimization issues of parallel execution may be easily introduced by the setting of switches within the user interface, which are then interpreted at runtime. Through the use of Virtual Shared Memory, restricted to array variables (Virtual Shared Grids), issues such as partitioning become matters of optimization, and not criteria for correct execution. Due to the restriction and optimization for structured grids, we expect the same parallel performance as for codes based on the traditionally used explicit Message Passing model. To speed the development of the P++ environment, we use an efficient, commercially available array language library, M++, developed in C++; the M++ array interface is also used as the P++ array interface.Recognizing that the acceptance of advanced parallel computers depends on their use by scientists, and not parallel researchers, it is hoped that P++ will simplify access to these parallel machines. While significantly simplifying our own research on parallel self adaptive local refinement methods, it is hoped that P++ will more generally simplify the introduction of structured grid methods for large scale scientific computing onto advanced parallel machines.
On subprograms with a variable number of parameters of varying types
Authors: Baowen Xu
Published: November 2005

Subprograms are the fundamental building blocks of program, and are therefore among the important concepts in programming language design. The effect and function of programs is affected by their parameter mechanisms. This paper describes two facilities: number-variable parameters and type-variable parameters. These two parameter mechanisms do not decrease the efficiency and reliability of a subprogram, and are very useful in many software development, especially in general software package development.
On the type extensions of Oberon-2
Authors: Nigro Libero
Published: November 2005

Oberon-2, the latest Prof. N. Wirth language design, supports object - oriented (OO) programming through an original record type extension mechanism. The language is expected to gain a growing acceptance both in the academic and industrial worlds. This short note aims to make a critical evaluation of Oberon-200 facilities by showing how the current language definition can be too restrictive in the building of usual type hierarchies like those allowed, for instance, by C++. A minor extension is suggested which improves the effectiveness of Oberon-2.
Parallel bounded quantification—preliminary results
Authors: Arro Henrik , Barklund Jonas , Bevemyr Johan
Published: November 2005

We have extended D. H. D. Warren's abstract machine for sequential Prolog with parallel instructions that implement bounded quantifications, an extension to Prolog proposed by Barklund and Bevemyr. These instructions are intended for parallel computers supporting the data parallel programming model. Luther, an emulator for the sequential abstract machine implemented in the C programming language, has been extended with these instructions, implemented in the data parallel C* programming language.We have coded three example programs that use bounded quantifications, and run them in the emulator on a Connection Machine model 200, a SIMD parallel computer. We compare the run times on this parallel computer with the run times obtained with a sequential implementation of bounded quantifications on a SUN-4M sequential computer.The best result is that one parallel bounded quantification program runs 30 times faster on the Connection Machine than an ordinary recursive program implementing the same algorithm running on the sequential computer. It is conceivable that one can obtain far higher speed-ups when running on larger data parallel computers using bounded quantifications.
Projecting functional models of imperative programs
Authors: Harman M. , Danicic S.
Published: November 2005

Functional modelling [17,29] enables functional reasoning methods to be applied to programs written in imperative languages. It is, however, the view of many workers [4, 24] that it is not the notation in which a program is written, but the sheer
size
of a program which prohibits the application of reasoning and proof techniques.The beauty of Projection is that
simple
aspects of programs have correspondingly
simple
models, irrespective of the size and complexity of the overall imperative program.We describe the Projection technique, showing how it allows for the manageable application of functional language technology to 'real' imperative programs. We demonstrate how Projection may facilitate the development of a proof of a program in terms of its constituents and how Projection may allow programmers to select the safety-critical sections of programs for particular attention.We briefly discuss the connection between Projection and Slicing, introduced by Weiser [34,35], and give examples of the functional programming techniques made available to imperative programmers by virtue of functional modelling. Specifically, we use formal proof [23, 24, 4], Transformation [5, 9] and Partial Evaluation [14, 16, 31]. We claim that the Projection of functional models lends itself to the analysis and proof of existing computer software written in imperative programming languages.
Blocks and procedures
Authors: Kießling Heiko , Krüger Uwe
Published: November 2005

Mössenböck proposes the
argument block
as a language construct for using statement sequences as arguments for procedures [Mös92]. Such a construct enables users to define their own control structures. Mössenböck is inspired by S
MALLTALK
-80 [GR83] and claims that most languages lack support of argument blocks but does not take into account a quality which in practice is crucial to their utilization. Stolz [Sto93] therefore falsely concludes the equivalence of argument blocks and anonymous procedures and points out that anonymous procedures were already supported in ALGOL 68 [vWMP
+
76]. We show the difference between blocks and procedures and describe implementation patterns which are taken under consideration for the programming language A
RISTARCH
/L. A
RISTARCH
/L is supposed to support the distributed operating system A
RISTARCH
/OS which is under development in S
AMOS
, a project undertaken by the Operating Systems Research Group at the University of Karlsruhe.
Efficient accommodation of may-alias information in SSA form
Authors: Cytron Ron , Gershbein Reid
Published: November 2005

We present an algorithm for incrementally including may-alias information into Static Single Assignment form by computing a sequence of increasingly precise (and correspondingly larger) partial SSA forms. Our experiments show significant speedup of our method over exhaustive use of may-alias information, as optimization problems converge well before most may-aliases are needed.
Dependence-based program analysis
Authors: Johnson Richard , Pingali Keshav
Published: November 2005

Program analysis and optimization can be speeded up through the use of the
dependence flow graph
(DFG), a representation of program dependences which generalizes def-use chains and static single assignment (SSA) form. In this paper, we give a simple graph-theoretic description of the DFG and show how the DFG for a program can be constructed in
O(EV)
time. We then show how forward and backward dataflow analyses can be performed efficiently on the DFG, using constant propagation and elimination of partial redundancies as examples. These analyses can be framed as solutions of dataflow equations in the DFG. Our construction algorithm is of independent interest because it can be used to construct a program's control dependence graph in
O(E)
time and its SSA representation in
O(EV)
time, which are improvements over existing algorithms.
Interprocedural constant propagation
Authors: Grove Dan , Torczon Linda
Published: November 2005

An implementation of interprocedural constant propagation must model the transmission of values through each procedure. In the framework proposed by Callahan, Cooper, Kennedy, and Torczon in 1986, this intraprocedural propagation is modeled with a
jump function
. While Callahan
et al.
propose several kinds of jump functions, they give no data to help choose between them. This paper reports on a comparative study of jump function implementations. It shows that different jump functions produce different numbers of useful constants; it suggests a particular function, called the
pass-through parameter jump function
, as the most cost-effective in practice.
Orchestrating interactions among parallel computations
Authors: Graham Susan L. , Lucco Steven , Sharp Oliver
Published: November 2005

Many parallel programs contain multiple sub-computations, each with distinct communication and load balancing requirements. The traditional approach to compiling such programs is to impose a processor synchronization barrier between sub-computations, optimizing each as a separate entity. This paper develops a methodology for managing the interactions among sub-computations, avoiding strict synchronization where concurrent or pipelined relationships are possible.

Our approach to compiling parallel programs has two components: symbolic data access analysis and adaptive runtime support. We summarize the data access behavior of sub-computations (such as loop nests) and split them to expose concurrency and pipelining opportunities. The split transformation has been incorporated into an extended FORTRAN compiler, which outputs a FORTRAN 77 program augmented with calls to library routines written in C and a coarse-grained dataflow graph summarizing the exposed parallelism.

The compiler encodes symbolic information, including loop bounds and communication requirements, for an adaptive runtime system, which uses runtime information to improve the scheduling efficiency of irregular sub-computations. The runtime system incorporates algorithms that allocate processing resources to concurrently executing sub-computations and choose communication granularity. We have demonstrated that these dynamic techniques substantially improve performance on a range of production applications including climate modeling and x-ray tomography, expecially when large numbers of processors are available.
First-class data-type representations in SCHEMEXEROX
Authors: Adams Norman , Curtis Pavel , Spreitzer Mike
Published: November 2005

In most programming language implementations, the compiler has detailed knowledge of the representations of and operations on primitive data typed and data-type constructors. In SCHEMEXEROX, this knowledge is almost entirely external to the compiler, in ordinary, procedural user code. The primitive representations and operations are embodied in first-class “representation types” that are constructed and implemented in an abstract and high-level fashion. Despite this abstractness, a few generally-useful optimizing transformations are sufficient to allow the SCHEMEXEROX compiler to generate efficient code for the primitive operations, essentially as good as could be achieved using more contorted, traditional techniques.
Handling control
Authors: Sitaram Dorai
Published: November 2005

Non-local control transfer and exception handling have a long tradition in higher-order programming languages such as Common Lisp, Scheme and ML. However, each language stops short of providing a full and complementary approach—control handling is provided
only
if the corresponding control operator is first-order. In this work, we describe handlers in a higher-order control setting. We invoke our earlier theoretical result that all denotational models of control languages invariably include capabilities that handle control. These capabilities, when incorporated into the language, form an elegant and powerful higher-order generalization of the first-order exception-handling mechanism.
Space efficient conservative garbage collection
Authors: Boehm Hans-Juergen
Published: November 2005

We call a garbage collector conservative if it has only partial information about the location of pointers, and is thus forced to treat arbitrary bit patterns as though they might be pointers, in at least some cases. We show that some very inexpensive, but previously unused techniques can have dramatic impact on the effectiveness of conservative garbage collectors in reclaiming memory. Our most significant observation is that static data that appears to point to the heap should not result in misidentified references to the heap. The garbage collector has enough information to allocate around such references. We also observe that programming style has a significant impact on the amount of spuriously retained storage, typically even if the collector is not terribly conservative. Some fairly common C and C++ programming style significantly decrease the effectiveness of any garbage collector. These observations suffice to explain some of the different assessments of conservative collection that have appeared in the literature.
Balanced scheduling
Authors: Kerns Daniel R. , Eggers Susan J.
Published: November 2005

Traditional list schedulers order instructions based on an optimistic estimate of the load delay imposed by the implementation. Therefore they cannot respond to variations in load latencies (due to cache hits or misses, congestion in the memory interconnect, etc.) and cannot easily be applied across different implementations. We have developed an alternative algorithm, known as balanced scheduling, that schedule instructions based on an estimate of the amount of instruction level parallelism in the program. Since scheduling decisions are program-rather than machine-based, balanced scheduling is unaffected by implementation changes. Since it is based on the amount of instruction level parallelism that a program can support, it can respond better to variations in load latencies. Performance improvements over a traditional list scheduler on a Fortran workload and simulating several different machine types (cache-based workstations, large parallel machines with a multipath interconnect and a combination, all with non-blocking processors) are quite good, averaging between 3% and 18%.
Reverse If-Conversion
Authors: Warter Nancy J. , Mahlke Scott A. , Hwu Wen-Mei W. , Rau B. Ramakrishna
Published: November 2005

In this paper we present a set of isomorphic control transformations that allow the compiler to apply local scheduling techniques to acyclic subgraphs of the control flow graph. Thus, the code motion complexities of global scheduling are eliminated. This approach relies on a new technique, Reverse If-Conversion (RIC), that transforms scheduled If-Converted code back to the control flow graph representation. This paper presents the predicate internal representation, the algorithms for RIC, and the correctness of RIC. In addition, the scheduling issues are addressed and an application to software pipelining is presented.
Branch prediction for free
Authors: Ball Thomas , Larus James R.
Published: November 2005

Many compilers rely on branch prediction to improve program performance by identifying frequently executed regions and by aiding in scheduling instructions.
Profile-based
predictors require a time-consuming and inconvenient compile-profile-compile cycle in order to make predictions. We present a
program-based
branch predictor that performs well for a large and diverse set of programs written in C and Fortran. In addition to using natural loop analysis to predict branches that control the iteration of loops, we focus on heuristics for predicting non-loop branches, which dominate the dynamic branch count of many programs. The heuristics are simple and require little program analysis, yet they are effective in terms of coverage and miss rate. Although program-based prediction does not equal the accuracy of profile-based prediction, we believe it reaches a sufficiently high level to be useful. Additional type and semantic information available to a compiler would enhance our heuristics.
Exploiting task and data parallelism on a multicomputer
Authors: Subhlok Jaspal , Stichnoth James M. , O'Hallaron David R. , Gross Thomas
Published: November 2005

For many applications, achieving good performance on a private memory parallel computer requires exploiting data parallelism as well as task parallelism. Depending on the size of the input data set and the number of nodes (i.e., processors), different tradeoffs between task and data parallelism are appropriate for a parallel system. Most existing compilers focus on only one of data parallelism and task parallelism. Therefore, to achieve the desired results, the programmer must separately program the data and task parallelism. We have taken a unified approach to exploiting both kinds of parallelism in a single framework with an existing language. This approach eases the task of programming and exposes the tradeoffs between data and task parallelism to compiler. We have implemented a parallelizing Fortran compiler for the iWarp system based on this approach. We discuss the design of our compiler, and present performance results to validate our approach.
ActorSpace: an open distributed programming paradigm
Authors: Agha Gul , Callsen Christian J.
Published: November 2005

We present a new programming paradigm called ActorSpace. ActorSpace provides a new communication model based on
destination patterns
. An
actorSpace
is a computationally passive container of actors which acts as a context for matching patterns. Patterns are matched against listed attributes of actors and actorSpaces that are
visible
in the actorSpace. Both visibility and attributes are dynamic. Messages may be sent to one or all members of a group defined by a pattern. The paradigm provides powerful support for component-based construction of massively parallel and distributed applications. In particular, it supports open interfaces to servers and pattern-directed access to software repositories.
Using scheduler information to achieve optimal barrier synchronization performance
Authors: Kontothanassis Leonidas , Wisniewski Robert W.
Published: November 2005

Parallel programs frequently use barriers to synchronize successive steps in an algorithm. In the presence of multiprogramming the choice of spinning versus blocking barriers can have a significant impact on performance. We demonstrate how competitive spinning techniques previously designed for locks can be extended to barriers, and we evaluate their performance. We design an additional competitive spinning technique that adapts more quickly in a dynamic environment. We then propose and evaluate a new method that obtains better peformance than previous techniques by using scheduler information to decide between spinning and blocking. The
scheduler information
technique makes optimal choices incurring little overhead.
Implementation of a portable nested data-parallel language
Authors: Blelloch Guy E. , Hardwick Jonathan C. , Chatterjee Siddhartha , Sipelstein Jay , Zagha Marco
Published: November 2005

This paper gives an overview of the implementation of NESL, a portable nested data-parallel language. This language and its implementation are the first to fully support nested data structures as well as nested data-parallel function calls. These features allow the concise description of parallel algorithms on irregular data, such as sparse matrices and graphs. In addition, they maintain the advantages of data-parallel languages: a simple programming model and portability. The current NESL implementation is based on an intermediate language called VCODE and a library of vector routines called CVL. It runs on the Connection Machine CM-2, the Cray Y-MP C90, and serial machines. We compare initial benchmark results of NESL with those of machine-specific code on these machines for three algorithms: least-squares line-fitting, median finding, and a sparse-matrix vector product. These results show that NESL's performance is competitive with that of machine-specific codes for regular dense data, and is often superior for irregular data.
Computation migration
Authors: Hsieh Wilson C. , Wang Paul , Weihl William E.
Published: November 2005

We describe
computation migration
, a new technique that is based on compile-time program transformations, for accesing remote data in a distributed-memory parallel system. In contrast with RPC-style access, where the access is performed remotely, and with data migration, where the data is moved so that it is local, computation migration moves part of the current thread to the processor where the data resides. The access is performed at the remote processor, and the migrated thread portion continues to run on that same processor; this makes subsequent accesses in the thread portion local.

We describe an implementation of computation migration that consists of two parts: an implementation that migrates single activation frames, and a high-level language annotation that allows a programmer to express when migration is desired. We performed experiments using two applications; these experiments demonstrate that computation migration is a valuable alternative to RPC and data migration.
Dialogues
Authors: O'Donnell John T.
Published: November 2005

The components of a programming environment must communicate with the user while maintaining a state that is constantly evolving. We introduce the “dialogue”, an abstraction of such components, and we implement a dialogue function in a purely applicative language. The dialogue function exploits the properties of lasy evaluation and recursion to implement communication and state through recursively defined streams. We show how to define programming environment components using dialogues. The components of the resulting programming environment are consistent in their treatment of communication and state.
The PSG - Programming System Generator
Authors: Bahlke Rolf , Snelting Gregor
Published: November 2005

The programming system generator developed at the Technical University of Darmstadt generates sophisticated interactive programming environments from formal language definitions. From a formal, entirely non-procedural definition of the language's syntax, context conditions and denotational semantics, it produces a hybrid editor, an interpreter and a library system. The editor allows both structure editing and text editing, guaranteeing immediate recognition of syntactic and semantic errors. The generator has been used to generate environments for PASCAL, MODULA-2 and the formal language definition language itself. A brief description of the generated environments and the definition language is given, and our experiences with formal language definitions are discussed from the language definer's point of view as well as from the programmer's point of view using the generated environments.
An algebra for program fragments
Authors: Kristensen Bent Bruun , Madsen Ole Lehrmann , Møller-Pedersen Birger , Nygaard Kristen
Published: November 2005

Program fragments are described either by strings in the concrete syntax or by constructor applications in the abstract syntax. By defining conversions between these forms, both may be intermixed. Program fragments are constructed by terminal and nonterminal symbols from the grammar and by variables having program fragments as values. Basic operations such as valuetransfer, composition and decomposition are defined for program fragments allowing more complicated operations to be implemented. Usual operations such as testing for equality are defined, and in addition more specialized operations such as testing that a program fragment is derivable from another and converting program fragments in concrete form to abstract form are defined. By introducing regular expressions in the grammar these may be used in program fragments in concrete form. By defining constructors for regular expressions these may also be used in program fragments in abstract form.
A model and an implementation of a logic programming environment
Authors: Komorowski Henryk Jan , Omori Shigeo
Published: November 2005

It has been claimed that logic programming offers outstanding possibilities for new concepts in programming environments. But with the exceptions of the pioneering work of Shapiro on algorithmic debugging, Pereira's rational debugging and early work on expert systems from Imperial College, there has been little progress reported in the field of logic programming environments. This summary describes our current work on a generic software engineering shell for logic programming. We use reflection and the amalgamation of meta-level language with the object level to express and support the
incremental
character of specifying/programming. An important facet of the shell is that we formalize some aspects of programming methodology and provide heuristics for avoiding errors. These heuristics formalize what experienced programmers may already know.

The shell bears similarities to an expert system since it has explanation mechanisms and provides programming-knowledge acquisition. Currently, it supports single user Prolog programming and runs in C-Prolog. The shell is generic in that it provides support for activities ranging from artificial intelligence programming to formal specification development.

This research has been supported in part by the IBM Young Faculty Development Award and in part by the NSF grant # MCS-84-05079.
Integration mechanisms in Cedar
Authors: Donahue James
Published: November 2005

The importance of integration in programming environments is well known. Perhaps the easiest way to build an integrated system is to build a closed system; the designers of the system can use whatever ad hoc techniques are available to make the pieces they provide hang together nicely. Many of the integrated editor/compiler/execution environments (like the Cornell Program Synthesizer) fall into this category [Teitelbaum81].

When building an open system, the problem for the designers of the system is not to integrate a fixed collection of tools, but to provide general mechanisms for tool integration. For instance, Unix “pipes” provide an elegant means of integrating new tools by making it easy to make the output of one tool the input of another; also, the simplicity of the Unix file system makes it easy to integrate new devices into the system - the file system conceals the physical peculiarities of the devices instead of making them visible [Kernighan81].
Module types, module variables, and their use as a universal encapsulation mechanism
Authors: Radenski Atanas
Published: November 2005

The objective of this paper is to develop a universal encapsulation mechanism which can serve as a single substitute for classes, packages, records and subroutines. The proposed mechanism, the module type, is based on a modification of the traditional meaning of the concept of type. A module type defines a collection of entities, such as constants, types, variables, and optionally, a module body. A module type can be used to declare module variables. The body of a module variable can be activated by a module call.It is demonstrated how module types can implement classes, and how module variables can serve the need for packages, subroutines, and records.The concept of module type is embedded in an experimental language whose main features are briefly described in the paper. A prototype compiler for this language has been developed. The implementation scheme is also discussed.Module types and module variables have uncomplicated and intuitively clear semantics. As a result, they are simple to use, and they allow more efficient implementation compared to traditional encapsulation mechanisms.The paper outlines a programming language experiment and is not aimed at a formal theoretical study of module types.
The self-similarity and computer programs
Authors: Kokol Peter
Published: November 2005

The concept of fractals and their underlaying feature of self- similarity is now used in many scientific areas like philosophy, medicine, engineering etc, In the present paper I would like to present two examples in which the concept of self similarity is concerned with the characteristics of computer programs, namely structure of variables and the frequency of reserved words and operators (Zipf's Low).It is always better to say right out what you think without trying to prove anything much: for all our proofs are only variations of our opinions, and the contrary-minded listen neither to one nor other.
Parsing with C++ classes
Authors: Conway Damian
Published: November 2005

Philip W. Hall IV [1] has outlined a preprocessor technique for building recursive descent parsers using C++ constructor functions. This paper presents an alternative C++-based parser generation scheme which uses a hierarchy of classes with appropriately overloaded operators to embed the actual grammar of one or more parsers in a standard C++ source file. This approach eliminates the need for preprocessing of source files and permits the use of parsing schemes somewhat more sophisticated than simple statically-defined recursive descent.
Propagation of Constants and Assertions
Authors: Sakharov Alexander
Published: November 2005

Constant propagation is a well-known data flow analysis time calculations and deletion of unreachable code. In this paper, constant propagation is generalized to allow propagation of a wider class of assertions. Along this class includes controlling expressions of assignments. The problem of propagating these assertions monotone data flow analysis frameworks. Propagation of the assertions enables additional deletion of assignments and redirection of control flow.
Propagation of constants and assertions
Authors: Sakharov Alexander
Published: November 2005

Constant propagation is a well-known data flow analysis problem. Constant propagation enables compiletime calculations and deletion of unreachable code. In this paper, constant propagation is generalized to allow propagation of a wider class of assertions. Along with equalities between variables and constants, this class includes controlling expressions of conditional branches and equalities originating from program assignments. The problem of propagating these assertions is solved by application of the mechanism of monotone data flow analysis frameworks. Propagation of the assertions enables additional optimizations: deletion of assignments and redirection of control flow.
Configurable REC
Authors: Cisneros Gerardo
Published: November 2005

This paper describes CREC, a library of C functions for compiling and executing REC programs whose operators and predicates are provided by the caller. Given a C program with a menu-based interactive interface, REC can be added as a programming language to the user interface by assigning menu choices to REC operators and predicates through entries in a table, and linking in the appropriate functions in CREC. Being a very concise language, REC programs are easy to write in an interactive context. The same conciseness allows the compiler to require only a small amount of space. Experience whereby the library benefitted some mathematics and physics programs is described.
Continuations without copying
Authors: Burson Scott L.
Published: November 2005

Common implementations of first-class continuations for Scheme involve copying the continuation when it is captured, when it is invoked, or both. Standard ML of New Jersey, on the other hand, creates all continuation frames in the heap to begin with; this eliminates the copying required for capture and invocation, but also gives up the optimization of using the "stack pop" operation to deallocate frames that have
not
been captured. In this paper, we show how to eliminate both copying steps while retaining efficient stack-wise deallocation for uncaptured flames.
Agent language NUML and its reduction implementation model based on HOπ
Authors: Manwu Xu , Jianfeng Lu , Fancong Zeng , Jingwen Dai
Published: November 2005

Higher--order π--calculus(HOπ)[3.4.6]] is a computation model with sufficient computation capability. It is suitable to describe the concurrency in computation. In this paper, the agent language NUML which is designed to describe DAI (distributed artificial intelligence) systems is presented; also its semantics in HOπ is given and finalliy a reduction implementation model of NUML based on HOπ is submitted.
A path-based method of parallelizing C++ programs
Authors: Zhu Genjiang , Xie Li , Sun Zhongxiu
Published: November 2005

This paper presents a path-based method for identifying parallelism in C++ programs and proposes an execution model which trades off the efficiency and parallelism. Based on the path information provided at compiler time or computed at run time, the model reduces the rollbacks while enhances the parallelism.
A review of exploitation of AND-parallelism and combined AND/OR-parallelism in logic programs
Authors: Zhang Kang
Published: November 2005

Logic programs provide many opportunities for parallel execution. Among different forms of parallelism found in logic programs, AND-parallelism and OR-parallelism have shown to be most effective in speeding up the execution of logic programs. This paper offers a review of major activities in exploiting AND-parallelism and combined AND/OR-parallelism. Full version of this paper (23 pages) can be retrieved through anonymous ftp from ftp.mpce.mq.edu.au.
Non-linear type extensions
Authors: Brown Bob
Published: November 2005

Type extension is a language facility proposed by N. Wirth and included in the programming language Oberon. The facility allows a type to be created based on another type while maintaining a hierarchic type relationship. This paper gives an introduction to the type extension facility as it is implemented in Oberon and shows how it can be generalised to allow a non-linear type hierarchy to be constructed and discriminated.
A geometrical data-parallel language
Authors: Dekeyser Jean-Luc , Lazure Dominique , Marquet Philippe
Published: November 2005

The HELP project proposes a model of data-parallel programming allowing a programmer to develop an algorithm the nearest of his thought. Usually, for many parts of a data-parallel program, the manipulations of data could be modelized as geometrical migrations in side a cartesian reference space.We define the language C-HELP in the frame of explicit data-parallel languages, the communications and the computations are separated, moreover any vector description is banished.This model and the associated languages are based on the hyper-space notion, and the algorithm development follows an original semantic of computations limited to a set of hyper-space points. The hyper-space is not only a compilation-oriented concept but consists in a multi-dimentional virtual array integrated at the programming model and provides a referential for any object access.
Developing an interprocedural optimizing compiler
Authors: Loeliger Jon
Published: November 2005

Compilers that perform interprocedural analysis require different user interfaces and different internal architectures than those used by compilers that process procedures independently. CONVEX Computer Corp. has developed a language-independent interprocedural optimizer that is packaged together with FORTRAN and C compilers in a product called the Application Compiler. User feedback and experience compiling large applications had a significant impact on the final user interface and system architecture.
ADL—an interface definition language for specifying and testing software
Authors: Sankar Sriram , Hayes Roger
Published: November 2005

This paper describes an interface definition language called ADL which extends OMG's CORBA interface definition language with formal specification constructs. In addition to ADL's use in formal documentation, ADL's primary use is for testing software. ADL can be adapted for use with most programming languages.This paper also presents an overview of a testing technology based on ADL and presents the highlights of a test-data description language (TDD) used to describe test-data.
Using interface inheritance to address problems in system software evolution
Authors: Hamilton Graham , Radia Sanjay
Published: November 2005

Two specific problems faced in large distributed systems are (1) evolving and managing different versions of an interface while minimizing the impact on existing clients, and (2) supporting the addition of auxiliary interfaces that are orthogonal to the main interface of an abstraction.In the context of the Spring distributed system, we addressed both problems using an object-oriented interface definition language. Different versions of an interface are represented as different types with an inheritance relationship that minimizes the impact on existing clients and allows easy management of versions.We distinguish between fundamental and auxiliary properties each of which are defined as separate types. Rather than use simple root inheritance, we use a combination of root and leaf inheritance. This provides flexibility in supporting auxiliary properties and allows us to add new auxiliary properties as the system evolves without forcing the system to be recompiled.The solutions have been tested and refined through their use in the Spring system.
Typechecking and modules for multi-methods
Authors: Chambers Craig , Leavens Gary T.
Published: November 2005

Two major obstacles hindering the wider acceptance of multi-methods are concerns over the lack of encapsulation and modularity and the absence of static typechecking in existing multi-method-based languages. This paper addresses both of these problems. We present a polynomial-time static typechecking algorithm that checks the conformance, completeness, and consistency of a group of method implementations with respect to declared message signatures. This algorithm improves on previous algorithms by handling separate type and inheritance hierarchies, abstract classes, and graph-based method lookup semantics. We also present a module system that enables independently-developed code to be fully encapsulated and statically typechecked on a per-module basis. To guarantee that potential conflicts between independently-developed modules have been resolved, a simple well-formedness condition on the modules comprising a program is checked at link-time. The typechecking algorithm and module system are applicable to a range of multi-method-based languages, but the paper uses the Cecil language as a concrete example of how they can be applied.
Type-theoretic foundations for concurrent object-oriented programing
Authors: Kobayashi Naoki , Yonezawa Akinori
Published: November 2005

A number of attempts have been made to obtain type systems for object-oriented programming. The view that lies common is “
object-oriented programming = λ-calculus + record
.” Based on an analogous view “
concurrent object-oriented programming = concurrent calculus + record
,” we develop a static type system for concurrent object-oriented programming. We choose our own Higher-Order ACL as a basic concurrent calculus, and show that a concurrent object-oriented language can be easily encoded in the Higher-Order ACL extended with record operations. Since Higher-Order ACL has a strong type system with a polymorphic type inference mechanism, programs of the concurrent object-oriented language can be automatically type-checked by the encoding in Higher-Order ACL. Our approach can give clear accounts for complex mechanisms such as inheritance and method overriding within a simple framework.