Abstract Data Type Usage Analysis

I am interested in implementing a program analysis, where the operations applied to an instance of an abstract data type (e.g. a list) determine the implementation's choice of data structure (e.g. array vs linked list).

For example if "insert" or "delete" is used, then a linked list might be chosen, or if "nth" operation (accessing the nth item) is applied then an array might be used.

I am unfamiliar with such analyses. Can anyone recommend any papers or related work?

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Type Analysis and Data Structure Selection

Curiously related to

this recent thread:

Though we don't describe implementation techniques in detail, I've presented what I think is a good general way to declare such ADT thingamabobs.

NYU's SETL language, IBM Research's Hermes language

SETL was intended to support such operations.
Hermes tables can be implemented differently depending on how they are used.