[Haskell-cafe] compilation related questions
Claus Reinke
claus.reinke at talk21.com
Fri Apr 10 18:12:41 EDT 2009
> On a related note, I have another question. Say we have some data
> structure, for instance a list, some functions on this data structure
> (probably defined with some well known functions, such as map or
> fold), and a program using them. Is there any research trying to
> rewrite the program, and the data structure, to optimize them ?
Do you mean "computer science"?-) Much of this field could be
rephrased as the search for better representations, to enable
better implementations of algorithms (for some measure of "better"):
do we represent programs as data structures to be interpreted,
or as code to be executed? do we use sets, lists, arrays, ..? how
do we represent sets/lists/arrays/..? do we recompute properties
of data, or do we store them (and is one better always, or sometimes,
and when? or do we need to optimize for the average or the most
common case? how do we define "better", anyway?)? which are
the options, for a particular application domain, or a general class
of data structure/algorithm, and how do they compare? and so on..
But if you limit your question sufficiently, you might have some
luck looking for papers that reference any of these:
Automatic data structure selection: an example and overview,
James R. Low, Communications of the ACM, 1978
http://portal.acm.org/citation.cfm?id=359488.359498
Techniques for the automatic selection of data structures
Low, Rovner, 3rd POPL, 1976
http://portal.acm.org/citation.cfm?id=811540
Rovner, P. Automatic representation selection for associative
data structures. Ph.D. Th., Harvard U., Cambridge, Mass;
Tech. Rep. TR10, U. of Rochester, Rochester, N.Y., Sept. 1976.
Claus
More information about the Haskell-Cafe
mailing list