Extensible and efficient double dispatch in single-dispatch...

Details Extensible and efficient double dispatch in single-dispatch... Extensible and efficient double dispatch in single-dispatch...

2001-01-22

2004-04-13

Follansbee, John (Department: 2126)

Electrical computers and digital processing systems: multicomput

Computer-to-computer data routing

Least weight routing

C709S241000, C717S116000

Reexamination Certificate

active

06721807

ABSTRACT:

FIELD OF THE INVENTION
This invention relates to the field of object-oriented programming and, more specifically, to extensible and efficient double dispatch in single-dispatch object-oriented programming languages.
BACKGROUND OF THE INVENTION
Three concepts are central to object-oriented programming: encapsulation, inheritance, and polymorphism. Encapsulation refers to how implementation details are hidden by an abstraction called an “object.” An object is said to encapsulate code and data as defined by a “class,” of which the object is an “instance.” An object is created by “instantiating” its class. The class specifies the code and data associated with each instance. A “concrete class” includes all the code necessary for instances to work correctly and may thus be instantiated. An “abstract class” may have some of the code or no code at all. Hence, it cannot be instantiated.
An object-oriented software system is made up of objects interacting with one another by “sending messages,” also known as “calling operations.” The set of messages (operations) that an object understands is called its “interface.” An object implements its response to a message in a “method” that is common to all instances of the object's class. A method typically elicits collateral message sends. Objects are unaware of each other's implementations. Objects only know the messages to which other objects can respond. Encapsulation controls complexity by partitioning the software system into small, well-defined pieces, and it makes it easy to change part of the system without affecting other parts.
Inheritance defines classes in terms of other classes. Class B that inherits from class A is called a “subclass” or “derived class” of class A (which is called the “parent class,” “base class,” or “superclass”). Class C derived from B may be termed a “descendant” of A as opposed to a “subclass.” The subclass responds to the same messages as its parent, and it may respond to additional messages as well. The subclass “inherits” its implementation from its parent, although it may choose to re-implement some methods, add more data, or both. An abstract class may explicitly defer implementation of a method to subclasses. Such a method (or operation) is termed “abstract” as it has no implementation. Non-abstract operations are sometimes called “concrete operations.” Inheritance lets programmers define new classes easily as incremental refinements of existing ones. It also enables polymorphism.
Polymorphism refers to the substitutability of related objects. Objects are “related” if they have the same “type,” and in most object-oriented languages that means they are instances of the same class, or they have a common superclass through inheritance. Objects of the same type are said to have “compatible interfaces.”
Objects with compatible interfaces may be treated uniformly, that is, without regard to their specific type. For example, a Graphic class that defines an abstraction for graphical objects may define a Draw method. The Graphic class might have subclasses Rectangle and Circle that re-implement Draw to draw a rectangle and circle, respectively. Polymorphism allows Rectangle and Circle instances to be treated uniformly as Graphic objects. In other words, all one needs to know to tell an object to draw itself is that the object is an instance of a Graphic subclass. Whether the object is an instance of Rectangle or Circle is immaterial; one can send it the Draw message without knowing its exact type (e.g., Rectangle or Circle).
Declaring the type of an object explicitly in the program lets the compiler ensure that objects are sent only messages that they implement. Compile-time checks for type incompatibility are valuable because they can catch common programming errors. If a program contains code that attempts to send a message to an object that does not implement a corresponding method—a coding error—then the compiler can detect it before the program is ever run. A compiler that performs such checks is said to enforce “static type safety.”
However, a programmer may circumvent the type checks run by the compiler through programming language mechanisms such as casts and run-time type tests. The former coerces an object to a particular (and possibly incompatible) type, while the latter tests the type of an object and performs computation based on the outcome of the test. Because these mechanisms are invoked at run-time, they are usually beyond the ability of the compiler to check. Thus they may induce type-related failures at run-time. Programs that can fail in this way are called “type-unsafe.”
An important goal of software design generally, and object-oriented design in particular, is to permit change in functionality without change in existing code—additive change instead of invasive change. Polymorphism furthers this goal by letting programmers write general code that can be customized later without change. Suppose there is code that draws pictures by sending Draw messages to a set of Graphic instances. Rectangle and Circle objects may be passed to such code, and it will tell the objects to draw themselves. Later, a new subclass of Graphic can be defined, say Polygon, implementing its Draw method appropriately. Because Polygon is a subclass of Graphic, instances of Polygon may be passed to the picture-drawing code, and it will draw polygons in the picture—with no modification whatsoever.
This example of polymorphism illustrates “single dispatch”: the code that executes in response to a message depends on the message (e.g., Draw) and the type of the receiver (Rectangle, Circle, etc.). It is also possible to dispatch on more than one type. Suppose one wants to draw a polygon either on the display or on hardcopy. The code for drawing a polygon on the display is likely to differ drastically from the code that prints it out. One could therefore define a class Device that abstracts the output device, with subclasses Display and Printer. If a programming language allows one to dispatch on two types—the Graphic subclass and the Device subclass—then the language supports “double dispatch,” as the code that executes in response to a message send (e.g., Draw) depends on the message and the type of two receivers (e.g., Circle and Printer). Single and double dispatch exemplify the more general notion of “multiple dispatch,” which permits dispatch on any number of types.
Mainstream object-oriented programming languages such as C++, Eiffel, Java, and Smalltalk support only single dispatch directly. Double and higher-order dispatch must be implemented explicitly in such languages. The VISITOR pattern [described in Gamma, E., et al., Design Patterns: Elements of Reusable Object-Oriented Software, Addison-Wesley, Reading, Mass., 1995] is a well-known approach to implementing double dispatch in single-dispatch languages.
VISITOR encapsulates double-dispatch functionality in concrete Visitor subclasses of a Visitor class. Double dispatch occurs when an instance of an Element subclass (e.g., ConcreteElement) receives an Accept message with an object of type Visitor as a parameter. In response, Accept sends a message to the Visitor; exactly which message depends on the particular Element subclass. In effect, this message identifies the concrete Element to the concrete Visitor and invokes code that is specific to the ConcreteVisitor-ConcreteElement pair—thereby effecting double dispatch.
FIG. 1
shows a Unified Modeling Language (UML) diagram of a typical VISITOR implementation. This figure (and
FIG. 2
) may be seen in Gamma, E., et al., Design Patterns: Elements of Reusable Object-Oriented Software, Addison-Wesley, Reading, Mass., 1995, p. 331-334, the disclosure of which is hereby incorporated by reference.
FIG. 1
shows a Client object interacting with Visitor and Element (through ObjectStructure) classes. The Visitor class is a base class, and the ConcreteVisitor
1
and ConcreteVisitor
2
concrete classes are subclasses of Visitor. Similarly, Element is a base class, and ConcreteElementA and Concrete

Affiliated with

Also associated with

Rating

Extensible and efficient double dispatch in single-dispatch... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Extensible and efficient double dispatch in single-dispatch..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Extensible and efficient double dispatch in single-dispatch... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3245874