1. 14

  2. 7

    Despite the name, this series is much more about the notion of the “right seminearring”. The series follows one large-scale example of using common structure of right seminearrings and polynomials of them. I’ll provide a really quick introduction to the concept itself below.

    Anyone with arithmetic skills have been introduced to the notion of a “ring” through using (+), (-), and (*) on numbers. Anyone with experience in high school algebra also knows that there’s some incredibly powerful stuff to be done over “sentences” written using numbers and those operators.

    Another way to find Rings is to build them up from below. If you have a notion of concatenation (with appropriate rules) you have a Monoid. Glue two of them together and have them “distribute” and you very quickly end up with a Ring. This notion of distribution is important so I’ll write it in high school arithmetic form:

    (a + b)c == ac + bc  -- distribution of (*) over (+) "on the right"
    c(a + b) == ca + cb  -- distribution of (*) over (+) "on the left"

    Now if you take your two monoids to be (+) and (*) you end up exactly with the high school algebra Rings you know and love. What’s interesting is that you get similar kind of structure by taking one monoid to be “and then” and the other to be “alongside”.

    process1 "and then" process2 "and then" process 3
    process1 "alongside" process2

    In particular, we might want to glue these two monoids together and look for distribution. For many ideas about what “and then” and “alongside” mean, you’ll end up realizing that you cannot get both of those distributivity laws I stated above—instead you must pick one. Let’s choose “on the right” arbitrarily

    (p1 "alongside" p2) "and then" p3 == (p1 "and then" p3) "alongside" (p2 "and then" p3)

    If you read that sentence it basically states that we can distribute p3 into our parallel processes by performing it in each thread.

    And this is exactly the notion of a seminearring—two monoids glued together where distributivity only partially holds. It’s really useful because it forms structure identical to that of many of the parser combinator libraries. It also, as shown in these articles, provides a structure which lets us quickly enumerate sequences of strings following a complex set of rules. This might also look identical to the differences between regular expressions, parsers, and the associated regular languages.

    All of them are seminearrings (basically).

    1. 3

      (Seminearrings impose an ordering on your regular language while semirings wouldn’t. Finally, you really want semirring closure in order to get the full power of regular languages—this is the Kleene star operator. Take a look at http://www.cl.cam.ac.uk/~sd601/papers/semirings.pdf for many more details.)