5 ms·
Stacks are used in parsing algorithms. In order to create a parallelized parsing algorithm the author has found this monoid representing stacks and stack operat
by Jtsummers 6y ago
Stacks are used in parsing algorithms. In order to create a parallelized parsing algorithm the author has found this monoid representing stacks and stack operations (specifically push and pop). If this pans out, the result is a potential tool in running parsing algorithms in parallel (specifically on GPUs in their desired use-case).
Edit: fixed some autoincorrects
- mdifrgechd 6y agoThank you. So am I correct that he had created a type (for lack of a better term) representing a number of pushes and pops. And the monoid is the algebraic construct that let's us combine those types. So faced with a string of square braces representing pushes and pops like in the example, we can divide them into chunks, count push and pops (also recording indices?) in parallel, and then combine them?
- raphlinus 6y agoYes, that's basically it. There are more details, like how I think this can efficiently be implemented on GPU hardware (it's not clear at all that this is the case), but you and GP have captured the basic motivation and idea.