Automatic selection of an abstract data type
An implementation of an abstract data type is automatically selected by a compiler of high-level language source code. The compiler chooses an implementation for each instance of an abstract data type in a program based on operations performed in the instance within the program. The compiler rewrites and compiles the high-level language source code in response to selecting the implementation.
1. A method, comprising steps of:
identifying, by a compiler, a set of operations that high-level language source code specifies for an instance of an abstract data type;
based on the set of operations, selecting, by the compiler, a certain implementation for said instance; and
in response to selecting said certain implementation, performing by the compiler:
rewriting the high-level language source code specifying operations on said instance to generate rewritten source code, and
compiling the rewritten source code using the certain implementation; and
wherein the method is performed by one or more computing devices.
2. The method of claim 1 , wherein said high-level language source code does not specify an implementation for said abstract data type.
3. The method of claim 1 , wherein said high-level language source code is written in a computer language that defines the abstract data type as a built-in abstract data type.
4. The method of claim 3 , wherein the operations defined for the abstract data type by the computer language include:
an operation to set a value for a key;
an operation to get a value for a key;
an operation to get a key associated with a minimum value; and
an operation to get a key associated with a maximum value.
5. The method of claim 4 , wherein selecting a certain implementation for said instance includes in response to determining that the high-level language source code specifies that any operation that removes a key from the instance is for a key that is a result of the operation to get a key associated with a minimum value, selecting a min-heap priority map implementation.
6. The method of claim 4 , wherein selecting a certain implementation for said instance includes selecting a max-heap priority map implementation in response to determining that the high-level language source code specifies that any operation that removes a key from the instance is for a key that is a result of said operation to get a key associated with a maximum value.
7. The method of claim 3 , wherein the operations defined for the abstract data type by the computer language include:
an operation to insert an item at the end of a list;
an operation to insert an item at the beginning of a list;
an operation to remove and return an item at the end of a list;
an operation to remove and return an item at the beginning of a list;
an operation to return an item at the end of a list; and
an operation to return an item at the beginning of a list.
8. The method of claim 7 , wherein selecting a certain implementation for said instance includes selecting a dynamic array implementation in response to determining that the high-level language source code specifies that any operation that removes a key from the instance is said operation to remove a key from the end of a list and that any operation that inserts a key into the instance is said operation to insert a key from the end of a list.
9. The method of claim 7 :
wherein selecting a certain implementation for said instance includes selecting a dynamic array implementation in response to determining that the high-level language source code specifies that any operation that removes a key from the instance is said operation to remove a key from the beginning of a list and that any operation that inserts a key from the instance is said operation to insert a key at the beginning of a list;
wherein the method further includes transforming said high-level language source code by performing at least one of the following transformations:
(a) replace any operation to remove and return an item at the beginning of a list with an operation to remove and return an item at the end of the list;
(b) replace any operation to insert an item at the beginning of a list with an operation to insert an item at the end of the list,
(c) replace any operation to return an item at the end of a list with an operation to return an item at the beginning of the list,
(d) replace any operation to return an item at the beginning of a list with an operation to remove and return an item at the end of the list,
(e) replace all forward iteration on the instance with reverse iteration, and
(f) replace all reverse iteration on the instance with forward iteration.
10. One or more non-transitory storage media storing instructions which, when executed by one or more computing devices, cause:
a compiler to identify a set of operations that high-level language source code specifies for an instance of an abstract data type;
based on the set of operations, the compiler to select a certain implementation for said instance; and
in response to selecting said certain implementation, the compiler to:
rewrite the high-level language source code specifying operations on said instance to generate rewritten source code, and
compile the rewritten source code using the certain implementation.
11. The one or more non-transitory storage media of claim 10 , wherein said high-level language source code does not specify an implementation for said abstract data type.
12. The one or more non-transitory storage media of claim 10 , wherein said high-level language source code is written in a computer language that defines the abstract data type as a built-in abstract data type.
13. The one or more non-transitory storage media of claim 12 , wherein the operations defined for the abstract data type by the computer language include:
an operation to set a value for a key;
an operation to get a value for a key;
an operation to get a key associated with a minimum value; and
an operation to get a key associated with a maximum value.
14. The one or more non-transitory storage media of claim 13 , wherein selecting a certain implementation for said instance includes in response to determining that the high-level language source code specifies that any operation that removes a key from the instance is for a key that is a result of the operation to get a key associated with a minimum value, selecting a min-heap priority map implementation.
15. The one or more non-transitory storage media of claim 13 , wherein selecting a certain implementation for said instance includes selecting a max-heap priority map implementation in response to determining that the high-level language source code specifies that any operation that removes a key from the instance is for a key that is a result of said operation to get a key associated with a maximum value.
16. The one or more non-transitory storage media of claim 12 , wherein the operations defined for the abstract data type by the computer language include:
an operation to insert an item at the end of a list;
an operation to insert an item at the beginning of a list;
an operation to remove and return an item at the end of a list;
an operation to remove and return an item at the beginning of a list;
an operation to return an item at the end of a list; and
an operation to return an item at the beginning of a list.
17. The one or more non-transitory storage media of claim 16 , wherein selecting a certain implementation for said instance includes selecting a dynamic array implementation in response to determining that the high-level language source code specifies that any operation that removes a key from the instance is said operation to remove a key from the end of a list and that any operation that inserts a key into the instance is said operation to insert a key from the end of a list.
18. The one or more non-transitory storage media of claim 16 :
wherein selecting a certain implementation for said instance includes selecting a dynamic array implementation in response to determining that the high-level language source code specifies that any operation that removes a key from the instance is said operation to remove a key from the beginning of a list and that any operation that inserts a key from the instance is said operation to insert a key at the beginning of a list;
further including instructions for transforming said high-level language source code by performing at least one of the following transformations:
(a) replace any operation to remove and return an item at the beginning of a list with an operation to remove and return an item at the end of the list;
(b) replace any operation to insert an item at the beginning of a list with an operation to insert an item at the end of the list,
(c) replace any operation to return an item at the end of a list with an operation to return an item at the beginning of the list,
(d) replace any operation to return an item at the beginning of a list with an operation to remove and return an item at the end of the list,
(e) replace all forward iteration on the instance with reverse iteration, and
(f) replace all reverse iteration on the instance with forward iteration.