[PDF] A Static C++ Object-Oriented Programming (SCOOP) Paradigm

View - Download A Static C++ Object-Oriented Programming (SCOOP) Paradigm

Previous PDF

Next PDF

A Static C++ Object-Oriented Programming

(SCOOP) Paradigm Mixing Benefits of

Traditional OOP and Generic Programming

Nicolas Burrus, Alexandre Duret-Lutz, Thierry G´eraud, David Lesage, and

Rapha¨el Poss

EPITA Research and Development Laboratory

14-16 rue Voltaire, F-94276 Le Kremlin-Bicˆetre, France

firstname.lastname@lrde.epita.fr Abstract.Object-oriented and generic programming are both supported in C++. OOP provides high expressiveness whereas GP leads to more ef- ficient programs by avoiding dynamic typing. This paper presents SCOOP, a new paradigm which enables both classical OO design and high per- formance in C++ by mixing OOP and GP. We show how classical and advanced OO features such as virtual methods, multiple inheritance, ar- gument covariance, virtual types and multimethods can be implemented in a fully statically typed model, hence without run-time overhead.

1 Introduction

In the context of writing libraries dedicated to scientific numerical computing, ex- pressiveness, reusability and efficiency are highly valuable. Algorithms are turned into software components that handle mathematical abstractions while these ab- stractions are mapped into types within programs. The object-oriented programming (OOP) paradigm offers a solution to ex- press reusable algorithms and abstractions through abstract data types and in- heritance. However, as studied by Driesen and H¨olzle [18], manipulating ab- stractions usually results in a run-time overhead. We cannot afford this loss of performance since efficiency is a crucial issue in scientific computing. To both reach a high level of expressiveness and reusability in the design of object-oriented scientific libraries and keep an effective run-time efficiency for their routines, we have to overcome the problem of "abstractions being ineffi- cient". To cope with that, one can imagine different strategies. A first idea is to find an existing language that meets our requirements, i.e., a language able to handle abstractions within programs without any penalty at execution time. This language has to be either well-known or simple enough to ensure that a scientist will not be reluctant to use our library. Unfortunately we do not feel satisfied with existing languages; for instance LOOM and PolyTOIL by Bruce et al. [11, 9] have the precise flavor that we expect but, as prototypes, they do not feature all what a complete language can offer. A second approach, chosen by Baumgartner and Russo [6] and Bracha et al. [8] respectively for C++ and Java, is to extend an existing expressive language by adding ad hoc features making programs more efficient at run-time. Yet, this approach requires a too great amount of work without any guarantee that extensions will be adopted by the language community and by compiler vendors. To overcome this problem, an alternate approach is to propose a front-end to translate an extended language, more expressive, into its corresponding primary language, efficient, such as Stroustrup [49] did with his erstwhile version of the C++ language. This approach has been made easier than in the past thanks to recently available tools dedicated to program translation, for instance Xt [57]. However, we have not chosen this way since we are not experimented enough with this field. Another strategy is to provide a compiler that produces efficient source codes or binaries from programs written in an expressive language. For that, several solutions have been developed that belong to the fields of static analysis and partial evaluation, as described by Chambers et al. [14], Schultz [42], Veldhuizen and Lumsdaine [56]. In particular, how to avoid the overhead of polymorphic method calls is studied by Aigner and H¨olzle [2], Bacon and Sweeney [4] for C++ and by Zendra et al. [58] for Eiffel. However, most of these solutions remain prototypes and are not implemented in well-spread compilers. Last, we can take an existing object-oriented language and try to bend it to make some constructs more efficient. That was for instance the case of the ex- pression templates construct defined by Veldhuizen [54] in C++, later brought to Ada by Duret-Lutz [19], and of mixin-based programming by Smaragdakis and Batory [44] in C++. These solutions belong to the field of thegeneric program- ming(GP) paradigm, as described by Jazayeri et al. [26]. This programming style aims at implementing algorithms as general so reusable as possible without sacrificing efficiency obtained by parameterization-related to thetemplatekey- word in C++ and to thegenerickeyword in Ada and Eiffel. However, from our experience in developing a scientific library, we notice several major drawbacks of GP that seriously reduce expressiveness and affect user-friendliness, whereas these drawbacks do not exist with "classical" OOP. A key point of this paper is that we donotsubscribe to "traditional" GP because of these drawbacks. Said shortly, they have their origin in the unbounded structural typing of param- eterization in C++ which prevents from having strongly typed signatures for functions or methods. Consequently, type checking at compile-time is awkward and overloading is extremely restricted. Justifications of our position and details about GP limitations are given later on in this paper. Actually, we want to keep the best of both OOP and GP paradigms- inheritance, overloading, overriding, and efficiency-without resorting to a new language or new tools-translators, compilers, or optimizers. The advent of the C++ Standard Template Library, mostly inspired by the work of Stepanov et al. [47], is one the first serious well-known artifact of GP. Following that example a lot of scientific computing C++ libraries arose during the past few years(they are referenced by oonumerics [39]), one of the most predominant being Boost [7]. Meanwhile, due to the numerous features of C++, many related GP tech- niques appeared and are described in the books by Czarnecki and Eisenecker [17], Alexandrescu [3], Vandevoorde and Josuttis [53]. Moreover, Striegnitz and Smith [48], J¨arvi and Powell [25], Smaragdakis and McNamara [45] have shown that some features offered by a non-object-oriented paradigm, namely the func- tional one, can be supported by the native C++ language. Knowing these C++ programming techniques, we then thought that this language was able to sup- port an OOP-like paradigm without compromising efficiency. The present paper describes this paradigm, namely a proposal for "Static C++ Object-Oriented

