User loginNavigation |
A Functional Representation of Data Structures with a Hole (1998)LtU doesn't seem to have any mentions of this paper by Minamide from 1998. Here's a simple problem that benefits from the ideas described in the paper. The usual way of writing functions like "map" or "append" in a strict language like ML involves building the result list in reverse and then reversing it, which uses 2x more memory than needed. Imperative languages like Java can do without intermediate lists, but at the cost of using mutation on the list nodes after allocating them. To get the best of both worlds, we can extend the idea of tail recursion to also allow "tail allocation" aka "destination passing style", which just means that a recursive call nested within a constructor call should be treated as tail-recursive, and compiled to code that uses mutation internally. That way, the naive implementations of functions like "map" and "append" become as efficient as imperative code, allocating only as much memory as needed for the final result. Some folks on the OCaml mailing lists have pointed out that such an approach would break some assumptions of the garbage collector, namely that the old generation never points into the young generation. I don't know if that problem outweighs the potential benefits of the technique. By Vladimir Slepnev at 2014-07-31 11:22 | LtU Forum | previous forum topic | next forum topic | other blogs | 18224 reads
|
Browse archives
Active forum topics |
Recent comments
25 weeks 4 days ago
25 weeks 4 days ago
25 weeks 4 days ago
47 weeks 5 days ago
52 weeks 16 hours ago
1 year 1 week ago
1 year 1 week ago
1 year 4 weeks ago
1 year 8 weeks ago
1 year 8 weeks ago