The seven specification ur-languages • Buttondown

2023-05-09 09:11:11

Final week Madhadron’s 2021 piece The seven programming ur-languages went viral. One I noticed loads was “the place does TLA+ and Alloy match into this?”

Hoo boy.

I’ve been dreading this one. You see, TLA+ and Alloy don’t match into any of the programming ur-languages, as a result of they aren’t programming languages. They’re specification languages (SLs) and are designed for modeling methods, not implementing them. Whereas there’s plenty of intermixing, SLs come from a unique lineage than PLs and we have to deal with them individually.

So, somebody has to jot down “the seven specification ur-languages”, and I actually don’t need to be that particular person for 3 causes:

Taxonomy is a idiot’s errand. All taxonomies are damaged, full cease. Your classes are gonna be fully mistaken and all people’s going to argue over each single factor. There isn’t any such factor as a fish.
I’m not remotely certified to do that. Positive I’ve toyed with a number of completely different formal specification languages earlier than, however I’ve solely been paid to do two of them.^{Ideally I’d need to be competent in 5 – 6 and in addition seek the advice of a number of consultants earlier than making an attempt to categorizing issues.}
Nothing is simple. No less than with programming languages you’ve received a bunch of on-line docs and “hiya world”s for comparisons. The whole lot within the formal strategies world is squirreled away in papers and 60 greenback books.

OTOH, a first-draft taxonomy is best than no taxonomy, it’s a subject I’m considering, and I’ve rabbit-holed a lot dumber issues earlier than. Some caveats earlier than we begin:

The title simply mimics madhadron’s piece. It’s extra correct to name it the seven ur-formalisms, as we’re speaking concerning the mathematical ideas individuals used to mannequin methods. Most end-state specification languages use a number of of those concepts together. Additionally it’s not a lot “ur-” as “archetype”.
That is nearly specification languages, not formal verification. So no Agda, Idris, Lean, or SPARK. That roundup can come another time.
I spent a day on analysis and writeup. That actually isn’t sufficient time to both analysis or clarify issues nicely, however I’ve plenty of different stuff I would like to do that week.
I don’t know how this ended up longer than the unique piece.

The Seven Specification Ur-Languages

1. Guarded Command Language

Invented by Edsger Dijkstra in 1975, that is principally a method of including nondeterminism to pseudocode.

if
  :: x < y -> x := y
  :: y < z -> y := z
fi

If solely one of many guard clauses is true, then it’s a regular if assertion. If a couple of is true, one command is chosen nondeterministically. Both x := y or y := z will occur, however not each. A number of instructions can have the identical guard, which might result in a random choice.

Dijkstra used this to summary implementation particulars from algorithms. Right here’s how he defines “Euclid’s Algorithm”, which finds the best widespread denominator of X and Y:

// Euclid's algorithm
x := X, y := Y
do 
 :: x > y -> x := x - y
 :: y > x -> y := y - x
od

He then confirmed that how this might refine to a number of completely different variations of the code.

I don’t suppose GCL is utilized by itself a lot as a result of the commonest purpose of specification is modeling a concurrent system, and whereas you are able to do that with purely nondeterminism primitives, you additionally need to some concurrency primitives too. However SLs nonetheless use GCL as a part of their semantics, the preferred of which is Promela/SPIN.^{PRISM additionally makes use of GCL for probabilistic modeling: every guard is related to a set of weighted instructions, letting you compute the chance of reaching any given state.}

2. Relational Algebra

In math the fundamental assortment sort is the set, collections of unordered distinctive parts. From units, we construct “capabilities”, a mapping between two units the place every enter maps to precisely one output. If we generalize capabilities, we get relations, which map every enter to any variety of outputs.^{A relational algebra, then, is a group of guidelines and operations for manipulating relations, like “lookup”.}

Essentially the most well-known relational algebra by far is Codd’s relational mannequin of databases. However it’s additionally actually prevalent in formal specification as a result of it permits very properly for manipulations with constraints. For instance, take the construction:

Every theatre seat could also be offered to at most one buyer

Mates are clients

If the present is a premier, all offered seats have to be buddies of the theatre

Right here’s how we are able to signify that every one relationally:

schema BoxOffice {
  varieties {Standing, Buyer, Seat}
  vals {
    standing: Standing
    buddies: set of Buyer
    seating: Seat -> Possibly Buyer
  }
  properties {
    standing = "premier" => vary(Seat) subset buddies
  }
}

The method represents statics elegantly however struggles a bit of with modeling change. Now we have to do one thing difficult: first acknowledge that BoxOffice itself is a kind with its personal relations, after which outline a “change” as a relationship between two BoxOffices.

