Discussion on the implementation of generic programming in non-C languages
Zuo Wei Hou 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. An example of the simplest stack (no implementation is given): Template
Class stack {
PUBLIC:
Void Push (Const Type & Item);
TYPE POP;
...
}
Stack application:
Stack
s;
Int data;
DATA = 1;
S.push (data); //
Int out;
OUT = S.POP; // out of the 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 build 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 created with a custom data type with an Integer member:
Tadt = Class
public
Data: integer;
END;
Let's look at the application:
VAR
Stack: TSTACK;
ADT1, ADT2: TADT;
Begin
Stack: = TSTACK.CREATE;
ADT1: = tadt.create;
Stack.push (ADT1); //
ADT2: = stack.pop as tadt; // out of stack
Stack.free;
This completes the storage of the ADT object. 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 an example:
In a list class, perform a lookup operation:
Template
Class List {
TYPE * FIND (TYPE & VALUE); / / 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); / / judge 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 of do not change the existing syntax of Delphi / Java, the solution that the author can think is to establish a TADT class as a base class for all data structures. 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 Pointer cannot perform complex operations. In actual operations, the programmer is a new class from the container class, or maintains in its own class. A container class. 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 implement the storage of ADT, Delphi / Java can also be implemented by the mechanism of single structure RTTI. 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 overloading to achieve the operation of the ADT. In Delphi / Java that does not support operator overload, the author failed to find a good replacement method. Establish a unified ADT abstract solution solution, can only be said to be an idea. :-( Some programmer tends to increase the operator overload in Delphi, this should be one of the reasons, do not know if Borland pays attention to. In addition, the next version of Java will fully support GP, I don't know what mechanism is achieved ? Please understand the insider's master.
