The stack monoid revisited
raphlinus.github.io
raphlinus.github.io
> In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element.
So M = (S, op, id)
My go-to example of a monoid is (the set of strings, string concatenation, the empty string). It's my go-to because there's e.g. no `x` such that `concat("blah", x) == ""`. Another example is (integers, +, 0), but it is not my go-to example because it also more than a monoid.
I did not find a clear explanation of what the stack monoid is here. Can someone state it, please?
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.
There's an interesting reason why strings are a good example - when you think of `string` as `List<char>`, that `List` in it actually turns out to be a "free monoid". That is, minimal amount of structure needed to encode monoid operations in such a way that you can interpret them later as needed into something else. And one possible interpretation function is something commonly called `reduce` - you can basically think of `[1,2,3].reduce((x, y) => x + y, 0)` as interpretation of this monoidal structure into monoid of integers with addition.
One way to look at it is as parenthesis balancing: replace a,b with (,) respectively and then the monoid is strings of (,) except any matched pairs () are removed.
Now change ( for lots of different elements you might want, say integers for their place in the string maybe. You get a presentation like < p, x \in X | \forall x \in X xp = e >, that is if you see an element of your data set immediately followed by a p (for pop) you can delete both. This is the stack monoid and elements may be described as p^n s, where s is a list of elements of X and may be read as “the stack operations of popping n times and pushing a,” or “the tree traversal of going up n nodes and then going down the path s.”
My favorite is the monoid of endomorphisms! "Endomorphism" is a fancy word, but it just means "if you give me a `T`, I'll return a `T` like it but with some changes."
Programs that operate on a stack usually look something like this (if we ignore everything that isn't touching the stack):
stack.push('a');
stack.push('b');
stack.pop();
stack.set(stack.get().push('a').push('b').pop());
The thing about operations like `Stack -> Stack` is that you can combine them together without even having a `Stack` handy. You just produce a function that does one, passes its result to the other, and returns the final result. And of course, I could write an identity function that returns the given stack unchanged. That makes `Stack -> Stack` (and really any `T -> T`) a monoid!
In other words, instead of `(stack.push('a')).pop()`, where we morally associate the parentheses to the left, we have something like `stack.(push('a').pop())`, except obviously OOP dot notation doesn't work that way. But that's the intuition -- we're combining the operations before we feed them a stack to operate on.
Ultimately, that's what Raph's stack monoid is based on, except instead of functions `T -> T` they describe `push` and `pop` with data. This is called "defunctionalization", and it basically works because we can write a single function (an interpreter) that performs the cumulative actions described by that data.
As a sibling comment explains, lists are the free monoid for a set of actions (where "free" means "assuming the least necessary"), so we could get by with `[Push 'a', Push 'b', Pop]` as a representation. But this contains more information than we actually need. We know that if a push is followed by a pop, the contents of the push don't matter to us. We can therefore remove any push-then-pop pair of actions. When we simplify in this way, we find that the only sequences of actions we have are N pops followed by M pushes. So Raph's representation coalesces the adjacent pushes and pops into `(Int, [Char])`
A signature like that would simply discard the value of the element on the stack, which makes the data structure write-only and superfluous. The signature should be `Stack -> (Char, Stack)`.
To be more explicit: Raph is modeling a scene graph, and a traversal of the scene graph consists of a series of pushes and pops on a stack, together with operations on nodes that act on a particular state of the stack. To parallelize these operations we need to be able to access the state of the stack at multiple points along the traversal.
Each operation will use `peek` (and likely `pop`, too, but notice that it doesn't affect other operations here; it's more like moving a cursor down the stack) to drive its own behavior, but those read operations are independent of the traversal itself. It is the traversal we are modeling.
If I have a list of numbers `xs`, there are two nice monoids available: (+, 0) and (*, 1). In a JS-like notation, I can reduce using either monoid with `xs.reduce(0, (acc, x) => acc + x)` or `xs.reduce(1, (acc, x) => acc * x)`, respectively.
The existence of `reduce` is actually exactly what makes lists the "free monoid"!
Back to the clipping problem though, in each intermediate step (when we still incorporating prefixed results), do we compute clipping for each elements progressively (the result array in 1st pseudo-code snippet), or do we just compute the clipping boxes (the stack array snapshot in 1st pseudo-code snippet) and then compute the final clipping for each elements in parallel when the clipping boxes (position of each push & their bounding boxes) are ready?
Sorry about my inaccurate terminology in advance as I didn't work closely with 2D graphics before.
So what isn't possible is having two threads push/pop to the same conventional stack. So I assume the author is doing something different.
So what I guess they're doing is descending down the tree, and splitting off all the operations that can be done in parallel so that you get a bunch of kernels feeding their results into each other with the structure of the tree. It seems like some synchronization is need so one thread waits for the results of another. A monoid, as I vaguely understand them, acts as a kind stored operation so this seems logical.
And if you ran out of threads, the monoid would just act as a conventional stack on some of the remaining threads.
Of course, none of this says the mechanism to implement this.
Indeed; what they're doing is building up a command object that represents a sequence of modifications to a stack. And that's something that you can parallelise, map-reduce style: they've come up with a representation for that command that makes it easy to combine two commands into a bigger command, and a technique for doing that combine in-place without needing extra scratch space. This doesn't need any synchronization between parallel threads - of course the final result is only formed when all the threads finish. (To materialize the final value of the stack you'd have to "run" the final command, but it turns out that's trivial for this command representation - just confirm that the number of pops is zero, and then the push sequence is the final value of the stack).
I'm still confused. If one calculates (x+y)*(z+w). You can divide the addition between threads but the multiplication has to happen once these two threads end.
If you're talking a "map-reduce" approach, as far as I understand it, the reduce has to happen once the mapping is done. Which would seem to require synchronization also.
https://github.com/mlang/chessIO/blob/master/src/Game/Chess/...
The goal of piet-gpu is that you just specify the scene graph (blue circle here, red line there, etc) and send it over to the GPU, and the GPU takes care of all the rendering.
GPUs are very good at processing data in the shape of arrays. For example, a pixel shader (or "fragment shader") processes a 2D array of pixels on the screen. piet-gpu needs to sometimes process data that has a tree structure, rather than an array structure, to support clipping (for example to show a shape that represents the intersection between a circle and a square). The stack monoid the article talks about is a way of doing tree-like operations in parallel on the GPU, and the author thinks it will end up being useful for being able to process clipping operations entirely on the GPU.
Quick question: wouldn't executing partially-ordered sets of operations in a semi-parallel or fully-parallel way already be an existing research topic in Computer Science? Obviously this project is attempting to find a solution for a singular application and not attempting to find a general algorithm, but still there must be some historical precedent.
I would imagine that companies like NVIDIA would have even already contributed to this space?
Are there any existing resources on the topic that perhaps you or the OP knows of?
Seems to be some old work based on a parallel memory model that used to be used (PRAM), some stuff from ken iverson's APL book, and some more APL stuff from someone's thesis.
[0] https://raphlinus.github.io/gpu/2021/05/13/stack-monoid-revi...
This is pretty misleading. Most 2D arbitrary paths are rendered on the CPU but there's a lot more to 2D graphics than that and run on the GPU today already just fine.
I'm still reading and I am trying to understand what this will do if you have long streaks of pushes with rare pops (but maybe still occasional enough to cause large shuffles in the in-place reduction). What do you do after the stack size is larger than the number of parallel thread?
The case where the stack depth is greater than the partition size is tricky for sure, and this is what I call the "backlink" mechanism. The tl;dr is that it follows the deepest link (furthest from top of stack) that it can, and continues the look-back process, until the slice is complete. You can search for "backlink" in the code - it's actually not a huge amount of logic, though it certainly was subtle to get right.
() moderately likely
(X) where X ~ (roughly) D quite likely
X Y where X,Y ~ (roughly) D slightly likely.