> <\body> <\hide-preamble> > > <\flat-size> <\std-mmx-code> > <\flat-size> <\std-cpp-code> > \; <\doc-data| with C++>|||<\author-affiliation> Laboratoire d'Informatique UMR 7161 CNRS Campus de l'École polytechnique 91128 Palaiseau Cedex France |>>|<\doc-note> This work has been partly supported by the grant of the Région Ile-de-France. ||<\author-affiliation> Laboratoire d'Informatique UMR 7161 CNRS Campus de l'École polytechnique 91128 Palaiseau Cedex France |>>> \; ||>> <\abstract> In this paper, we give a detailed description of the interface between the language and C++. In particular, we describe the mechanism which allows us to import a C++ template library (which only permits static instantiation) as a fully generic template library. > Until the mid nineties, the development of computer algebra systems tended to exploit advances in the area of programming languages, and sometimes even influenced the design of new languages. The system was developed shortly after the introduction of . Symbolic algebra was an important branch of the artificial intelligence project at during the sixties. During a while, the system was the largest program written in , and motivated the development of better compilers. The system was at the origin of yet another interesting family of computer algebra systems, especially after the introduction of domains and categories as function values and dependent types in and II>. These developments were at the forefront of language design and type theory. later evolved into the system. In the project, later renamed into , the language and compiler were redesigned from scratch and further purified. After this initial period, computer algebra systems have been less keen on exploiting new ideas in language design. One important reason is that a good language for computer algebra is more important for developers than for end users. Indeed, typical end users tend to use computer algebra systems as enhanced pocket calculators, and rarely write programs of substantial complexity themselves. Another reason is specific to the family of systems that grew out of : after IBM's decision to no longer support the development, there has been a long period of uncertainty for developers and users on how the system would evolve. This has discouraged many of the programmers who did care about the novel programming language concepts in these systems. In our opinion, this has led to an unpleasant current situation in computer algebra: there is a dramatic lack of a modern, sound and fast general purpose programming language. The major systems > and > are both interpreted, weakly typed, besides being proprietary and expensive. The system relies on and merely contents itself to glue together various existing libraries and other software components. The absence of modern languages for computer algebra is even more critical whenever performance is required. Nowadays, many important computer algebra libraries (such as , , , , etc.) are directly written in C or C++. Performance issues are also important whenever computer algebra is used in combination with numerical algorithms. We would like to emphasize that high level ideas can be important even for traditionally low level applications. For instance, in a suitable high level language it should be easy to operate on vectors of, say, bit floating point numbers. Unfortunately, would have to be completely redesigned in order to make such a thing possible. For these reasons, we have started the design of a new software, , based on acompiled and strongly typed language, featuring signatures, dependent types, and overloading. is intended as a general purpose language, which supports both functional and imperative programming styles. Although the design has greatly been influenced by II> and its successors and , the type system of contains several novel aspects, as described in. is also a free software, which can be downloaded from |http://www.mathemagix.org>. with C++> One major design goal of the compiler is to admit a good compatibility with existing programming languages. For the moment, we have focussed onC andC++. Indeed, on the one hand, in parallel with the development of the compiler, we have written several high performance C++ template libraries for various basic mathematical structures (polynomials, matrices, series, etc.). On the other hand, the compiler currently generates C++ code. We already stated that was inspired by and in many respects. Some early work on interfacing with C++ was done in the context of . There are two major differences between C++ and which are important in this context. On the one hand, provides support for genuine generic functional programming: not only functions, but also data types can be passed as function arguments. For instance, one may write a routine which takes a ring and an integer on input and which returns the ring |]> \ |]>>. The language also provides support for dependent types: a function may very well take a ring together with an instance of as its arguments or return value. On the other hand, provides support for templates. We may write a routine which takes an instance of an arbitrary type on input and returns . However, and even though there is some work in this direction, it is currently not possible to add the requirement that must be a ring when declaring the template . Hence, the correctness of the template body can only be checked at the moment when the template is instantiated for a particular type . Furthermore, only a finite number of these instantiations can occur in a program or library, and template parameters cannot be passed to functions as objects. In , there is no direct equivalent of templates. Nevertheless, it is possible to implement a function which takes a ring and an instance of on input, and which returns . It thus makes sense to consider the importation of C++ template libraries into . Although contain a precise strategy for realizing such interfacing, part of the interface still had to be written by hand. features two main novelties with respect to the previous work which was done in the context of and . First of all, the language itself admits full support for templates with typed parameters; see our paper on the type system for more details. Secondly, C++ template libraries can be imported into in a straightforward way, without the need to write any non trivial parts of the interface by hand. The ability to transform a C++ template library which only permits static instantiation into a fully generic template library is somewhat surprising. Part of the magic occurs in the specification of the interface itself. Indeed, the interface should in particular provide the missing type information about the parameters of the C++ templates. In this paper, we will describe in more details how this mechanism works. We think that similar techniques can be applied for the generic importation of C++ templates into other languages such as or . It might also be useful for future extensions of C++ itself. The paper is organized as follows. In Section

