Earlier quoted context omitted.
Outside of distributed systems what is it used for? I've only ever heard of it's use in the formalization of distributed systems.
Indeed, TLA+ is mostly known for formalizing and verifying distributed systems and concurrent algorithms. This has a few reasons: 1. Lamport's algorithmic work is in concurrent and distributed algorithms, and as he uses TLA for his own algorithms -- and he's TLA+'s first user -- that's how it's known. 2. Few other general software verification formalisms are able to handle concurrency as easily as TLA, so that is whe…
Leslie Lamport: Video course on TLA+
51–60 of 78 posts
Re: Leslie Lamport: Video course on TLA+
#52Earlier quoted context omitted.
I have a passing familiarity with proof assistants such as Cow and HOL. How would you compare TLA+ with those? https://en.m.wikipedia.org/wiki/Coq https://en.m.wikipedia.org/wiki/HOL_(proof_assistant)
This is a complicated question. I am currently writing a blog post series on the theory of TLA+ that I will publish in May that, among other things, touches precisely on this point. But I will try to quickly point out some areas of difference, but the most important thing to remember is that both Coq and TLA+ -- as far as specifying and verifying software is concerned (not general math) -- are universal formalisms. U…
Re: Leslie Lamport: Video course on TLA+
#53Earlier quoted context omitted.
This is a complicated question. I am currently writing a blog post series on the theory of TLA+ that I will publish in May that, among other things, touches precisely on this point. But I will try to quickly point out some areas of difference, but the most important thing to remember is that both Coq and TLA+ -- as far as specifying and verifying software is concerned (not general math) -- are universal formalisms. U…
AFAIK, TLAPS does not support temporal reasoning in full currently, so you are not able to prove liveness properties of your system. On the other hand, Coq is able to express both LTL logic and infinite trace, so you can prove such things in it.
THEOREM ASSUME NEW F, NEW G,
F ⤳ G, F
PROVE ◇G
PROOF BY PTL
and it works fine (PTL stands for propositional temporal logic). I suppose there are some things that aren't supported (TLAPS has quite a few missing features), but TLAPS is very new by proof-system standards. Note that in general, TLA+ tries to avoid temporal logic as much as possible. Lamport has repeatedly said "temporal logic is evil". A 1000-line spec, will probably have no more than a couple of uses of temporal operators.(Of course, most people don't bother writing proofs at all for real, large, complex software as that is just too costly. They just use the model checker, that can check liveness, too.)
Re: Leslie Lamport: Video course on TLA+
#54So how amenable is tla+ to automatic translation to an existing programming language?
Didn't use it, but watch a few presentations, i.e: https://channel9.msdn.com/Events/Lang-NEXT/Lang-NEXT-2012/Bl...
Re: Leslie Lamport: Video course on TLA+
#55Great to see this here! I act as a TA for Dr. Lamport's TLA+ courses at Microsoft, and can answer any questions y'all have. TLA+ in one sentence: it is a language used to write specifications, same as you might write a spec in English/your chosen informal language, except here you write your spec in basic mathematics; benefits of a formal specification language include freedom from ambiguity, model-checking, and even…
I haven't watched the videos yet but I have been keeping my eye on TLA+ ever since seeing the whitepaper from Amazon and how they use TLA+ to spec out their distributed systems. As someone that works on distributed systems that could use some formality I think TLA+ could help, however, I have a hard time really understanding it. Do you know of any straight forward non-trivial examples? Something a little more complex…
I think it would help to have a good mentor, as I did, or a lecture series from the language inventor. I ran through the trial version of these videos when Lamport was developing them and it's quite approachable even for someone who's more of a liberal arts kind of person.
Re: Leslie Lamport: Video course on TLA+
#56Earlier quoted context omitted.
AFAIK, TLAPS does not support temporal reasoning in full currently, so you are not able to prove liveness properties of your system. On the other hand, Coq is able to express both LTL logic and infinite trace, so you can prove such things in it.
TLAPS supports temporal reasoning. I've personally used it only for safety (inductive invariant), but to make sure it supports liveness, I just checked the following: THEOREM ASSUME NEW F, NEW G, F ⤳ G, F PROVE ◇G PROOF BY PTL and it works fine (PTL stands for propositional temporal logic). I suppose there are some things that aren't supported (TLAPS has quite a few missing features), but TLAPS is very new by proof-s…
> They just use the model checker, that can check
> liveness, too
This is not quite true. Liveness is about infinite number of states, but any real model checking is bounded by definition.
For an engineer this is not a problem at all, but as for comp.sci researcher your ability to use TLA+ is limited in this respect.
> Lamport has repeatedly said "temporal logic is evil"
Well I respect Mr.Lamport`s point, but to prove liveness you are almost doomed to use temporal logic.
Re: Leslie Lamport: Video course on TLA+
#57Earlier quoted context omitted.
TLAPS supports temporal reasoning. I've personally used it only for safety (inductive invariant), but to make sure it supports liveness, I just checked the following: THEOREM ASSUME NEW F, NEW G, F ⤳ G, F PROVE ◇G PROOF BY PTL and it works fine (PTL stands for propositional temporal logic). I suppose there are some things that aren't supported (TLAPS has quite a few missing features), but TLAPS is very new by proof-s…
Temporal reasoning is a lot more than that you mentioned, so by providing this example you can not conclude that TLAPS support temporal reasoning. I have read several papers of S.Merz, Lamport's student and now a researcher, who mentioned that there is no temporal reasoning apparatus available in TLAPS. Maybe something have changed since then but I found no evidence for this. > They just use the model checker, that c…
> Liveness is about infinite number of states, but any real model checking is bounded by definition.
First, model checking is not bounded to a finite number of states in principle, and certainly not by definition[1]. Even in practice, modern, state-of-the-art model checkers do support infinite state spaces[2] -- of course, not in general, but in some cases. However, TLC, the model checker packaged with the TLA+ tools, is indeed not such a model checker, and can only check finite state spaces; it is what's known as an explicit state model checker. Second, liveness is not about an infinite number of states, but infinite behaviors, i.e. infinite sequences of states; the two are not the same.
> but to prove liveness you are almost doomed to use temporal logic.
Oh, absolutely, and after all, the TL in TLA stand for temporal logic, but the point is that proving complex liveness properties in real-world software systems is rare, simple liveness seems to be supported by TLAPS (although most people just use the model checkers), and complex temporal reasoning hardly ever comes up. That's why supporting complex temporal reasoning -- if it is indeed missing in TLAPS -- is not a priority. The features of TLA+ are in general very much driven by the needs of engineers working on real systems.
However, if you happened to come across a liveness property you wanted to but couldn't prove with TLAPS, I'd love to hear about it.
[1]: The name model checking comes from the model checking problem in logic, namely checking that a structure M (a program in the case of software) satisfies a logical proposition 𝜑, i.e., that M ⊨ 𝜑, or that M is a model of 𝜑. The name "model" comes from a logical model, i.e., a structure that satisfies a theory or a proposition.
[2]: E.g., https://cpachecker.sosy-lab.org/
Re: Leslie Lamport: Video course on TLA+
#58(To understand PlusCal, you need first understand the basics of TLA+, but you don't need to understand the action system 100% in-depth.)
The idea behind PlusCal is to write your algorithm in it, leaving out the "unimportant" bits, and using the nondeterministic operators in place of any value that is not in your algorithm's control. The model checker, TLC, can then run all possible traces of your algorithm to search for conditions under which it may deadlock or violate some assertion you have made.
Re: Leslie Lamport: Video course on TLA+
#59Great to see this here! I act as a TA for Dr. Lamport's TLA+ courses at Microsoft, and can answer any questions y'all have. TLA+ in one sentence: it is a language used to write specifications, same as you might write a spec in English/your chosen informal language, except here you write your spec in basic mathematics; benefits of a formal specification language include freedom from ambiguity, model-checking, and even…
I haven't watched the videos yet but I have been keeping my eye on TLA+ ever since seeing the whitepaper from Amazon and how they use TLA+ to spec out their distributed systems. As someone that works on distributed systems that could use some formality I think TLA+ could help, however, I have a hard time really understanding it. Do you know of any straight forward non-trivial examples? Something a little more complex…
Re: Leslie Lamport: Video course on TLA+
#60Earlier quoted context omitted.
I have a passing familiarity with proof assistants such as Cow and HOL. How would you compare TLA+ with those? https://en.m.wikipedia.org/wiki/Coq https://en.m.wikipedia.org/wiki/HOL_(proof_assistant)
This is a complicated question. I am currently writing a blog post series on the theory of TLA+ that I will publish in May that, among other things, touches precisely on this point. But I will try to quickly point out some areas of difference, but the most important thing to remember is that both Coq and TLA+ -- as far as specifying and verifying software is concerned (not general math) -- are universal formalisms. U…
I'd love to read your posts. Is there a url or twitter account where I can get updates on your work?