Programming Techniques, Tools and Languages Group

Research

Programming with C++ Concepts

The new concepts mechanism slated for inclusion in the next revision of C++, C++0x, allows the specification of "concepts", as used in the specification of the Standard Template Library, directly in code.

The concepts mechanism allows for retroactive, lightweight, low-cost, non-intrusive adaptation of types through the use of the concept_map feature; a concept_map specifies how and in what way a type satisfies the modeling relationship to a concept.

Concept-Based Optimizations

Traditional compilers typically simplify expressions via a set of built-in optimizing rules whose correctness is generally justified by certain algebraic laws. These optimizing rules, however, are hard-coded and only apply to expressions of built-in types. For example, a C++ compiler will simplify the integer addition x + 0 via the optimizing rule i + 0 -> i justified by the algebraic right identity law . The same law also holds for the user-defined string operator+(x, y) in C++, and that is, we can safely rewrite s + string() into s. The C++ compiler, however, fails to conduct this rewriting, because the compiler's optimizing rules are hard-coded with specific built-in types, neither allowing users to specify optimizing rules nor automatically proving the validation of the right identity law for string and applying this law to s + string(). Instead, to optimize s + string(), the compiler has to inline the default constructor of the string class, the string operator+(x, y), and analyze the expanded code against the built-in optimizing rules, which means significant amount of work.

A straightforward means to enable the compiler to apply the right identity law to the string operator+(x, y) is supplying the compiler with this rewrite rule s + string() -> s. Obviously, directly encoding this rule in the compiler is not the standard course of programming compilers. A pre-processor or source-to-source translator may allow users to specify rewrite rules and preprocess users' code via these customized rules. This approach's limitations consist of: 1) users need to specify different rewrite rules for different types, though all of these rewrite rules are instances of one algebraic law such as the algebraic identity law; 2) this pre-processor or source-to-source translator hardly utilizes the results of compilers' analyses and optimizations that can reveal new facts for rewriting; for example, in the sequence code string s; string t=string(); string l = s + t, accessing the code's data flow graph reveals s + t == s + string(), which in turn justifies applying the rewrite rule s + string() -> s.

A second approach is allowing users to specify generic algebraic laws, and declare the validation of applying these laws to certain expressions of specific types (both built-in and user-defined), and designating the compiler to accomplish the application. Because it is the compiler that performs the rewriting on expressions, this approach can be integrated with the compiler's analyses and optimizations.

Lambda functions for C++

This project deals with a partial implementation of the C++ standards proposal N2329: "Lambda expressions and closures for C++," by Jaakko Järvi, John Freeman, and Lawrence Crowl

Local Specialization

We describe the support of local specialization in the categorial computer algebra algebra system OpenAxiom by abstract interpretation.

In typeful programming languages, many algebraic structures in computer algebra systems can be best expressed through parametric interfaces and datatypes. The properties of such algebraic structures can depend upon aspects of the parameters. For instance, the set of integers ℤ/kℤ modulo a natural number k carries the ring structure for all values of k; however, when k is prime, ℤ/kℤ also carries the field structure. In a generic programming setting, expressing such a dependent property at a single definition point is called local specialization. Several categorial computer algebra systems support local specialization to varying degrees. We present a principled compilation strategy to support local specialization in OpenAxiom grounded by the theory of abstract interpretation.

OpenAxiom

OpenAxiom is an open source platform for symbolic, algebraic, and numerical computations. It offers an interactive environment, an expressive programming language, a compiler, a large set of mathematical libraries of interest to researchers and practitioners of computational sciences.

OpenAxiom strives to support ubiquitous, advanced, high quality open source computer algebra on major operating systems, in particular major Unix variants, GNU/Linux variants, Windows, and handheld devices. It aims at being the open source computer algebra system of choice for research, teaching, engineering, etc.

Open Multi-Methods

Multiple dispatch-the selection of a function to be invoked based on the dynamic type of two or more arguments-is a solution to several classical problems in object-oriented programming. Open multi-methods generalize multiple dispatch towards open-class extensions, which improve separation of concerns and provisions for retroactive design. We present the rationale, design, implementation, performance, programming guidelines, and experiences of working with a language feature, called open multi-methods, for C++ . Our open multi-methods support both repeated and virtual inheritance. Our call resolution rules generalize both virtual function dispatch and overload resolution semantics. After using all information from argument types, these rules can resolve further ambiguities by using covariant return types. Care was taken to integrate open multi-methods with existing C++ language features and rules. We describe a model implementation and compare its performance and space requirements to existing open multi-method extensions and work-around techniques for C++ . Compared to these techniques, our approach is simpler to use, catches more user mistakes, and resolves more ambiguities through link-time analysis, is comparable in memory usage, and runs significantly faster. In particular, the runtime cost of calling an open multi-method is constant and less than the cost of a double dispatch (two virtual function calls). Finally, we provide a sketch of a design for open multi-methods in the presence of dynamic loading and linking of libraries.

Property Models

Property Models serve as a mechanism for explicitly describing certain incidental data structures and algorithms, with particular application in the area of user interfaces. A library implementation of this idea is under development by John Freeman, Jacob Smith, Jaakko Järvi, Mat Marcus, and Sean Parent.

The Pivot

The Pivot is a framework for static analysis and transformation of C++ programs, being developed at Texas A&M University. It aims at the support for high-level parallel and distributed programming techniques. It "understands" the higher levels of C++ (e.g. templates, specializations, concepts), crucial for advanced optimizations, validation of safety, enforcement of dialects, support for staging libraries.

eXtensible Typing Library

Type systems built directly into the compiler or interpreter of a programming language cannot be easily extended to keep track of run-time invariants of new abstractions. Yet, programming with domain specific abstractions could benefit from additional static checking. This paper presents library techniques for extending the type system of C++ to support domain specific abstractions. The main contribution is a programmable ``subtype'' relation. As a demonstration of the techniques, we implement a type system for defining type qualifiers in C++ as well as type system for the XML processing language, capable of, e.g., guaranteeing that a program only produces valid XML documents according to a given XML Schema.

 


Upcoming Events




Share This Article




Headlines

About Us | Parasol Lab | Computer Science and Engineering | ©2010 Texas A&M University