Thanks, Rich, for sticking your head into comp.lang.lisp and pointing me at hash array mapped tries. It just occurred to me that they have another advantage, besides performance, over the binary trees I am currently using for FSet: they make it much easier to implement weak functional maps. And weak functional maps are the critical piece needed for functional graphs.
Persistent functional graphs, to my mind, are the Holy Grail of functional data structures. Without them, there's no completely satisfactory functional way to construct arbitrarily interconnected structures, potentially including cycles. For example, a truly general implementation of functional graphs could be used to simulate the heap: you could put all the state in your program into a functional graph; instead of updating a slot of an object, you would build a new graph in which the graph node representing that object had a different edge. It would be slow, certainly, but not combinatorially slow; each update would take time logarithmic in the size of the heap. And it would give you the unique ability to retain past states of the heap for review. Even if it ran 1000 times slower than normal execution, it could still be very useful for debugging. But there are likelier uses than simulating the entire heap. Persistent functional graphs would be useful for things like program transformation, for instance. Any interactive program can benefit from having data structures that make undoing easy. The usual way to construct arbitrary graph structures is with side- effects, of course. An alternative (used in Haskell, for instance) is to represent the graph as a map from node to (map from edge-label to target node). This works, but loses the benefit of garbage collection: even if some node is not reachable from anywhere in the heap other than the map that implements the graph, nor is reachable within the graph from any node that is reachable from elsewhere in the heap, it won't be GCed because it's still in the _domain_ of the map. One workaround for this problem is to GC the graph itself at the user level. This could be done, for instance, by walking it from a known rootset, copying the nodes reached to a new graph, and finally discarding the old graph and keeping the copy. This can work in some situations, but is not satisfactory in general because it requires knowing the correct rootset. Another approach, apparently common in Haskell, is simply to ignore the problem, letting the garbage nodes be collected when the entire graph becomes garbage. This is not a general solution either, obviously. A third approach in Haskell is to simulate the imperative implementation using monads, but let's not go there :) I see only one fully general solution: weak functional maps. Implementing weak functional maps using binary trees is difficult for an obvious reason: because the values in the map are used to navigate the map. If the value at a tree node were to disappear, because the tree node held it weakly and it became garbage, then when we came to that node while walking the tree, we wouldn't know whether to go left or right. It's conceivable that the tree could be fixed up somehow, but I haven't yet worked out how to do it and it's clear that it's going to be a royal PITA, if indeed it's possible at all. HAMTs do not have this problem: navigation of the trie is controlled entirely by the hash code for the value being looked up. Implementing weak functional maps using HAMTs seems quite doable. You might want to think about doing this for Clojure. It seems possible that functional graphs would enable Clojure programs to read and update fewer refs, which could be desirable in some cases. (I don't think I'll convert FSet to using HAMTs anytime soon, though I'm definitely more motivated now; there are things I would already like to use functional graphs for.) -- Scott --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/clojure?hl=en -~----------~----~----~----~------~----~------~--~---