Programming": SCOOP.

This paper is composed of three parts. Section 2 discusses the OOP and GP paradigms, their limitations, existing solutions to overcome some of these limita- tions, and finally what we expect from SCOOP. Section 3 shows how SCOOP is implemented. Finally some technical details and extra features have been moved into appendices.

2 OOP, GP, and SCOOP

A scientific library offers data structuresandalgorithms. This procedural point of view is now consensual [35] although it seems to go against OOP. Actually, an algorithm is intrinsically a general entity since it deals with abstractions. To get the highest decoupling as possible between data and algorithms, a solution adopted by the C++ Standard Library and many others is to map algorithms into functions. At the same time, data structures are mapped into classes where most of the methods are nothing but the means to access data. Last, providing reusable algorithms is an important objective of libraries so we have to focus on algorithms. It is then easier to consider that algorithms and all other entities are functions (such as in functional languages) to discuss typing issues. For all these reasons, we therefore adopt in this section a function-oriented approach of algorithms.

2.1 About Polymorphisms

A function is polymorphic when its operands can have more than one type, either because there are several definitions of the function, or because its definition allows some freedom in the input types. The right function to call has to be chosen depending on the context. Cardelli and Wegner [13] outline four different kinds of polymorphism. Ininclusion polymorphism, a function can work on any type in atype class. Type classes are named sets of types that follow a uniform interface. Func- tional languages like Haskell allow programmers to define type classes explicitly, but this polymorphism is also at the heart of OO languages. In C++, inclusion polymorphism is achieved via two mechanisms: subclassing and overriding of virtual functions. Subclassing is used to define sets of types. Theclass(orstruct) keyword is used to define types that can be partially ordered through a hierarchy: i.e., an inclusion relation

1. A function which expects a pointer or reference to a classA

will accept an instance ofAor any subclass ofA. It can be noted that C++"s typing rules make no difference between a pointer to an object whose type is exactlyAand a pointer to an object whose type belongs to the type class ofA2. Overriding of virtual functions allows types whose operations have different implementations to share the same interface. This way, an operation can be implemented differently in a subclass ofAthan it is inA. Inclusion polymorphism is sometime calledoperation polymorphismfor this reason. These two aspects of inclusion polymorphism are hardly dissociable: it would make no sense to support overriding of virtual functions without subclassing, and subclassing would be nearly useless if all subclasses had to share the same implementation. Inparametric polymorphism, the type of the function is represented using at least one generic type variable. Parametric polymorphism really corresponds to ML generic functions, which are compiled only once, even if they are used with different types. Cardelli and Wegner states that Ada"s generic functions are not to be considered as parametric polymorphism because they have to be instantiated explicitlyeach time they are used with a different type. They see Ada"s generic functions as a way to produce several monomorphic functions by macro expansion. It would therefore be legitimate to wonder whether C++"s function templates achieve parametric polymorphism. We claim it does, because unlike Ada"s generics, C++"s templates are instantiatedimplicitly. In effect, it does not matter that C++ instantiates a function for each type while ML compiles only one function, because this is transparent to the user and can be regarded as an implementation detail 3. These two kinds of polymorphism are calleduniversal. A nice property is that they are open-ended: it is always possible to introduce new types and to use them with existing functions. Two other kinds of polymorphism do not share this property. Cardelli and Wegner call themad-hoc. Overloadingcorresponds to the case where several functions with different types have the same name. Coercion polymorphismcomes from implicit conversions of arguments. These conversions allow a monomorphic function to appear to be polymorphic. All these polymorphisms coexist in C++, although we will discuss some no- table incompatibilities in section 2.3. Furthermore, apart from virtual functions,1 Inclusion polymorphism is usually based on a subtyping relation, but we do not enter the debate about "subclassing v. subtyping" [15].

2In Ada, one can writeaccess Aoraccess A"Classto distinguish a pointer to an

instance ofAfrom a pointer to an instance of any subclass ofA.

