What is Pbind composition (Pchain) from a Computer Science (theory) perspective?

1

Let’s ignore for the moment the fact that Pbinds are ordered, i.e. let’s assume that they are records (Dictionary in SC). What does ‘<>’ (i.e. Pchain) actually do to Pbinds in Computer Science terms?

My first thought was that it is partial function composition, but that’s not at all the case. (To see why not, simply consider the simple case where all field values are numbers; then all record fields have type from string (key) to number, so there can be no function composition going on here, because it clearly would not type check.)

So ather dusting off some computer science papers, I think the correct answer is that (at this level of abstraction, i.e. Pbind approximated as a record), what <> does to record is what Bracha and Lindstrom call record override.

In their notation, which I’m simplifying by dropping a subscript r1 <- r2

produces a result that has all the attributes of r1 and r2. If r1 and r2 have names in common, the result takes its values for the common names from r2

Except Pchain works in the opposite sense, i.e. p1 <> p2 it is the values from p1 that override those of p2.

The “record override” terminology is a slightly unfortunate. The actually define a notion of record merging in the same paper (a few lines before “override”), but with the caveat that there must not be any key/name conflicts. Of course, the “override” is really just a merge in a more general sense, but for records you have potentially many ways how to solve conflicts. The “override” just unformely prefers keys from one record in case of conflicts.

The notion of record override doesn’t translate into anything useful for total functions, (you’d be just replacing the whole “destination” function with the “source”), but interestingly it’s non-trivial for partial functions (which records can also be though of as being), because you can override just what isn’t defined, e.g. take the constant 5 as a function; you can use it to override the undefined/nil values of the (partial) function 1/x (in the math sense, forget about how SC implements it with inf) with the meaning that the function (in Bracha’s notation) 5 <- 1/x (or 1/x <overrides> 5 in a pseudo-SC notation) overrides 5 with 1/x everywhere except at x=0. So clearly this is a different notion of “composition” than function composition.

And yet… Pchain is actually generic in SC, i.e. it composes data (i.e. non-event) streams roughly like function composition works. The “overriding business” happens entirely in Pbind because it isn’t simply a record, but rather a function from records to records, or more precisely it is a partially applied function that stores a record and uses it to record-override its argument (the protoEvent).

Thoughts/comments?

1 Like
2

IMO it is function composition.

In math, given functions f and g, their composition f•g is a new function that evaluates g given an input x and passes that result to f.

f = Pbind(...);
g = Pbind(...);
h = f <> g;

f is a function that accepts an event as input, and adds or replaces information in it. (I think a single Pbind implements “record override” by itself – because you can pass a non-empty event into Pbind and the Pbind will add to or overwrite data in the input event. I don’t think their composition is a different sort of record override.)

g is a similar function.

h is, mathematically, their composition: first g operates on the input, then f operates on that result.

Just an opinion.

hjh

3

Yeah, I think you’re correct, the chaining is still function composition, it’s just confusing that the Pbinds are overrides… so composition of overrides.

It’s confusing because records (or Pbinds) can themselves be thought as functions. In the totally trivial case where they would be total overrides Pbind(7) would be the constant function that returns the number 7 for all inputs, i.e. f(x) = 7. So a composition like Pbind(7) <> Pbind(5) would override the input twice (first with 5, then with 7), with the result being always 7.

But Pbinds are really just partial overrides. They don’t change some of the inputs! Any keys not specified in the Pbind (some RHS Pbind value-hacks aside) are left untouched. So, a non-trivial equivalent example needs partial override functions like

f = {|x| if (x < 0) {5} {x} }
g = {|x| if (x < 2) {7} {x} }

(-3..3) collect: (g <> f).(_)
// -> [ 5, 5, 5, 7, 7, 2, 3 ]

Since the Pbind inputs (Events) are “multi-dimensional”, that’s more properly illustrated with a 2-arg function, but the above was insightful already for me.