Add immutable funsors Dict, Set and use them for funsor data

[fritzo]

Alternative to #526

The problem

Funsors currently store data in immutable structures that are typically either nested tuples or frozensets, e.g. Subs converts its dict argument to a nested tuple-of-tuples representing key,value pairs. These internal data structures complicate funsor traversal algorithms (e.g. reinterpret, ast(), get_children()), since the intermediate non-Funsor data structures lack metadata such as .inputs, .output, .fresh, .bound. This complication manifests as extra checks for isinstance(-, Funsor) and extra handling to manually traverse funsor data asts.

Proposed solution

This issue proposes to replace all internal data structure of funsors by additional low-level Pythonic funsors Tuple, Dict, and Set. Like other more mathy funsors, these data structural funsors implement metadata like .inputs, .output, substitution via .__call__() and reinterpreted construction and hash consing via type(-).__call__().

For example Subs.subs : Dict, Delta.terms : Dict, etc.

Remaining questions

1. Should we also implement Funsor subclasses for constants Str as used as keys? Ideally all terms would be immutable and hash-consed, however strs are used so ubiquitously as keys that it may not be worth the performance overhead. One option would be to instead rely on Python's built-in hash-consing of strings via sys.intern() and move metadata elsewhere, as in #526

Tasks

• [ ] Implement an immutable Dict funsor
• [ ] Implement an immutable Set funsor
• [ ] Use Dict and Set internally in other Funsors
• [ ] Simplify funsor.interpreter

[ordabayevy]

@fritzo is this still relevant? I would like to try to implement Dict and Set funsors.

[fritzo]

I'm unsure whether this is still relevant, and I'd be fine closing this. I haven't minded the singledispatch solutions to special casing. I'm also concerned that being more abstract will lead to higher overhead.

@eb8680 WDYT?