[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Is TLA+ still useful if your implementation language is a purely functional one, like Haskell?

I’m trying to understand if TLA+ is useful if your primary implementation language is a functional one like Haskell. So I’m going to make some assertions and come to a conclusion, in the hopes that people will point out where I’m going wrong or right. I’m half-way through the TLA+ book, so I apologize if I get some things wrong.

1 My Understanding of TLA+ Specs

Specs in TLA+ take the form of temporal formulas with the following structure:

Spec == Init /\ [][Next]_vars /\ Liveness

Here, Spec can be said to be satisfied by a certain class of behaviors. Behaviors are a sequence of states. Crucially, a state is a set of variables whose values can change over time.

2 Purely Functional Programs Reduce TLA+ Specs to Non-Temporal Formulas

Functional languages like Haskell heavily discourage the use of variable mutation. So is this a problem for TLA+?

There are two cases to analyze.

First case: The first case is when you are breaking the rules of Haskell, and introducing mutable state into your program anyway. In Haskell this is discouraged but allowed. Well, in this easy case, TLA+ can help you reason about your partially stateful program as usual (i.e., TLA+ will be just as useful to you had you written your program in C or Java).

Second case: Now suppose your program is completely pure. What then is the use of TLA+? It seems to me that the following would be true:

Thus, if you are writing a purely functional program, all of your TLA+ specs will be purely non-temporal, in the sense that they will take the form of first-order logic sentences with no temporal symbols like [] or apostrophe. But, I conclude, writing such a spec will still be helpful, for it will force you to reason about the properties of your (purely functional) program in the mathematical language of first-order logic. This is because it will force you to think of your program at a higher-level than even Haskell.

3 Conclusion: TLA+ is Still Useful to Functional Programmers

If your program is purely functional, then TLA+ forces you to write a non-temporal spec. But reducing your spec to a non-temporal formula still forces you to think and write in terms of math (i.e., first-order logic and set theory), which seems useful. Finally, if your functional program requires the use of mutable state anyway (which can be done in Haskell, despite being discouraged), then a TLA+ spec will be just as useful to you had you written your program in a non-functional language like Java or C.

So do people think this line of reasoning is sound?