Pragmatic Category Theory | Part 3: Associativity

Community
1

Hi everyone! :wave:

I’ve finished writing the third part of my Pragmatic Category Theory series (some code examples are in OCaml):

Previous discussion:

P.S. I would’ve edited the previous topic instead of creating a new one but looks like I haven’t touched it for a while, so I can’t edit the title and the body anymore.

9 Likes
2

Who would’ve thought the OOP principle of incapsulation and separating internals from the interface would hunt us here??

Should hunt be haunt?

3

Thanks, @AsimovIV! Fixed :slight_smile:

1 Like
4

It means, based just on this absraction of Semigroup, we’ve built an extensible interface where users just need to configure what they want to be calculated, and they automatically get an ability to query this operation over segments.

I think I found another one. Abstraction*, I suppose.

5

I need to configure my spellchecker better :sweat_smile:

And also add a link to GitHub, so people can fix typos easily on their own!

6

Another use case where associativity matters: merging in VCS such as git. Git doesn’t respect associativity (as most VCS) and it’s the raison d’être of pijul. The theory behind pijul is also grounded on category theory and is modeling branch merging as a pushout (see this blog post where no knowledge of category theory is needed to understand it).

1 Like
7

Ooh, I love Pijul! I’m more familiar with Darcs but looks like Pijul solves the exponential merging problem nicely.

I know that this theory of patches heavily relies on commutavity. One practical example is how you can change the order of “rename the file” and “edit the file” patches which is quite annoying to do in git.

I just recently learned about pushouts, but didn’t know Pijul actually uses them! Thanks, I’ll have a look.

8

IIUC, it was the main purpose behind Pijul: having a clean theory of patch and solving the exponential merging problem.

Until the version 0.2 version Pijul was written in OCaml and then they switch to Rust. I remember having ask the main author (a french computer scientist) about this choice, and he’s motivation was:

For the last point (about threads), it was in the pre-multicore era.

We have the same kind of problem with the inheritance diamond problem. Suppose we have two classes B and C that extends a same base class A. Can you inherit from both B and C? The question is analogous to the merging problem.

Basically, IIUC, at the heart of pijul, there is two fundamental operations:

module Pijul : sig
  (* a graggle represents the repository states *)
  type graggle
  type patch

  (* fundamental operation of a VCS *)
  val commit : patch -> graggle -> graggle
  val merge : graggle -> graggle -> graggle
end

The associative property means that we want merge g1 (merge g2 g3) = merge (merge g1 g2) g3).

What I found funny and interresting, it is that the graggle data structures both represents a conflicting state and a clean state (clean state is only a subtype of this type), so a merge always “succeed” (the merge function is total, there is always a pushout) and solving a merging issue also amounts to apply a patch to a conflicting state.

Commutativity arises when two series of patches are independent: a patch p1 only touch the file foo and a patch p2 only touch the file bar, then they commute. The commit function in the above signature is equivalent to function application: a patch is a function that applies to graggle (the morphisms in the category where graggle are objects), and in the previous example we will have p1 (p2 g) = p2 (p1 g), the patches commute.

If I remembered correctly, Pierre-Étienne Meunier spent a lot of time and care to design the implementation details of the graggle data structure (to be efficient and solve the exponential merging problem)

2 Likes