Lattices, and by extension semilattices, are one of my favourite algebraic structures in the context of programming. Their applications are innumerable, from access control, to distributed systems, to constraining the information flow of privileged information.
For example, CvRDTs (a class of conflict-free replicated data types), are made up of the semilattices over a monotonic operation. If you can prove a few basic properties about your data + the merge operation over it, you can construct a CRDT. It won't necessarily be efficient, but it's a good starting point for reasoning about the problem.
People spend a lot of time trying to sell abstract algebra using monads, but in my opinion it's a lot easier to grasp the applications of lattices.
Similarly, the most general form of rational decision theory or rational choice theory is based on lattices. That makes intuitive sense, since preference relations ~are~ partially ordered sets.
Then, analyzing rational (vs. for example boundedly rational choice behavior) is equivalent to analyzing lattice optimization problems (monotonicity).
Then, parameterizing the choice situation and / or introducing strategic dependecies between actors leads to analyzing sub/supermodular correspondences on these sets. In fact, the most general version would make use of quasi-supermodularity. I think Milgrom&Roberts 94 show that this is the most general way, one can think of coherent (rational) decision theory.
yes of course, but even then we are left to describe such intransitivities in a useful manner rather than conclude the actors is simply non-rational.
If it were so, then human behavior would be impossible to analyze. Instead, if we focus on causes and consequences of non transitive preferences - like in behavioral economics - we may regain the ability to do analyzes.
Lattices are also ordered (by intellectual descent) with respect to early explorations in philosophy, such as using transitivity on "Socrates is a man" and "All men are mortal".
Without lattices, we would never have had the ambiguous phrase "computer scientists commonly choose models which have bottoms, but prefer them topless" occurring in a serious textbook.
Edit: agreed, intellectual descent is only partially ordered, but the interval between aristotle's example syllogism and lattices contains a chain. Guess I should've said "also comparable (by."
Not the parent and this might be different from what they meant, but this reminded me of Lindsey Kuper's PhD work on something called LVars (lattice variables): "We present LVars, a new model for deterministic-by-construction parallel programming that generalizes existing single-assignment models to allow multiple assignments that are monotonically increasing with respect to a user-specified lattice. LVars ensure determinism by allowing only monotonic writes and “threshold” reads that block until a lower bound is reached." (from https://users.soe.ucsc.edu/~lkuper/papers/lvars-fhpc13.pdf ); "The LVars model allows communication through shared monotonic datastructures to which information can only be added, never removed, and for which the order in which information is added is not observable." (from https://users.soe.ucsc.edu/~lkuper/papers/effectzoo-pldi14.p... ); more at https://users.soe.ucsc.edu/~lkuper/
LVars are one of my favorite concepts, and they have roots in Vijay Saraswat's thesis on concurrent constraint programming, which is parametric over a choice of lattice. I second the recommendation for the LVars series of papers, and I also highly recommend digging up a copy of Saraswat's thesis work, which was published as a book. https://mitpress.mit.edu/books/concurrent-constraint-program...
The semantics of determinate CCP programs (and by extension, LVars programs) can be described really beautifully in terms of closure operators on the underlying domain. I'm not sure this made it into the initial published thesis, but this is an accessible paper on the topic: http://www.lix.polytechnique.fr/comete/stages/references/ccp...
A lattice has a least upper bound and greatest lower bound. A semilattice only has one of these two.
A monotonic operation is one that’s either non-decreasing or non-increasing. That is, it never reverses direction.
So in the context of conflict-free replicated data types, you can think of something like an append-only database as a basic example. Over time, the database can only grow or stay the same. It can never shrink. This allows you to split the database into pieces and distribute them. You always know they can be merged back together because they’re append-only. This makes it a join semilattice with the union of corresponding tables being the least upper bound operation.
For example, CvRDTs (a class of conflict-free replicated data types), are made up of the semilattices over a monotonic operation. If you can prove a few basic properties about your data + the merge operation over it, you can construct a CRDT. It won't necessarily be efficient, but it's a good starting point for reasoning about the problem.
People spend a lot of time trying to sell abstract algebra using monads, but in my opinion it's a lot easier to grasp the applications of lattices.