循序式語意

循序式語意對程式初學者而言其實很不自然，最主要的原因就是因為它的常見實作語言是C 語言家族，而 C 語言的 assign 符號跟數學的等於是同一個符號(都是 =)。當然改個符號就能解決辨識問題，事實上另一個曾經的主流循序式語言家族Pascal 就採用了 := 符號因此沒有任何問題。但接著我們還是遇到了語意上的問題，我們知道數學上等於是永久的，一但我們指定「 i 是整數 1 」，它在接下來的討論之中都會一直是 1 。然而循序式程式語言裡面「 i 是整數 1 」是暫定的，它真正的語意是「『現在』 i 是整數 1 」。沒錯，關鍵是時間，循序式語意編碼了時間。 = 符號的左側是現在、右側是過去，因此 i = i + 1 是「『現在』 i 是『剛才』的 i 加整數 1 」，而 i += 1 只不過是前面語法的簡寫。到這裡，可以說已經涵蓋了初學者會看到的各種情況下可能寫出來的程式了。在探討更複雜的情況之前，我們來看看沒有這個語意的話要怎麼辦呢？

如果沒有這樣的語意，要怎麼表示狀態呢？我們需要轉換一下觀點。在日常生活下，我們養出了我們是世界的一部分的感覺，因此操作世界是不可想像的。但事實上我們一直在操作整個世界，只不過是擷取部分之後操作，例如我們把物體運動其時間與位置的對應拿來操作分析。所以我們知道了關鍵是擷取，狀態也一樣，我們只要回傳新世界就可以了！於是輸入是舊狀態，輸出則是新狀態的函數就是我們所需要的新觀點。 i = i + 1 現在變成了 f(i) 而 f(n) = n + 1 。如果我們需要再加 2 呢？我們只需要再一個函數 g(f(i)) 而 g(n) = n + 2 。如果是 i += 1 且 j += 1 呢？只要引入 product type 即可： (f(i), f(j)) 。但如果我們有 10 個變數，這豈不是越來越蠢？因此不可變的傳奇到此為止，完全不可變的語言最後無可避免地需要 monad 一類的抽象，並且寫出與原先的循序式語意完全一樣但更莫名其妙的程式：

foo :: State Int Int
foo = do
    i <- get
    put (i + 1)
    return i

現在我們可以安然回到循序式語意裡面，前面說還有更複雜的情況，其中一個原因就是 concurrent(例如 thread 等)。一但允許 concurrent，我們單一美好的時間線就一去不復返了，現在我們不得不面對繁雜困難的「分支時間線」啦！在最簡單的情況下，各個分支之間沒有關聯，因此時間軸任意一點上我們可以視其為單一時間線的程式，這種情況一般被稱為適合 concurrency，因而挑戰並不在這種情況下發生。由於我們可以在任何一個時間點上聲明我們想要「誰」現在變成什麼狀態，因此另一個分支對那個「誰」的狀態進行讀取就是危險的，這種情況我們簡稱為競態條件(race condition)。困難點在於，我們並不清楚先後問題，因為兩個時間線並沒有關聯，我們最多知道它們從哪裡分支出來，不幸的是這通常對事情沒有幫助。我們需要能夠保障這個「先寫再讀」順序的機制，很自然的想法是聲明這個「誰」(變數)還不能用。但有時候我們只是需要確保沒有兩個時間線同時在修改同一個變數，有時候我們又只在乎某個修改不會被打斷，這些綜合起來就變成了各種鎖的機制。

回到分支出來的時間點有沒有用的部分，如果我們知道這個修改變數的分支在我們讀取之前就合併回去了呢？這種情況下我們又得到了美好的單一世界線，因此諸多標記系統就是為了讓這些情況更容易被檢測出來而設計的。在「先寫再讀」的情境裡，我們需要保證該變數被寫入的時間線都比現在讀取的時間線分支出來之前更早合併，而且比現在讀取的時間線合併回去之後才分支。因此追蹤變數的引用非常重要，不幸的是這非常難搞定，在 Java 這種 reference based 語言裡面這類型的分析根本就是究極惡夢，傳進函數的變數都可以視為可能被寫入，因此我們只能做慢得要死的全域分析，很不幸的是現代電腦太慢了，沒辦法在合理時間內處理這類分析(請不要忘了不是只有自己寫的程式要處理，還有引用的程式要處理，想想 npm 黑洞)。因此我們顯然需要別的方式，標記就是一種合理的選擇，在 C++ 裡面我們可以用 const 聲明一個變數、參考或是指標是不是不可變的，在 Rust 裡面預設就是不可變，並且保證可變權(mut)與所有權(ownership)一次只有一個地方可以得到。另一種作法，則是採用完全不可變語意，這確實偶爾可以解決一些問題，但代價是普通常見的單一時間線程式變難寫，取捨應該端看實際需求到底是什麼。

那麼，我們有辦法穿梭在時間線之間嗎？其實可以，continuation 是電腦科學裡面的一個理論，指「將來」要做的事，而「支援 continuation」一般指可以直接存取「將來」的內建功能，或是手工改寫(手動寫成的 continuation 形式又稱 continuation passing style)。既然我們都提到「將來」了，其實大家都猜得到穿梭是怎麼回事了吧，只要把「現在」的「將來」存到變數裡面，那「未來」的其他程式就隨時可以回到「現在」了。continuation 其實在程式語言裡面不常出現，但各種跳躍結構其實都用上了這個理論(而且其實我們有好理由不直接支援 continuation)，例如 return 其實是一種 continuation，把函數的結果傳進「將來(等同呼叫者)」裡面運算； throw 跟 return 類似，但如果沒有遇到處理它的值的程式就會繼續找更上層的「將來」把值傳給它。因此 racket 語言雖然沒有提供內建 return ，卻可以寫成：

(define (foo x y z)
  (let/cc return
    ...
    (when error-a
      (return (+ x y z)))
    ...))

let/cc 僅是一種得到當前 continuation 的神奇結構，使用它不需要深入理解這是怎麼辦到的。事實上，所有的控制結構都能換成 continuation，但為什麼我們不這麼做呢？這是因為 continuation 太難正確使用了，在內建 throw 的語言裡面紀錄當前的背景資訊(stack trace)以利後續追蹤是語言實作通常有的。而使用 continuation 就意味著使用者得明白當前背景資訊要怎麼拿，拿到之後怎麼堆疊，到最頂層都沒有處理者的話要怎麼印錯誤訊息，這些都不是不可能，但絕對大大的提升了使用難度。因此最好避免直接使用 continuation，我們通常都能找到其他內建結構代替，更何況如果真的有只能用 continuation 做到又沒有內建的功能的話，那它遲早會被語言內建進去的。

希望這篇的說明有讓你了解到為什麼變數是偉大的發明。複雜的 concurrency 是怎麼走到今天，未來又有什麼樣的可能。以及為什麼雖然有一切控制結構的終極統一我們最好還是讓它躺著就好。下次見，掰掰。