« Home

使用 TLA+ 的第一步 [tla-0000]

由於很多 TLA+ 入門教學似乎都沒有談到實務上要從哪裡開始使用 TLA+,所以這裡我想介紹實際上要怎麼做。一個 TLA+ 的檔案以 .tla 為副檔名,其中由 --- MODULE name --- 開頭,由 === 結尾,例如

---- MODULE plustwo ----
=====

在其中可以引用模組,寫成 EXTENDS xxx, yyy, ...

---- MODULE plustwo ----
EXTENDS Integers
=====

使用 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 TRANSLATIONEND TRANSLATION 裡面,可以發現它還會檢查 checksum。由於這個區塊內的程式會被機器生成的內容覆蓋,因此千萬不要把自己寫的不變量放在這個區塊中。

上面的 CONSTANT Limit 可以在 model 的設定檔 .cfg 中指定,這是為了避免把常數寫死在 TLA+ 主程式中,好在檢查前可以進行修改。

增加不變量 [tla-0002]

在有了這些程式之後,可以開始增加自己的不變量

Even(x) == x % 2 = 0

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              IsInc == x >= 0

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              Inv == IsInc /\ Even(x)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              THEOREM Terminated == Spec => Termination
  1. IsInc 要求 x 總是大於初始值 0
  2. Even(x) 要求我們寫的程式只會產生偶數
  3. Inv 把所有我們想證明的不變量組合在一起,/\ 表示邏輯的「a 且 b」語句。我想很容易猜到 \/ 表示邏輯的「a 或 b」語句

THEOREM 部分宣告 Spec 蘊含 Termination 不變量,這兩者都是 PlusCal 產生的,所以不用太在意細節,這裡的意義是證明程式確實會終止。

這裡介紹了 TLA+ 如何運作,TLA+ 對現實程式的幫助會體現在編寫非同步的程式時,TLA+ 擅長對只有有限狀態、可以使用經典邏輯推導的程式進行檢查,主要可以發現死鎖與違反不變式等錯誤。對 TLA+ 所使用的數學方面的學習可以參考 Lamport 本人寫的 A Science of Concurrent Programs