[FLOLAC]心中有Monad，萬物皆Monad

1.打完之後才突然發現....我原本只是想打個輕鬆的心得文，怎麼搞的那麼嚴肅 Orz

2.竟然遇到小我X(消音)屆的高中+大學學弟，嚇然發現自己變老人了

3.我給了幾個人聯絡方式，可是後來才想到我沒拿任何人的聯絡方式。如果有同學看到歡迎回個文。

正文開始 Orz

---

星期二時，scm老師談到「今年FLOLAC中，Functional Programming的課比較少，選用的是OCaml而不是Haskell，不會討論Monad之類的東西」。有趣的是，我覺得「就Operation Semantics的角度，來討論imperative program的derivation」，這件事本身就有濃厚的FP味道存在。

首先，從最基本的<s1, s>->s'談起：給予一個statement S1及初始狀態s，會得到最終狀態s'。對於deterministic semantics，<s1, s>->s' and <s1, s>->s'' imply s'=s''。換句話說，如果將S1視為一個routine，給予相同的input，會得到相同的output，這不就是pure function的定義嗎？另外就像Josh Ko談過的：與其說FP沒有side-effect，不如說FP沒有implicit state。然而<s1, s>->s'這樣的表達法，也讓imperative language中的所有狀態變化被攤開來，使其在某些方面可以像FP一樣地分析。

接下來，舉出老師在課堂上給的兩個quiz：

* 原本derivation只做到statement的層次。如果要將arithmetic expression做derivation，其型別應該是什麼？(Ex. x = y + 5; )
* 如果語言中出現「具有side effect的arithmetic expression」，其derivation的型別是什麼？ (Ex. x = ++y; )

假設算數運算的值域為整數，其中第一個應為<AExp, State> -> int。第二個應為<AExp, State> ->(int, State)。這個答案其實很直觀：前者只要求值，後者求值順便變更狀態。這不是跟State Monad中的一些型別很像嗎？

• 語意為「修改狀態不求值」
  <Statement, State>->State
  execState :: State s a -> s -> s
• 語意為「不改狀態只求值」
  <AExp, State> -> int
  evalState :: State s a -> s -> a
• 語意為「又改狀態又求值」
  <AExp, State> ->(int, State)
  runState :: State s a -> s -> (a, s)

State Monad是pure functional language中可以模擬imperative language的關鍵，而Operational Semantics又以接近pure functional的方式去分析imperative language（在不涉及parallel與nondeterministic的情況下）。上OP的課時，我反而在心中印證了對於FP的認知。

---