gistfile1.txt

先貼連結，大概就是講這個，依照上面的 source 順序講
http://okmij.org/ftp/tagless-final/course/optimizations.html#PPL2015

我這邊只講大意，主要還是要看 source 裡面寫的東西，
會比我描述的清楚許多

首先是在 http://okmij.org/ftp/tagless-final/course/BasicGates.hs
裡面定義基本的語言：
class Symantics repr where 那段
實作這個語言的部份則是：
instance Symantics R where
也是很簡單用 haskell 去實作而已

接下來我們看到：
instance Symantics S where
這個有趣的地方在於，他是同一個語言，只是用另一種方式去看
即另一種 interpreter
他不是 eval 出一個 Bool, 而是 eval 成一個 String
這個主要用途是方便觀察後面其他 transformer (pass) 的結果

是說
-- * QUIZ: How to avoid too many parenthesis?
-- Write a precedence printer
這邊還真的沒有內容，Oleg 在講的時候是有給我們看內容的 XD
簡單地說，就是讓 ((a & b) & c) & d) 顯示成 a & b & c & d
可以避免使用括號時避免使用

接著我們看 http://okmij.org/ftp/tagless-final/course/BConstProp.hs
這個：
instance Symantics repr => Symantics (TCP repr) where
實作另一種 interpreter, 大抵上就是在每一個 term 上面貼上標籤，
貼上 Unk (unknown) 或是 Lit (literal)
在貼標籤的過程中，我們就把 True & term 簡化成 term,
或是 term & True 簡化成 term, 或是 False & term
簡化成 False, 依此類推

這樣當我們有：
exc1 = xor wireX (xor wireY (lit True))
時，直接 view exc1 會得到原始的結果，
但如果跑 view $ dyn exc1 時，我們就可以得到簡化後結果

exc1 就是我們的原始程式，透過不同的 transformer,
我們可以改寫原始程式而得到某種「最佳化」

[...] 中間各種 transfomer 跳過... [...]

最後直接跳到 http://okmij.org/ftp/tagless-final/course/HConstProp.hs
我們的最佳化 transformer (pass) 就是：
chain = obsHCP . obsCP . obsN2N . obsNDown
簡單地說就是做四種 transformation
裡面包括將 !(a & b) 推成 !a | !b
還有 !!a 推成 a 等等
連做三次：
ehadd3t_tr = ntimes 3 $ ehadd3t
可以觀察
view ehadd3t
和
view ehadd3t_tr
的差異。後者將式子簡化非常多

這讓我想到 llvm 上的 optimization pass...
有趣的地方是，真工夫似乎就是在這些 transformer 究竟要怎麼套？
像是 !!!!!!a 要做三次去掉 !! 的才能簡化成 a
!(a & !b) 也要先把 ! 推進去成 !a | !!b 才能再簡化為 !a | b
要做多少次才停？

Oleg 說，原則上就是做到 fixed point,
不過下個問題就是那我們怎麼知道什麼時候會到 fixed point?
答案是不知道 XD 更何況也有可能會做一次從 A 跳到 B,
再做一次又從 B 跳到 A, 這樣可能也找不到 fixed point...

另一方面，這邊 class/instance 的運用也真是讓我覺得
haskell 真是有夠簡潔呀