3This implementation detail has an advantage, though: it allows specialized instan-

tiations (i.e., template specializations). To establish a rough parallel withinclusion polymorphism, template specializations are to templates what method overriding is to subclassing. They allow to change the implementation for some types. the resolution of a polymorphic function call (i.e., choosing the right definition to use) is performed at compile-time.

2.2 About the Duality of OOP and GP

Duality of OOP and GP has been widely discussed since Meyer [33]. So we just recall here the aspects of this duality that are related to our problem. Let us consider a simple functionfoothat has to run on different image types. In traditional OOP, the image abstraction is represented by an abstract class, Image, while a concrete image type (for instanceImage2D) for a particular kind of 2D images, is a concrete subclass of the former. The same goes for the notion of "point" that gives rise to a similar family of classes:Point, which is abstract, andPoint2D, a concrete subclass ofPoint. That leads to the following code4: structImage{ virtual voidset(constPoint& p,intval) = 0; structImage2D :publicImage{ virtual voidset(constPoint& p,intval){/?impl?/} voidfoo(Image& input,constPoint& p){ // does something like: input.set(p, 51); intmain(){

Image2D ima; Point2D p;

foo(ima, p); foois a polymorphic function thanks toinclusion through class inheritance. The callinput.set(p, 51)results in a run-time dispatch mechanism which binds this call to the proper implementation, namelyImage2D::set. In the equivalent

GP code, there is no need for inheritance.

structImage2D{ voidset(constPoint2D& p,intval){/?impl?/} template voidfoo(IMAGE& input,constPOINT& p){ // does something like: input.set(p, 51); }4 Please note that, for simplification purpose, we usestructinstead ofclassand that we do not show the source code corresponding to thePointhierarchy. intmain(){

Image2D ima; Point2D p;

foo(ima, p); foois now polymorphic throughparameterization. At compile-time, a par- ticular version offoois instantiated,foo, dedicated to the particular call tofooinmain. The basic idea of GP is that all exact types are known at compile-time. Consequently, functions are specialized by the compiler; moreover, every function call can be inlined. This kind of programming thus leads to efficient executable codes. The table below briefly compares different aspects of OOP and GP.notionOOPGP typingnamed typing through class namesstructural so explicit in class definitionsso only described in documentation abstractionabstract classformal parameter

(e.g., image)(e.g.,Image)(e.g.,IMAGE)inheritanceis the way to handle abstractionsis only a way to factorize code

methodno-variant- (set)(Image::set(Point, int)-Image2D::set(Point, int))- algorithma single code at program-timea single meta-code at program-time (foo)(foo)(template<..> foo)and a unique version at compile-timeand several versions at compile-time (foo)(foo, etc.)efficiencypoorhigh From the C++ compiler typing point of view, our OOP code can be trans- lated into: type Image ={set : Point→Int→Void} foo : Image→Point→Void foois restricted to objects whose types are respectively subclasses ofImageand Point. For our GP code, things are very different. First, the image abstraction is not explicitly defined in code; it is thus unknown by the compiler. Second, both formal parameters offooare anonymous. We then rename them respectively "I" and "P" in the lines below and we get: ?I,?P, foo : I→P→Void Finally, if these two pieces of code seem at a first sight equivalent, they do not correspond to the same typing behavior of the C++ language. Thus, they are treated differently by the compiler and have different advantages and drawbacks. The programmer then faces the duality of OOP and GP and has to determinate which paradigm is best suited to her requirements. During the last few years, the duality between OOP and GP has given rise to several studies. Different authors have worked on the translation of some design patterns [22] into GP; let us mention G´eraud et al. [23], Langer [27], Duret-Lutz et al. [20],

Alexandrescu [3], R´egis-Gianas and Poss [40].

Another example concerns thevirtual typesconstruct, which belongs to the OOP world even if very few OO languages feature it. This construct has been proposed as an extension of the Java language by Thorup [51] and a debate about the translation and equivalence of this construct in the GP world has followed [10, 52, 41]. Since the notion of virtual type is of high importance in the following of this paper, let us give a more elaborate version of our previous example. In an augmented C++ language, we would like to express that both families of image and point classes are related. To that aim, we could write: structImage{ virtual typedefPoint pointtype = 0; virtual voidset(constpointtype& p,intval) = 0; structImage2D :publicImage{ virtual typedefPoint2D pointtype; virtual voidset(constpointtype& p,intval){/?impl?/} point_typeis declared in theImageclass to be an "abstract type alias" (virtual typedef .. point_type = 0;) with a constraint: in subclasses ofImage, this type should be a subclass ofPoint. In the concrete classImage2D, the alias point_typeis defined to bePoint2D. Actually, the behavior of such a construct is similar to the one of virtual member functions: usingpoint_typeon an im- age object depends on the exact type of the object. A sample use is depicted hereafter:

Image?ima =newImage2D();

Point?p =new(ima->pointtype)();

At run-time, the particular exact type ofpisPoint2Dsince the exact type ofima isImage2D. An about equivalent GP code in also an augmented C++ is as follows: structImage2D{ typedefPoint2D pointtype; voidset(constpointtype& p,intval){/?impl?/} template where I{ typedefpointtype; voidset(constpointtype&,int); voidfoo(I& input,const typenameI::pointtype& p){ // does something like: input.set(p, 51); intmain(){

Image2D ima; Point2D p;

foo(ima, p); Such as in the original GP code, inheritance is not used and typing is fully structural. On the other hand, awhere clausehas been inserted infoo"s signature to precise the nature of acceptable type values forI. This construct, which has its origin in CLU [30], can be found in Theta [29], and has also been proposed as an extension of the Java language [36]. From the compiler point of view,foo"s type is much more precise than in the traditional GP code. Finally, in both C++ OOP augmented with virtual types and C++ GP augmented with where clauses, we get stronger expressiveness.

2.3 OOP and GP Limitations in C++

Object-Oriented Programmingrelies principally on the inclusion polymor- phism. Its main drawback lies in the indirections necessary to run-time resolution of virtual methods. This run-time penalty is undesirable in highly computational code; we measured that getting rid of virtual methods could speed up an algo- rithm by a factor of 3 [24]. This paradigm implies a loss of typing: as soon as an object is seen as one of its base classes, the compiler looses some information. This limits optimization opportunities for the compiler, but also type expressiveness for the developer. For instance, once the exact type of the object has been lost, type deduction (T::deducted_type) is not possible. This last point can be alleviated by the use of virtual types [52], which are not supported by C++. The example of the previous section also expresses the need for covariance: foocalls the methodsetwhose expected behavior is covariant.fooprecisely callsImage2D::set(Point2D,int)in the GP version, whereas the call in the OOP version corresponds toImage::set(Point,int). Generic Programingon the other hand relies on parametric polymorphism and proscribes virtual functions, hence inclusion polymorphism. The key rule is that the exact type of each object has to be known at compile-time. This allows the compiler to perform many optimizations. We can distinguish three kinds of issues in this paradigm: -the rejection of operations that cannot be typed statically, -the closed world assumption, -the lack of template constraints. The first issues stem from the will to remain statically typed. Virtual func- tions are banished, and this is akin to rejecting inclusion polymorphism. Fur- thermore there is no way to declare an heterogeneous list and to update it at run-time, or, more precisely to dynamically replace an attribute by an object of a compatible subtype. These operations cannot be statically typed, there can be no way around this. The closed world assumption refers to the fact that C++"s templates do not support separate compilation. Indeed, in a project that uses parametric polymor- phism exclusively it prevents separate compilation, because the compiler must always know all type definitions. Such monolithic compilation leads to longer build times but gives the compiler more optimization opportunities. The C++ standard [1] supports separate compilation of templates via theexportkeyword, but this feature has not been implemented in mainstream C++ compilers yet. voidfoo(A1& arg) arg.m1() voidfoo(A2& arg) arg.m2() }template voidfoo(A1& arg) arg.m1() template voidfoo(A2& arg)// illegal arg.m2() }template voidfoo(A1& arg) arg.m1() template<> voidfoo(A2& arg) arg.m2() Fig.1.Overloading can be mixed with inclusion polymorphism (left), but will not work with unconstrained parametric polymorphism (middle and right). The remaining issues come from bad interactions between parametric poly- morphism and other polymorphisms in C++. For instance, because template arguments are unconstrained, one cannot easily overload function templates. Figure 1 illustrates this problem. When using inclusion polymorphism (left), the compiler knows how to resolve the overloading: ifargis an instance of a sub- class ofA1, resp.A2, it should be used with the first resp. second definition of foo(). We therefore have two implementations offoo()handling two different sets of types. These two sets are not closed (it is always possible to add newquotesdbs_dbs14.pdfusesText_20

[PDF] object oriented programming c++ lecture notes ppt

[PDF] object oriented programming mcq with answers pdf

[PDF] object oriented programming questions and answers pdf

[PDF] object oriented programming with c++ balagurusamy solutions pdf

[PDF] objective c interface multiple inheritance

[PDF] objectives of financial management

[PDF] objectives of therapeutic drug monitoring

[PDF] objects first with java: a practical introduction using bluej 6th edition pdf

[PDF] obligatoire en anglais synonyme

[PDF] obligatoire en anglais traduction

[PDF] obligatoire en anglais traduire

[PDF] occupational therapy short term goals examples

[PDF] ocr computer science end of unit quiz 2.1

[PDF] ocr computer science end of unit quiz 2.1 answers

[PDF] octave fft example