schema System {
  states: set of BoxOffice
  init: BoxOffice
  buy: BoxOffice -> BoxOffice
}
properties {
  forall b -> b': buy {
    some seat: Seating, c: Buyer {
      no b.seating.seat
      b'.seating = b.seating ++ (seat -> c)

      // do not change the rest
      b'.standing = b.standing // and many others and many others and many others
    }
  }
}

This instance was tailored from Using Z (pg. 179). Z (pronounced Zed) was the primary relational specification language, and arguably the primary SL to see “important” use by different individuals. No person makes use of Z anymore for a lot the identical causes we don’t use COBOL and ALGOL: we discovered classes and made higher languages.

The relational mannequin is nice for construction however actually advantages from some additional change semantics. One descendant, B (not pronounced Mattress however ought to be), provides state machine semantics. That is later refined with Occasion-B, which we’ll speak about later. One other descendant, Alloy, used to hew nearer to the pure relational mannequin however lately added temporal logic. There was a lot rejoicing.

Talking of temporal logic:

3. Temporal Logic

You realize the standard instance of a deductive proof?

All males are mortal

Socrates is a person

Due to this fact, Socrates is mortal.

This solely lets us work with certainties. Philosophers additionally like to control uncertainties:

AS FAR AS WE KNOW, all males are mortal

WE ARE SURE Socrates is a person

Due to this fact, Socrates is— AS FAR AS WE KNOW— mortal.

That provides us modal logic, common logic augmented with “positively” (□) and “probably” (◇). There are completely different interpretations of what “positively” and “probably” are literally about, resulting in completely different modal logics. Certainly one of these interpretations is that “positively” means “on a regular basis” and “probably” means “among the time”. This offers us some taste of temporal logic.

In 1977, Amir Pneuli invented linear temporal logic (LTL) and utilized it to formal specification. Temporal logics rapidly get widespread as a result of they’re very good at specifying system properties. Right here’s the way to say “all seats are finally offered:

offered(seat) = some c: Buyer:
  (seat -> c) in seating

property  ◇offered(s)

And right here’s the way to say 1) “finally we’re offered out” and a couple of) “all seats are finally offered and keep offered”:

property  offered(s)) 
property  ◇□offered(s)

Due to this flexibility, you usually see SLs use one notation for his or her system modeling language after which use some sort of temporal logic for expressing the properties of the system. SPIN and PRISM each do that: they use GCL for expressing the system after which LTL for expressing the properties of the system.

Different SLs use temporal logic for each modeling and properties. TLA+ is probably the most well-known occasion right here. However individuals additionally write total methods in LTL (or a sister temporal logic, like Computation Tree Logic).

4. Course of Calculi

(The whole lot previous this level is far shakier floor and why it is a publication and never a weblog publish, regardless of being 2500+ phrases.)

Course of calculi are a household of approaches to modeling concurrency as a group of unbiased, interacting “processes”. Course of right here doesn’t imply an OS course of, however any sort of computational entity with native state. The purpose of the calculus is to provide you with guidelines for the way the processes share data, in order that we are able to infer properties concerning the world system, comparable to if it will probably impasse or not.

mtype = {okay, already_sold, err};

chan purchase = [1] of {Seat};
chan resp = [1] of {mtype};

lively proctype Buyer()
{
  begin:
    Seat selection; // arbitrary seat
    purchase!selection; // write `selection` to `purchase` channel

    do
      :: resp?okay -> break; // learn okay from `resp` channel
      :: resp?already_sold -> goto begin;  // and many others and many others
      :: resp?error -> break;
    od
}

(Discover that we don’t have to outline the server in the identical place, so long as we are able to outline the channels that it makes use of. This arguably makes processes extra composable than uncooked temporal logic or relational fashions.)

Course of calculi are particularly fascinating as a result of, in contrast to prior mentioned strategies, they’re additionally utilized by programming languages! Most famously Tony Hoare’s Communicating Sequential Processes (CSP) impressed Go channels, whereas the Actor Mannequin is utilized in Erlang and Pony. Even when you aren’t utilizing one thing with native processes you possibly can usually discover a framework like Akka which implements a calculus on the library-level.

There’s additionally a protracted historical past of utilizing course of calculi for summary modeling. FDR4 immediately checks CSP specs and P relies on the actor mannequin. SPIN and mCRL2 have their very own homegrown calculi.

5. State machines

A state machine is a peculiar sort of system. System adjustments are organized into “transitions” between states, which have circumstances and results. If a number of transitions can be found, the system can select which one to take.

