4 ms·
So this isn't really the stack monoid, this is mutations as a monoid (which is a construction that exists for anything mutable), or the command monoid. The insi
by lmm 6y ago
So this isn't really the stack monoid, this is mutations as a monoid (which is a construction that exists for anything mutable), or the command monoid. The insight is that these mutations have a nice representation as first-class values and you can combine two "stack mutation commands" efficiently.
- Twisol 6y ago> So this isn't really the stack monoid, this is mutations as a monoid (which is a construction that exists for anything mutable) I can see why you'd balk at the name "stack monoid", but the specific commands / actions being modeled (push/pop) are exactly the ones modeling a stack. It's not a purely syntactic construction because a push followed by a pop is evaluated away. The representation as `(pops, pushes)` is the natural conclusion of this line of semantic analysis. > this is mutations as a monoid In general though, yeah, this is the secret sauce. The history of commands on a mutable cell is sufficient to recover the value of the cell at any point in time, and the history of values held by the cell is sufficient to derive a (not necessarily unique) history of commands going between each snapshot. Typically, though, we only remember the "latest" value of the cell, so we lose a lot of information. In a parallel algorithm, multiple "points in time" need to be accessible simultaneously, so you get a lot by moving to a representation where you're not already missing information.