Discussion on the implementation of generic programming in non-C ++ languages

Implementation of generic programming in non-C languages ​​Zuo Lianghou 2001.9.22

GP (Generic Programming, generic programming) is called another revolution in programming ideas. However, in the data of GP, it is generally discussed based on C languages. So, can the GP can be implemented in other programming languages? This is a problem that the author has been thinking, because the level of level is limited and the information is lacking, and the harvest is very small. Some immature ideas are now sorted out, please visit the guests. In this paper, Delphi as an example (Java is similar, can be referred to), and discussing another implementation of GP. The code is written, not verified. According to the author's understanding, the key to GP is achieved, in the implementation of ADT (Abstract Data Type, abstract data type). Only ADTs can be separated from the common algorithm to the general algorithm. In C , the storage of the ADT is implemented by a template. Elive an example of a simplest stack (no implementation): Template class stack {public: void push (const type & item); type pop; ...}

Stack application: stack s; int data; data = 1; s.push (data); file: //

Int out; out = s.pop; file: // out of stack

By establishing a Stack object of an int type, storage of int type data is implemented. However, in Delphi / Java, there is no template mechanism. So how do you implement ADT? Unlike C , Delphi / Java's inheritance system is single structure, that is, in Delphi, all Class is forced by compiler, which guarantees subclass of TOBJECT (Object in Java). This TOBJECT can be seen as the highest level of all classes. So, can it think that Delphi / Java has provided support for ADT? Try to create a stack with this idea: tstack = class public procedure push (item: TOBJECT); Function Pop: TOBJECT; ... END;

This TSTACK class operates for the TOBJECT type object. However, this category cannot be applied immediately, because in Delphi, the simple data type is not an object. So you must build a custom data type. The following is established with a custom data type with an Integer member: Tadt = Class Public Data: Integer; end; then look at the application: var stack: tstack; adt1, adt2: tadt; begin stack: = tstack.create; ADT1: = Tadt.create; stack.push (ADT1); file: // Add stack ADT2: = stack.pop as tadt; file: // out of stack.free; This completes the storage of ADT objects. It must be noted that the ADT object is directly in the stack when it is incorporated, because the TSTACK class is operated to TOBJECT, because the single structure of Delphi can assign any type of object to the TOBJECT type variable. However, when the stack is put, the return is also a TOBJECT variable, so it must be mapping a downward mapping with AS. Due to single structures, Delphi / Java provides powerful support for RTTI, so this downward mapping is a light. However, there is no doubt that RTTI has lost in efficiency. How can I achieve the operation of the ADT after the storage of the ADT is implemented? In C , this problem is solved by operator overload. Look at: In a list class, perform a lookup operation: Template class list {type * find; file: // Find the specified data item, then return to its address, otherwise returns null .. Template type * list :: find (type & value) {type * p = first-> link; where (p! = null &&! (p-> data == value)) {p = P-> link;} return p;

In the implementation of the Find function of the List class, the code is copied from the realization of the chain table structure, and does not need to be careful. There is only one place to pay attention to, that is, P-> DATA == Value in the judgment condition. Since P-> Data and Value are ADT, they may be simple data when establishing a List class, or any custom data type. However, it is still possible to use the == such an operator to operate it. why? The reason is the operator overload. Below with a Point class, this is used:

Class Point {private: int x, y; public: int operator == (const point & point); file: // Judgment whether two Point objects are equal ...}

INT POINT :: Operator == (const point & point) {if (x == point.x && y == poing.y) {return 1;} else {return 0;};

It can be seen that more than two POINT objects can be compared due to heavy load == operators. Similarly, any data type, as long as the corresponding operator is heavy, it can be unified by the container class. When the gaze re-turns non-C , the problem has appeared again: Delphi / Java does not support operator overload. As a remedy, you can use a function instead of the operator. For example, uniform use of the Equals function instead ==. However, a bigger problem is that the object of the container operation is TOBJECT, and the TOBJECT does not have a method such as equals. (In Java, Object has an equals method, but there is no other complete operation method.) Under the premise that the author does not change the existing syntax of the Delphi / Java, the solution can be thought of is to establish a TADT class, as all data Structure base class. A lot of abstract methods such as Equals, Add is defined in tadt. Customized data types are derived from TADT and overload the corresponding method. The container class only needs to operate TADT to achieve a general algorithm. However, this solution is not ideal. (Supplementary, in fact, Delphi provides some universal containers such as TLIST, TCOLLECTION, TSTACK, TQUEUE, etc., but different from this article, they are stored not Tobject, but Pointer. Due to Delphi "reference object Model "mechanism, store Tobject object, in fact, is also equal to storage a Pointer, the difference is that Pointer can not only store objects, but also store basic data types. This should also be the reason why Borland is designed. However, these containers are only available The management method such as Add, Delete does not provide a general algorithm because of the complex operation of Pointer. In practice, it is often sent a new class from the container class, or maintains one in your own class. Containers. This is also a solution, but the algorithm cannot be independent.) In summary, the author's view is as follows: 1, C through the template mechanism to achieve the storage of ADT, Delphi / Java can also pass single The mechanism of structure RTTI is implemented. Its difference is that the implementation of C is grammar, and Delphi / Java is logically, that is, C is implemented through a special syntax, and Delphi / Java is based on OOP theory and itself. The class library system is naturally implemented. The author considers that from this perspective, Delphi / Java's implementation mechanism is simpler and intuitive. 2. Calculated from operational efficiency, C is stronger than Delphi / Java, because C implementation is compiled, while Delphi / Java is running. The use of RTTI will have a small impact on efficiency. However, from another perspective, the ADT has benefited from the implementation of the runtime, which is the type of data stored in the container class by arbitrarily changing the container class. The author has not considered such a "data type polymorphism" that will bring a substantive consequence of programming. However, it is boldly imperative, and it may be encapsulated in the compiled module such as DLL, even in the COM object provided in the OS, and programmers only need to create their own data type, and submit it to the corresponding interface. ? ... 3, C by operator overload, to achieve the operation of the ADT.