2009/05/06

On states

我想我發現一個比「functional languages 沒有 side effects」更好的說法:functional languages 沒有 implicit states。寫過一點 functional programs 的人都知道,很多概念仍然和 imperative programs 是對應的。例如 functional, tail-recursive fibonacci 和 imperative, iterative fibonacci 其實是同一件事情:

ffib : ℕ → ℕ → ℕ → ℕ
ffib 0 x y = y
ffib (suc n) x y = ffib n y (x + y)
(本來是要用 Haskell 寫的,可是 n + k patterns 最近又掀起一小波筆戰,很討厭 XD。)在 ffib 裡面,第一個 parameter 是 loop counter(順便一提,絕大部份的 for loops 都是 induction)、第二和第三個 parameter 就相當於對 x, y 兩個變數做 parallel assignment x, y = y, x + y。稍微追蹤一下 ffib 的求值過程,就能感覺到對應的 imperative program 該有的 states 一點不缺,只是 functional version 把所有 states 明確寫出來而已。更明顯的例子自然是 state monad,因為 monad structure 把 state 藏起來了,如果又用 do notation 寫的話,monadic code 一看就覺得根本是 imperative programs。

所以在 state 這件事上,functional languages 和 imperative languages 有時候其實是異曲同工。把全部的 states 都寫出來,就不會為了顧及 implicit states 而在推理轉換時絆手絆腳;但當 state 規模變大時,處理起來就不那麼順手了,此時 imperative programs 的專門語法反而比較方便。因此我想 functional langauges 最大的威力還是 "functions as first-class values"。不過這是後話了…

--
本來覺得很 trivial 不想寫,但還是寫一下好啦 XD。

Labels: