由於很多 TLA+ 入門教學似乎都沒有談到實務上要從哪裡開始使用 TLA+,所以這裡我想介紹實際上要怎麼做。一個 TLA+ 的檔案以 .tla
為副檔名,其中由 --- MODULE name ---
開頭,由 ===
結尾,例如
---- MODULE plustwo ---- =====
在其中可以引用模組,寫成 EXTENDS xxx, yyy, ...
---- MODULE plustwo ---- EXTENDS Integers =====
使用 PlusCal 語言 [tla-0001]
使用 PlusCal 語言 [tla-0001]
比起直接寫出 Spec
等不變式,先寫 PlusCal language (https://lamport.azurewebsites.net/tla/tutorial/intro.html) 的程式再使用用它生成的 Spec
不變量會更簡單也更實用。因為 TLA+ 會嘗試生成所有可能的狀態,有可能出現所謂的 unbound model (https://learntla.com/topics/unbound-models.html),就結果而言對它進行檢查永遠不會完成。用 PlusCal 語言寫的程式相對容易發現這種錯誤。
---- MODULE plustwo ---- EXTENDS Integers CONSTANT Limit (* --algorithm plustwo variables x = 0; begin while x < Limit do x := x + 2; end while; end algorithm; *) \* BEGIN TRANSLATION (chksum(pcal) = "3f62e9ff" /\ chksum(tla) = "239a9ecd") \* END TRANSLATION =====
由 PlusCal 產出的不變量會被包在 BEGIN TRANSLATION
到 END TRANSLATION
裡面,可以發現它還會檢查 checksum。由於這個區塊內的程式會被機器生成的內容覆蓋,因此千萬不要把自己寫的不變量放在這個區塊中。
上面的 CONSTANT Limit
可以在 model 的設定檔 .cfg
中指定,這是為了避免把常數寫死在 TLA+ 主程式中,好在檢查前可以進行修改。
增加不變量 [tla-0002]
增加不變量 [tla-0002]
在有了這些程式之後,可以開始增加自己的不變量
Even(x) == x % 2 = 0 IsInc == x >= 0 Inv == IsInc /\ Even(x) THEOREM Terminated == Spec => Termination
IsInc
要求x
總是大於初始值0
Even(x)
要求我們寫的程式只會產生偶數Inv
把所有我們想證明的不變量組合在一起,/\
表示邏輯的「a 且 b」語句。我想很容易猜到\/
表示邏輯的「a 或 b」語句
THEOREM
部分宣告 Spec
蘊含 Termination
不變量,這兩者都是 PlusCal 產生的,所以不用太在意細節,這裡的意義是證明程式確實會終止。
這裡介紹了 TLA+ 如何運作,TLA+ 對現實程式的幫助會體現在編寫非同步的程式時,TLA+ 擅長對只有有限狀態、可以使用經典邏輯推導的程式進行檢查,主要可以發現死鎖與違反不變式等錯誤。對 TLA+ 所使用的數學方面的學習可以參考 Lamport 本人寫的 A Science of Concurrent Programs。