作為個人觀念中計算機(jī)科學(xué)中的三大浪漫之一,在下終于在這個學(xué)期有機(jī)會去實(shí)現(xiàn)了一個相對較為完整的編譯器。雖然僅僅是作為課程作業(yè),不過也實(shí)現(xiàn)了編譯器所需要的許多部分:Parser, Optimizer, Instruction Selection Module等等,而除此之外也從個人的角度去了解了一些有關(guān)編譯器或者編譯器實(shí)現(xiàn)的信息靶病,在此記錄下來權(quán)當(dāng)一份備忘。而這第一篇口予,我們先說說我們用來實(shí)現(xiàn)這個編譯器的語言:Haskell娄周。
現(xiàn)在應(yīng)該不存在任何一個成熟語言不能被用來實(shí)現(xiàn)編譯器了,從傳統(tǒng)的選擇如C, Caml,到相對較新的Go, Rust沪停,幾乎都有用其寫成的編譯器煤辨,甚至是編譯本身的編譯器裳涛,甚至是官方用來編譯自己的編譯器。而對于這個貫穿了整個學(xué)期的大作業(yè)众辨,我們選擇了Haskell作為實(shí)現(xiàn)語言端三。而從結(jié)果來看,這個選擇給我們帶來了許多便利泻轰,當(dāng)然也有一些麻煩技肩。
從便利的角度來講,Haskell有著很方便的Data Constructor語法浮声,與之配套的Pattern Match和Guard Expression,以及非常強(qiáng)大的<del>被囚禁了一萬年的力量</del>Monad旋奢。前者可以幫助我們很好的去進(jìn)行模式匹配泳挥,特別是在編寫優(yōu)化代碼的時候,例如:
mergeStmts (IRMov toTemp@(IRTemp _ _) val)
(IRMov loc (IRLoc fromTemp@(IRTemp _ _)))
| toTemp == fromTemp = [IRMov loc val]
mergeStmts (IRAsgnOp toTemp@(IRTemp _ _) op val1 val2)
(IRMov loc (IRLoc fromTemp@(IRTemp _ _)))
| toTemp == fromTemp = [IRAsgnOp loc op val1 val2]
mergeStmts lastStmt newStmt = [lastStmt, newStmt]
當(dāng)然這并不是Haskell所獨(dú)有的至朗,其他的函數(shù)式編程語言屉符,例如OCaml也有相似的語法,不過如果在C或者Python里面锹引,大概就要用宏或者M(jìn)eta Programming來替代了矗钟。
而后者,作為筆者初學(xué)Haskell時記憶最深的東西嫌变,在筆者經(jīng)過一個學(xué)期從覺得各種坑到離開Monad就不會寫程序的轉(zhuǎn)變之后吨艇,筆者的感覺是Monad確確實(shí)實(shí)很好用,一方面腾啥,它可以允許程序員在特定的時候使用更加貼近過程式語言的文法來減少行數(shù)东涡,進(jìn)而減少錯誤;另一方面倘待,配合不同的Monad以及Haskell強(qiáng)大的類型系統(tǒng)疮跑,它可以有效地幫助避免編寫時的錯誤,并且提高可讀性凸舵,例如是分離有副作用和沒有副作用的代碼祖娘。當(dāng)然Monad本身幾句話是說不完的,一個比較有趣的文章是Monad Transformer and Modular Interpreter啊奄,介紹了常用的State渐苏,Reader,Writer等Monad在實(shí)現(xiàn)解釋器中的作用增热。
而從麻煩的角度來說整以,最大的問題當(dāng)然是
教練,我們都沒用過Haskell熬稹公黑!
其次則是關(guān)于惰性求值。惰性求值意味著當(dāng)且僅當(dāng)一個變量的值真的被用到(例如IO操作,Trace)凡蚜,它和它的子表達(dá)式才會被求值人断,所以寫程序的時候務(wù)必要時刻記著這一點(diǎn),特別是<del>你想用你的方式守護(hù)你心愛的程序的時候</del>使用一些Unsafe或者IO相關(guān)的東西的時候朝蜘。例如我們?yōu)榱私档途幾g器超時的可能性恶迈,選擇對寄存器染色進(jìn)行限時,但這是要務(wù)必用Seq或者DeepSeq保證實(shí)際的染色結(jié)果在時限內(nèi)被完全求值谱醇,否則限時就只是在限制構(gòu)造出這段程序本身了暇仲。
而最后則是性能問題。編譯器中的特定部分副渴,例如上文提到的寄存器染色復(fù)雜度很高奈附,而Haskell中由于所有的變量都是不變量,絕大多數(shù)操作煮剧,包括Map斥滤,都需要至少O(log N)的復(fù)雜度,除非用ST Monad或者IO Monad相關(guān)的可變?nèi)萜髅阒选9P者在這個問題上選擇的更加激進(jìn)的做法:用C++實(shí)現(xiàn)模塊佑颇,在Haskell中通過FFI調(diào)用,但也遇到了各種Segmentation Fault什么的草娜,而且挑胸,并沒能完全解決掉。
而一點(diǎn)題外話則是Haskell本身的編譯系統(tǒng)很值得了解驱还,雖然筆者只是看了一些皮毛嗜暴,但是還是感受到了<del>如此強(qiáng)大的力量(你要玩多少遍這個梗啊)</del>议蟆。通過巧妙地運(yùn)用指針低位等黑科技闷沥,Haskell的編譯器能夠生成非常高效的的代碼,如果沒有被程序員誤用的話咐容。
(待續(xù))