We will start by introducing the concept of ``Open Implementations''. We will suggest that one of the key questions in designing an open implementation is deciding how much language or compiler support is required to support a particular open implementation interface. The bulk of the note will be used to present systems and approaches that use varying degrees of language and compiler support. Where possible, systems with a numerical bent are highlighted.
The term, open implementation, has coined by Kiczales's group at PARC. The group's Open Implementation home page can be found at [26].
The first questions to be asked in designing an open implementation are,
[14] discusses design guidelines for ``open implementations''. This table, adapted from one at the end of the paper, summaries the design guidelines presented in the paper,
| Interface Style | How Strategy is Selected | Tradeoffs | When appropriate |
| Style A - No implementation strategy control interface | Module can do whatever it wants. Can be adaptive. | Same as Black-Box Abstraction | One implementation strategy is enough. Or, module can adequately pick the strategy. |
| Style B - Client provides declarative information about its use. ``sequential file scan.'' | Module matches against user's usage. | Usage does not uniquely specify implementation. Patterns are hidden; why is the user to know which usage patterns will result in which implementation? | When the module can do an adequate job with the declarative usage description. |
| Style C - Client specifies the implementation strategy. ``LRU cache management.'' | User selects strategy. | User may pick the wrong strategy. Fixed number of strategies. | There are few candidate implementation strategies, but it is difficult to choose among them automatically |
| Style D - Client provides the implementation strategy. ``Here a function pointer for the policy.'' | User provides the strategy. | User has complete control, but the module might be very difficult to engineer. The user may find implementing the strategies difficult. | It is not feasible for the module to implement alll strategies. |
[22] presents a methodology for developing the interfaces and designs for the sorts of open implementations designed in [14].
The next question to ask is,
Some interfaces require little or no language support above and beyond that provided by the target language. Below are some systems that fall into this category.
In the case of CLOS, the user's code and meta-code is executed as the same time, at run-time. These is not the case with all MOP's, as we will see in Section 8.
Another approarch to implementing open implementations is by using techniques that fall under the umbrella of ``generic programming''. Language constructs for generic programming are found in many languages For example, ``templates'' in C++ are such a construct.
Template constructs (C++ templates in particular) require some additional syntax to the core language and often require relatively sophisticated compiler optimization to obtain good performance. However, these optimizations are generally specific to the language constructs and not to the particular problems in which they are used.
Good introductions to generic programming and templates can be found in any good C++ book. This section discusses approaches above and beyond their usual use.
([34]) suggests that there are situations in which stand-alone mixin classes are not enough: coupled mixin classes are required. In order to maintain the consistency between these classes, and in order to simplify the instantiation of these classes, the authors propose the use of meta-mixin classes, or mixin layers.
Here is how it might be done in C++: Suppose that we have several container classes, of which BINTREE is one example,
template<class Entry> class BINTREE {
class Node { ... }
class Container { ... insert and delete methods ...}
}
Here is a mixin layer for adding time-stamping to one of these container classes:
template<class Super> class TIMESTAMP : public Super {
class Node : public Super::Node { ... }
class Container : public Super::Container {
... override insert and delete methods ... }
}
These classes can be instantiated as,
x = new TIMESTAMP< BINTREE< int > >
In a generic algorithm, there are two types: the abstract type, which is used within the generic algorithm, and the application type, which is used outside of the generic algorithm. This paper addresses the problem of mapping between the two.
Conceptually, this can be done by thinking of the abstract type as a record with a set of basis variables. These variables form a basis, in the sense that, a change to one do not effect any of the others; the variables are ortogonal. Associated with each basis variable are accessor and mutator methods. The mapping problem can be restated as, how can such a record be constructed that maps a particular application type onto a given abstract type.
If one were to use this approach in an object oriented language, the application and abstract types would be implemented using distinct classes, which mapping between the two would be implemented as a "wrapper" or "ambassador" class that was a subclass of the abstract class. The programmer would have to write this class themselves, and there would be some amount of overhead associated with the translation at runtime.
Novak proposes two things ([23]):
Clusters ([24]) are to views what mixin layers ([34]) are to mixins.
In the Template Numerical Toolkit (TNT) ([31] [32]), dense and sparse vectors and arrays are built on top of the STL. Several canonical representations are provided for each type. For instance, various implementations of sparse vectors are built on top of the STL's list<>, map<>, and vector<> templates.
The usual operators are defined. Algorithms for direct methods and iterative methods are provided.
It is suggested that parallelism be handled in one of the following manners,
The BLITZ++ numerical library ([7]) uses very sophisticated C++ template code in order to obtain high-performance implemenations. These codes do not require additions to ANSI C++, but they do require sophisticated template optimizations in the base C++ compiler.
In [40], the author builds upon the material in [39] and [38] and shows various examples of how templates and inlining in C++ can be used to write programs that are succint and yet are optimized to the point that they competitive with hand-optimized F77 and F90 codes.
[41] introduces the Array templates of Blitz++. Expression templates are used to build efficient loops from high-level array notation (e.g., a = b + c). Many kinds of array and vector notations are provided. Loop transformations are done, but it is not shown how they are done.
Some interfaces require extensions to the base language or special purpose optimizations be performed by the base language compiler. Traditionally, a library writer in this situation had only two options: abandon the effort or design an implement a new language system (i.e., compiler, optimizations, debugger, etc.). Neither choice is very attractive.
Recently a third alternative has been proposed: extend the existing base-language compiler. In order to assist the library writer in implementing this third choice, two bodies of research have been pursued. The first is a vocabulary and methodology for incorporating language and compiler extensions into interface designs; the second is a body of work on compiler archicture for the open compiler implementer to draw upon. We will address the former in this section and the later in the subsequent sections.
Kiczales's group at PARC has developed the idea of Aspect-Oriented Programming (AOP) to discuss the sorts of language and compiler extensions that are sometimes required. The Aspect-Oriented Programming home page at Xerox PARC is at [2].
Traditionally, a programmer first decomposes an application into loosely coupled components (e.g., modules, objects). The more loosely couple the components, the better design. The application, then, consists of, ([15]),
It has be observed, however, that a better design does not necessarily lend itself to an efficient implementation. A good example of this is sparse matrix computations. An interface for a generic sparse matrix is fairly simple to design and implement, but will likely result in a lousy implementation. On the one hand, the library writer needs to implement a storage format, but, on the other hand, the properties that determine which format is appropriate are not available to the library writer. In the AOP vocabulary, the decision of how to store a sparse matrix cross-cuts the interface.
The key idea behind AOP is that solutions to these cross-cutting concerns can often be abstracted from the specific problem in much the same way that the components are. In the AOP vocabularly, these cross-cutting solutions are called aspects. An application, in this framework, might consist of,
Compiler optimizations that we know and love, like loop transformations, message aggregation, storage layout optimization, are all aspects, albeit, very general and sophisticated ones. What the AOP people are suggesting is that we consider extensions and optimizations that may not be general purpose at all. That is, the programmer may be able to identify problem- or domain-specific extensions or optimizations that can be packaged as aspects.
An introduction to AOP concepts can be found in [15]. AOP ideas applied to sparse matrix computations are discussed in [16], [30], [29].
Here are several questions that come to mind about designing an AOP system,
Some instances of AOP systems are systems that provide language constructs that allow the programmer to write modules in a manner that separate the use of data structures from their implementations.
These systems provide open implementations of data structures, but they themselves are not open systems. That is, these systems do not allow the user to provide additional language or compiler extensions.
Yes, the Bernoulli Sparse Compiler is an AOP system, and we didn't even realize it. The component language is BMF, the aspect exposed to the user is sparse matrix storage format implementation (i.e., black-boxes), and the aspect language is O'Caml.
The DiSTiL ([33]) system provides two sets of extensions to C:
One of the key ideas of adaptive programming is to design ``structure-shy'' programs.
For instance, suppose that design a class heirarchy for the AST's to be used by a compiler. Traditionally, if the compiler writer wants to compute ``the set of expressions in the program that reference A'', then they need to write code that will first access the program object of the class Program, and then access objects of the Procedure class, then access objects of the Statement class, and then access objects of the Expression class. While each of these classes may be relatively self-contained, the code which uses them is not: it hard-codes the entire class hierarchy whenever the AST is travered!
An alterative is to add a traverse construct to the component language that allows the programmer to more or less directly say
traverse from Program p to Expression e do
if e.accesses("A") then
result.add(e);
end if
end traverse
and allow the compiler to figure out how the class hierarchy needs to be
traversed in order to implement this. The advantage of using the
traverse construct is that the class heirarchy can be changed
(e.g., Procedure becomes Method) without having to change
this code fragment at all.
A CACM article on adapative programming can be found at [20], and the home page for the Demeter research project can be found at [19].
[9] shows how the ``traversal'' construct from adaptive programming can be implemented in an open compiler using these two mechanisms,
If taken to its logical conclusion, it seems that an AOP system should allow the user to specify their own aspects. This requires an open compiler implementation that accepts user language and compiler extensions. In this section we discuss compiler systems that provide a transformational framework and provide a mechanism for user-provided program transformations.
Intentional Programming ([1]) is basically a program transformation system with the following additions,
The idea is that the user adds their own domain specific intentions to the intentions already in the system, and then turns the transformation crank to get the final code.
A different approach to designing an open compiler is to expose the compiler's data structures to the user. These data structures are often implemented in an object oriented manner, and the user changes the compiler's default behaviour by creating new classes, specializing methods, etc. This approach can be characterized as a compile-time metaobject protocol (MOP).
The compile-time MOP's discussed in the literature seem to built upon either the program's parse tree, or the class graph infered from the program.
The author ([10]) takes lcc as a base implementation. He layered a slightly cleaned up IR on top of lcc's IR, and layered other high-level interfaces on top of this. A user can then implement compiler transformations and optimizations that use these informations. He then set up lcc so that the user can specify modules on the command line that will be dynamically linked and invoked by the compiler.
The author give numerous applications of this really simple hack:
The author claims that this took less than a man-month's worth of work.
Strictly speaking, this is not a ``MOP'' design, but it has a similar flavor to many of the other compile-time MOP systems, and it demonstrates the simpilicity and flexibility of this approach.
A compile-time MOP for C++ ([35], [27]).
The system is implemented as a preprocessor that reads Open C++ and writes C++. The meta-classes are the classes of the AST's used by the preprocessor. The user's meta-code is linked into the preprocessor prior to running. The preprocessor simply invokes ``Compiler'' methods on each of the meta-objects (i.e., AST objects) until the code stabilizes.
The paper describes how lexical extensions can implemented for C++.
The examples given of use of this system are,
Set("size<=1000;sorted")).
Sequential: [18]. Parallel: [21]
Strongly-typed intermediate form ([36]).
The FLINT system has multiple front-ends, a single monolithic middle-end, and multiple back-ends. The middle-end performs the usual optimizations. Adding a new language front-end might (probably will) require augmenting the FLINT IR with new types and operators and updating the middle-end optimizations for the new types and operators. The system is designed to be expressive, but not extensible.
This system ([43]) takes an abstract description of an AST type and produces code that in some language (e.g, C++, Java, ML) implements,
It's powerful enough to handle the AST types in a real system (eg, SUIF).
JTS ([8]) provides two basic tools -
Jak: Language extensions to Java that provide (a) quasiquote/unquote capabilities for generating AST's of Java programs, and (b) hygenic renaming of temporary variables in the generated code.
Bali: Essentially a parser generator. Takes as input a grammer with an associated class hierarchy for the AST, and generates a preprocessor for that grammer. Language extension can be done by composing Bali grammers.
([11])
AST's in SUIF 2 ([37]) are constructed by declaring subclasses of abstract AST classes. The hope is that analysis and optimization routines can be written to use only the methods of the abstract classes. That way, someone using SUIF 2 can add new programming constructs to the AST without having to change the analysis and optimization routines.
Abstract: Intentional programming is a new paradigm in software engineering that allows programming languages to be implemented in a highly extensible manner. In particular, the programmer can specify new abstractions that are specific to his problem domain, while simultaneously recording any domain specific optimizations that may apply to such new abstractions. This paper describes a system that implements intentional programming, focusing on the facilities for program transformation. The key difference with other approaches lies in the way the order of transformation is controlled: great emphasis is placed on specifying that order in a compositional fashion, so that transformations are easily re-used.
Keyword: program transformation, domain-specific languages, optimization, design composition, extensible programming languages
Abstract: This paper describes how the cmcc compiler reuses code -- both internally (reuse between different modules) and externally (reuse between versions for different target machines). The key to reuse are the application frameworks developed for global data-flow analysis, code generation, instruction scheduling, and register allocation. The code produced by cmcc is as good as the code produced by the native compilers for the MIPS and SPARC, although significantly less resources have been spent on cmcc (overall, about 6 man years by 2.5 persons). cmcc is implemented in C++, which allows for a compact expression of the frameworks as class hierarchies. The results support the claim that suitable frameworks facilitate reuse and thereby significantly improve developer effectiveness.
Keyword: CLOS, metaobject protocol, Lisp
Abstract: Parallel numerical software based on the message-passing model is enormously complicated. This paper introduces a set of techniques to manage the complexity, while maintaining high efficiency and ease of use. The PETSc 2.0 package uses object-oriented programming to conceal the details of the message passing, without concealing the paralleism, a a high-quality set of numerical software libraries. In fact, the programming model used by PETSc is also the most appropriate for NUMA shared-memory machines, since they require the same careful attention to memory hierarchies as do distributed-memory machines. Thus, the concepts discussed are appropriate for all scalable computing systems. The PETSc libraries provide many of the data structures and numerical kernels required for the scalable solution of PDEs, offering performance portability
Keyword: PETSc, numerical libraries, parallel libraries, sparse computations
Abstract: The Jakarta Tool Suite (JTS) aims to reduce substantially the cost of generator development by providing domain independent tools for creating domain-specific languages and component-based generators called GenVoca generators. JTS is a set of precompiler-compiler tools for extending industrial programming languages (e.g., Java) with domain-specific constructs. JTS is itself a GenVoca generator, where precompilers for JTS-extended languages are constructed from components.
Keyword: Java, extensible compilers, domain-specific languages, macros
Abstract: We study a recent programming paradigm known as Adaptive Programming (AP) as an ideal candidate for a metaobject protocal (MOP) for object-oriented programming languages; we call it the APMOP. The major benefit of the APMOP is to provide a mechanism for writing base-level programs in a structure-shy manner. Doing so, the prograams are more robust to changes in the structural aspects of the applications. We describe AP/S++, an implementation of the APMOP using the Scheme-based, object-oriented language S++. AP/S++ is a compile-time MOP and has no negative effects on the run-time performance of programs. The constributions of this paper are: (i) to show a new application for reflection; (ii) to clearly identify the abstraction boundaries of AP; and (iii) to propose an implementation of the APMOP that can easily be reproduced in many object-oriented programming languages.
Keyword: adaptive programming, metaobject protocals
Abstract: Programmers have traditionally been passive users of compilers, rather than active exploiters of their transformational abilities. This paper presents MAGIK, a system that allows programmers to easily and modularly incorporate application-specific extensions into the compilation process. The MAGIK system gives programmers two significant capabilities. First, it provides mechanisms that implementors can use to incorporate application semantics into compilation, thereby enabling both optimizations and semantic checking impossible by other means. Second, since extensions are invoked during the translation from source to machine code, code transformations (such as software fault isolation [14]) can be performed with full access to the symbol and data flow information available to the compiler proper, allowing them both to exploit source semantics and to have their transformations (automatically) optimized as any other code.
Keyword: Magik, compiler intrastructure, open compilers, lcc
Abstract: Previously, techniques such as class hierarchy analysis and profile-guided receiver class prediction have been demonstrated to greatly improve the performance of applications written in pure object-oriented languages, but the degree to which these results are transferable to applications written in hybrid languages has been unclear. In part to answer this question, we have developed the Vortex compiler infrastructure, a language-independent optimizing compiler for object-oriented languages, with front-ends for Cecil, C++, Java, and Modula-3. In this paper, we describe the Vortex compiler's intermediate language, internal structure, and optimization suite, and then we report the results of experiments assessing the effectiveness of different combinations of optimizations on sizable applications across these four languages. We characterize the benchmark programs in terms of a collection of static and dynamic metrics, intended to quantify aspects of the "object-oriented- ness" of a program.
Keyword: vortex, compiler infrastructure, compiling object-oriented languages
Keyword: sparse blas
Keyword: metaobject protocol, CLOS, Lisp, object-oriented languages
Abstract: Designing reusable software modules can be extremely difficult. The design must be balanced between being general enough to address the needs of a wide range of clients and being focused enough to truly satisfy the requirements of each specific client. One area where it can be particularly difficult to strike this balance is in the implementation strategies, tuned for a wide range of clients, aren't necessily optimal for each specific client -- this is especially an issue for modules that are intended to be reusable and yet provide high-performance. An examination of existing software systems shows that an increasingly important technique for handling this problem is to design the module's interface in such a way that the client can assist of participate in the selection of the module's implementation strategy. We call this approach open implemention. When designing the interface to a module that allows its clients some control over its implementation strategy, it is important to retain, as much as possible, the advantages of traditional closed implementation modules. This paper explores issues in the design of interfaces to open implementation modules. We identify key design choices, and present guidelines for deciding which choices are likely to work best in particular situations.
Keyword: open implementations, software design, software reuse
Abstract: We have found many programming problems for which neither procedural nor object-oriented programming techniques are sufficient to clearly capture some of the important design decisions the program must implement. This causes the implementation of those design decisions to be scattered throughout the code, resulting in "tangled" code that is excessively difficult to develop and maintain. We present an analysis of why it is that such design decisions have been so difficult to clearly capture in actual code. We call the issues these decisions address ASPECTS, and say that the reason they have been hard to capture is that they CROSS-CUT the system's basic functionality. We present the basis for a new programming technique, called aspect-oriented programming, that makes it possible to clearly express programs involving such aspects, including appropriate isolation, composition and reuse of the aspect code. The discussion is rooted in systems we have built using aspect-oriented programming. Object-oriented programming has been presented as a technology that can fundamentally aid software engineering, because the underlying object model provides a better fit with real domain problems. But we have found many programming problems where OOP techniques are not sufficient to clearly capture all the important design decisions the program must implement. Instead, it seems that there are some programming problems that fit neither the OOP approach nor the procedural approach it replaces.
Keyword: aspect-oriented programming, open compilers
Abstract: The expressiveness conferred by high-level and object-oriented languages is often impaired by concerns that cross-cut the basic functionality. Execution time, data representation, and numerical stability are three such concerns that are of great interest to numerical analysts. Using aspect-oriented programming we have created AML, a system for sparse matrix computation that deals with these concerns separately and explicitly while preserving the expressiveness of the original functional language. The resulting code maintains the efficiency of highly tuned low-level code, yet is ten times shorter.
Keyword: sparse compiling, aspect-oriented programming, open compiling
Abstract: This is a progress report on an experiment to build a compile-time metaobject protocol for Scheme. The compilation setting raises issues not present in runtime oriented MOP's, due to the complexity of the domain and the coupling between different parts. To address the complexity of the domain, we have developed a structure that decomposes the description of an implementation into a combination of many small, partially interacting choices. To address the coupling, we have developed a decision making process that allows implementation choices to be made by a collaboration between user interventions and default decision making
Keyword: Scheme, open implementation
Keyword: adaptive programming
Keyword: adapative programming, Demeter
Abstract: A compiler that automatically chooses a program's parallelization if often unable to choose either the best one or the particular one that a programmer has in mind. This has led to systems that provide the programmer with explicit control over a program's parallelization, for example, via compiler pragmas. The pragma approach is like the metaobject protocol (MOP) approach in that pragmas provide control over what would otherwise be hidden aspects of an implementation. However, it differs because the set of pragmas is fixed, thereby limiting the amount of control provided. We investigated whether it was possible to increase the amount of control using the full MOP approach. We were in fact successful, but the resulting MOP differs from previous ones in that it is present at compile-time rather than at run-time. In this paper, we compare the MOP approach with other approaches, and discuss what is needed in order to produce a production-quality MOP-based statically parallelizing compiler.
Keyword: metaobject protocol, open implementation, parallelizing compiler
Abstract: This paper describes a methodology for designing Open Implementations - software modules that can adapt or change their internals to accommodate the needs of different clients. Analysis techniques are used for capturing domain knowledge, user requirements, and domain properties that influence the module's eventual implementation. Design techniques are used for determining and refining the interfaces by which clients control the modules implementation strategies. The methodology has evolved over the past two uears in several pilot projects.
Keyword: software design methodology, software reuse, open implementation, framework, metaobject protocal
Abstract: Software reuse is inhibited by the many different ways in which equivalent data can be represented. We describe methods by which views can be constructed semi-automatically to describe how application data types correspond to the abstract types that are used in numerical generic algorithms. Given such views, specialized versions of generic algorithms that operate directly on the application data can be produced by compilation. This enables reuse of the generic algoriths for an application with minimal effort. Graphical user interfaces allow views to be specified easily and rapidly. Algorithms are presented for deriving, by symbolic algebra, equations that related the variables used in the application data to the variables needed for the generic algorithms. Arbitrary application data structures are allowed. Units of measurement are converted as needed. These techniques allow reuse of a single version of a generic algorithm for a variety of possible data representations and programming languages. These techniques can also be applied in data conversion and in object-oriented, functional, and transformational programming.
Keyword: view, program transformation, generic algorithm, software reuse, data conversion, visual programming, symbolic algebra, abstract data type
Abstract: A generic procedure can be specialized, by compilation through views, to operate directly on concrete data. A view is a computational mapping that describes how a concrete type implements an abstract type. Clusters of related views are needed for specialization of generic procedures that involve several types or several views of a single type. A user interface that reasons about relationshipts between concrete types and abstract types allows view clusters to be created easily. These techniques allow rapid specialization of generic procedures for applications.
Keyword: software reuse, view, generic algorithm, generic procedure, algorithm specialization, partial evaluation, direction-manipulation editor, abstract data type
Abstract: Developing computational codes that compute efficiently with sparse matrices is a difficult and error-prone process that requires a lot of specialized knowledge from the programmer. The resulting codes are very complicated due to the specialized data structures used to store nonzero elements of the matrices. Automatic generation of sparse code from the corresponding dense version would simplify the programmer's task, provided that a compiler-generated code is fast enough to be used instead of a hand-written code. Generating efficient sparse matrix code is complicated, as the performance depends on many factors. We propose a new Sparse Intermediate Program Representation (SIPR) that spearates the issue of maintaining complicated data structures from the actual matrix computations to be performed. Cost analysis of SIPR allows for the prediction of the program efficiency, and provides a solid basis for choosing between many possible sparse implementations. The SIPR framework allows the use of techniques that are frequently used in the hand-written code but previously were not considered for compiler-generated codes due to their complexity.
Keyword: spare compilation
Abstract: We present a new C++ library design for linear algebra computations on high performance architectures. The Template Numerical Toolkit (TNT) for Linear Algebra is a successor to the Lapack++, Sparselib++, and IML++ packages, providing support for direct and iterative solvers. Its goal is to formally integrate these ideas into a generic algorithm library supporting user-defined data types and data neutrality. The design of the core library utilizes components from the C++ Standard Template Library (STL) and the basic parallel extensions defined in HPC++.
Keyword: TNT, sparse libraries
Abstract: DiSTiL is a software generator that implements a declarative domain-specific language (DSL) for container data structures. DiSTiL is a represenative of a new approach to domain-specific language implementation. Instead of being the usual one-of-akind stand-alone compiler, DiSTiL is an extenion library for the Intentional Programming (IP) ttransformation system (currently under development by Microsoft Research). DiSTiL relies on several reusable, general-purpose infrastructure tools offered by IP that substantially simplify DSL implementation.
Keyword: domain-specific language, intentional programming, container classes, automatically generated data structures
Abstract: Mixin layers are a technique for implementing layered object-oriented designs (e.g. collaboration-based designs). Mixin layers are similar to abstract subclasses (mixin classes) but scaled to a multiple-class granularity. We describe mixin layers from a programming language viewpoint, discuss checking the consistency of a mixin layer composition, and analyze the language support issues involved.
Keyword: mixins, object-oriented programming, C++, CLOS
Abstract: This paper presents a metaobject protocol (MOP) for C++. This MOP was designed to bring the power of meta-programming to C++ programmers. It avoids penalties on runtime performance by adopting a new meta-architecture in which the metaobjects control the compilation of programs instead of being active during program execution. This allows the MOP to be used to implement libraries of efficient, transparent language extensions.
Keyword: metaobject protocol, C++, open implementation
Abstract: Application languages are very effective in solving specific software problems. Unfortunately, they pose great challenges to reliable and efficient implementations. In fact, most existing application languages are slow, interpreted, and have poor interoperability with general-purpose languages. This paper presents a framework for building a high quality systems environment for multiple advanced languages. Our key innovation is the use of a common typed intermediate language, named FLINT, to model the semantics and interactions of various language-specific features. FLINT is based on a predicative variant of the Girard-Reynolds polymorphic calculus F-omega, extended with a very rich set of primitive types and functions. FLINT provides a common compiler infrastructure that can be quickly adapted to generate compilers for new general-purpose and domain-specific languages. With its single unified type system, FLINT serves as a great platform for reasoning about cross-language inter-operations. FLINT types act as a glue to connect language features that complicate interoperability, such as mixed data representations, multiple function calling conventions, and different memory management protocols. In addition, because all runtime representations are determined by FLINT types, languages compiled under FLINT can share the same system-wide garbage collector and foreign function call interface.
Keyword: flint, intermediate forms, compiler infrastructure
Abstract: Expression Templates is a new C++ technique for passing expressions as function arguments. The expression can be inlined into the function body, which results in faster and more convenient code thatn C-style callback functions. This technique can be used to evaluate vector and matrix expressions in a single pass without temporaries. In preliminary benchmark results, one compiler evaluates vector expressions at 95-99.5% efficieny of hand-coded C using this technique (for long vectors). The speed is 2-15 times that of a conventional C++ vector class.
Keyword: C++, templates, metaprogramming
Abstract: No abstract.
Keyword: C++, templates, metaprogramming
Abstract: After years of being dismissed as too slow for scientific computing, C++ has caught up with Fortran and appears ready to give it stuff competition. We survey the reasons for the historically poor performance of C++ (pairwise expression evaluation, the abstraction penalty, aliasing ambiguities) and explain how these problems have been resolved. C++ can be faster than Fortran for some applications, due to template techniques (such as expression templates and template metaprograms) which permit optimizations beyond the ability of current Fortran compilers.
Keyword: Blitz++, C++, templates, metaprogramming
Abstract: This paper describes Blitz++ arrays, which offer functionality and effciency competitive with Fortran 90, but without any language extensions. One of the key ideas behind Blitz++ is moving features out of compilers and into libraries. Blitz++ handles parsing and analysis of array expressions on its own, and performs optimizations (particularly loop transformations) which have until now been the responsibility of compilers. This is done using the expression template technique. Blitz++ provides many features unavailable in Fortran 90, such as arbitrary transpose operations, array renaming, tensor notation, scans, partial and block reductions. Blitz++ arrays achieve a median performance of 95-98% that of Fortran over 23 loop kernels on the Cray T3E.
Keyword: Blitz++, C++, templates, metaprogramming
Abstract: The Zephyr Abstract Syntax Description Language (ASDL) describes the abstract syntax of compiler intermediate representations (IRs) and other tree-like data structures. Just as the lexical and syntactic structures of programming languages are describe with regular expressions and context free grammars, ASDL provides a concise notation for describing the abstract syntax of programming languages. Tools can convert ASDL descriptions into the appropriate data-structure definitions and functions to convert the data-structures to or from a standard flattened representation. This makes it easier to build compiler components that interoperate. Although ASDL lacks subtyping and inheritance, it is able is able to describe the Stanford University Intermediate Format (SUIF) compiler IR, originally implemented in C++. We have built a tool that converts ASDL info C, C++ Java, and ML data-structure definitions and conversion functions. We have also built a graphical browser-editor of ASDL data structures. ASDL shares features found in many network interface description languages (IDLs), algebraic data types, and languages such as ASN.1 and SGML. Compared to other alternatives ASDL is simple and powerful. This document describes ASDL in detail and presents an initial evaluation of ASDL.
Keyword: Zephyr, compiler infrastructure, abstract syntax trees