, we describe how to import and export non templated classes and functions from and to . In Section

, we briefly recall how genericity works in , and we describe what kind of C++ code is generated by the compiler for generic classes and functions. The core of the paper is Section

, where we explain how C++ templates are imported into . In Section

we summarize the main C++ libraries that have been interfaced to , and Section

contains a conclusion and several ideas for future extensions.

Different programming languages have different conventions for compiling programs, organizing projects into libraries, and mechanisms for separate compilation. C++ is particularly complex, since the language does not provide any direct support for the management of big projects. Instead, this task is delegated to separate configuration and Makefile systems, which are responsible for the detection and specification of external and internal dependencies, and the determination of the correct compilation flags. Although these tasks may be facilitated up to a certain extent when using integrated development environments such as > (trademark of Foundation, Inc.), > (trademark of Inc.), or Builder> (trademark of Embarcadero Technologies, Inc.), they usually remain non trivial for projects of a certain size. uses a different philosophy for managing big projects. Roughly speaking, any source file contains all information which is necessary for building the corresponding binary. Consequently, there is no need for external configuration or Makefile systems. Whenever we import functionality from C++ into , our design philosophy implies that we have to specify the necessary instructions for compiling and/or linking the imported code. To this effect, provides special primitives , and for specifying the compilation and linking flags, and C++ header files to be included. For instance, the library of contains implementation for various numerical types. In particular, it contains wrappers for the and libraries with implementations of arbitrary precision integers, rational numbers and floating point numbers. The interface for importing the wrapper for arbitrary precision integers starts as follows: <\mmx-code> foreign cpp import { \ \ cpp_flags \ \ "\0numerix-config --cppflags\0"; \ \ cpp_libs \ \ \ "\0numerix-config --libs\0"; \ \ cpp_include "numerix/integer.hpp"; \ \ ... } On installation of the library, a special script is installed in the user's path. In the above example, we use this script in order to retrieve the compilation and linking flags. Notice also that is the C++ header file for basic arbitrary precision integer arithmetic.

Ideally speaking, the bulk of an interface between and a foreign language is simply a dictionary which specifies how concepts in one system should be mapped into the other one. For ordinary classes, functions and constants, there is a direct correspondence between and C++, so the interface is very simple in this case. Assume for instance that we want to map the C++ class from into the class , and import the basic constructors and arithmetic operations on integers. This is done by completing the previous example into: <\mmx-code> foreign cpp import { \ \ cpp_flags \ \ "\0numerix-config --cppflags\0"; \ \ cpp_libs \ \ \ "\0numerix-config --libs\0"; \ \ cpp_include "numerix/integer.hpp"; \; \ \ class Integer == integer; \ \ literal_integer: Literal -\ Integer == \ \ \ \ make_literal_integer; \; \ \ prefix -: Integer -\ Integer == prefix -; \ \ infix +: (Integer, Integer) -\ Integer == infix +; \ \ infix -: (Integer, Integer) -\ Integer == infix -; \ \ infix *: (Integer, Integer) -\ Integer == infix *; \; \ \ ... } The special constructor allows us to write literal integer constants such as using the traditional notation. This literal constructor corresponds to the C++ routine <\cpp-code> integer make_literal_integer (const literal&); where is a special C++ class for string symbols. The syntax of C++ is quite rigid and often directly related to implementation details. For instance, in C++ the notation necessarily presupposes the definition of a class or structure with a field . In , the operator .x> can be defined anywhere. More generally, the language provides a lot of syntactic sugar which allows for a flexible mapping of C++ functionality to .\ Another example is type inheritance. In C++, type inheritance can only be done at the level of class definitions. Furthermore, type inheritance induces a specific low level representation in memory for the corresponding class instances. In , we may declare any type to inherit from a type by defining an operator U>. This operator really acts as a converter with the special property that for any second converter T>, automatically generates the converter U>. This allows for a more high level view of type inheritance. also provides a few built-in type constructors: T> provides adirect equivalent for the C++ reference types, the type T> can be used for writing functions with an arbitrary number of arguments of the same type , and T> corresponds to a stream of coefficients of type . The built-in types T>, T> and T> are automatically mapped to the C++ types, T\> and T\> in definitions of foreign interfaces. The containers T\> and T\> are defined in the C++ support library for , where represents the namespace.

