Home » forums » LtU Forum

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?

By cdiggins at 2007-03-20 16:58 | LtU Forum | previous forum topic | next forum topic | other blogs | 7889 reads

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

Try Type Analysis and Data Structure Selection by Cai, et al.

By Ethan Aubin at Tue, 2007-03-20 20:59 | login or register to post comments

Curiously related to

this recent thread:
http://lambda-the-ultimate.org/node/2153#comment-27139

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.

By Michael Sloan at Sun, 2007-03-25 21:50 | login or register to post comments

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.

By dbremner at Tue, 2007-03-27 19:21 | login or register to post comments