Compiler的一些事(其一)

作為個人觀念中計算機(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ù))

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末舆逃,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子戳粒,更是在濱河造成了極大的恐慌路狮,老刑警劉巖,帶你破解...
    沈念sama閱讀 223,002評論 6 519
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件蔚约,死亡現(xiàn)場離奇詭異奄妨,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)苹祟,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,357評論 3 400
  • 文/潘曉璐 我一進(jìn)店門砸抛,熙熙樓的掌柜王于貴愁眉苦臉地迎上來评雌,“玉大人,你說我怎么就攤上這事直焙【岸” “怎么了?”我有些...
    開封第一講書人閱讀 169,787評論 0 365
  • 文/不壞的土叔 我叫張陵奔誓,是天一觀的道長斤吐。 經(jīng)常有香客問我,道長厨喂,這世上最難降的妖魔是什么和措? 我笑而不...
    開封第一講書人閱讀 60,237評論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮杯聚,結(jié)果婚禮上臼婆,老公的妹妹穿的比我還像新娘。我一直安慰自己幌绍,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,237評論 6 398
  • 文/花漫 我一把揭開白布故响。 她就那樣靜靜地躺著傀广,像睡著了一般。 火紅的嫁衣襯著肌膚如雪彩届。 梳的紋絲不亂的頭發(fā)上伪冰,一...
    開封第一講書人閱讀 52,821評論 1 314
  • 那天,我揣著相機(jī)與錄音樟蠕,去河邊找鬼贮聂。 笑死,一個胖子當(dāng)著我的面吹牛寨辩,可吹牛的內(nèi)容都是我干的吓懈。 我是一名探鬼主播,決...
    沈念sama閱讀 41,236評論 3 424
  • 文/蒼蘭香墨 我猛地睜開眼靡狞,長吁一口氣:“原來是場噩夢啊……” “哼耻警!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起甸怕,我...
    開封第一講書人閱讀 40,196評論 0 277
  • 序言:老撾萬榮一對情侶失蹤甘穿,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后梢杭,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體温兼,經(jīng)...
    沈念sama閱讀 46,716評論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,794評論 3 343
  • 正文 我和宋清朗相戀三年武契,在試婚紗的時候發(fā)現(xiàn)自己被綠了募判。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片荡含。...
    茶點(diǎn)故事閱讀 40,928評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖兰伤,靈堂內(nèi)的尸體忽然破棺而出内颗,到底是詐尸還是另有隱情,我是刑警寧澤敦腔,帶...
    沈念sama閱讀 36,583評論 5 351
  • 正文 年R本政府宣布均澳,位于F島的核電站,受9級特大地震影響符衔,放射性物質(zhì)發(fā)生泄漏找前。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,264評論 3 336
  • 文/蒙蒙 一判族、第九天 我趴在偏房一處隱蔽的房頂上張望躺盛。 院中可真熱鬧,春花似錦形帮、人聲如沸槽惫。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,755評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽界斜。三九已至,卻和暖如春合冀,著一層夾襖步出監(jiān)牢的瞬間各薇,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,869評論 1 274
  • 我被黑心中介騙來泰國打工君躺, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留峭判,地道東北人。 一個月前我還...
    沈念sama閱讀 49,378評論 3 379
  • 正文 我出身青樓棕叫,卻偏偏與公主長得像林螃,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子谍珊,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,937評論 2 361

推薦閱讀更多精彩內(nèi)容