Troll: Normalization and Optimization

[ChrisEPhifer]

During the short group discussion today our group had the following thoughts / questions regarding Troll and its implementation:

• The paper could have done a better job of motivating / justifying the abstract non-normalized representation of data. More concretely, why choose to only have singleton multisets and represent larger collections using unions explicitly? Were there optimization trade-offs to not using, for example, lists hidden behind an abstract type?
• Are the finite maps representing the values in Troll what is meant by "multiset" in the context of the abstract syntax and normalization? That is, are the multisets themselves the association lists, or are the association lists produced as an intermediate step in the interpreter?
• The optimizations being presented as lists of equations without much other context was unhelpful; it would have been nice to have some informal discussion in the paper about where those equations came from (even if it meant paraphrasing a referenced source.)

[msoturn]

Regarding your first point about singleton multisets, I think the linearity of the probability calculations depends on the independent nature of the individual dice rolls/actions.

From the top of the right column on p. 1913:

Even so, enumerating O(n^9) multisets to find the distribution for sum nd10 requires a lot of time and space. Fortunately, we can do better by the following observation: Since sum( A U B ) = sum(A) + sum(B), we can find the distribution for sum nd10 by first finding the distributions for sum( n - 1 ) d10 and sum d10 and combine these into a distribution for sum nd10. If we apply this recursively, we never need to store a distribution with more than O(n) values, since there are only O(n) possible outcomes for sum md10 where m<n.

Basically, I take it to mean, 'because dice rolls are independent, we can just store the individual probabilities of each die-roll and have linear probability calculation/sampling, without having to somehow search the much larger event tree of the combined multi-dice roll' (in this case, the size is O(n) with a c of 10, the possible outcomes of each d10 in the calculation)

[ChrisEPhifer]

Yeah, that actually makes a lot of sense. I still wonder if there's a performance benefit to not considering larger collections, but the relevant probabilistic justifications are great to have, too.

Thanks!