[TYPES] Optimizing data representation

[Richard Eisenberg]

At last year's ICFP in Berlin, I was fortunate enough to head out for the evening with someone working on optimizing type representations. The work he described sounded amazing, but I have failed to recall any details helpful in finding the work to follow up on.

The main idea is to analyze a type declaration to find more efficient ways of representation. I seem to think the analysis included both the type declaration and its use sites. For example, the tool could figure out that `data Nat = Zero | Succ Nat` should really be a number stored in binary, not a linked list with no information stored in the nodes. (I don't remember how it dealt with the unbounded nature of Nat vs the bounded nature of machine integers.) The analysis could also, if I recall, figure out that a list accessed by index is better represented as an array. Having performed this analysis, the tool could then transform the code to use the more efficient representation.

Does anyone know of recent work in this direction? I seem to recall there was a publication in 2018 or 2019 about this all. It sounded very impressive, and I would like to know more.

Thanks!
Richard

-=-=-=-=-=-=-=-=-=-=-
Richard A. Eisenberg, PhD
Principal Researcher at https://tweag.io
https://richarde.dev/