When importing a C++ class into , we finally notice that the user should implement a few compulsory operators on . These operators have fixed named in C++ and in , so it is not necessary to explicitly specify them in foreign interfaces. The first compulsory operator is Syntactic>, which converts instances of type into syntactic expression trees which can then be printed in several formats (ASCII, , , etc.). The other compulsory operators are three types of equality (and inequality) tests and the corresponding hash functions. Indeed, distinguishes between ``semantic'' equality, exact ``syntactic'' equality and ``hard'' pointer equality. Finally, any C++ type should provide a default constructor with no arguments. Simple classes and functions can be exported to C++ in a similar way as C++ classes and functions are imported. Assume for instance that we wrote a class with a constructor, accessors, and a few operations on points. Then we may export this functionality to as follows: <\mmx-code> foreign cpp export { \ \ class Point == point; \ \ point: (Double, Double) -\ Point == \ \ \ \ keyword constructor; \ \ postfix .x: Point -\ Double == get_x; \ \ postfix .y: Point -\ Double == get_y; \ \ middle: (Point, Point) -\ Point == middle; } > Before we discuss the importation of C++ template libraries into , let us first describe how to define generic classes and functions in , and how such generic declarations are reflected on the C++ side. provides the construct for the declaration of generic functions. For instance, a simple generic function for the computation of a cube is the following: <\mmx-code> forall (M: Monoid) cube (x: M): M == x*x*x; This function can be applied to any element whose type is a monoid. For instance, we may write <\mmx-code> c: Int == cube 3; The parameters of generic functions are necessarily typed. In our example, the parameter is a type itself and the type of a . The category specifies the requirements which are made upon the type , and a typical declaration would be the following: <\mmx-code> category Monoid == { \ \ infix *: (This, This) -\ This; } Hence, a type is considered to have the structure of a in a given context, as soon as the function M> is defined in this context. Notice that the compiler does not provide any means for checking mathematical axioms that are usually satisfied, such as associativity. Already on this simple example, we notice several important differences with the C++ ``counterpart'' of the declaration of : <\cpp-code> template\typename M\ M cube (const M& x) { return x*x*x; } First of all, C++ does not provide a means for checking that admits the structure of a monoid. Consequently, the correctness of the body can only be checked for actual instantiations of the template. In particular, it is not possible to compile a truly generic version of . By default, always compiles functions such as in a generic way. Let us briefly describe how this is implemented. First of all (and similarly to), the definition of the category gives rise to acorresponding abstract base class on the C++ side: <\cpp-code> class Monoid_rep: public rep_struct { \ \ inline Monoid_rep (); \ \ virtual inline ~Monoid_rep (); \ \ virtual generic mul (const generic&, \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ const generic&) const = 0; \ \ ... \ }; A concrete monoid is a ``managed pointer'' ( the objects to which they point are reference counted) to a derived class of with an actual implementation of the multiplication . Instances of the type correspond to managed pointers to objects of arbitrary types. The declaration of gives rise to the following code on the C++ side: <\cpp-code> generic cube (const Monoid& M, const generic& x) { \ \ // x is assumed to contain an object "of type M" \ \ return M-\mul (x, M-\mul (x, x)); } The declaration gives rise to the automatic generation of a class which corresponds to the class with the structure of a: <\mmx-code> struct Int_Ring_rep: public Ring_rep { \ \ ... \ \ generic \ \ mul (const generic& x, const generic& y) const { \ \ \ \ return as_generic\int\ (from_generic\int\ (x) * \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ from_generic\int\ (y)); \ \ } \ \ ... }; The declaration itself corresponds to the following C++ code: <\cpp-code> Monoid Int_Ring= new Int_Ring_rep (); int c= from_generic\int\ \ \ \ \ \ \ \ \ \ (cube (Int_Ring, as_generic\int\ (3))); Notice that we did not generate any specific instantiation of for the type. This may lead to significantly smaller executables with respect to C++ when the function is applied to objects of many different types. Indeed, in the case of C++, a separate instantiation of the function needs to be generated for each of these types. In particular, the function can only be applied to a finite number of types in the course of a program. <\remark> Of course, for very low level types such as , the use of generic functions does imply a non trivial overhead. Nevertheless, since the type is essentially a , the overhead is kept as small as possible. In particular, the overhead is guaranteed to be bounded by a fixed constant. We also notice that provides an experimental keyword which allows for the explicit instantiation of a generic function. <\remark> Although generic functions such as are not instantiated by default, our example shows that we do have to generate special code for converting the type parameter to a . Although this code is essentially trivial, it may become quite voluminous when there are many different types and categories. We are still investigating how to reduce this size as much as possible while keeping the performance overhead small. also allows for the declaration of generic container classes; the user simply has to specify the typed parameters when declaring the class: <\mmx-code> class Complex (R: Ring) == { \ \ re: R; \ \ im: R; \ \ constructor complex (r: R, i: R) == { \ \ \ \ re == r; \ \ \ \ im == i; \ \ } } Again, only the generic version of this class is compiled by default. In particular, the internal representation of the corresponding C++ class is simply a class with two fields and of type . Regarding functions and templates, there are a few other important differences between C++ and : <\enumerate> Dependencies are allowed between function and template parameters and return values, as in the following example: <\mmx-code> forall (R: Ring, M: Module R) infix * (c: R, v: Vector M): Vector M == \ \ [ c * x \| x: M in v ]; Template parameters can be arbitrary types or (not necessarily constant) instances. For instance, one may define a container for vectors with a fixed size. Functions can be used as arguments and as values: <\mmx-code> compose (f: Int -\ Int, g: Int -\ Int) \ \ \ \ \ \ \ \ (x: Int): Int == \ \ f g x; Notice that and admit the same advantages with respect to C++.

One of the most interesting aspects of our interface between and C++ is its ability to import C++ template classes and functions. This makes it possible to provide a fully generic interface on top of an existing C++ template library. We notice that the interface between and C++ also provided a strategy for the importation of templates. However, the bulk of the actual work still had to be done by hand. Before coming to the technical details, let us first give a small example of how to import part of the univariate polynomial arithmetic from the C++ template library , which is shipped with : <\mmx-code> foreign cpp import { \ \ ... \ \ class Pol (R: Ring) == polynomial R; \ \ \ \ forall (R: Ring) { \ \ \ \ pol: Tuple R -\> Pol R == keyword constructor; \ \ \ \ upgrade: R -\> Pol R == keyword constructor; \; \ \ \ \ deg: Pol R -\> Int == deg; \ \ \ \ postfix []: (Pol R, Int) -\> R == postfix []; \; \ \ \ \ prefix -: Pol R -\> Pol R == prefix -; \ \ \ \ infix +: (Pol R, Pol R) -\> Pol R == infix +; \ \ \ \ infix -: (Pol R, Pol R) -\> Pol R == infix -; \ \ \ \ infix *: (Pol R, Pol R) -\> Pol R == infix *; \ \ \ \ ... \ \ } } As is clear from this example, the actual syntax for template imports is a straightforward extension of the syntax of usual imports and the syntax of generic declarations on the side. Actually, the above code is still incomplete: in order to make it work, we also have to specify how the ring operations on should be interpreted on the C++ side. This is done by the category toC++: <\mmx-code> foreign cpp export category Ring == { \ \ convert: Int -\> This == keyword constructor; \ \ prefix -: This -\> This == prefix -; \ \ infix +: (This, This) -\> This == infix +; \ \ infix -: (This, This) -\> This == infix -; \ \ infix *: (This, This) -\> This == infix *; } This means that the ring operations in C++ are the constructor from and the usual operators , and. The programmer should make sure that the C++ implementations of the imported templates only rely on these ring operations. The first thing the compiler does with the above C++ export of is the creation of a C++ class capable of representing generic instances of arbitrary ring types. Any mechanism for doing this has two components: we should not only store the actual ring elements, but also the rings themselves to which they belong. This can actually be done in two ways. The most straightforward idea is to represent an instance of a generic ring by a pair >, where is the actual ring (similar to the example of the C++ counterpart of a monoid in Section

) and an actual element of . This approach has the advantage of being purely functional, but it requires non trivial modifications on the C++ side. Indeed, whenever a function returns a ring object, we should be able to determine the underlying ring from the input arguments. In the case of afunction such as R>, this means that has to be read off from the coefficients of the input polynomial. But the most straightforward implementation of the zero polynomial does not have any coefficients! In principle, it is possible to tweak all C++ containers so as to guarantee the ability to determine the underlying generic parameters from actual instances. We have actually implemented this idea, but it required a lot of work, and it violates the principle that writing a interface for a C++ template library should essentially be trivial. The second approach is to store the ring in a global variable, whose value will frequently be changed in the course of actual computations. In fact, certain templates might carry more than one parameter of type , in which case we need more than one global ring. For this reason, we chose to implement a container Cat,Nr\> for generic instances of a type of category , with an additional integer parameter for distinguishing between various parameters of the same category. The container Cat,Nr\> is really a wrapper for: <\cpp-code> template\typename Cat, int Nr\ class instance { public: \ \ generic rep; \ \ static Cat Cur; \ \ inline instance (const instance& prg2): \ \ \ \ rep (prg2.rep) {} \ \ inline instance (const generic& prg): \ \ \ \ rep (prg) {} \ \ instance (); \ \ template\typename C1\ instance (const C1& c1); \ \ ... }; For instance, objects of type Ring,2\> are instances of the second generic parameter of templates. The corresponding underlying ring is stored in the global static variable Ring,2\::Cur>. When exporting the category to C++, the compiler automatically generates generic C++ counterparts for the ring operations. For instance, the following multiplication is generated for Ring,Nr\>: <\cpp-code> template\int Nr\ inline instance\Ring,Nr\ operator * (const instance\Ring,Nr\