Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1997-03-12
2001-05-22
Powell, Mark R. (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S152000, C717S152000, C717S152000, C717S152000
Reexamination Certificate
active
06237134
ABSTRACT:
The foregoing copending applications are incorporated herein by reference.
A portion of the Disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to the fields of generic programming and parallel programming, and more particularly to a generic adaptor for converting from a non-future function pointer to a future function object.
2. Description of the Related Art
Parallel Programming Futures
Parallel programming or parallel processing is a method of processing that executes on a computer containing two or more processors running simultaneously. A primary objective of parallel processing is dividing a task so that it may be distributed among the available processors. Parallel programming has developed the concept of futures which are place-holders for values or computations. Future abstractions are useful in parallel programming because they allow asynchronous computation by enabling delaying the computation of the value of an object until the value is required. Futures are also useful for writing parallel programs that look similar to their sequential counterparts.
The parallel programming arts have developed numerous futures mechanisms. The state of the art is represented by futures mechanisms such as the MultiLisp future primitive, the Argus promise type, the Concurrent Smalltalk Cbox, the Concurrent ML future functor, the Mentat return-to-future, the ES-Kit future ref, the polymorphic future, and the future for a future-based parallel language for a general-purpose highly-parallel computer.
Future mechanisms such as the MultiLisp future primitive as taught by Halstead (Halstead, Robert H., Jr. MultiLisp: A Language for Concurrent Symbolic Computation. ACM Transactions on Programming Languages and Systems, 7(4):501-538, October 1985) and the Concurrent Smalltalk Cbox as taught by Yokote (Yokote, Yasuhiko. The Design and Implementation of Concurrent Smalltalk. World Scientific, 1990) provide polymorphic futures, those with arbitrary future types and dynamic type resolution at runtime.
Future mechanisms such as the MultiLisp future primitive as taught by Halstead, the Concurrent Smalitalk Cbox as taught by Yokote, the ES-Kit future ref as taught by Leddy et al. (Leddy, Bill and Smith, Kim. The Design of the Experimental Systems Kernel. In Proceedings of the Conference on Hypercube and Concurrent Computer Applications, Monterey, Calif., 1989) also provide implicit type conversion.
Concurrent Smalltalk Cbox as taught by Yokote and the ES-Kit future ref as taught by Leddy et al. allow user-defined operations as part of the future, known as computational futures.
Additional futures mechanisms include the teachings of the Argus promise type as taught by Liskov et al. (Liskov, Barbara and Shrira, Luiba. Promises: Linguistic Support for Efficient Asynchronous Procedure Calls in Distributed Systems. In Proceedings of the SIGPLAN'88 Conference on Programming Language Design and Implementation, pages 260-267, June 1988); the Concurrent ML future functor as taught by Reppy (Reppy, John H. Concurrent Programming with Events: The Concurrent ML Manual. AT&T Bell Laboratories, February 1993. version 0.9.8); the Mentat return-to-future as taught by Grimshaw (Grimshaw, Andrew S. Easy-to-use Object-oriented Parallel Processing with Mentat. IEEE Computer, pages 39-51, May 1993); the polymorphic future as taught by Lavender et al. (Lavender, R. Greg and Kafura, Dennis G. A Polymorphic Future and First-class Function Type for Concurrent Object-Oriented Programming. Sponsored in part by National Science Foundation grant CCR-9104013); and the future for a future-based parallel language for a general-purpose highly-parallel computer as taught by Callahan et al. (Callahan, David and Smith, Burton. A Future-based Parallel Language For a General-purpose Highly-parallel Computer. Tera Computer Company, 400 N. 34th Street, Suite 300, Seattle, Wash. 98103. ARPA Order No. 6512, Program Code No. E20 issued by DARPA/CMO under Contract #MDA972-89-C-0002 and sponsored by the Defense Advanced Research Projects Agency Information Science and Technology Office).
Despite the above developments in future mechanisms and features, the prior art has failed to develop a generic future mechanism or a generic future abstraction for use in generic programming.
Generic Programming
Generic programming provides a paradigm that abstracts concrete efficient algorithms that may be combined with different data representations to produce a wide variety of useful software. Given N data types, M containers, and K algorithms as components of a software system, the generic programming paradigm provides a mechanism to reduce the possibly N*M*K implementations to N+M+K implementations. For instance, using this paradigm, a generic sorting algorithm may be instantiated to work with different aggregate data structures like linked lists or arrays. Originally developed in Ada and Scheme, a library implementing this paradigm in C++, known as the Standard Template Library or STL, has been adopted by the C++ ANSI standard committee.
The Standard Template Library
The standard template library implements the four abstractions of generic programming, data, algorithmic, structural, and representational, as a container class library in C++.
Data Abstractions
Data abstractions are data types and sets of operations on them. These are implemented as containers or template classes in C++. Templates or parameterized types in C++ provide a uniform interface and implementation abstractions for different data types. For instance, a template stack class may be instantiated to a stack of integers, a stack of doubles, or a stack of any user-defined type. Thus, for N data types only one template container class is provided which may be instantiated N ways.
Algorithmic Abstractions
Algorithmic abstractions are families of data abstractions with a common set of algorithms, known as generic algorithms. For instance, a sort algorithm could work on a linked list or a vector data abstraction. Algorithmic abstractions are implemented as template functions in C++, and are typically parameterized over iterators or structural abstractions.
Structural Abstractions
Structural abstractions are defined with respect to algorithmic abstractions. Structural abstractions are data types defined by data abstractions over which algorithmic abstractions may be instantiated. These structural abstractions are implemented as iterators in STL, and are data type templates exported by container classes. Algorithm templates work over iterators rather than directly over containers; therefore, a same algorithm template may be instantiated for different container instantiations. An iterator may be of one of the following kinds: input, output, forward, backward, or random-access. There are interfaces, depending on the kind of the iterator, that enable referencing and traversing data abstractions. The referencing operator is an overloaded * operator which returns the value at the position pointed to by the iterator. This operator may be used to read or write in an assignment expression the data pointed to by the iterator. Traversal operators include ++(auto-increment), −−(auto-decrement), +n (jump n positions forward), and −n (jump n positions backward).
Representational Abstractions
Representational abstractions are mappings from one structural abstraction to another. Representational abstractions are known as adaptors in STL, and are casting wrappers that change the appearance of a container (building a stack from a list), or change the appearance of an iterator (converting a random-access iterator to a bidirectional
International Business Machines - Corporation
Johnson Prentiss W.
Powell Mark R.
Vo Ted T.
LandOfFree
Method of, system for, and article of manufacture for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of, system for, and article of manufacture for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of, system for, and article of manufacture for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2445927