Based on experimenting with the trade-offs of different representation choices, we see two broad kinds of finite map representations for use with Adapton:
[x] key-value hash tries: get-only finite maps, built from a sequence of key-value associations, in a batch fashion. They do not permit updates, but they permit incrementally-efficient folds over the key-value pairs.
[ ] key-value logs: put/get finite maps, which permit a sequence of both puts and gets, but do not permit incrementally-efficient folds over the latest key-value pair associations, only the log of pairs itself (where a key may appear more than once).
Both of these representations should be "chunky", aka, gauged. In particular, we generally want a ratio of 1000 key-value pairs for each Adapton-based pointer.
Implement finite map representations for IODyn.
Based on experimenting with the trade-offs of different representation choices, we see two broad kinds of finite map representations for use with Adapton:
get
-only finite maps, built from a sequence of key-value associations, in a batch fashion. They do not permit updates, but they permit incrementally-efficientfold
s over the key-value pairs.put
/get
finite maps, which permit a sequence of bothput
s andget
s, but do not permit incrementally-efficientfold
s over the latest key-value pair associations, only the log of pairs itself (where a key may appear more than once).Both of these representations should be "chunky", aka, gauged. In particular, we generally want a ratio of 1000 key-value pairs for each Adapton-based pointer.