state On-line {
  on Powerbutton(tender?) {
    if tender? {
      save_everything();
    }
    goto Offline;
  }
}

State Offline {
  on Powerbutton(_) {
    goto On-line;
  }
}

Now this appears an entire lot like guarded command language, and you’ll implement a state machine purely with GCL. The distinction is extra concerning the position in modeling. In languages with GCLs, the guarded instructions outline native nondeterministic procedures, like “add one or decrement one.” In languages with state machines, the state machine decides the general construction of the system.

State machines are the closest factor FM’s received to a paradigm, and it’s arguably the paradigm. There’s a joke in formal strategies that it doesn’t matter what language you begin with, you’re going to finish up with a state machine. They simply work so nicely for modeling complicated methods, they usually implement nicely, too.

Languages with native state machine syntax embody Event-B (pg 12), NuSMV, and P. Different SLs won’t have syntax however you’ll handroll state machines anyway. There are additionally formalized extensions of state machines, like Harel statecharts and Labeled Transition Systems, that add extra options. Statecharts are cool, test em out.

6. Petri nets

That is arguably simply one other extension of state machines, however it developed individually and is used individually and is value discussing individually.

The circles are “locations” and the bars are “transitions”. A transition is “dwell” if each inbound circle has a dot in it. When a dwell transition “fires”, take away a token from each inbound circle and place a token in each outbound circle. If a number of transitions are dwell, any of them can fireplace. It’s a bit of extra complicated than that however not a lot extra complicated. To my understanding individuals in course of and chemical engineering used Petri nets earlier than they migrated over to CS.

Petri nets can’t mannequin very a lot. You’ll be able to add two numbers or compute their minimal however not multiply two numbers or compute their most. In different phrases, they’re not Turing full. Which means that sure properties are decidable! You’ll be able to algorithmically decide if a internet has a token bound or not and in principle even decide if a selected configuration is reachable.

The issue is that modeling something with nets is a large chore, and any addition that makes it much less of a chore is exceedingly likely to make it Turing complete. Nonetheless, there are some widespread extensions, probably the most notable of that are “coloured petri nets” the place locations can maintain values moreover “variety of tokens”. The primary instrument for that CPN Tools. I imagine Statebox can also be making an attempt to make use of Petri nets as a proper modeling instrument.

I actually like Petri nets. They aren’t very helpful for modeling, however they’re a enjoyable puzzle. How do you mannequin $BASIC_SYSTEM with simply petri nets? How do you make the graph look good? I like this book on them.

7. Diagram-first

The whole lot mentioned thus far was primarily based on mathematical constructs became modeling notations. The vast majority of specification languages had been invented elsewhere and used as considering and communication aides. Virtually universally these are diagrammatic notations, and any formal semantics comes later. The first flow chart shares little or no in widespread with the notations individuals converged on 20 years later.

Which brings us to the preferred formal specification language: UML. Extra individuals have drawn sequence diagrams than have used all the different strategies, mixed. UML wasn’t a lot its personal language as a compromise between three different diagram notations that attempted to ensure backwards compatibility with all of them. That ones one of many issues that in the end hindered its adoption. SysML is a venture to make one thing just like UML that’s grounded in formal semantics.

Equally, the C4 architecture model is meant as a method of speaking and documented giant scale structure. No person’s making an attempt to formally confirm them but but when it sticks round lengthy sufficient, that very nicely might occur.

Miscellaneous

Issues I omitted:

Dynamic logic, which is a modal logic that’s not precisely a temporal logic. The one dynamic logic SL I do know off the highest of my head is KeyMaeraX.
SLs which are embedded in a programming language and particularly designed to mannequin methods that may finally use that language. Examples: Stateright and Spectacle.
Fault, BPMN, VDM, CADP, LOTOS…
How individuals in {hardware} do formal strategies
No matter they’re doing within the blockchain area, I do know nothing concerning the blockchain area

What to do with this

Like with programming, studying SLs that use completely different mixes of formalisms is a mind-opening expertise that may make you higher at specification. Not like with programming, being higher at specification isn’t that vital. No person’s going round telling folks that state machines are a dead-end and course of calculi are the long run. It’s all this mishmash of various concepts slammed collectively to make one thing good for modeling actual methods. Study whichever specification language your mates and coworkers already know, and when you’re the primary, be taught whichever appears the best to you.

My essential takeaway is that I ought to get round to studying SPIN.

TLA+ Workshop

This upcoming Monday! Use the code C0MPUT3RTHINGS for 15% off.

(After this week I’ve yet another workshop in June after which I can lastly cease pitching this in newsletters. I’m excited to be achieved. I don’t get pleasure from placing these adverts in my publication.)