Re: purely functional (原 [問題] SCJP6.0)
果然出去吃個飯回來就斷線了 orz
p 幣看來會少很多 :s
※ 引述《sbrhsieh (sbr)》之銘言：
: ※ 引述《godfat (godfat 真常)》之銘言：
: : 其實我覺得簡單地說就是，不能有任何 side-effect,
: : 因此不能有任何 state. 大概就這樣，其他都是衍生出來的性質。
: : 這邊不會跟 no side-effect 直接連上關係的原因，
: : 我想是有些情況下 side-effect 是可以被允許的。
: 這邊的 side-effect 該怎麼定義？涵蓋的範圍？
我想 side-effect 的涵蓋範圍應該不太可能能被定義..?
如果是 side-effect 本身要怎麼定義的話，大概就是不能有 state,
然後 function/expression 本身具有感染性，只要用上任何有含
side-effect 的東西，本身就會變得具有 side-effect.
: 我試想過如果一個 FP 語言不允許 function/procedure 有任何的 side-effect，
: 那麼這個語言寫出來的程式會蠻受限的，幾乎只能寫純處理數據的工作。
: 有太多的工作本身就是一種 side-effect，是無法單純 consume 某些 input，並
: 以特定 output value 來呈現(resource manage、IO)。比如：
: 「刪除給定路徑的某個檔案」，這件工作本身就是變更檔案系統的狀態，這不可能
: 由一個毫無 side-effect 的 procedure(expression)來實現。
我覺得這個就可以去找特定的資料來看，例如 Haskell.
Haskell 本身是 purely functional, 但同樣允許 side-effect,
也可以做 IO, 因此並不是只能處理純數據的工作...
這靠 monad 來達成這件事。這是借自 category theory 的詞：
http://en.wikipedia.org/wiki/Monad_(functional_programming)
很不幸的是 XD 雖然我一直想把他讀完，不過到現在還是一直沒找到
機會把他讀完，所以細節都不是很清楚... 雖然聽說這是 haskell 裡，
會第一個碰到的障礙，甚至也有文章副標題是: "Don't Panic"
http://pages.cpsc.ucalgary.ca/~robin/class/521/monadGuide.pdf
噫，我應該想辦法找時間來把這些看完的。
最早我是看 Yet Another Haskell Toturial:
http://www.cs.utah.edu/~hal/docs/daume02yaht.pdf
這篇我之前看的時候還沒寫完，很多地方是空白的，現在不知道寫完了沒？
總而言之，我可以大概提一下目前的理解。很可能有錯，就大概看看.....
跟下面的 stream 一起說好了。
: Stream 這種觀念/東西感覺上也跟狀態很有關係，有玩過比較純的 FP 語言(諸如
: Clojure)的人，可否說明一下該 FP 語言是否有實做 stream 概念的東西？
: 若有，又是如何去實現管理/操作(manipulation) stream 的 procedure，能夠
: 讓這些 procedure 沒有 side effect 又有好的效率？
我稍微查了一下，在 haskell 中，拿來對付類似的東西，好像大多是用
Data.ByteString.Lazy: http://www.cse.unsw.edu.au/~dons/fps.html
效率好不好嘛，上面是說效率很好，有人說效率有 C 的 1/2
我覺得像是這種本身就具有大量 state 的問題，
purely functional 本身是不太可能比得贏 C 之類直接的操作啦...
這跟架構有關，在別人的地盤上，先天上就輸了不是嗎 XD
我個人覺得類似的效能評比，應該用在其他架構上，例如 distributed
最近很紅的 Erlang, 實作 CouchDB, 諸如此類從「架構上」尋求的解答。
或許沒什麼關係，不過有個類似的語言，也是寫在 JVM 上：
http://en.wikipedia.org/wiki/E_(programming_language)
不過這個沒怎麼維護了的樣子？或許直接看 Erlang 即可...
回到 monad, 大抵上的概念就是我們把「狀態」視為一種值，
而每一次狀態改變，則會產生新的值，再把這個值繼續傳遞下去。
就像 Schelfaniel 在推文裡提到的：
: → Schelfaniel:函數式語言的變數，都是不變的吧，但物件導向有可能變 08/04 20
: → Schelfaniel:也就是說，如果process1要變，變化會放在它的傳回值 08/04 20
: → Schelfaniel:像是這樣 (process2 (process1 java-object)) 取其變 08/04 20
我們假設現在的系統狀態是 X, 則兩次對螢幕輸出 Hello, World! 則可看成：
puts("Hello, World!", puts("Hello, World!", X))
而不是：
puts("Hello, World!")
puts("Hello, World!")
也就是說，puts 這個 function, 他會回傳一個新的系統狀態，假設叫 Y,
就可以看成是：
Y = puts("Hello, World!", X)
Z = puts("Heelo, World!", Y)
因為第二個 puts depend on 第一個 puts 的 return value,
也就是新的系統狀態，因此兩者的順序是不可以被顛倒的，
這邊不是兩個各自獨立的 statement, 而是一個不可分割的 expression.
haskell 的 monad 就是把這件事包裝起來。很多 IO function 的回傳
都是 IO (), 表示他是一個 IO monad.
Prelude> :t putStr
putStr :: String -> IO ()
putStr 本身是一個 String -> IO () 的 function.
來看剛剛 ByteString 的範例：
module Test where
import Data.ByteString.Lazy.Char8 as L
test = do
s <- L.readFile "/dev/zero"
-- 這邊就是把 /dev/zero 這個檔案的內容，讀到一個 IO ByteString 裡面：
-- L.readFile :: FilePath -> IO ByteString
-- 前面 IO () 是表示我們不關心這個 IO monad 究竟存有什麼狀態，
-- 比方說，我們並不關心螢幕（or remote）被輸出了什麼資料，
-- 但這邊我們關心我們讀入了什麼資料，因此是 IO ByteString
return (L.unpack (L.take 10 s))
-- 這邊從剛剛的 s 裡，讀取前面前 10 個 Char8
-- 而 L.unpack 則是把這個 ByteString, 轉成 haskell 原本的 String,
-- 也就是 [Char], 字元串列。最後再把整個結果回傳回去。
-- return 是用在 monad 裡面，他會把現在的「狀態」包起來。
-- test :: IO [Char]
-- 我們最後是回傳 String (等同於 [Char]), 因此整個 test 的結果，
-- 就是一個 IO String
main = do
s <- test
Prelude.putStr s
-- 這邊我們把 test 的結果，也就是剛剛的 IO String,
-- 存到 s 裡面，然後再把這個 s 印出來。
也就是說，monad 本身是有感染力的，只要你用到 monad,
整個 function 也會變成 monad. 要讓你的 function 不成為
monad, 只能完全避開任何的 monad, 也就是任何 IO.
接著再由其他 monad function 去使用你其他的 pure function.
這邊也可以參考 Eiffle, 在昨天 referential transparency 的連結裡：
http://en.wikipedia.org/wiki/Referential_transparency_(computer_science)
提到 command-query separation:
http://en.wikipedia.org/wiki/Command-query_separation
command 有 side-effect, 而 query 沒有，因此是 referential transparency.
這邊其實有點類似這樣的味道，像在上面的 main 裡有：
s <- test
Prelude.putStr s
但是不能簡寫成：
Prelude.putStr test
因為 test 是回傳 IO String, 而 putStr 是要吃 String 的。
透過 s <- test 把 IO String 裡的 String 抓出來，放在 s 裡，
才能把這個 s 丟給 putStr 把結果印出來。
在這邊由於使用了 do notation, 因此寫起來的感覺跟一般
imperative 的程式差不多：逐次執行，可以有 side-effect.
但實際上這其實是 syntactic 上的 sugar:
http://en.wikipedia.org/wiki/Monad_(functional_programming)#do-notation
看起來是一行一行的，也沒有牽涉到 state 間的轉換，是底層幫你做好了。
如果要全部自己來的話，寫起來是會很可怕，很複雜的結構，例如上面的範例：
a = do x <- [3..4]
[1..2]
return (x, 42)
會被轉成：
a = [3..4] >>= (\x -> [1..2] >>= (\_ -> return (x, 42)))
沒有人會想這樣寫程式的... XD
簡單地說，利用 monad, 我們在 pure function 的世界裡，
做出一種模擬 side-effect 的結構，然後讓你把 pure function
跟其他 side-effect 做一層切割，有點像是防火牆這樣的味道...
因此如果寫 haskell 程式只用 monad 和 do notation 的話，
感覺就沒什麼用 pure function (thus haskell) 的意義在了...
然而如果談到效率的話，當然不可能會有最底層那樣來得好。
當然是越接近機器架構會越快，這是當然的。不過這也不表示說
用這種 monad 的方式會很慢很慢，因為很顯然，大部份的時候
那些 state 根本不需要真的被 evaluate 出來，既然不需要被觀察，
這些 state 也不會影響到其他 state, 那在 compile 時，
基本上就可以完全捨棄掉。這就是最佳化要解決的問題了...
理想上當然是能把抽象化程式，依照目前機器架構，做最好的最佳化。
把所有多餘也不關心的操作都拿掉。GHC 本身就有很多很多的最佳化.. XD
==
我打太久了，不能再花時間在這上面，就暫時不校稿了...
--
Hear me exalted spirits. Hear me, be you gods or devils, ye who hold
dominion here:
I am a wizard without a home. I am a wonderer seeking refuge.
Sacrifice
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.128.121.85
※ 編輯: godfat 來自: 220.135.28.18 (08/05 20:56)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 5 之 6 篇)：