4 ms·
> The only difference in this paper is that Lamport insists that programs should be syntactically represented as state machines Just to make sure: He does not
by pron 10y ago
> The only difference in this paper is that Lamport insists that programs should be syntactically represented as state machines
Just to make sure: He does not intend for compilable programs to be represented as TLA formulas, just as electrical circuits are not laid out with ODEs. He says that reasoning about the properties of programs should be done in a system like TLA, just as electrical circuits can be modeled as ODEs. TLA+ itself comes with a tool that lets you write specification in a syntax called PlusCal, which is similar to familiar imperative languages, and Lamport himself says that he made that language because that syntax may be more convenient for some tasks.
> while most PLT people would insist that this is too much of a restriction.
Reasoning syntactically about a program in its ready-for-construction source has several advantages, but I doubt anyone would view TLA as any sort of a restriction (quite the opposite: it allows to specify discrete dynamical systems that are not even computable). But the main difference for practitioners is this: TLA works today for a wide range of programs. The ideal of reasoning about programs in their source language with similar cost is far from realized. TLA succeeds in practice simply because it is far less ambitious.
> Typed programs enable more abstract programs and specifications, because the abstraction mechanism offered by types is in some sense dual to refinement.
I am not sure what you mean.
> Combined with higher-order functions (i.e., first class functional abstraction), this allows you to achieve more abstract specifications than what can be done with state machines.
I am not sure you quite realize how state machines are used in TLA. You can use higher-order functions to your heart's content, as well as higher-order state machines. The machine's are abstract, and what constitutes a state is completely up to you. TLA+ is rich enough that you can write an entire program completely using pure functions, that executes as a single TLA step.
But reasoning with functions is a specific level of abstraction. TLA allows you to go arbitrarily higher or lower. Functions are too high an abstraction if you're interested to reason about, say, complexity, and they're too low an abstraction if you want to reason about interaction (where they can only constitute single monadic steps). They may be either too high or too low for concurrency. Of course, you can embed TLA in FP and vice versa, but TLA is "naturally" broader in scope.
> You cannot really hide internal states
Why not? That's what existential temporal quantification is for. `∃∃ x : F`, means that F performs its observable operation using some internal hidden state, x (∃∃ is usually written as bold ∃)
> In a typed programming language, quantification gives you the dual abstraction of restricting the users of your program.
I'm not sure exactly what you mean. You can achieve the same thing you can with types in an untyped TLA-based language like TLA+. For example, the typing judgment `f:A->B` is simply a conjunction with the proposition `f ∈ [A → B]` in TLA+. Remember that the environment is also part of the process (or machine).
> Crucially this invariant does not have to be a (bi)simulation
The concept of bisimulation is a rather complex one designed to explain the difference between trace inclusion and stronger forms of equivalence in algebraic models that do not model state explicitly (like CSP/CCS). In TLA, bisimulation and trace equivalence are the same, and simulation is just trace-inclusion. The famous result "the existence of refinement mapping" by Abadi and Lamport shows that this is complete, namely that any implementation relation "A implements B" can be modeled as "A refines B", which in TLA translates to the familiar implication operator `A ⇒ B`. So there is no such thing as two machines, one implementing the other, that cannot be expressed in this way.
> In this generality, this is only sound for typesafe clients
Again, in TLA, a "typesafe client" is no more than an assumption about the properties of the client "process". In TLA, a specification often takes the form `◻User ∧ ◻Program` or the equivalent `◻(User ∨ Program)`
> That's what makes it valuable.
I would say that in practice the opposite holds. TLA+ is used by "ordinary" engineers to reason about systems that are far larger and trickier (concurrent, distributed) than anything that is currently done by engineers using equational reasoning in typed PFP. This advantage may (or may not) be short-lived, but I think the combination of simplicity, ease of learning, and scalability both in size and in scope is precisely TLA's pragmatic edge.
- mrefj 10y ago> But reasoning with functions is a specific level of abstraction. Excellent point. The level of abstraction is a fundamental concern, not just in modeling but also in reasoning about systems. And state machines (as used in TLA or otherwise) add temporal abstractions to the mix of abstraction mechanism. To add to its power, it does not lead to any loss of generality; since any program in a language with well-defined operational semantics can be modeled using state machine (transition systems with infinite state space to be little more precise). > In TLA, bisimulation and trace equivalence are the same, and simulation is just trace-inclusion. There is a fundamental difference between (bi)simulation and trace inclusion(equivalence); the former is a branching time notion and the later is a linear time notion. In fact if one it is easy to show if A is a simulation of B then A is also a "trace inclusion" of B. And this difference has some practical ramifications as well. The branching time notions of refinement also has (not so famous) the completeness result. http://www.ccs.neu.edu/home/pete/pub/charme-refinement-branching-time.pdf http://www.ccs.neu.edu/home/pete/pub/charme-refinement-branc... https://arxiv.org/pdf/1502.02942v1.pdf https://arxiv.org/pdf/1502.02942v1.pdf This has some practical ramification as well: the refinement map in Abadi/Lamport is a projection function, while in branching time it can be arbitrary function. The former is intuitively clear but often difficult in practice. The flexibility has been exploited to efficiently analyze correctness of several non-trivial systems like pipelined processors. > So there is no such thing as two machines, one implementing the other, that cannot be expressed in this way. To drive home the point what the completeness result means is that one can always reason at the level of abstraction that was use to specify the system: state and their successors. This is what we are after in type-based reasoning: reasoning at the level of functional abstraction.
- pron 10y ago> the former is a branching time notion and the later is a linear time notion I think it is more precise to say that you cannot formally encode the concept of (bi)sumlation in LTL while you can in CTL. The notion itself, however, is a general structural relation between state machines that is independent of the temporal logic you use to formalize properties of their behavior, if any. I.e. (bi)simulation would exist even if temporal logic didn't. > the refinement map in Abadi/Lamport is a projection function One of the few things I don't like in TLA+ is that you can create a "refinement" mapping which isn't sound (and therefore isn't a refinement). In particular, you can add auxiliary variables that interfere with the specification. I know Lamport is working on a paper where he gives syntactic rules that ensure that the mapping is sound. > This is what we are after in type-based reasoning: reasoning at the level of functional abstraction. The challenge is making that reasoning rich enough (to reason about a wide class of programs), scalable enough, and at the same time affordable and simple for engineers. This goal is far from realized (and currently falls short, at least in the last two requirements). P.S I also think that TLA allows reasoning about structural properties of the state machine without any use of temporal logic at all. If A and B are action formulas and S is a state-predicate, then `S ∧ A` denotes the set of transitions from the set of states denoted by S (conversely `S' ∧ A` is the set of transitions into S). And so `S ∧ A ⇒ S ∧ B` means "for every transition A leaving S, there is a transition B leaving S". I think that you can therefore show (bi)simulation directly, structurally, rather than behaviorally; there is no use of behaviors (traces) or computation trees here at all (you may want to show that all the states S are reachable from the initial states). [1]: Unless behaviors are sequences of states, in which case the relationship coincides with the trace-equivalence relationship. There may be subtle technical differences (that I don't quite understand) even then, but they don't matter.