Laziness as a Special Case of Semilattice Updating

General
1

One thing I’ve been trying to wrap my head around recently is the idea, popularized in Purely Functional Data Structures, that laziness in languages like Haskell enables algorithmic improvements in the performance of persistent data structures.

The argument goes like this. When you design a data structure, you might not be able to get certain operations to be constant time, but you can get them to be amortized constant time, which means that if you perform them n times, then you only do O(n) work, even if individual operations might cost more than O(1). However, in the context of persistent data structures (data structures which never mutate), this goes out the window. This is because you can find the one operation at one specific state that costs more than O(1), and perform that operation at that state over and over! So amortized constant time requires mutability. However, there is a very sneaky form of mutability that is acceptable “purely”: laziness!

The way that laziness is implemented under the hood is that a lazy value of type a is actually something like Ref[Either[() => a, a]]. That is, it is a pointer to either a function that returns a, or an actual a. When you attempt to read the lazy value, if it is Left(f), then it returns x = f() and sets its value to Right(x). If it is Right(x), then it just returns x. So secretly Haskell is all built on mutation under the hood!

Using laziness, we can fix our amortized persistent data structures issue. Specifically, expensive computations go in lazy values, so that they only get evaluated once. But because laziness is ephemeral to the user, we still get to pretend like we are just using pure data structures.

My thought about this was… are there other types of mutation that could be totally benign? Why is this mutation specifically acceptable? Well, one reason is idempotence. Reading a lazy value twice doesn’t change anything. Another reason is concurrency-obliviousness. If we have multiple readers of a value, it doesn’t matter what order they read it in (except perhaps for performance reasons… also note that while f is computing you have to somehow “lock” other reads so that they don’t also compute f…).

A possible generalization of this that has the same properties is semilattice updating. Specifically, suppose that A is a type with a join-semilattice structure, so A is a cocomplete poset. Then if we have a mutable reference r of type A, the operation

r := r \vee x

is idempotent, and the ordering of the operations r := r \vee x, r := r \vee y doesn’t matter. We call this operation “semilattice updating”.

We can think of a lazy value as having two states: “uncomputed” and “computed”, and uncomputed < computed.

Anyways, my question is: are there “semi-persistent” data structures, whose only form of mutation is semilattice updating? One example that immediately comes to mind is an e-graph. An e-graph stores a partial, congruent, equivalence relation on a set of terms in some formal language. Partial equivalence relations are like equivalence relations but without reflexivity, and an equivalence relation on terms is congruent if f(t_1, \ldots, t_n) \sim f(t_1', \ldots, t_n') whenever t_1 \sim t_1', \ldots, t_1 \sim t_n'. If we have a presentation of an algebraic structure (as given by an algebraic theory) by generators and relations, then we might have an e-graph which only stores some of the derived equations that come from the equations in the theory and the relations in the presentation. Adding more derived equations to the e-graph, however we do it, is an instance of semilattice updating, if we consider the join-semilattice of partial equivalence relations.

E-graphs are data structures which heavily use mutation, but we can see from this that the result is very “benign”.

One might imagine a programming paradigm based totally on semilattice updating, in the same way Haskell is based on laziness, and that would be… propagation networks. I won’t get into the details of that today though.

2

The really important question: is it “lazyness” or “laziness”? I think it’s “laziness”.

1 Like
3

It seems like the version of me that wrote the post agrees with you, while the version that wrote the title does not!

1 Like
4

Another important aspect of laziness is that you can’t tell whether someone else has read the value. There is no way to extract the (() => a)-typed value.

This doesn’t seem to hold of semilattice updating. If I run r := r \vee x in one part of the code and examine the results, and r := r \vee y in another part, then the order that I performed them in does matter.

I think you recover something like this property with the e-graph example, because IIUC you’re only adding redundant information for performance reasons. There isn’t actually anything changing about the observable properties of the object.

5

That’s a good point. Maybe you should only be able to read certain properties once they have “finalized”, i.e. gotten to a certain stage in the semilattice. I guess maybe the more appropriate word for this all is memoization.

6

This is an interesting idea. One way to think about the appearance of semilattices here is as commutative idempotent monoids; more generally, we can imagine having a monoid of operations that we can apply to a particular piece of structured data (in essence, the endomorphisms of that type of data in some appropriate category — eg a Kleisli category). We can then think about what properties this monoid should have in order to ensure that the operations are non-destructive and non-interfering.

This reminds me of graphic monoids; monoids satisfying the equation xyx = xy. In particular, taking y to be the identity e shows that every element is idempotent: xx = xex = xe = x. Every commutative idempotent monoid is graphic, since in that case xyx = xxy = xy. The graphic condition is a weaker version of commutative idempotence which essentially says “Once you’ve done something (x) once to your data, there is no point doing it again no matter what else (y) you do in the meantime”. The graphic property therefore implies that action (right multiplication) is non-destructive.

As for non-interfering, graphic monoids have the same difficulty that Radvendii mentioned. One way to think of this is that we are looking at endomorphisms in a Kleisli category. As a simple case suppose A is some finite alphabet and consider the free idempotent commutative monoid P(A) on it and the writer monad for P(A): a Kleisli enomoprhisms is a morphism of the form X \to X \times P(A) which we can think of as a pair of a read operation r : X \to P(A) and a mutation m : X \to X. Composition of such endomorphisms is given by (m, r) \circ (m', r') = (m \circ m', r \cup (r' \circ m)); therefore, even if m and m' commute (and even though the monad is commutative), the Kleisli composites will not as one will have r \cup (r' \circ m) and the other r' \cup (r \circ m') in the second component. Essentially we are running into a non-commutative semi-direct product of commutative monoids.

1 Like