4 ms·

An earlier post (https://raphlinus.github.io/gpu/2020/09/05/stack-monoid.html https://raphlinus.github.io/gpu/2020/09/05/stack-monoid.html) explains it. The ele

An earlier post (https://raphlinus.github.io/gpu/2020/09/05/stack-monoid.html https://raphlinus.github.io/gpu/2020/09/05/stack-monoid.html) explains it. The elements of the monoid are stack operations represented by pairs `(n, vs)`, where `n` is a number of values to pop off the stack and `vs` is a list of values to push on afterwards. So e.g. `(3, [])` is “pop 3 values”, `(1, ['foo', 'bar'])` is “pop 1 value then push 'foo' and 'bar'”, etc. Two elements are composed by combining their pop counts and push lists to reflect what happens to the stack if you apply the operations sequentially, e.g. the previous two examples compose to `(4, ['foo', 'bar'])`. The identity is `(0, [])`.

lmm 5y 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 5y 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.

lmm 5y 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 5y 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.