| Mighty morphin' data structures:
programmers often have to make somewhat-arbitrary decisions when
writing code - e.g. whether to implement a table mapping from keys to
values using a linked list, using a hash table, or perhaps using some
kind of more elaborate scheme. From the point of view of performance
the `correct' decision depends on how the data structure will be used
(e.g. whether insertions are frequent, or what kinds of searches or
updates will be performed) and on the volume of data being held.
Such decisions are more difficult in library code which may be used in
many different ways by different clients.
This project proposes a form of `magical' data structure in which the
programmer specifies merely the abstract data type that they require
- i.e. the operations and behaviour that they need - and the system
selects an appropriate representation. It may do this based on
automatic feedback from previous execution runs, or even change the
representation dynamically as program behaviour shifts between phases.
A possible way to proceed is to modify an implementation of the JVM to
provide these facilities. ADTs could be represented by Java
interfaces. If the programmer attempts to instantiate an interface
(something that's not normally legal) then the system should select a
particular implementation of that interface.
This project is somewhat similar to the auto-tuning
software suggestion, but concentrates on selecting appropriate data
structure implementations rather than appropriate parameters for
tuning values.
| 
