search

plum-umd / adapton.ocaml

(Nominal) Adapton in OCaml
50 stars 5 forks source link

IMP: Use Bill Pugh's hash-trie in place of the association list-based store #17

Closed matthewhammer closed 9 years ago

matthewhammer commented 9 years ago

We are currently using an association list-based representation of the store.

The problem with this representation is that, since it encodes a total order for the store bindings, each lookup is sensitive to the particular order in which the bindings are made. This is undesirable since the order of distinct store variables in the list cannot affect the outcome of any lookup, i.e., this order is not semantically relevant. We'd like it if incremental reuse exploited this independence.

To achieve independence between independent bindings, we should use Bill Pugh's "Hash Trie" representation of the store. Currently, we name cons cells in the association list using our notion of eta. Analogously, in the case of the hash trie, we will name a new trie path by the same eta. Unlike the association list, the structure (and thus query paths) of the trie are independent of the order of district variables' operations. Hence, when distinct variable effects are re-ordered, the resulting trie will be indistinguishable from that of the original ordering.

dvanhorn commented 9 years ago

I spoke to @labichn and he's on board with taking this. I've assigned the issue to him.

@matthewhammer Do you have an experiment that will perform poorly under the assoc list but work well with tries? I think the "swap two assignments" experiment was what we discussed right? Is there code for that?

matthewhammer commented 9 years ago

Swapping two assignments is what I had in mind. We haven't written code for that mutation yet. It will be a variation on what's already written (find the first assignment, find the second assignment, swap them).

dvanhorn commented 9 years ago

OK, I will take that part.

dvanhorn commented 9 years ago

BTW, the representation of the store should be something the semantics is parameterized by, right? That way we can compare the two strategies.

matthewhammer commented 9 years ago

Yeah, we would like to be able to switch between the two versions, for experiments. It may be worth trying to generalize the implementation to handle both (e.g., by using a functor).

dvanhorn commented 9 years ago

Moved to plum-umd/inc-interp#1.