Tag

2018年9月20日 星期四

黃禍

黃禍,作者是王力雄,ISBN:9789862138502

本書是小說,主要在描述中國由於一場水災,造成一系列的連鎖反應,總書記被暗殺、各地軍閥四起、中國內戰、美俄介入,最後以世界大戰作為終結。

我對<黃禍>的評價是最低的。
第一個畢竟這是 1996 年的小說,預測偏很多也不是很意外,書裡的台灣甚至還反攻中國,然後「毫無防備」的台北被丟原子彈……反攻中國?毫無防備?看到與其說是驚呆不如說噴笑。
第二個是主因:作者寫這本書更大的原因,反而是想宣傳他想出的新式民主:逐級遞選制;這本書也就不那麼純粹,轉變成為政治理念服務的小說。雖然說文以載道,但當宣道變成主要目的,文的價值就淡化甚至消失了。
作者在書裡想像了幾天就能成熟的「薯瓜」,可以在營養液裡快速成長,可以在行走中攜帶成長;最後三分之一(也就是下冊)開始描述中國人們在上述逐級遞選制的引導之下,離開中國到富裕國家尋求生存,北邊遷入西伯利亞;西邊走新疆一路到歐洲;南邊去澳洲;東邊跨海到美國。
單純的評論就是作者的一廂情願,也許是作者想像了一幅千萬人遷移的壯觀畫面,又或者作者只是想表達他的逐級遞選制才能成功帶領人群,即便在無秩序世界裡以最有效率的方式達成治理?無論作者所想是哪一個,總歸而言就只是本空想的小說,在一套空想的政治制度下,吃著空想的食物走一趟空想的旅程。

事實上我認為從中冊開始,有些人物就開始變成木偶,隨劇情需要做出各種不同的反應、出現在他該出現的地方、說他該說的話,至於他們到底怎麼做到、或者他們怎麼換腦的?反正作者寫了算。
反正作者的主軸就是讓中國崩潰順便傳個教,嚴格來說雖然中國崩潰看起來很政治不正確,但從字裡行間看來作者還是跳脫不出身為中國人的思考模式,就算中國崩潰了也要拖全世界下水,誰瞧不起中華民族我們就算死也要拉你一起;日本人表面和善可是背地捅刀;美國就是個人信仰,拿起槍背判政府想作亂就作亂……認真來看這本書問題一堆。
我不否認作者文以載道的努力,就如同他的另一部小說<大典>,闡述的是在全面監控的高科技之下,至高無上的威權,如何在「掌握監控科技」的人的手中傾頹,雖然也是小說,裡面的科技監控也過於匪夷所思;但從後記來看,作者想表達的也是他對於科技民主的期待,對照近期中國社會信用制度的上線,讓大典顯得不這麼空洞。

當年在撰寫黃禍時,作者對於逐級遞選制,也同樣有著他的期待,如果能看到作者這層思想,我想閱讀這本書也就值了,但畢竟是本過時的空想著作,值得看的部分其實不怎麼多。

總評:2.5/10
簡單評論:浪費時間 看看就好* 值得一看 非看不可

黑土

黑土,作者為:Timothy Snyder,ISBN:9789570851236
udn導讀

如果提到二戰對猶太人的大屠殺,大家腦中會浮現什麼?
我試著打一段大屠殺描述的文字,大家覺得其中「」標起來的關鍵字同意多少?
大屠殺:納粹德國在希特勒的意識型態下,由「德國人」開動德國之「國家機器」,有系統將「德國之猶太人」標籤、分類、運送往「德國奧斯威辛*」為代表的的「集中營」,以「毒氣室」對猶大人進行工業化的大屠殺。(*或譯奧許維茲集中營)

事實上,對於歷史上的大屠殺來說,上面幾個標籤都不太正確,這是黑土想要述說的論點,一個一個來看:
  • 德國人:部分正確,但真實的大屠殺發生地帶其實是從波蘭以東,進到白俄羅斯、烏克蘭、波羅的海三小國等地,進行煽動的或許是德國人,動手的卻未必,多數是在地的警隊跟居民。
  • 國家機器:正好相反,不是因為德國動員國家機器殺人,而是德國在東歐創造了大片無政府狀態的區域,使得大屠殺得以發生。
  • 德國之猶太人:同樣的,德國猶太人存活率顯著高於東歐地帶的猶太人*,只要能持有國家保護的身分,國家要動手也要瞻前顧後,還會受到官僚的綁手綁腳。
  • 德國奧斯威辛、集中營:事實上集中營大多在前述的佔領區,奧斯威辛在波蘭,德國想要殺人,得先把人遣送到無政府地帶才能動手。
  • 毒氣室:事實是集中營無論在重要性和時間上,在大屠殺中只能排第三,真正重要的大屠殺是東歐的大規模屍坑槍決跟毒氣車。
* 網路上找到以 Anne Frank 為名的紀念網站,雖然比例上有出入,但結論是類似的:大部分被屠殺的猶太人都非德國人。

本書的內容大約分成下面幾個部分:
  • 希特勒的世界觀,戰間期猶太人與波蘭間的競合
  • 德國入侵東歐摧毀國家後的屍坑大屠殺
  • 奧許維茲悖論,國家主權與猶太人存活的關係
  • 拯救猶太人的故事
  • 結語
作者在開頭很仔細的解釋了希特勒的世界觀與波蘭對猶太人的政策,隨後鉅細靡遺的介紹,在巴巴羅薩行動進佔東歐之後,發生在各地的大屠殺與手法;這段的重點在補足全書的脈絡,提醒讀者們大屠殺並不是集中營,而是發生在東歐更廣大的事件,二次世界大戰並不是連綿不絕的戰爭,而是一段極端行為變成日常的時間。
奧許維茲悖論是為本書的關鍵,對大屠殺來說,集中營這個符號跟標誌實在太過顯著,使得大家關注大屠殺只想到集中營,而忽略在奧許維茲真正開始運作之前,在廣袤的東歐土地上,德國已經在當地居民協助下殺害九成九的猶太人,更有甚者,當大部分猶太人被屠盡之後,身在集中營的勞動營 - 作為它本來的目的 - 的猶太人,反而是最後才遭到殺害的。
如果大屠殺在東歐確實發生,我們就要回答:是什麼讓人民互相殘殺?是什麼清除了管理社會的組織?是誰讓人變成獸?起初在東歐國家毀滅上,蘇聯其實也插了一腳,但隨著德國戰敗,蘇聯重新進佔東歐,某種程度上強調集中營正好非常理想的開脫了真正行刑者的責任,使得責任落在德國人與德國的頭上,輕易迴避了東歐民眾當時作為協力者的責任,以及大屠殺真正的關鍵因素:國家毀滅。

作者帶你走遍歐洲各國,看看猶太人何時被殺、為何被殺、被殺多少,發現都和國家主權息息相關,其效果甚至能壓過當地反猶的政治傾向,即便淪為德國的附庸、又是德國近鄰、本身又有強烈反猶政策的丹麥,仍有九成以上的猶太人能存活,只因為丹麥主權堪稱完整;甚至同為軸心國的義大利,猶太人死亡率反而低得出奇,大規模的遣送也要等到墨索里尼倒台,由德軍強力佔領義大利之後才開始行動。
國家不只是一個統治的主體,它同時給予人們身份和連結,在國家內的猶太人能夠求救於官僚、行政體系、朋友,而不致於被歸類為一個猶太人、一個猶太家庭,從社會被分離出來而被殺害,承平時期讓人惱怒的行政效率,反而是猶太人保命的關鍵;同時國家還能保持對外連結,一方面公民身分是國家統治的象徵,要維護國家地位,對於德國不會輕易的交出猶太人;到了二次世界大戰末期,軸心國開始失勢時,本來配合德國的國家也紛紛開始收手,轉而配合國際呼籲暫停國內的猶太遣送行動。

那些拯救猶太人的行動,國家主權再一次發揮力量,無論如何鳳山或日本的杉原千畝發放的簽證、亦或瑞典外交官 Wallenberg 發放的保護護照,只要能拿到簽證或護照,存活的機會就大大升高,每每以成千上萬的規模保護猶太人;透過國際合作進行的保護行動,也是透過流亡英國的波蘭政府四處奔才得以進行。
沒有國家保護的,就只能仰賴極為少數且力量有限的救援者,甚至就連救援者也受國家主權影響,位在西歐國家的救援者遠比東歐安全,庇護猶太人甚至不是能夠問罪的事情,例如庇護 Anne Frank 的 Miep Gies 即便被發現也能存活,在東歐的國家毀滅區卻會引來殺身之禍。

從黑土中給出來的訊息,在於國家存續的重要性。
對於國家人們有許多看法,但無論是合法壟斷暴力的實體,還是人民、領土、主權、政府綜合體,國家都代表一個授與、守護多數個人權利的主體,我們再怎麼小政府、大企業、開放資料、拆政府原地重建,國家、政府、主權仍然是一個強大、無可取代的組織(就如同七月的颱風,市政府一聲令下四點放假,大家四點就乖乖的去馬路上當停車場、到捷運站擠沙丁魚)。
失去國家的瞬間,所有國家所背書的一切文件、證照、證明都會失去效力,要在這樣的極端環境下,動物星球的極致:大屠殺才得以發生。

以上的情境,我相信身為台灣人的我們其實並不陌生,無論是 1895 年日本政府殖民、或 1949 年中國政權殖民台灣,台灣都在那一瞬間面臨國家的毀滅,接下來就是全國範圍的大清洗,把所有高知識份子跟具有號召能力的人全部洗掉,這一切在波蘭都曾經發生過。
眼下最為危險的,正如同二次大戰前德國所宣稱:波蘭並非國家而且始終不曾存在主權,因為不曾存在,所以所有主權證明都視為無效、所有的法律規定也不曾存在。同樣如此宣稱的,正是海峽對岸的中國政權,堅稱台灣政府不曾擁有主權,本身就是一個危險的信號,可以想見一但台灣政府垮台,等待台灣人民的,只可能是 1895, 1949 年大屠殺的重演,沒有其他;所有代表政府曾經運作,以及可以維持主權機能的人:軍人、警察、公務人員、高知識份子、社會領袖,絕對會被清掃乾淨,別無例外。
所謂「人之所以異於禽獸者,幾希」,差別在於人類組成國家社會,將人類社會一步步複雜化,用種種規約、法律、習俗,將人身上的動物性給壓制下來,在一個多樣化充滿連結的社會,每條關係都彼此牽制,將我們禽獸的一面給壓制住。

另外一個訊息則是耐心,社會、國家是一個變動遲緩的巨型生物,對一般人來說每分每秒的生活之中,我們幾乎感受不到以數年計量的社會漂移。
但所有的行動,都不可能一蹴可及,就如同今年年底的同婚公投,如果沒過會如何?很可能同婚合法化會等到 10 年之後,說來殘酷,但那又如何?社會本來就是緩慢的,不可能明天起床,所有人都被洗腦成你的觀點,但每天說服一個人、一個就好你願意嗎?
曾經看過一句話:人們都會高估一年能做什麼,卻會低估十年能做什麼。

人們需要知道特效電影如 Avenger ,那樣的超級災難和超級英雄是不切實際的,改變社會和未來是一項大工程,枯燥而且乏味,但卻是唯一預防任何激進行動的唯一方式,如同書名隱喻的,在烏克蘭的肥沃黑土對二戰的德國意味著確保生存的解決方案,德國需要殖民烏克蘭,用黑土確保德國的糧食供應。
這可以套用在任一個國家,面對溫暖化、糧食危機的當今世界,面對風吹草動的危機,黑土意味某種快速、簡單、直覺思考、快問快答的解決方式,如同希特勒將日後餵飽全世界的綠色革命棄若敝屣,轉而訴諸簡單的陰謀論:一切都是猶太人在背後搞鬼,以及快速的解決方案:進佔東歐、殺光住民、殖民確保糧食來源;當陷於快速簡單的解決方案,人們也就失去自省,以及任何替代思考的可能性。
正如一戰未曾結束,希望在巴黎畫畫地圖就能讓歐洲永久和平,只會換得一紙 20 年的停戰協定。科學不會有陰謀論吸引人;枯燥的論述不若網紅的激進發言刺激;冗長的討論也不會比一來一往的網路留言有趣,但我們需要耐心才能真實解決問題,如果我們只想著某種快速的解決方案,我們就更朝希特勒的世界前進一步。


本書最大的問題體現在翻譯上,偶爾會出現一些超級長、夾帶兩層甚至三層意思的句子,像是:「希特勒與那種認為人類之所以異於自然是因為人類有能力想像並創造新的合作形式的政治思想之間有著斷裂」,或者有些明明可以斷句卻又沒斷,感覺就像是全書曾經先用過機器翻譯,之後的校稿潤稿又沒有好好做的結果,不得不說很妨礙閱讀。

總評:6.5/10
簡單評論:浪費時間 看看就好 值得一看* 非看不可
我認為全書內容可以到 7.5 - 8,不過翻譯問題實在太過嚴重,因此稍微扣了點分。

不曾結束的一戰

不曾結束的一戰:作者為 Robert Gerwarth,ISBN:9789571374338
udn導讀

歷史學家或者歷史教育通常喜歡用一個個事件來描述歷史,箇中原因在於,每個人的一生會被無數事件交錯纏繞,人物誌會讓人看不出事情的全貌,編年史會讓事件被時間切成碎片,用事件可以把其中各造都拉進來,綜合編年史和人物誌的優點,完整呈現事件各方立場和時間順序。
有利必有弊,事件史的缺點可以說是歷史的片段化,一個全面的歷史會是任何時間、任何地點都在發生事件的組合,但這遠超過一般人能理解的程度,也因此一些重大事件通常就成為標誌,其開始和結束常被當作歷史的中斷點,一個世界都為之暫停的斷點,但事實上通常不是這樣。

一次世界大戰就是一個例子,由於西線的壕溝戰、毒氣戰、機槍、坦克打造的絞肉機太過引人注目,幾乎都能聽到書寫歷史新頁的沙沙聲,於是大家的目光都集中在西線,第一次世界大戰結束的 1918 年 11 月 11 日,正是西戰線停戰的日子。
普遍的印象,在一次世界大戰結束之後,歐洲進入了所謂的戰間期,普遍印象歐洲也進入一段和平歲月,直到 1939 年德國打響二次世界大戰,事實上,只要稍加涉獵,就知道蘇聯在戰間期時,曾有過紅白兩軍的內戰,跟和平其實相差甚遠。
不曾結束的一戰,寫作目的正是要打破以上的印象,本書從1917年的俄羅斯革命開始,到 1922 年的希土戰爭終局的士麥那大屠殺,從三個面向完整介紹這段時間:1. 戰敗國的下場;2. 橫跨戰勝國與戰敗國的革命與反革命;3. 巴黎和會與帝國解體。
對戰後發生在東歐、中歐、南歐,遍及土耳其帝國、奧匈帝國和俄羅斯帝國的一連串事件,作了清晰完整的介紹。

一戰之後,帝國或因為革命、或因為不堪戰爭拖累、或因為凡爾賽條約,相繼在一戰後瓦解,但隨後而來卻非期盼已久的和平,而是一連串更長久的紛爭,帝國雖然專制,實際上卻對境內各民族都提供一視同仁的權利保障,隨著戰後威爾遜民族自決的風潮,帝國瓦解後的新生民族國家,如波蘭、捷克、匈牙利等國,對國內少數民族的保障更形欠缺,本來相安無事的多民族區域,在「民族」國家這個旗號的擠壓下,緩衝的空間都失去了,於是發源於民族的暴力衝突反而更多;對於多民族區域的歸屬,更引發多國間的競爭角力,甚至於強制性的地區人口交換。作為無根蘭花的猶太人,則變得四處不是人,在各國都被從國家保護中分離出去,最後淪為各國都亟卻清除的對象。
此外凡爾賽條約淪為戰勝國爭利益的場所,有些戰勝國如義大利、希臘無法滿足於條約結果,引爆國內極端主義或再次對外用兵;戰敗國視條約為奇恥大辱,無不謀求以各種方式打破條約;條約又無力調解新生國家地域衝突和民族衝突,以為戰勝就能在地圖上用畫筆訂下新國界;威爾遜的民族自決又有種族限定,以致無法適用的國家同樣無法信任新生的國際聯盟。
凡此種種都為 20 年後的亂局打下根基。

同時,一戰後的革命與反革命為進階化的暴力打開窗口,平民跟戰鬥員的界線首次抹去,頭一回的總體戰,平民成為需要為國家敗戰負起責任的一部分,導致隨之而來的二次世界大戰,目標不再是擊敗對手,而是為了完全消滅國家、消滅人民、謀求「優等」人民的生存空間。
一戰用一個全新民族國家的體制,取代視為落後的專制帝國,卻也因此種下更長遠的暴力。今年正好是標誌上的一次世界大戰結束100週年,正好透過本書,用全新的視角看待一次世界大戰,事實上正如作者所言,即使到了今日,從敘利亞內戰、庫德族等事件,亦或是最近塞爾維亞與科索沃互換領土的爭端(),見證一次世界大戰結束後,當年鑄下的苦果現在為人們所承受著。
有感於大家的歷史常識通常忽略了戰間期,這個重新塑造歐洲,為二次大戰種下遠因的時期,許多重大事件如俄羅期內戰、芬蘭獨立戰爭、希土戰爭,通常不在大家的關注範圍,本書是補助戰間期一本極佳的著作。

相對來說,本書最大的問題是缺乏地圖,由於全文出現許多地名,多是東歐、西亞等不常出現的區域,缺乏地圖讓本書在空間感上略顯薄弱,是個可以改進的方向。

總評:8/10
簡單評論:浪費時間 看看就好 值得一看 非看不可*

2018年8月25日 星期六

用 PEG 寫一個 C parser

故事是這樣子的,之前我們寫了一個自創的程式語言 Simple Language ,還用了 Rust 的 pest 幫他寫了一個 PEG parser,雖然說它沒有支援新加入的函式等等,本來想說如果年底的
MOPCON 投稿上的話就把它實做完,結果沒上,看來是天意要我不要完成它(欸

總而言之,受到傳說中的 jserv 大神的感召,就想說來寫一個複雜一點的,寫個 C language 的 PEG parser 如何?然後我就跳坑了,跳了才發現此坑深不見底,現在應該才掉到六分之一深界一層吧 QQQQ。
目前的成果是可以剖析 expression 並依照正確運算子順序處理,還有部分的 statement 也能正常剖析,因為通常能處理 expression 跟 statement 剖析裡麻煩的工作就完成 50 %,決定寫小文介紹一下,啊不過我還沒處理 expression 出現轉型的時候該怎麼辦,array reference 出現要怎麼辦,所以這部分可能還會改。
本來專案想取名叫 rcc 或 rucc,但這樣的專案名稱早就被其他人的 rust c compiler 用掉了,因為寫 Rust 的人好像都很喜歡用元素來當專案名稱,這個專案的名字就叫 Carbon 了XD。

其實寫這個跟寫 simple parser 沒什麼差,只是語法更加複雜,複雜之後就容易寫得沒有結構化;PEG 有個好處是在處理基礎的結構的時候,比起用 regular expression 各種複雜組合還要簡潔,像是 floating point 的時候,這是 C floating point 的語法,雖然這還不含 floating point 的 hex 表達式,但不負責任的臆測,要加上 hex 的支援只要多個 (decimal | hex) 的選擇就好了:
sign = { "+" | "-" }
fractional = { digit* ~ "." ~ digit+ | digit+ ~ "." }
exponent = { ("e" | "E") ~ sign? ~ digit+ }
floating_sfx = { "f" | "F" | "l" | "L" }
floating = @{ fractional ~ exponent? ~ floating_sfx? }

不過脫離基本結構,開始往上層架構走的時候麻煩就來了。
我的感想是,在大規模的語言剖析上 PEG 其實不是一個很好用的剖析方式,寫起來太隨興,沒有一套科學分析的方法告訴你怎麼樣寫比較好,甚至怎麼寫是對的,就連 C standard 的寫法都是用 CFG 可以處理的格式寫的,PEG 畢竟比較年輕才沒人鳥它;在傳統 CFG,List 就是用 List -> List x 那套來表達,在 PEG 裡卻可以直接把剖析的文法用 +, * 重複,層數相較 CFG 可以有效扁平化,相對應的壞處是很容易寫到壞掉,目前為止花了很大的心力在調整語法各部分的結構,非常耗費時間。

例如在剖析函式的內容,C 語法大概是這樣定義的:
compound_statement -> block_list
block_list -> block_list block
block -> declaration_list | statement_list
declaration_list -> declaration_list declaration
statement_list -> statement_list statement

上面這段大致體現了 declaration 跟 statement 交錯的寫法,一開始寫的時候,直譯就翻成
compound_statement -> block*
block -> declaration* ~ statement*

很直覺對吧?但上述的語法會直接進到無窮迴圈,上下層兩個連續的 * 或 + 是 PEG 語法的大忌,當上層跳入 * 無窮嘗試的時候,下層就算沒東西 match 了,照樣可以用 * 的空集合打發掉;同理上層是 + 下層是 * 也不行,理由相同;真正的寫法是上層用 * ,下層用 + ,在沒東西的時候由下層回傳無法匹配讓上層處理。
這個例子最後的寫法其實是這樣:
compound_statement -> block*
block -> (declaration | statement)+

或者是這樣,反正轉成 AST 之後也沒人在意 block 到底是只有 declaration 、只有 statement 還是兩個都有,乾脆把所有 declaration 跟 statement 都攪進一個 block 裡:
compound_statement -> block
block -> (declaration | statement)*

這個例子很明顯的體現出 PEG 文法的問題,透過文法加上 ?+*,我們可以很有效的把本來的 list 打平到一層語法,但連接數層的 +* 就需要花費時間調解層與層之間的融合,是一件複雜度有點高的事情。
很早之前在看參考資料的時候有看到這句,現在蠻有很深的體會:「我覺得用 PEG 類工具可以很快的擼出一個語法,是日常工作中的靠譜小助手,但要實現一個編程語言什麼的話,還得上傳統的那一套。」(註:原文為簡體中文此處直翻正體中文)
像是我的 simple parser 跟 regex parser,用 PEG 寫起來就很簡明,一到 C 這種複雜語言就頭大了;CFG 那邊的人大概會指著 PEG 的人說,你們 PEG 的人就是太自由了,哪像我們當年(誒

剖析寫完再來還要把文法轉譯成 AST。
在實作上大量參考強者我學長 suhorng 大大的 haskell C compiler 實作,想當初跟學長一起修 compiler,那時候我還很廢(其實現在也還是很廢),光是寫 C lex/yacc 能把作業寫出來不要 crash 就謝天謝地了,然後學長上課的時候 haskell 敲一敲筆電就把作業寫完了 QQQQ。

用 rust 的 pest PEG 套件寫轉換的程式,大部分都是 match rule ,看是哪種 Rule 之後去呼叫對應的函式來處理。
在expression 的部分可以直接使用 pest 提供的 precedence climbing 功能,無論是文法或建 AST 都很簡單,文法甚至可以收到一行,因為 expression 都是一樣的格式:
expression -> unary_expr (binary_op unary_expr)*
再到 precedence climbing 為所有 op 分出順序,就像 climb.rs 裡面那壯觀的 C operator 優先次序:
fn build_precedence_climber() -> PrecClimber<Rule> {
  PrecClimber::new(vec![
    Operator::new(Rule::op_comma,    Assoc::Left),
    Operator::new(Rule::op_assign_add,   Assoc::Right) |
    Operator::new(Rule::op_assign_sub,   Assoc::Right) |
    Operator::new(Rule::op_assign_mul,   Assoc::Right) |
    Operator::new(Rule::op_assign_div,    Assoc::Right) |
    Operator::new(Rule::op_assign_mod,  Assoc::Right) |
    Operator::new(Rule::op_assign_lsh,    Assoc::Right) |
    Operator::new(Rule::op_assign_rsh,    Assoc::Right) |
    Operator::new(Rule::op_assign_band, Assoc::Right) |
    Operator::new(Rule::op_assign_bor,    Assoc::Right) |
    Operator::new(Rule::op_assign_bxor,  Assoc::Right) |
    Operator::new(Rule::op_assign_eq,     Assoc::Right),
    Operator::new(Rule::op_qmark,    Assoc::Right) |
    Operator::new(Rule::op_colon,    Assoc::Right),
    Operator::new(Rule::op_or,       Assoc::Left),
    Operator::new(Rule::op_and,      Assoc::Left),
    Operator::new(Rule::op_bor,      Assoc::Left),
    Operator::new(Rule::op_bxor,     Assoc::Left),
    Operator::new(Rule::op_band,     Assoc::Left),
    Operator::new(Rule::op_eq,       Assoc::Left) |
    Operator::new(Rule::op_ne,       Assoc::Left),
    Operator::new(Rule::op_gt,       Assoc::Left) |
    Operator::new(Rule::op_lt,       Assoc::Left) |
    Operator::new(Rule::op_ge,       Assoc::Left) |
    Operator::new(Rule::op_le,       Assoc::Left),
    Operator::new(Rule::op_lsh,      Assoc::Left) |
    Operator::new(Rule::op_rsh,      Assoc::Left),
    Operator::new(Rule::op_add,      Assoc::Left) |
    Operator::new(Rule::op_sub,      Assoc::Left),
    Operator::new(Rule::op_mul,      Assoc::Left) |
    Operator::new(Rule::op_div,      Assoc::Left) |
    Operator::new(Rule::op_mod,      Assoc::Left),
  ])
}

match 之後一定有些規則是無法處理的,例如 match statement 的時候就不用管 op_binary 的 rule,這裡我寫了一個函式來承接這個規則,Rust 函式的 ! 型別相當於 C 的 noreturn,已經確定這個還是不會回傳值了,印出錯誤訊息後就讓程式崩潰;這個函式就能在任何 match 的 _ arm 上呼叫。
fn parse_fail(pair: Pair<Rule>) -> ! {
  let rule = pair.as_rule();
  let s = pair.into_span().as_str();
  unreachable!("unexpected rule {:?} with content {}", rule, s)
}
這樣這個函式就能出現在任何地方,例如 match 當中,每一條分支都應該要得到同樣的型別,不過這個函數可以是例外,畢竟它確定不會再回來了:
match (rule) {
  Rule::op_incr => Box::new(CastStmt::StmtPostfix(CastUnaryOperator::INCR, primary)),
  Rule::op_decr => Box::new(CastStmt::StmtPostfix(CastUnaryOperator::DECR, primary)),
  _ => parse_fail(pair),
}
我自己是覺得,把 PEG 文法剖析出來的結果轉換到 AST 上面,麻煩程度差不多就跟寫一個 recursive descent parser 差不多,而且用了 PEG 套件很難在使用者給了不正確程式時,給出有意義的錯誤訊息,我用的 pest 最多只能指著某個 token 大叫不預期這個 token ,預期要是哪些哪些。
到頭來要給出好一點的錯誤訊息跟發生錯誤的回歸能力,也許還真的只能像 gcc, llvm 一樣,直接幹一個 recursive descent parser。

不過以下是我不負責任的想法,我我暗暗覺得 PEG 的語法和 recursive descent parser 之間應該有某種對應的關係,也就是說,如果設計好 PEG ,應該能給出一個不錯的 recursive descent parser 的骨架,搭配使用者設計好在哪些文法遇到哪些錯誤該如何處理函式群,生出一個 recursive descent parser 來;不過以上只是不負責任的臆測,請各位看倌不要太當真。

這個專案其實還在草創階段,還有超多東西沒有支援(其實連個像樣的功能都沒有吧...),各位看倌大大手下留情QQQQ

下一步我也還沒想好怎麼做,之前有看到 rucc 的專案,是直接使用 rust 跟 LLVM 組合的套件,把剖析的程式碼直接轉成 LLVM IR,也許可以參考這種做法也說不定。


2018年8月17日 星期五

寫了一個不知道幹什麼用的 regex library 跟 parser

故事是這樣子的,之前寫 understanding computation 的時候,發現 regular expression 的實作,只有最基本的五種:empty 匹配空字串,literal 匹配文字、repeat * 匹配零個或多個 regex、concatenate 匹配連續的 regex、choose 匹配嘗試數個 regex。
大約幾天前想到也許可以把這個 project 拓展一些,讓它威力更強力一點點,順便當個練習。

預計要加入的東西有:
  • 支援 +, ? 兩種擴展的重複方式。
  • 支援 “.” 匹配 any character。
  • 支援 "[]", "[^]" 匹配在/不在集合中的字元。

+跟? 是最簡單的,它們和狀態機的設計無關,只要修改產生狀態機的方式即可;"*" 的時候是引入一個 start_state,將 start_state 和原本狀態機的 accept_state 加入新的 accept_state,並用 free_move 將 accept_state 跟原本狀態機的 start_state 連起來。
+ 的話是新的 start_state 不會是 accept_state 的一員。
? 的話是原本狀態機的 accept_state 不會用 free_move 和 start_state 連線。

Any 相對也很好做,本來我們的 farule 是一個 struct ,現在變成一個帶 enum type 的 struct,該有的都有:一個 state 到另一個 state;取決於 enum type ,會使用不同的 match 規則來決定適不適用規則。
像是 Any 就是全部都適用,literal char 的話會是比較一下字元是否相同。

[] 的實作…我發現到之前的實作,不太容易實作出 [^] 的規則。
[] 相對容易,簡單看來它就只是把裡面所有的字元變成 choose rule,例如 [a-z] -&gt; a|b|c..|z,但 [^] 就不同了,因為在 NFA 裡面,一個輸入的字元會跟所有可以嘗試的 rule 去匹配,但我們不可能把 [^] 之外所有的字元都接一個 choose 去 accept state (好吧理論上可以),如果在 [^a-z] 把 a-z 接去一個 dummy state, 用一個 any rule 接去 accept state,表示任何輸入的字元在嘗試 any rule 的時候都會通過它漏到 accept state 去。
最後還是在一條 rule set 裡面,保留所有可匹配字元的方式解決 QQ,這樣一來 match 一個字元的 rule 就變成這個 rule 的子集(不過為了方便還是保留這個 rule),接著 regex 的 [] [^] 就只是直接轉譯成 Rule set 就行了。

剩下的應該就只有改一下 PEG parser,這部分比較沒什麼,其實寫這個 project 沒什麼突破性的部分,大部分都是做苦工,好像沒什麼好值得說嘴的。
而且這樣改還有一個後遺症,就是匹配變得只能在 NFA 下進行,不能轉成 DFA 來做了,因為如 rule any, rule set 都會讓我們無法走訪目前所有可能的匹配結果,目前我看到市面上(?) 的 regular expression 實作,也都不是用這種 NFA 的方式在實作的,所以說我寫這個 project 到底是為了什麼……。

寫文章附上原始碼是常識我知道我知道:
https://github.com/yodalee/nfa_regex

當然還是有一些好玩的東西,例如測試可以任我寫:
https://github.com/yodalee/nfa_regex/blob/master/src/regular_expressions/mod.rs#L132

2018年7月27日 星期五

把 NFA 轉成 DFA 這檔事

故事是這樣子的,最近在時寫一些跟 Regex 相關的程式碼,無意間發現我之前understanding computation 這本書的實作中,並沒有實作非確定有限自動機(下稱 NFA)轉成有限自動機 的程式碼。

所以說我們這次就來實作一下。

概念很簡單,我們手上有一個,我們可以把這個 NFA 拿來,從開始狀態開始,將這個狀態可以接受的字元都走走看,把每一個字元輸入之後的狀態組合都記下來(因為是NFA,同時可以存在許多狀態上),重複這個流程直到所有狀態組合都被記錄過之後, 就能產生對應的 DFA,這個新的 DFA 每一個狀態都會原本 NFA 狀態的組合。
這也代表:其實 NFA 並沒有比 DFA 更「高級」的能力,一切都可以用 DFA 來完成,NFA 只是在表示跟建構上,比 DFA 方便一些而已。

實作一樣使用 Rust 的實作,雖然說也只是照著書上的 ruby code 實作就是了。
在這之前我們已經完成了 FARule, NFARulebook, NFA, NFADesign 等一系列的 struct ,用上了 Rust 的泛型,確保 FARule 可以接受任何型別作為狀態,無論是整數還是一個 struct,這點很重要,這樣我們後面的修改都不用再擔心狀態型別的問題。

首先我們先創了一個 NFASimulation 的 struct,把之前已經實作完成的 NFADesign 塞進去,並加上一個新的函式 to_nfa_with_states,接受一個 NFA 狀態為參數,產生一個以這個狀態為初始狀態的 NFA (一般 NFADesign 產生的 NFA 的初始狀態是固定的)。
接著我們在 NFASimulation 實作兩個函式:next_states 和 rule_for:
  • next_states 會拿到一個 NFA 狀態(HashSet<T>)跟一個字元,回傳的是接受這個字元之後,NFA 新的狀態,注意所謂 NFA 的狀態意思是 DFA 下狀態的組合,因此型態是 HashSet<T>。
  • rule_for 參數是 NFA 狀態,嘗試 NFA 中所有可能的輸入字元,回傳從這個狀態出發,所有可能的規則(FARule)。
最後把上面兩個函式結合在一起,實作 discover_states_and_rules 函式,拿到只有一個初始狀態的集合之後,先呼叫 rule_for 得到所有從這個狀態出發的 rule,將每個 rules 指向的狀態取出來;如果新的狀態集合是輸入狀態集合的子集,表示所有可能的字元輸入都不會得到新的狀態,我們就已經遍歷整個 NFA 了;否則,再把這個狀態集合丟進 discover_states_and_rules 裡面,遞迴直到收集到所有狀態為止。

話是這麼說,但開始實作之後就遇上一個問題,NFA 狀態表示是 HashSet<T>,discover_states_and_rules 的輸入就是 HashSet<HashSet<T>> (NFA 狀態的集合);但 Rust 並不支援 HashSet<HashSet<T>> 這樣的泛型,當我試著從 discover_states_and_rules,設定回傳型別是 HashSet<HashSet<T>> ,rustc 立刻就噴我一臉錯誤,rustc 預設並沒有 HashSet<T> 的雜湊方式,也因此無法把它作為 HashSet 的 key。

當然這是有解法的,後來是參考了下面這個連結
不能直接使用 HashSet<HashSet<T>>,得先把 HashSet<T> 封裝起來,放到名為 StateSet 的 tuple struct 當中,tuple struct 的角色就是單純的封裝,可以用 struct.0 取得第 0 個封裝的元素,也就是封裝的 HashSet<T>。
如此一來我們就可以實作一個 StateSet<T> 使用的雜湊方式,說出來沒啥特別,就是把整個 set 裡面的元素拿出來再雜湊一遍就是了,下面是相關的實作:
use std::hash::{Hash, Hasher}
impl<T: Eq + Clone + Hash + Ord> Hash for StateSet<T> {
  fn hash<H>(&self, state: &mut H) where H: Hasher {
    let mut a: Vec<&T> = self.0.iter().collect();
    a.sort();
    for s in a.iter() {
      s.hash(state);
    }
  }
}

將 HashSet<T> 封裝成 StateSet 之後,就能使用 HashSet<StateSet<T>> 表示 NFA 狀態的集合,從狀態集合到狀態集合的規則,也能用 FARule<StateSet<T>> 表示,這樣就能夠完成 discover_states_and_rules 函式,其返回值是 (states, rules),即型別 (HashSet<StateSet<T>>, Vec<FARule<StateSet<T>>>)。
利用 discover_states_and_rules 一口氣拿到一個 NFA 所有可能的狀態集合,還有對應的規則,就可以產生一個對應的 DFA。
pub fn to_dfa_design(&self) -> DFADesign<StateSet<T>> {
  let start_state = self.nfa_design.to_nfa().current_state();
  let mut start_set = HashSet::new();
  start_set.insert(StateSet::new(&start_state));
  let (states, rules) = self.discover_states_and_rules(&mut start_set);
  let accept_state = states.into_iter()
    .filter(|state| self.nfa_design.to_nfa_with_state(&state.0).accepting())
    .collect();
  DFADesign::new(StateSet::new(&start_state), &accept_state, &DFARulebook::new(rules))
}

在寫這一段程式碼的時候,因為是看著書中的 Ruby 範例程式碼在寫, 其實有很多地方的程式碼還滿像的,例如在 discover_states_and_rules 裡面,除了在型別上面卡關非常久之外,其他語法跟 Ruby 幾乎沒有什麼差別,真不虧是Rust,也許該私下稱 Rust 為「強型別的 Ruby/Python 」XD。
不過呢,在 HashSet<HashSet<T>> 的問題上面,還有例如將兩個 HashSet<T> union 起來上,還是被 rustc 嗆了非常久,真的是深切體會 Python, Ruby 等等知名語言背後到底幫我們處理多少髒東西。

這篇文章相關的原始碼可見:
https://github.com/yodalee/computationbook-rust/blob/master/src/the_simplest_computers/finite_automata/nfasimulation.rs

心得一:我真的覺得,寫 Rust 的話,一定要記得下個 :set matchpairs+=<:> 開啟 <> 的 match,不然看看上面那複雜的嵌套,眼睛直接花掉。
心得二:寫過 Rust 之後再寫 C++ ……,這又醜又囉唆的語言是哪裡冒出來的,超級不習慣,不過就我目前的一點…直覺,我覺得 C++ 如果把過去的東西都拋掉,把 std、reference、smart pointer 用到極致,就會得到一個很像 Rust 但沒有 Rust 記憶體檢查等功能的語言。
心得三:Rust 是世界上最好的程式語言
心得四:頑張るビー (誤

2018年7月21日 星期六

開始使用 Google Test:基本設定

故事是這樣子,最近突發奇想用一些零碎時間寫了一個 C++ 的 regex project,因為已經好久沒有寫 C++ 都在寫 Rust,回鍋發現 C++ 怎麼可以廢話這麼多,長得又醜,以後哪個人再跟我說 Rust 的的生命週期很醜的,我就叫你去看 C++ 的 template code,看你還敢不敢再說 Rust 醜。
扯遠了,總之這次寫的 C++ 專案,其實只是當個練習,看能不能藉由實作專案熟悉 C++ 11、14的功能,也決定引入 CMake 和 Google test 等等我之前一直都沒有學會的東西,從做中學這樣。

這篇先來介紹一下 Google test 超基礎設定,詳細請參考官網。

當我們把程式準備好,通常會自己偷懶寫一個 main,然後在裡面呼叫所有測試用的函式,測試就是手動執行編譯出來的執行檔,但是這樣做的問題不少:諸如缺乏足夠的 assert 跟框架支援,測試很難擴張,沒有量化多少測試通過等等(有時也會重新發明這些輪子來測試就是XDD)。
這當然是個問題,所以很多公司或單位都推出測試框架,讓寫測試變成一件愉快大家都願意做的事,Google Test 就是其中一個,看一看覺得不難寫就決定用了,同樣在使用 Google Test 的包括像 Google 自己的 chromium,LLVM 編譯器等等;其他的測試框架像是強者我同學 JJL 推的 catch2。
要使用 Google test 的第一步是先安裝,Linux 只要用套件管理員安裝即可,Windows 的話我救不了你,請到 Google test Github 網頁看編譯教學。
接著我們要設定專案,首先寫一個測試,如果是自幹一個主程式的話,通常會像這樣:
void test_something();

int main(int argc, char *argv[])
{
  test_something();
  return 0;
}

void test_something() {
  assert(true);
}
執行下去沒噴掉就是測試通過了,我知道可能有些人在暗自竊笑:怎麼可能有人這樣子寫測試程式,不過真的很對不起我以前真的就這樣子寫測試,為了要測不同的東西還分成許多執行檔,導致 Makefile 裡面一堆項目,各種雷,請大家叫我雷神王。
不過如果你已經這樣子寫測試了,把它改成 Google test 也是相當簡單的事情;每一個測試的函式會對應到Google test裡面的 TEST,用 TEST(test_suite_name, test_case_name) 代替;主程式會由 Google test 生成不用寫,整個測試會修改成這樣:
// include google test
#include "gtest/gtest.h"

TEST(testSuite1, test_something) {
  EXPECT_TRUE(true) << "This should not fail";
}

變得簡短很多,不需要再維護我們有多少個測試,把測試寫到主程式也省掉,只需要維護好每一個單一測試即可。
Google 測試提供一系列的 assert 跟 expect 兩種測試用的函式,兩者的差別在於 assert 會直接將中止程式,expect 只會顯示錯誤之後繼續執行測試;基本上可以的話用 expect 就對了,在一次測試中回報盡可能多的結果。
只要是能夠透過 ostream 輸出的內容,都可以用接續在 assert 跟 expect 後面,作為失敗時的輸出。
Assert 跟 Expect 完整的列表可以在 Github 上 Google test 的文件找到。

再來我們就可以來編譯了,如果你是用 Makefile 的話,在編譯的時候加上 Google test 安裝路徑,在連結的時候 -l gtest 即可。
https://gist.github.com/mawenbao/9223908

如果是用 CMake 的話我,是參考這個連結
# Google Test
add_executable(unittest unittest.cpp)
enable_testing()
target_link_libraries(unittest gtest gtest_main)
add_test(unittestSuite unittest)

我們要產生一個新的執行檔 unittest,在 link library 加上 gtest 跟 gtest_main,CMake enable_testing 我也不確定是什麼意思,老實說我覺得 CMake 對我來說有一點複雜到不透明了,我很難理解每一個 command 是在做什麼,要做到什麼功能需要加上什麼 command,如果不 Google 的話也很難知道怎麼寫,有一種在寫 javascript 的感覺(誒

編譯完成之後就會出現 unittest 這個執行檔,此時再執行即可:
[==========] Running 3 tests from 1 test cases.
[----------] Global test environment set-up.
[----------] 3 tests from testDFA
[ RUN ] testDFA.test_dfa_rulebook
[ OK ] testDFA.test_dfa_rulebook (0 ms)
[ RUN ] testDFA.test_dfa
[ OK ] testDFA.test_dfa (0 ms)
[ RUN ] testDFA.test_dfa_design
[ OK ] testDFA.test_dfa_design (0 ms)
[----------] 3 tests from testDFA (0 ms total)

[----------] Global test environment tear-down
[==========] 3 tests from 1 test cases ran. (1 ms total)
[ PASSED ] 3 tests.

祝大家 google test 愉快,我相信隨著我 project 變大,很快的我會遇到更多 CMake 跟 Google Test 的用法,到時候再整理出來發文了。

2018年7月14日 星期六

有關 Rust test 的那些奇奇怪怪的東西

有關 Rust test 的那些奇奇怪怪的東西
最近因為在寫 Rust code,想到那句朗朗上口的口號「原碼未動,測試先行」,想說就來寫點測試,嘗試一下傳說中的 TDD 開發,連路上的計程車也愈來愈多 TDD 了你還不 TDD
想說就來整理一下 Rust 測試相關的編排,還有我遇到那堆奇奇怪怪的開發經驗。
簡而言之,我們先放掉什麼把 test 寫在 comment 裡面的設計,那東西我至今沒用過也不太看人用過,註解跟文件什麼的只是裝飾而已,上面的大人物是不會懂的
我們只看兩個:單元測試跟整合測試。

在 rust 裡面單元測試直接跟程式碼寫在一起,通常是在一個模組的 mod.rs 裡,或者是 lib.rs 裡,要寫在一般的原始碼裡面也可以,但通常到模組層級才會開始寫測試,有關 rust 模組的架構就請參考拙作

寫測試的時候首先先加上測試的模組,裡面加上測試用的函式:
#[cfg(test)]
mod tests {
  use super::*;

  // test rule can match content exactly
  fn can_parse(rule: Rule, content: &str) -> bool {
    match CParser::parse(rule, content) {
      Err(_) => false,
        Ok(mut pair) => {
          let parse_str = pair.next().unwrap().into_span().as_str();
          println!("{:?} match {}", rule, parse_str);
          parse_str == content
        },
    }
  }

  #[test]
  fn test_identifier() {
    assert!(can_parse(Rule::identifier, "a123_"));
    assert!(!can_parse(Rule::identifier, "123"));
    assert!(can_parse(Rule::identifier, "_039"));
  }
}

#[cfg(test)] 宣告這是測試用的模組,只有用 cargo test 才會執行,呼叫 cargo build 並不會編譯測試模組。
測試模組為被測試模組的子模組,地位就如同其他被測試模組中的檔案一樣,如果呼叫被測試模組中的原始碼,使用 super 先來到被測試模組的位置,再向下 use 其他檔案即可。不過測試模組有一些特別的權限,一般來說不加 pub 的函式都是 private ,在其他檔案無法呼叫,唯有測試模組可以。
再來就是盡情地寫測試,測試的函式要用 #[test] 標註,模組中也可以加上不是測試用的輔助函式,就如上文中的 can_parse。
初次寫的時候一定會覺得 #[cfg(test)] 跟 #[test] 有夠難打,這部分一定要加進編輯器的自動補齊裡面。

Rust 的整合測試位在整個模組之外,呼叫模組的函式時,就跟所有使用你模組的人一樣,也只能呼叫公開的函式。
這個功能我到現在還沒用過,畢竟我還沒寫出一個完整的模組過XDD
總而言之,我們在 src 資料夾之外建立一個 tests 資料夾,在這個資料夾裡面的所有原始碼都會是測試用的原始碼,每個檔案都會單獨進行編譯,這裡也不需要指定 #[cfg(test)],全部預設就是測試的原始碼。
要使用原本的模組必須用 extern crate 的方式引入,然後直接在 use 的時候,從整個函式庫的名字完整的打出來。
在 tests 裡面的測試也可以分門別類,建立測試的模組跟測試前設定的函式,不過我都還沒用過所以這裡就不多說了。

要執行測試,只需要使用 cargo test 即可,另外這裡有一些很常用的變體:

cargo test -- --test-threads=1
使用一個執行緒進行測試,讓測試的結果不會交錯輸出。

cargo test -- --nocapture
測試正常來說會把所有寫到 stdout 的內容全部截下來,普通是看不到的,測試失敗才會將該測試的內容印出;如果平常就想看到測試印出的內容,就要加上 --nocapture 選項;要注意的 cargo test 一定會把輸出到 stderr 的內容截下來,沒有什麼方法可以讓它吐出內容,所以測試裡唯一能用的真的就只有 println。

cargo test keyword
測試很多的時候也許只會想跑其中某些測試,這時可以下 keyword,只有測試名稱包含keyword 的測試才會執行,當然以函式名稱直接當作皮我就會執行一個測試了。

cargo test -- --ignored
有些測試可以加上 #[ignore] 標註這個測試現在還不用跑,下命令的時候可以加上 --ignored 來強制執行這些測試。不過我猜一般人測試都不會多到需要這個功能(或者說大家加測試的時候通常都是 code 寫完了,「原碼未到、測試先行」的狀況反而比較少)。

其實綜觀上面這幾個設定,多少可以看到一些測試設計上的準則,例如要能夠平行不相依,測試不管輸出,原則上所有測試都要通過,加 ignore 是非不得已等等;不過管他測試怎麼寫,能測出錯誤的就是好測試。

本篇文章內容主要來自 rust doc 的這兩篇:
https://doc.rust-lang.org/book/second-edition/ch11-02-running-tests.html
https://doc.rust-lang.org/book/second-edition/ch11-03-test-organization.html

2018年7月4日 星期三

不正經,關箱文

故事是這樣子的,2012 年8月資訊展的時候,因為舊筆電面臨解體,那時入手了一台新筆電,宏碁的 Aspire V3-571g,當時還寫了開箱文,算是 blog 非常早期的文章之一,後來好像也沒什麼人看這台筆電就過氣了QQ。
算算到今天,再過一個月也要滿六年了,老到我現在連官網上都找不到相關介紹了,大約兩個月前決定將他出售,主要理由有幾個:

第一是畢竟用的六年,累積下來的傷痕也不少,下面會詳細討論這點。
再來雖然已經拆開過兩次用空氣噴槍清除灰塵,但處理器附近的機殼打不開,散熱膏也沒有換,現在用起來容易過熱。太熱也容易影響效能,裝了 windows 之後有時還是覺得它不是 i7 的筆電。
還有一個原因是重量,那時要跑模擬買了運算力強的機種,因為科技進步的關係比舊筆電輕,但加上電池 2.2 kg 還是相對重了些。一方面現在出國機會增加,搭廉航的話行李克克計較,背包限制 7 kg,2.2 kg 就重很多了。另外也是老了,背這麼重都覺得累(yay,想當年背著它爬山都沒在怕的說owo。

用了六年也是傷痕累累,這裡就細數一下這台身上到底有多少傷:
  • 散熱孔:應該是撞到,有兩條塑膠散熱片有破裂,不過除了外觀之外沒什麼大問題。
  • 光碟機:光碟機外殼的塑膠片有時候原因不明脫出卡榫,要用力把它卡回去。
  • 鋼琴烤漆機身:很自然的有點傷痕。
  • 背板螺絲:因為塑膠機殼慢慢磨損,塑膠上的螺紋磨掉,背板螺絲就無法鎖上去,會很自然的掉出來,後來在那個螺絲孔外貼了一塊膠帶XD。
  • 螢幕轉軸:這是第二次打開機殼清灰塵時發現的,在那之前有一段時間,開螢幕的時候都會覺得有點卡,原因是螢幕的金屬轉軸已經生鏽,變得比較不靈活,這時候持續開關螢幕,不靈活的金屬轉軸會把應力傳給周圍的塑膠機殼,最後連接金屬轉軸的塑膠部分斷掉,這時候開關螢幕又變得不卡了呢 (不~~~。
  • 鏡頭:本來是鏡頭藍色故障,改用外接鏡頭;最後交貨前安裝了 Linux Mint ,變成直接讀不到鏡頭訊號(Input/Output Error)
  • 充電線:Acer 的老毛病,變壓器之後接電腦的細線,電線在內部斷掉,舊筆電也發生過同樣問題,最後去維修站買了新的充電線,偏偏細線連著變壓器,要買就要買一個新的變壓器。
  • 貼紙:左邊本來有五張貼紙,Intel、Acer 的都掉了(Intel 是第一個掉的 XD),Nvidia 兩張掉一張 ,只剩一張Windows 跟另外一張 Nvidia 的。右邊的規格貼紙開始刺手之後也撕掉了。

資料保密上,我是用 Archlinux 開機碟進去,然後下:
dd if=/dev/zero of=/dev/sda
把整個硬碟覆寫掉,這只是覆寫 0 ,專業點(有電子顯微鏡等級)還是有機會被讀出來,要求安全還是會推薦 0, 1 多寫個幾遍,或者直接用專門的 shred 把硬碟寫個三遍,但這些都很花時間,就算是 zero 覆寫 1TB 的資料也要大約三小時。
也有人推薦用 urandom 生成密鑰,然後用 AES 加密 zero 作為亂數:
dd if=/dev/zero bs=1M count=100 | gpg --symmetric --passphrase `dd if=/dev/random bs=4 count=8 2>&1 | sha256sum | head -c 64` - > /dev/null
反正 AES 一定超快,比硬碟還要快,不能直接用 urandom 是因為 urandom 慢很多,zero 可以到 100M/s,random 只有 20 M/s;話說回來就算是電子顯微鏡也不是一般人拿得到手的東西吧,更何況我的硬碟根本不值這個價www,如果膽子大一點,其實把硬碟刪掉之後,重新安裝一個全新的作業系統,應該就能防止大部分直接讀硬碟的方式回覆資料了(吧?。

出售方式是在 ptt 的 nb-shopping 版貼文,那裡的交易速度還滿快的,基本上一貼文就有很多人來洽詢。
最終成交價格是 6,800,當初買的價格是30,800 剩四分之一左右(不計通膨),或者稱二手損失(second hand loss)6.57 dB(誒,也有可能是我一開場喊價喊太低,導致後來二手價都拉不上來,不然以一台 i7 的電腦,加上 8G 的記憶體,也許能賣更好一點點,但反正這台六年老筆電加上各種傷痕,搖一搖都可以感覺到快解體的感覺,能賣這樣子,夠了夠了。
據強者我學弟 Shouko 的經驗,Mac 系列的二手損失好像都比較小,如果是新品話搞不好還有二手增益(好啦應該沒有…。
註:據強者我學弟 Shouko 給的參考:其實過了五年 Mac 的二手損失也超過 10 dB了,跟一般電腦似乎不相上下。

下面是交易時拍得一些照片:





總之,六年了。
感謝這台 Acer 筆電,百操不壞的硬碟(Hitachi 的XD)讓我亂刷了一堆 Linux,當初第一次從 Ubuntu 跳槽 Archlinux ,也是在這台電腦上做驗證。
研究所的時候用基本上是用桌電做硬體,用筆電寫程式;陪我寫了系統程式、編譯器作業,跟 jserv 大神的虛擬機作業大戰 300 回合,幫忙開發有上千星星的 github project,我在程式真正變強的過程上,這台 V3-571G 絕對不缺席。
在這台上面畫過百萬人看過的地圖,錄過沒什麼人看的 word 教學跟 git 教學 ,和我一起去了世界各地(雖然很重),參加過東京實習,陪我上山下海,三個東京市都去過(誒

為了驗證電腦各元件都沒問題,做最後的清洗之後裝了 Linux Mint,此文獻給我的 Acer V3-571G,希望你能幫助下一件使用者再戰十年。
敬禮 <( ̄ㄧ ̄ )

2018年6月16日 星期六

實作麻雀雖小五臟俱全的程式語言

故事是這樣子的,很早以前曾經看過 understanding computation 這本書,這本書第二章的內容,是利用操作語義(operational semantic)的方式,自訂一款極簡程式語言,非常簡單但已經有 if 判斷式,while 迴圈等功能。
最近剛修完 coursera 上面的 programming language,其中有一個作業也是用 racket 的操作語義定義一款程式語言, 這個程式語言更複雜,在資料結構上支援 pair -> list,同時還支援函式,這是之前 Understanding Computation 沒有實做的部分。
花了幾天的時間,把過去的 code 擴展了一些,在那上面實作了函式,在這裡就簡單介紹一下相關的內容,還有一些個人的心得,心得內容可能有對有錯,如果有錯就請路過野生的大大們指教一下:
要看到原本的內容,可以參考之前發在這個 blog 的筆記,還有 Github 上面的原始碼。
https://yodalee.blogspot.com/2016/03/rust-recursive-structure.html
https://github.com/yodalee/computationbook-rust/tree/master/src/the_meaning_of_programs/simple
本次修改的程式碼則可見:
https://github.com/yodalee/simplelang

所謂操作語義,就是明白的定義程式的各指令實際執行起來是如何,實際執行的機器當然是一台虛擬機,模擬執行的過程。原本書裡面有兩種操作語義的方式,一種是小步 reduce,每次將程式的內容變小一些些;一種則是直接 evaluate,有什麼結果直接計算出來。
要實作函式的部分,我把 reduce 的實作刪掉了,因為我實在不知道要怎麼用 reduce 實作函式,reduce 每次只會拿一個指令,然後把它縮小一些些,但在處理 function 上,只要進到 function 內部就要代換成另一個環境給它,步步執行的 reduce 做不到這點。
因為我的程式是來自於 Understanding Computation,所以裡面有些 code 像 while, sequence 是來自書中,其實我們有了 function ,就可以用 recursive 的方式取代 while,sequence 也可以適度修改,例如把 assign 變成如 let var = val in expression 的形式,在環境裡將一個值賦值給變數之後,以這個環境執行第二個 expression,就不需要 sequence 這樣的語法了;這部分大家自己知道就好。

看一個最簡單的例子:加法。
首先我們定義我們程式的單位:Node,要實作加法需要實作兩種 Node,代表數字和代表加法運算的 Node,接著我們就可以用 Node::number(100) 代表數字,用 Node::add(Node::nubmer(3), Node::number(4)) 代表加法;另外要實做一個 evaluate 函式,讀入一個 Node 並做出對應的操作,例如加法是分別把兩個參數都 evaluate 過,用 value 取值,用我們熟悉的加法加起來;其他運算如乘法、判斷用的大於、小於,都是類似的實作。

再深入一點要實作變數,例如 x = 10,就會需要環境 (environment.rs),它是 evaluate 需要的參數,實作是一個簡單的 HashMap,將變數名稱映射到相對應的 Node 上面,注意是 Node 不是實際地址,在我們的實作下輸入地址都是虛擬化為 Node;如此一來就能定義 Variable 跟 Assign 兩種 Node,分別會從環境中拿出值和將某段程式賦予給某個變數 。

再來就是複雜一些的 Pair, List,先定義 pair 以及兩個輔助用的 fst, snd Node,一個 pair 其實就是把兩個程式組合在一起,之後可以用 fst 跟 snd 取出第一個和第二個的值。
在這裡我們偷懶一下,重複使用 donothing 這個 Node 來表示 list 的結尾,一個 list 即是表示為許多 pair 的嵌套,最後一個 pair 的第二個 Node 必須是 donothing。
使用 iter 搭配 fold 就能輕易將 rust 的 integer vec 轉成我們這個程式語言中的 integer list,從最後一個元素開始,一個一個用 pair 與上一次的結果組合起來。
pub fn vec_to_list(v: Vec) -> Box {
  v.iter().rev()
   .fold(Node::donothing(), |cdr, car| Node::pair(Node::number(*car), cdr))
}
結果:
pair (1, pair (2, pair (3, pair (4, pair (5, do-nothing)))))

這裡有個小小的心得是,程式和資料其實是不可分開的,當我們在組合程式的過程,定義一些特定的組合方式就能將程式轉為資料,反之亦然;雖然這是我偷懶的關係,但 DoNothing 可以是程式,表示不做任何事情,也可以是資料,用來表示 pair 的結尾;程式和資料其實是一體兩面,端視我們執行的時候怎麼處理它。

我們來看一下函數,我們創了三個相關的 Node:
  • Fun:參數是一個 string 作為函數名稱,一個 string 作為變數名稱,還有一個 Node 是函式內部的程式碼。
  • Closure: 我一直很好奇 closure 到底有沒有標準中文翻譯,看到有些翻譯稱為閉包,Closure 是執行時遇到 Func 產生的東西,包含函式內的程式碼,以及 evaluate Fun 時的環境。
  • Call:以給定的參數傳給一個 Closure 並執行。
把 Fun 丟進 evaluate 會把當下的環境打包起來,生成一個 Closure;如果是 Closure 的話就不會特別做什麼。
Call 是最複雜的,它有下列幾個步驟:
  1. 把 closure 跟參數 evaluate 過,如果拿到的不是closure 就會發生錯誤。
  2. 將 closure 儲存的環境跟函式取出來。
  3. 在這個環境中加上兩個新的變數:一個是函數名稱指向自己這個 closure,這樣在函式內 Call 自己的名字就能做到遞迴呼叫的效果; Fun 的參數名稱指向傳進來的變數值。
  4. 用新的環境去 evaluate Fun 所帶的程式。
其實如果寫過 closure ,了解相關的概念之後,再去看下面這個 functionalC 的 repository 就滿好懂的了,如果要實作 Functional Programming 裡面的概念,函式都要自帶一個執行的環境,才能把函式像 first class member 一樣丟來丟去,由於 C 的函式並沒有強制要求這點,所以這一個 repository 裡面才會自己定義 closure 這個 struct ,基本上和我的定義一樣,都包含一個真正要執行的函式,還有執行的環境。
struct closure {
  void *(*fn)(list *);
  list *env;
};
再深入一點,假設程式一開始先設定 1000 個變數,然後再定義一個函式,這個函式要包含的環境是否需要這 1000 個變數?如果完整複製所有環境,太浪費空間了,實際上我們只需要記下函式中真正需要的變數即可,以下面這個函數為例子:
let x_add_y = Node::fun(
  "add1", "y",
  Node::add(Node::variable("x"), Node::variable("y")));
它接受一個參數 y 並將它和變數 x 相加 ,這時只要記錄 x ,其他變數都不需要保存,連變數 y 也不需要,因為 y 一定會在呼叫函式的時候被參數 y 給蓋掉(Shadow)。
變數 x 我們稱之為 free variable ,沒有被程式中的 assign 賦值或是以參數的方式掩蓋掉,它在執行時可視我們的環境設定自由變動。

我在 evaluate.rs 另外寫了一個 cal_free_vars 的函式來計算一段程式內的自由變數,它會生成兩個 HashSet 記錄出現過的變數跟自由變數,然後丟給 helper 函式處理。
大部分的處理方式都差不多,就是一路遞迴往下呼叫,像加法就是分別對兩個 Node 計算內部的自由變數;比較不一樣的是 Variable, Assign, Fun;在 Assign 跟 Fun 的地方,分別要把變數名稱、函數名稱跟參數名稱加到變數名單中,如果 Variable 取用的變數還沒在變數名單內,這個變數就是自由變數。
最後修改 evaluate Fun 的地方:
let free_vars = get_free_vars(self);
let mut new_env = Environment::new();
for var in free_vars {
  new_env.add(&var, env.get(&var));
}
用 get_free_vars 得到函式內的自由變數,生成一個新的環境,從現在的環境取得自由變數的值,用新的環境產生 closure;如果環境中沒有自由變數的值,環境的實作會直接崩潰,強制在執行函式的時候,環境中必須要有它的記錄。
以上大概就是一個有函式的程式語言會需要的實作,基本上這個語言能做到一些相當複雜的事,例如遞迴跟 currying 等,在 evaluate.rs 裡有一些相關的測試,例如階乘的遞迴實作:
fn test_simple_big_function_recursive() {
    let factor = Node::fun("factor", "x", Node::if_cond_else(
            Node::gt(Node::variable("x"), Node::number(1)),
            Node::multiply(Node::variable("x"),
              Node::call(Node::variable("factor"), 
              Node::subtract(Node::variable("x"), Node::number(1)))),
            Node::number(1)));
    let statement = Node::sequence(
        Node::assign("entry", factor),
        Node::assign("result", Node::call(Node::variable("entry"), Node::number(10)))
    );
    let mut env = Environment::new();
    println!("{}", statement.evaluate(&mut env));
    assert_eq!(3628800, env.get("result").value());
}
寫完這款程式語言,我開始覺得其實我是在寫個虛擬機,或者說有點像在實作一台電腦。
我們先把所有的資料:數值、真假值虛擬化為 Node 這個單位,一切的操作都是在 Node 上進行;就像真實的 CPU,也是將數字轉化為記憶體內部的 0, 1,在加法這個指令被執行的時候,會拿出記憶體的內容,通過一連串的邏輯閘變成輸出,再存回記憶體。 記憶體就好比我們的 Node,邏輯閘實作則是 evaluate,CPU 執行 x86 指令這款「語言」對應我們自訂的程式語言,只是CPU是真實的機器,我的程式是一台虛擬機 。
程式其實根基於數學,加法是一個概念,我們只是透過 CPU/電腦的實作,亦或是這篇文的操作語義,用虛擬機模擬出加法這個概念,所謂「程式語言」應是數學之神座下超凡的存在。 我們用上人類智慧的極致,打造 CPU,打造電腦,試著去追趕的這神聖的目標,追之求之,卻稱這款模倣的玩意兒為「程式語言」,何等自傲?想想不禁啞然失笑。

2018年6月9日 星期六

東京區知性學習之旅

故事是這樣子的,四月看完了上季霸權之一<比宇宙更遠的地方>,隨意瀏覽相關資料時,發現第三集的極地科學館在東京立川,而且初代南極探測船宗谷,一直都擺在台場的船之科學館進行公開展示,之前去的時候竟然都不知道,點進船之科學館的網站看到正好到 6/10 有特展,當下感到一陣衝動,就訂下五月底為期四天的東京宅爆聖地巡禮知性學習之旅。

機票:
機票選用香草航空,它的好處是有紅眼班,可以最大化旅行的時間效率
去程 JW100 0150 台北 -> 0610 成田
回程 JW107 2200 成田 -> 1255 台北
因為是五月初訂機票,加一件行李來回加起來 9000-10000,其實沒有特別便宜,頂多省個2~3000, 不過記得我跟朋友有這段經典的對話:
A: 都這個價格你幹嘛不搭華航或是長榮?
B: 因為傳統航空的時間都比較差。
A: 原來那個叫做時間比較差喔
反正現在年輕還可以燃燒新鮮的肝來換旅遊時間,再過個幾年大概就不能這樣玩了,特別是去程 0150 的飛機,我幾乎睡不到 2 hr 就被窗戶射進來的陽光照醒了,如果不是在 skyliner 上有睡一下,第一天早上搞不好只能呆在飯店大廳補眠。

住宿:
三個晚上的住宿,下塌ホテルマイステイズ上野イースト,離上野車站走路大概10分鐘,如果是地下鐵就是銀座線稻荷町站。
個人建議在東京玩的話,住宿可以選擇東京車站以北、上野、日暮里、王子、往西到池袋、往東到淺草。
東京車站附近因為比較貴通常不選;上野到日暮里是最理想的,因為從成田機場搭京成 skyliner,在東京的兩個停靠站就是上野跟日暮里,王子和池袋分別可以透過京濱東北線和山手線在15分鐘內抵達日暮里,轉搭 skyliner 非常方便,當然再遠一點也不是不行,山手線沿線時間算好就是了。

通訊:
因為這次可能會和同行者分開行動,所以我們分別申請了網路漫遊,我是使用中華電信 7 天 1G 168 的方案,不貴而且網路速度不差;有了這個基本上已經打爆市面上所有 SIM 卡了,不用插卡,價格也算實惠,1GB 省著點也不是一般人在一個星期用得完的量。

交通:
從成田進到東京市的交通,選擇京成 skyliner ,搭配後兩天的行程選配東京地鐵兩日券,地下鐵跟都營都可以搭,隨意轉乘任我行,如果沒有一日券就要注意在兩個系統間切換的話要另外付錢;另外通常從地下鐵系統換去都營都有一點距離,必要的時候請使用 hyperdia 這類路線規劃軟體,不然隨便走個 700 公尺轉車也不是不可能的。
還有手線跟中央線是 JR 的,換車也要付錢(不同系統的路線也不玩轉乘優惠那一套)。

大致行程與景點,我實際的路線有些許差異,第一天下午我跑去找之前來東京認識的人了,這裡綜合我跟同行者的行程,大致記錄一下:

第一天:
因為上午 06 才飛到,視飛機上的睡眠狀況而定,睡眠狀況不佳可以在飯店大廳多休息一下,排行程的時候有料到這個狀況,所以第一天行程只排台場,累的話就 1500 可以 check in 之後早早回飯店休息。

成田機場第三航廈飲食部:早餐
築地市場 :海鮮午餐,有興趣的話可以加逛築地本願寺。

台場:船之博物館宗谷開放<比宇宙更遠的地方>,特展到 6/10,除了前甲板和輪機室進不去,其他的地方包括主控室都有開放參觀,又是免費上船,值得一看。
回程的時候可以走一小段路去看台場的鋼彈,已經換成新機型了,待到晚上有燈光秀。
東京車站:<Lovelive Snow Halation>,這是我同學去的,不是他說我壓根不知道原來 snow halation 的場地是在東京車站。或者直接拉去秋葉原神田明神社<Lovelive>也可以,這次因為我們兩個都去過就跳過這個點。

交通除了台場之外,都搭配上面的地鐵/都營1-3日券;說實在台場沒有什麼特別好玩的東西,兩家交通線都不是都營或者地下鐵系統,百合海鷗線又超級貴,每次去都要大噴錢…後來就很不想去。

第二天:
淺草:雷門、淺草寺(嚴格來說 lovelive 也來過這裡),這裡大概是大眾景點了我們就跳過介紹吧

鷲宮:鷲宮神社<Lucky Star>,其實就是個鄉間神社,要不是 lucky star 我猜沒多少人會特別排這個點吧,此行真正的目的是東武動物公園,只是鷲宮正好就在旁邊就順便來一下

午餐在東武動物公園站吃連鎖餐廳解決。

東武動物公園<動物朋友>:來這裡看 fururu。來的時候剛好東武動物公園在跟動物朋友進行第二波合作到 7/1,各種動物都有插動物朋友的立牌,不過立牌的尺寸非常的小,有些還藏到非常奇怪的地方,一不留神就會錯過

秋葉原:Game Center 打 Lovelive AC 機台<Lovelive>:打機台也是很重要的,特別是 Lovelive AC 機台台灣都沒有進
簡單來說就是把手機的遊戲畫面變成機台畫面,打節奏改用按鈕打,再怎麼暴力打都沒關係(X,比較要注意的大概是介面設計,九個打節奏的按鈕只是選擇,要按右下角的藍色按鈕跟左下角的紅色按鍵才是確認跟取消;100塊錢可以打三首歌,非常便宜,機台也都有支援電子票證付款,推廣期間優惠五塊錢,想積少成多可以多多用電子票證付款。
由於不是每間遊戲中心都會有,最好先查閱官網稼動站舖一覽確認一下,當然秋葉原地區店舖是最多,這家沒有換下一家就是了。

交通在市內的移動,如早上上野到淺草,晚上去秋葉原,都用 skyliner 買到的一日券。
去鷲宮跟東武動物公園則是用東武鐵道,從淺草搭車。在曳舟跟久喜間要改搭急行,車程大約 40 分鐘。往久喜也有 JR 鐵道可以選擇,一般來說 JR 都會比私鐵便宜一丁點,這樣大家就自己選擇
晚上的行程也可以排晴空塔,這次我們都沒興趣所以沒有上去看夜景,但其實晴空塔的夜景應該是我看過數一數二好的。

第三天:立川

國立極地研究所南極、北極科學館<比宇宙更遠的地方>:來的時候剛好也遇到跟<比宇宙更遠的地方>的合作,不過距離合作開始已經有一段時間,有些立牌跟看板都開始撤掉了,這裡展品內容十分豐富,資料、模型、體驗一應俱全,又是免費入場,超級划算的展場景點。
午餐:三井立飛 lalaport,在單軌立飛站,因為有單日票怎麼搭都沒差,這裡週末人會非常多要注意一下(把它想成林口三井就是了)

 多摩動物公園,藪貓<動物朋友>:大老遠跑來這裡就為了看藪貓,如果要看他們的藪貓跳躍表演,就要關注一下他們的官網,左邊的日曆可以看每日的活動,下一次的表演是 6/23。
晚餐:新宿風雲兒沾麵,本次吃到最好吃的一餐,雖然要排一點隊不過非常值得。
新宿都廳夜景:看免錢的夜景,同時可以看到晴空塔跟東京鐵塔,就是視野被新宿附近的大樓所遮蔽,沒有晴空塔夜景那種一望無際的感覺,但反正是免錢的,不要要求太多。
新宿 SEGA 遊戲中心,Lovelive AC 機台<Lovelive>:因為六月開始有東條希生日活動,活動剛開放馬上來打XD。

立川其實不算近的景點,比一般人會去的吉祥寺、三鷹等再遠許多,遠到想用 JR 東京近郊一日券都沒辦法,只能乖乖刷電子票。我們是從上野先到神田,再換中央線快速到立川,單程 640 元,只要搭上急行或特快,基本上是一小時內可到。
在立川可以利用當地的立川 monorail,一日券搭配多摩動物公園入場券只要1000元,再搭去極地博物館絕對值回票價。

第四天:川越
這天只是找個一日遊景點填時間,倒是沒有一定要去哪裡。

川越冰川神社,關東有名的結緣神社之一,可以在這裡用釣魚抽籤,看看滿滿的風車。川越也有不少租和服浴衣體驗,不去關西也能體驗和服浴衣,算是東京近郊一個想體驗古風不錯的一日遊景點;午餐就在川越老街上的餐廳解決。
池袋,Lovelive AC 機台<Lovelive>,昨天還沒達成東條希活動的條件,今天怎麼能放過?再打兩場XD,打完就要回去啦。
成田機場第三航廈飲食部晚餐

交通我們從池袋出發,用東武東上線的 700 元一日券(或搭配公車 950 元),可以來回池袋跟川越間一次,同樣搭急行的話只要約 40 分鐘就會抵達川越,在川越就全程換步行。
回程就搭山手線到日暮里搭回程的 skyliner。

四天的行程大概就是這樣,算是會走滿多路的行程,必要時請評估自己腳力,特別是兩個動物公園佔地廣闊,東武動物公園從東走到西要 2km,應該一天破 10000 步都算滿簡單的。
在日本搭火車絕對不要搭各停,會快非常多,東京特別是如此,第二天到第四天的東武、立川、川越,搭上急行列車大約 40 分鐘都會抵達,如果搭各停可能就會超過一小時;不過通常(只是通常,不保證),他們都會安排各停列車在某一站等急行列車,這時只要走去對面換車即可。

ps. 以上照片部分由強者我同學 JJL 提供

2018年5月10日 星期四

使用 procedence climbing 正確處理運算子優先順序

上一篇我們說完如何用 Rust 的 PEG 套件 pest 生成簡單的程式碼分析器,但其實還有一些沒有解決的問題,像是 1 * 2 + 3 * 4 = 20,這是因為我們在處理 expression 時沒有處理運算子優先次序,只是從左到右掃過一遍。
真正的 parsing 要考慮運算子優先權跟括號等等,例如:
1 + 2 + 3 -> ((1 + 2) + 3) : Left associative(左相依)
1 + 2 * 3 -> (1 + (2 * 3)) : * 優先權高於 +
2 ^ 3 ^ 4 -> (2 ^ (3 ^ 4)) : Right associative(右相依)

在這裡我們要介紹 precedence climbing 這套演算法,假設我們已經有了 Term (op Term)* 這樣的序列,現在要將它 parse 成 syntax tree,可以參考這篇的內容

precedence climbing 其實不難,首先我們會先讀進一個 token 作為 lhs token,優先權為 0。
接著持續取得下一個 operator 的優先權和 associative,如果運算子優先權 >= 目前優先權,則:
right associative,以同樣的優先權,遞迴呼叫 parse。
left associative ,則以高一級的優先權遞迴呼叫 parse。

虛擬碼大概如下:
climb (min_precedence)
  lhs = get_token()
  while next_op precedence >= min_precedence
    op associative is left:
      next_precedence = min_precedence + 1
    op associative is right:
      next_precedence = min_precedence
    rhs = climb (next_precedence)
    lhs = op (lhs, rhs)

  return lhs
來個簡單的範例:如果所有運算子都是 left associative 、同樣優先權,例如 1+2+3+4,lhs 剖析出 1 之後,以高一級的優先權呼叫 climb,所有遞迴呼叫的 climb 都不會進到 while,而是直接回傳剖析到的第一個 token 給第一次呼叫 climb 的 while loop 作為 rhs, parse 成 (((1+2)+3)+4)。
如果是遇到更高權限的運算子,則呼叫的 climb 會進到 while loop ,把後面的 token 都消耗掉再回傳其 lhs,可能因為這樣因此取名為 precedence climbing。

當然,比起我們自己實作,pest 裡面已經幫我們實作好了,只是在文件裡面都沒有提及,我也是看了用 huia-parser 這個用 pest 作 parsing 的 project ,才知道原來有這個功能可以用。

廢話不多說直接來寫,首先我們要在 Project 中引入 pest 的 precedence climbing 實作:
use pest::prec_climber::{Assoc, PrecClimber, Operator};
我們需要建好一個 PrecClimber 的物件,這個物件會儲存一個 Operator 的 Vec,優先權依順序增加,如果有相同優先權的運算子,則用 | 連接,每個 Operator 中會保存 parser 中定義的 Rule 跟 Assoc::Left 或 Assoc::Right,例如我們的 simple 的定義(這裡我加上一個 op_sub 來示範 | 的用法):
let PREC_CLIMBER = PrecClimber::new(vec![
    Operator::new(Rule::op_lt,  Assoc::Left),
    Operator::new(Rule::op_add, Assoc::Left) | Operator::new(Rule::op_sub, Assoc::Left),
    Operator::new(Rule::op_mul, Assoc::Left)
])
要剖析的時候則是呼叫 PrecClimber 的 climb 函式,它的型態乍看之下有點複雜:
pub fn climb<'i, P, F, G, T>(&self, mut pairs: P, mut primary: F, mut infix: G) -> T
where
    P: Iterator<Item = Pair<'i, R>>,
    F: FnMut(Pair<'i, R>) -> T,
    G: FnMut(T, Pair<'i, R>, T) -> T
其實也不難理解,它只是將上面的 precedence climbing 虛擬化為幾個函式:
pairs: P 是全部要走訪的 (term (op term)*) iterator。
primary: F 會吃一個 term 將它轉為剖析後的結果。
infix: G 為結合方式,拿到兩個剖析後的結果跟一個運算子,將兩個結合起來。

這裡的 primary 其實就是我們寫過的 build_factor:
fn build_factor(pair: Pair<Rule>) -> Box<Node> {
    match pair.as_rule() {
        Rule::variable => Node::variable(pair.into_span().as_str()),
        Rule::number => Node::number(pair.into_span().as_str().parse::<i64>().unwrap()),
        _ => unreachable!(),
    }
}
infix_rule 其實也只是把我們之前 build_expr 的東西給取出來:
fn infix_rule(lhs: Box<Node>, pair: Pair<Rule>, rhs: Box<Node>) -> Box<Node> {
    match pair.as_rule() {
        Rule::op_add => Node::add(lhs, rhs),
        Rule::op_mul => Node::multiply(lhs, rhs),
        Rule::op_lt => Node::lessthan(lhs, rhs),
        _ => unreachable!(),
    }
}

build_factor 會吃進 token,將它轉為我們 AST 的型態 Box<Node>;infix_rule
使用 climb ,當我們拿到一個 expression token,要做的就只剩下把它丟給 climb 去爬,into_inner 將 expression token 轉為下層的 token iterator;:
// pair.as_rule() == Rule::expr
pub fn climb(pair: Pair<Rule>) -> Box<Node> {
    PREC_CLIMBER.climb(pair.into_inner(), build_factor, infix_rule)
}
最後一小步,我們想要避免每次要 climb 的時候,還要重新產生 PREC_CLIMBER 這個物件,反正語法固定之前 PREC_CLIMBER 沒理由會變動,因此我們用了 lazy_static 這個套件,將它變成 static 的物件:
#[macro_use]
extern crate lazy_static;

lazy_static! {
    static ref PREC_CLIMBER: PrecClimber<Rule> = build_precedence_climber();
}
fn build_precedence_climber() -> PrecClimber<Rule> {
    PrecClimber::new(vec![
        Operator::new(Rule::op_lt,  Assoc::Left),
        Operator::new(Rule::op_add, Assoc::Left),
        Operator::new(Rule::op_mul, Assoc::Left)
    ])
}
這麼一來我們的 simple 剖析器就完成了,現在 1 * 2 + 3 * 4 會是正確的 14 了,可喜可賀可喜可賀。

2018年5月6日 星期日

使用 rust pest 實作簡單的 PEG simple 剖析器

上一篇我們看了 PEG 相關的內容,這篇我們就來介紹該如何用 PEG 寫一個簡單的剖析器,當初會開始這系列文章,是因為自己 computation book rust 實作中,並沒有像原作者的 ruby 實作,有用 treetop 這個 PEG parser 寫一個剖析器,剖析文法變成裡面的程式,例如 simple, regupar expression, pushdown automata, lambda calculus 等等,最近想說把這部分補上,結果在第一關 simple 上就研究了好一陣子。
本來預估一個星期寫完,根本太樂觀,回家晚上能自己寫 code 的時間估太多,到現在應該已經快一個多月了,才有初步的結果,當然我們也可以說原因是 rust pest 沒有 ruby treetop 這麼好用(炸。

要使用 rust pest,首先是透過 cargo 安裝,為了這點我一開始先花好一陣子,把整個 project改寫成 cargo 管理,詳見這篇文章,之後才開始相關的實作,整個完成的程式碼可以看這裡
接著就是安裝 pest,在 Cargo.toml 中加上:
[dependencies]
pest = "^1.0"
pest_derive = "^1.0"
pest_derive 為 pest 剖析器產生器,他會分析你指定的 PEG 文法,生成對應的剖析規則跟剖析器;pest 則是引入剖析後生成的資料結構,兩個都要引入。
接著在原始碼中加入:
#[cfg(debug_assertions)]
const _GRAMMAR: &'static str = include_str!("simple.pest");
#[derive(Parser)]
#[grammar = "the_meaning_of_programs/simple.pest"]
struct SimlpeParser;
_GRAMMAR 是用來提醒編譯器,在 simple.pest 檔案更新的時候,也要觸發重新編譯(不然就會發現改了文法,cargo build 不會重新編譯),該 pest 檔的路徑是相關於目前的原始碼檔案;grammar 後的路徑則是相對於 src 資料夾,我試過不能用 .. 的方式回到 src 上一層目錄,grammar 檔案內容就是PEG 的語法,在編譯的時候會被 pest 轉換成 parser 的實作儲存在 SimpleParser 裡面。

pest 的語法基本上跟 PEG 沒有太大差別,在文法檔案中,就是 rule = { rule content } 的方式去定義規則:
  • 匹配字串使用雙引號包住,用 ^ 設定 ASCII 為無關大小寫,例:op_add = { “+” }, const = { ^”const” }
  • 一定文字範圍的用單引號搭配 ..,例:number = { ‘0’..’9’ }
  • 選擇規則用 | ,例:alpha = { ‘a’..’z’ | ‘A’..’Z’ }
  • 連結規則用 ~,跟 PEG 定義用空白直接連接不同,空白在 pest 用做排版,例:stat_assign = { variable ~ “=” ~ expr ~ “;” }

定義規則中,可以用到其他規則,例:factor = { (variable | number) }。
另外有一些特別的規則,包括:
  • whitespace:whitespace 裡指定的字串,會自動在 ~ 連結的位置中插入 (whitespace)*,平常不需要特別指明處理 whitespace,例如上面的 stat_assign 就變得能夠剖析 ”foo = 123” 而不只是 “foo=123”。
  • comment:comment 會在規則和子規則間被執行,不需特別指明。
  • any:匹配任一字元,對應 PEG 中的 .。
  • soi, eoi:對應匹配內容的開始和結束,這兩個還滿重要的,以之前的 S = A, A = aAa | a 為例,如果直接寫 S = { A },那去匹配一個以上的 a 都會匹配成功,因為我們沒指定 S 之後要把整個字串匹配完,正確的寫法是:S = { A ~ eoi }。
  • push, pop, peek:分別 push/pop/peek 字串到 stack 上面,push(rule) 將 rule 匹配到的字串送到 stack 上; epop/peek 會用 stack 內容的字串去做匹配,但 pop 會消耗掉 stack 的內容;這個規則我還沒有實際用過,不確定哪裡會用到它。

由於 pest 的文法規則都會被轉成一個 rust enum ,所以 rule 的取名必須避開 rust 的關鍵字,我在這裡是加上一些前綴或後綴來迴避,例如 stat_while;規則在剖析過後會生成對應的 token,內含剖析到的字串,如果是直接實寫的文字就不會產生出結果,這部分等等會看到。
  • 用 // 在規則中寫註解。
  • PEG 中 ?+* 三個符號,也是直接加上,有需要特別分隔的地方,可用小括號分開,例:number = @ { (digit)+ }、stats = { (stat)* }
  • e{n},e{,n},e{m,},e{m,n}:分別是 n 個,至多 n 個,m個以上,m至n個匹配。
  • PEG 的 & 跟 ! predicate 也是直接使用(不過我沒用過XD)

每個規則前面可以加上四個 optional modifier,分別如下:
  • Silent _ :剖析的時候不產生這個規則對應的節點,例如我的 factor 是:factor = _{ (variable | number) },那在剖析完之後,會直接跳過 factor,產生 variable 或 number 的節點。
  • Atomic @:這跟上面的 whitespace 有關,像我的 variable 寫成 variable = { (alpha) ~ (alpha | digit)* } ,豈不是可以接受 “a 123” 這樣奇怪的變數名?這時候就用 @ 確保規則中不執行 whitespace 規則。
  • Compound-atomic $:這跟 atomic 一樣,只是規則的子規則,例如 expr = $ { “-” ~ term } ,則 term 仍然適用 whitespace。
  • Non-atomic !:因為一個 atomic 規則下所有規則都會是 atomic,可以用 ! 來停止這樣的效果。

我們可以把上面這些都綜合起來,寫出一個極簡的 simple language parser,當然這實在是太簡單了,簡單到會出一些問題:
alpha = { 'a'..'z' | 'A'..'Z' }
digit = { '0'..'9' }

whitespace = _{ " " | “\n” }

variable = @ { (alpha) ~ (alpha | digit)* }
number = @ { (digit)+ }

op_add = { "+" }
op_mul = { "*" }
op_lt  = { "<" }
op_binary = _ {op_add | op_mul | op_lt }

factor = _{ (variable | number) }
expr = { factor ~ (op_binary ~ factor)* }

stat_assign = { variable ~ "=" ~ expr ~ ";" }
stat_while = { "while" ~ "(" ~ expr ~ ")" ~ "{" ~ stats ~ "}" }
stat_if = { ("if" ~ "(" ~ expr ~ ")" ~ "{" ~ stats ~ "}" ~ "else" ~ "{" ~ stats ~ "}" ) |
            ("if" ~ "(" ~ expr ~ ")" ~ "{" ~ stats ~ "}") }
stat = _{ ( stat_if | stat_while | stat_assign ) }
stats = { (stat)* }

simple = _{ soi ~ stats ~ eoi }
simple 就是整個剖析的進入點,在原始碼中呼叫 SimpleParser 的 parse 函式,對字串進行剖析,參數要代入想要剖析的規則和內容,這裡我們用 expression 來舉例,畢竟寫過 parser 就知道 expression 算是最難爬的東西之一,通常搞定 expression 其他都是小菜一碟:
let pair = SimpleParser::parse(Rule::expr, "1 * 2 + 3 * 4")
                .unwrap_or_else(|e| panic!("{}", e))
                .next().unwrap();
parse 之後會得到一個 Result<Pairs<R>, Error<R>>,表示是否成功,這裡如果不成功我們就直接 panic ,成功的話取出 Pairs,用 next unwrap 將第一個 Pair 取出來,也就是剖析完的 Expr Token,因為剖析失敗的話在剛剛的 Result 就會得到 Err 了,這裡我們都可以大膽的用 unwrap 取出結果。
Pair 有幾個函式可呼叫:

  • pair.as_rule() 會得到剖析的規則,此時的 pair.as_rule() 為 Rule::expr,這可以用來判斷剖析到什麼東西。
  • pair.into_span() 會取得 token 的範圍資訊。
  • pair.into_span().as_str() 會得到 token 匹配的字串內容,像在處理 assign的時候會用這個拿到變數名稱 。
  • pair.into_inner() 會拿到下一層的 Pairs,以 expr 來說,會對應到 { factor ~ (op_binary ~ factor)* },之前有提過字串並不會產生 token,上面的 stat_if, stat_while 就是例子,在 into_inner 的時候,括號、角括號等只是匹配,但不會有 token 產生。

在這裡我們把 expr 的 Pair 直接丟下去給另一個函式 build_expr,由它把 expression 剖析成 simple language 的 Node,它會先用 into_inner 叫出 expr 的內容物,然後依序取出左值、運算符跟右值並建成 Node Tree;可以從 op 的處理方式看到如何使用 as_rule() 來看看剖析到什麼。
fn build_expr(pair: Pair<Rule>) -> Box<Node> {
    let mut inner = pair.into_inner();
    let mut lhs = build_factor(inner.next().unwrap());
    loop {
        let op = inner.next();
        match op {
            Some(op) => {
                let rhs = build_factor(inner.next().unwrap());
                lhs = match op.as_rule() {
                    Rule::op_add => Node::add(lhs, rhs),
                    Rule::op_mul => Node::multiply(lhs, rhs),
                    Rule::op_lt  => Node::lessthan(lhs, rhs),
                    _ => unreachable!(),
                }
            },
            None => break,
        }
    }
    lhs
}

因為我們沒有處理運算符優先順序的問題,所以 1 * 2 + 3 * 4 的結果會是 20,如果要正確處理就需要實作 precedence climbing 之類的方法,不過這個留待下篇文章再來解決這個問題,至少我們已經能 parse 一個 simple program,自動轉成 Rust 的 simple AST 了(其實原作者的 treetop parser 也沒有考慮這個問題,所以其實我們可以裝傻當作沒這回事XD)。

以上大概就是 pest 的介紹,基本上使用 pest,一個規則用一個單獨的函式來處理,就能把每次修改的範圍縮到最小,熟練的話應該能在短時間內魯出一個基本的 parser 來用。

2018年5月1日 星期二

剖析表達文法 PEG 簡介

剖析表達文法 PEG 為 Parsing Expression Grammar 的縮寫,2004 年由 Bryan Ford 教授所提出,相對於一般在編譯器課上教 parsing 所用的 CFG (Context Free Grammar) ,已經被鑽研數十年之久,可說是相當年輕的形式化語言。

其實 PEG 和 CFG 在本體上幾乎沒有不同,從創作概念上來看,CFG 著重的是語法的產生和定義,PEG 則專注在剖析語法上,找資料時就有在中國的知乎論壇上看到這句:「CFG 作為產生式文法,很適合用來生成內容丰富多彩的垃圾郵件」不禁會心一笑,過去定義程式語言,都是先教 CFG,通常都會有這麼一句:「寫出 CFG 就定義了一個程式語言」
生成文法的切入點在<產生>,我們定義產生文法來定義語言,討論各種文法的強度,看看它們能產生什麼,不能產生什麼;用這套文法產生出來的東西,管它到底多亂多醜多長,都符合這個文法(有點回文),從 CFG 的觀點來看,先想好怎麼產生程式語言,接下來再來看怎麼剖析它,然後再討論 LL, LR 等等剖析方法。

PEG 則沒有這麼繞圈圈,PEG 本身即是 parser 的抽象定義,PEG 定義的 parser 會由一條一條規則組成,每條規則會去匹配輸入,如果成功則消耗輸入,失敗則不會消耗輸入。
PEG 的 terminal 規則如下,大致和 CFG 相同:
* 字串即匹配字面上的字串
* eps (ε) 匹配空集合,永遠成功且不消耗輸入
* . 匹配任意字元
* [abc] [a-z] 表示符合集合中任一字元

Non-terminal 的規則是跟 CFG 較多不同之處:
* PEG 同樣提供來自 regexp 的 ? + * 三個結合符號,也就是零或一個、一個或多個、零至多個,全部都是 greedy。
* e1 e2:依序剖析 e1,在剩餘的字串上剖析 e2,如果 e1, e2 任一剖析失敗則整個規則都失敗(記得如果規則失敗則不會消耗 input)。
* e1 / e2:嘗試 e1,失敗的話就換 e2,這是 PEG 跟 CFG 最大的不同之處,CFG 的接續規則是沒有先後次序的,雖然 CFG 的剖析器,通常為了方便會加入一些先後次序來處理歧義性的問題,例如對 dangling else 採用 shift over reduce ,把多的 else 先拉進來,但在 PEG 中這樣的歧義性可以很簡單的用 / 來消除。
S <- “if” C “then” S “else” S / “if” C “then” S
* 另外有兩個 And predicate &e 跟 Not predicate !e:可以向前看之後的內容是否匹配/不匹配 e,但無論成功或失敗,predicate 都不消耗輸入;理論上的 PEG predicate 可以擁有無限的 predicate 能力,但在實作上應該都有一定的限制。

下面可以舉一些跟 non-terminal 有關的例子:
a* a:永遠會失敗,e1 會吃光所有的 a,造成 e2 失敗。
!”_” .:匹配除底線外任意字元。
“>” / “>=”:是個錯誤的寫法,要不是失敗就是 e1 成功消耗 > 字元,第二個 >= 只是裝飾用的,在運算符的匹配上,應該要依序從長到短排序:>> / << / >= / <= / > / </ =。
另外我查 PEG 時也有遇到一些詭異的文法剖析結果,例如參考資料舉出的:
S -> A $
A -> "a" A "a" / "a"
PEG 會很見鬼的匹配 2^n-1 個 a,以 5 個 a 的狀況,後三個 a 會剖析為 A = aAa,但下一步合併失敗,導致第二個 a 被剖析為 A = a,最後只剖析了前三個字元:失敗。

PEG 的好處在於簡單漂亮,每個 PEG 都是無岐義的,實作上一條規則正好對應一條處理函式,類似 parser combinator,由上而下一跟呼叫:parseExpr -> parseTerm -> parseFactor -> identifier / number 這樣的剖析順序,可以把剖析器寫得漂亮好改;也因此一些語言都有開始支援 PEG parser generator:例如 rust 的 rust-peg, pest,haskell 的 peggy,Dlang 的 pegged 等等。
PEG 並不是單純 CFG 的超集或子集,事實上兩者的概念不太一樣,我建議不要把兩者混為一談,例如知名的 a{n} b{n} c{n} 這個 CSG(n個a 接 n個b 接 n個c,這用 CFG 是產生不出來的),卻可以用 PEG 來剖析;目前是否 CFG 產生出來的文法都能用 PEG 來剖析還是一個開放問題,就留給有興趣的人去挑戰了。

會寫這篇文章,因為最近正在試著用 rust pest 寫一個簡單的剖析器,發現有關 PEG 的中文討論相當的少,就先整理一篇,其實目前要查中文,用「解析表達文法」查到的比較多,但台灣的 parse 就是剖析,所以我標題還是下「剖析表達文法」; pest 的部分因為文件有點少還在卡關當中,下一篇應該會整理相關的用法,然後用它寫個超簡單剖析器。

參考資料:
https://github.com/PhilippeSigaud/Pegged/wiki
本文基礎,大部分的例子都是裡面來的 :P
http://qnighy.hatenablog.com/entry/2015/11/12/162424
神文大推(日文就是…),用了 haskell monad 實作了 CFG, PEG parser,兩者的差距只在 Maybe 跟 list 的差別,現在還在研究當中。
https://www.zhihu.com/question/28525605
一些 CFG 跟 PEG 的比較,算簡單易懂,可以看過去

附註:
S -> A $
A -> "a" A "a" / "a"
這個問題,後來我有想通了,先假設 k 個 a 的時候是可以匹配的;在輸入 n 個 a 的時候,每一個 a 都會率先匹配為 aAa 的前一個,最後 k 個 a 則會匹配為 A,但後面已經沒有 a 了,因此倒數 k+1 個 a 開始的 A = aAa 匹配失敗,匹配為 A = a,接著如果要匹配成功,就要前後都有 k 個 a 才行。
得到結論:k 個 a 匹配則下一個為 2 * k + 1。

2018年4月27日 星期五

西方憑什麼

每天上下班搭公車通勤,都會看書打發時間,滑手機的話字太小,聽音樂的話公車太吵,發現看書還是最理想的。剛好公司又有借書制度,能看的書多不少,最近看完的是這本<西方憑什麼>,來寫篇心得感想。

<西方憑什麼>想要回答的是一個存在百年的謎題,1840年的甲午戰爭,為何是英國打贏中國,是西方打敗東方,而不是中國艦隊來到泰晤士河大敗英軍?這個問題看似簡單,因為英國發動了工業革命,但若接續問:為何是英國而非中國發動工業革命,可就沒那麼容易回答了。
一般面對這個問題有兩種答案:古早決定論和一時碰巧論。
前者就如<細菌、槍砲與鋼鐵>一書的論點:因為西方條件硬是比較優良,有更多大型動物提供獸力,有更好的氣候,更好的地形,因此發展較為迅速;或者有些論點覺得西方人比較聰明,注定就是西方要發動工業革命;一時碰巧論則認為西方只是一路運氣好,東西方同樣有機會發現新大陸,只是西方運氣好;東西方都能發動工業革命,只是西方運氣好。

作者的立論則認為兩種都不對(當然,不然他寫書幹嘛),作者在前兩章,先回答一個問題:何謂超前,先回答何謂領先,才能評斷領先的原因,否則問西方何以超越東方只是在打高空。
由於過去的狀況都需要用考古跡證來反推,時間會洗掉一切細節,放大反推的困難,又如發掘到文化遺跡,又要如何從文化去分辨優劣?要來辯論拼音字比方塊字還要先進嗎?這種東西根本沒標準答案。
作者選擇了四個指標,都是足夠反映社會強度、容易量化比較、從考古、歷史文件容易推算的項目,包括:地區最大城市人口數、社會平均取用能源、最大軍事能力、資訊處理能力。四項指標多少有點相關,要取用足夠的能源(包含從食物攝取能量)才有多餘的能量分給城市人,有足夠的人口才有足夠的軍事力,足夠資訊處理能力才能撐起大城市。
作者將這四個指數套到東西方文明上,畫出東西兩文明的量化社會發展曲線,這和我們用歷史常識畫出來的曲線驅勢差不多:一如東方從遠古一路上升到漢,五胡十六國時期下跌,唐宋升高,滿清帝國又再次上升,直到近代工業革命後呈指數上升。
作者由兩條曲線,驗證古早決定論確實有其根據,因為西方從美索不達米亞開始,無論是聚落的形成,農業的發展,城邦與國家的興起造成的分數上升,都領先東方 2000 年以上;但也有足夠的證據反駁古早決定論,例如唐宋時期東方一路超過西方,西方要等到東方滿清帝國時代,工業革命前夕才再次超車。

作者論點也很常識:大體來說社會發展伴隨著人口上升,引發資源短缺與社會動盪,各個國家都有發展天花板,如漢朝、羅馬,都無法突破發展天花板而面臨下跌,但若抓住時機突破天花板,無論是取用全新的資源,制度上的變革,突破之後就能再次引領上升,例如晉將長江一帶開發為沃土,成為唐宋盛世的基礎;工業革命解放化石能源,其成果自不待言。
作者多少也是抱持古早決定論的,西方之所以能搶先發現美洲,建立大西洋經濟圈,純粹就是大西洋比太平洋還要窄,西歐又有繞過威尼斯、土耳其到印度的動機,如果給東方多個兩百年,也許也能建成太平洋經濟圈,發展工業革命,當然歷史不會有如果,搶先解放化石能源的西方自此統領世界到今天(作者持悲觀論,因為沒有動機,就算沒有西方打擾東方也要許久才會嘗試橫渡太平洋)。

我認為作者在本書最大的貢獻,在於提供一個足夠客觀的量化證據,讓古早決定論或一時湊巧論,都能在這個量化證據上進行辯駁。內容反而不那麼重要,剩下幾章作者都在說故事,將他的論點代入歷史證劇,還原當時的社會概況,可以當成小說一樣讀過去。
最後一章作者試圖預測未來世界的走向,以及西方是否能持續領先,但呈現出來的效果比較像「我大膽預測,明天的股票不是漲就是跌」過去各文明都曾在不同的地方遇上瓶頸,誰能預料現代社會不會在 1000 分遇到另一個上界?從分數可以看出古文明遇上什麼困難,卻無法預知未來,飢荒、天災、戰爭、疾病一直是歷史上的常客,受惠於科技進步,這些問題看似都能解決(也許因為人類的愚蠢,戰爭例外),但又有誰能預測下一場巨大災害?人類歷史大多都是矇眼爬山,在無限的未知中尋求道路,然後祈禱老天保佑,現在也差不了多少。

看完本書籍是有些感想,首先如作者所言,英雄和天才並不存在,社會的發展基於社會集體,找個社會隨機抽 100 人出來,各類型的人的比例都差不多。工業革命之所以在英國,並不是瓦特有三頭六臂,而是英國社會正好在煤礦坑排水問題上,需要比獸力更高階的能源,鐵器製造和生產也正好跟上蒸氣機所需;前導的科學革命也是因為當時跨大西洋經濟體成形,需要新的知識來解決全新的問題,例如在海上測定經度,需要以機械化、科學化的方式去觀察自然的運作。
歷史就是一連串的見神殺神、見佛殺佛;何以秦朝和羅馬幾乎在同時出現君主集權的國家?為何春秋和希臘的哲人們,會同時發展出眾多不同的治國思想和哲學?明鄭和西歐會同時向海洋前進?為何阿拉伯會在天文學上保持領先直到 16 世紀?
愛因斯坦不會比亞里斯多德聰明,張衡也不會比沈括差太多,社會遇到什麼問題,大家就努力突破,僅此而已。
所以說,問對問題,創造解決問題的環境,比生出一個兩個天才更重要;隨著社會更複雜,未來更重要的是組織和打群架,不要期待天才解決問題,一個人甚至一百人都不是關鍵,組織和環境才是;同時不要害怕嘗試,舊方法解決不了新問題,嘗試新方法、新制度才有突破的可能,曾經我們以為採集勝過農業、以為分封勝過帝制、以為女性應該關在家裡不事生產,如今都在實驗之後被證明優劣,裹足不試的國家無法引領未來。

另外,我曾經聽過許多都市傳說,主張人類文明的跳躍,都是由外星人帶來,像是金字塔、積體電路、IBM 5100 等等,實際上歷史和文明都是一層層的累積,就如同考古的沉積層,從底層的石器到淺層的鐵渣,只不過越接近現代,累積愈為迅速。
重大發明看似跳躍,但我們仍能從小型、中型、大型金字塔;從一開始的鍺電晶體、矽電晶體到積體電路,看到背後的進展歷程和解決思維,瓦特也不是發明蒸汽機,而是改良無效率的蒸汽機(Miner’s friend),所謂外星人的巨大黑石板,純屬無稽之談。

這裡也能延伸兩個想法,第一個是所謂的<全新工作>,農場文常說未來十年會有多少工作被消滅,認為現在人應該為明日的工作做好準備,但現在我覺得:所有的全新工作,其實都是基於現有工作難題而來,資料科學是要處理從雲端服務收集到的大量資料,積體電路是為了解決大量電晶體生產除錯困難的問題;沒有所謂的為未來工作做準備這回事,預測未來工作最好的方式就是把舊有工作做到最好,解決痛點時就成為新的工作了,連現有工作的痛點在哪都不知道,以為新工作會突然噴出來,無異守株待兔。

第二就是所謂的彎道超車,最近中興晶片事件鬧得很大,正顯出工業革命以降,歐美累積出的知識、技術和資本是如何的深厚,近二三十年中國的快速成長和歐美的金融風暴,再再都予人西方已日薄西山之感,但現實正好相反,人們(有時包括西方自己)都很難意識到西方手握的資源是何等龐大,即便西方成長率不如東方各國,乘在巨大的基礎上,還是能不斷保持領先。
翻翻中興相關的文章就能看到,美國的科技大廠一年砸了多少錢去做研發,藉此保持在技術上的領先,技術上面又有連帶的生態系,光一條鏈就把你壓的死死的,超車何等困難。
當然這樣還是太悲觀了,其實現代社會產業鏈之複雜,在林林總總的產業總有不同的問題等待解決,只要能在一個領域把事情做好,就有領先的可能性,好比如台積電把做晶圓製造這件事做到最好,假設我們先不想要在整個科技領域上全面性的超車,只要加入世界產業鏈裡面,到處都有小螺絲的位子(好吧也許這對某些國家來說有些困難)。

如果真的想要在領域當霸主,也不是這樣喊打喊殺就能成事,而是耐著性子去重新打造輪子,重打輪子不是隨便打,他們一定是看到需要更好的地方:ARM 提供嵌入式系統更省電跟精簡的設計;LLVM 提供更模組、更有秩序的編譯環境;Mozilla Servo 大量使用 06 年後 CPU 平行化的功能,加速網頁瀏覽;總是有那些小小的利基點,能夠做出一點點的差異,讓後繼者在某些領域茁壯,進而挑戰現有霸主的地位。
當然可以聚焦在現有系統的微幅改進,不敢去想下一代的東西,只是這樣註定做不出 ground breaking 的東西;等到 ground breaking 的東西出來了,驚訝之餘也就只能徒呼負負了。
重新打造輪子必定是個死傷泰半……不!是個<只有一位能活下來>的行為,但即便是最後沒人用的輪子,也會在打造的過程中習得<如何打造輪子>的技能,也許某一天這項技巧就能用來打造出真正能用的輪子;真的就是那句「豔陽高照,練兵完畢」,連兵都不想練,哪能期待看到豔陽?

本來想打個簡單的心得,結果不小心打了超長一篇……,混合了書本介紹、心得和一些過去的發文。
這本書以知識密度上來說有點不足,其實沒有很推,由於我們本身熟於東亞歷史,全書一半的內容只是稍稍重複課本內容,如果真的有閒的話,拿來當故事書看看,溫習一下中西歷史也不錯就是了。

2018年4月6日 星期五

整理 rust module 的安排方式

故事是這樣子的,兩年前因為傳說中的 jserv 大神的推薦,我讀了 Understanding Computation 這本書,讀完覺得學到很多東西,深受啟發;後來大概花了兩個月的時間,用Rust 重寫了裡面所有的範例程式碼,目前在 github 上查了一下,我應該是除了原作實作之外,實作最完整的一個,可謂一人之下,萬人之上(誤。
最近因為一些原因,把之前的實作打開來看,馬上關上,假的!趕快在筆電前面打坐。
當初到底怎麼寫這麼醜,還查到有些章節的內容沒有實作完,那時候可能太難不會寫,先跳過結果就忘了QQ……最近這一兩個禮拜陸續花了一點時間整理。

這次整理的一大修正,是把本來是散在各處的原始碼,重新照 rust 慣例統整到 src 資料夾下面,並使用 cargo 管理,帶來的好處包括有:可以一次 cargo build 編譯所有程式;引入 cargo test 代替本來編譯成執行檔用 println debug 的實作;在各章的內容間重用 module ,提升重用比例;另外也能使用網路上其他人寫的 Rust module(其實這才是原初整理的目的)。
例如在我之前實作的程式碼,在寫 finite automata 時,dfa, nfa 各自有一個實作,使用 u32 作為狀態;但到了 regular expression 的時候,為了產生 nfa 就不能用 u32 作為狀態,於是我複製了一版 nfa,改成用 object pointer 作為狀態,兩者程式碼的重複率就非常高,這次也一併改成 generic 的 nfa 實作,兩邊就能分享同一套程式碼。

本來以為整理就是把程式碼搬一搬,也差不多就結束了,結果不是(當然有一部分是我自己蠢),但也是因為這個機會,弄懂的 Rust 的 module 系統,這裡作個記錄。

在一個 rust project 當中,最重要的都放在 src 資料夾下面,包括要編成函式庫或執行檔的原始碼都在這裡,其他像編譯結果的 target、文件的 doc、測試的 test ,相對來說比較沒這麼重要(好啦還是很重要,只是不是本文要討論的重點)。

rust 的編譯是由 cargo.toml 所驅動,一個 rust 模組只能編出一個 rlib,由 cargo.toml 的 [lib] 所指定,例如我這個專案指定 library 名稱跟路徑如下:
[lib]
name = "computationbook"
path = "src/lib.rs"
如果不設定的話,cargo 會預設編譯 src/lib.rs,並自動從資料夾名稱產生 library 名稱;這個 library 名稱非常重要,先把它記著。

函式庫的實作就在 lib.rs 裡面,包含函式庫所有的函式,可以加上 pub 讓外界可以取用;當函式多的時候,就開始需要幫他們分門別類,也就是 rust 的 module:
fn libraryfun () {}
mod modulename {
 fn libraryfun () {}
}
用起來有點像 C++ 的 namespace,上面例子中,兩個 libraryfun 是不會衝突,一個是 libraryfun,一個是 modulename::libraryfun。
然後 Rust 以它預設什麼都不開放的嚴謹著稱,上面的不寫 pub mod,pub fn 的話,外面是無法取用的。

函式更多,可以把整個 module 移到另一個檔案,lib.rs 裡面只留下 mod 宣告:
mod modulename;
內容移到 modulename.rs 裡面;或者有足以獨立出來的功能,可以放到 modulename 資料夾下,並加上 modulenmae/mod.rs 來表示這個資料夾是一個 module。

module 大致的規則就是這樣
一:可直接在檔案內定義。
二:只寫 mod modulename,內容放在其他檔案。
三、只寫 mod modulename,內容放在同名且內含 mod.rs 的資料夾內。
注意第二、三個方法互相衝突的,不能有 mymodule.rs 跟 mymodule/mod.rs 同時存在,rust 會跳出編譯錯誤。
另外有一個特例是在 src 下,只有 lib.rs 有權限宣告 submodule,例如 lib.rs 宣告一個叫 network 的 module 並把內容放在 src/network.rs,network.rs 就不能再宣告它有一個 module server。
// src/lib.rs
mod network;
// src/network.rs
mod server; // compile error
這裡的 error 訊息很詭異,是 file not found for module ‘server’,但初遇時覺得見鬼,檔案就在那邊你跟我說沒有…。
正確作法是把 network.rs 移到 network 資料夾中,改名為 mod.rs 指明這個資料夾下有哪些 module,這時候 src/lib.rs 裡面的 mod network; 就會指向 network/mod.rs 裡寫的 mod;把 server.rs 放在network 資料夾中,就適用上述的規則二,在 mod.rs 裡只寫 mod server;,內容放在其他檔案。

講完 module 的定義,現在可以來講引用,這部分要分成兩種,一是 src 下函式庫的引用:
上面第三種規則的,拿我的 dfa module 為例, mod.rs 定義了 dfarulebook.rs 跟 dfa.rs ,dfa 需要 dfarulebook,因為他們都在 dfa module 內,要引用時就用:
use super::dfarulebook::{DFARulebook};
因為這些檔案不太可能會分開,用 super 的好處是無論 dfa 資料夾到哪這個參照都不會變;在 mod.rs 裡面實作測試的 module 也是一樣,測試當然需要原本 module 裡的東西,這個時候也是使用 super:
mod dfarulebook;
#[cfg(test)]
mod tests {
  use super::dfarulebook::{DFARulebook};
同樣是第三種規則的 mod.rs,mod.rs 本身就是 dfa module,它需要用到 dfarulebook.rs 的內容,則是:
mod dfarulebook;
mod dfa;
use self::dfarulebook::{DFARulebook};

來自 dfa 之外的引用就要用完整路徑,從 src 開始一路指定:
use the_simplest_computer::dfa::dfarulebook::{DFARulebook};
你可以想像,從 src/lib.rs 開始,要可以透過一連串的 mod.rs 找到我們要的 module;上面的 lib.rs 裡就有 mod the_simplest_computer; ;the_simplest_computer/mod.rs 裡有 mod dfa; 一路像串棕子一樣把各模組串起來,如果有地方沒串好,cargo 就會回報錯誤。

再來是執行檔,這裡我也是試好久才試出來。
現在的 cargo 可以在 Cargo.toml 裡面,用 [[bin]] 欄位指定多個執行檔目標,不然就是預設的 src/main.rs,這跟 library 不同,一個 Cargo.toml 就只能有一個 [lib] 目標。
這裡關鍵的點就是:執行檔不是 library 的一部分,cargo 先從 lib.rs 編譯出函式庫,然後編譯執行檔跟函式庫做連結;執行檔要用編譯的函式庫,就要先宣告 extern crate,然後每層 use 都在前面多加上函式庫,上面說要記著的函式庫名稱就是這裡要用到:
extern crate computationbook;
use computationbook::the_simplest_computer::dfa::dfarulebook::{DFARulebook};
超級長對吧XD
如果函式庫名稱是 cargo 自動產生,可以去 target/debug/ 看它編譯出什麼,我上面的例子就是:libcomputationbook.rlib

故事大概就到這裡,這次總算弄懂 cargo 如何管理各 module 了,感謝大家收看。

在這裡就雷一下大家,下一篇就要來說一下,本來整理這個 project 要做的東西,估計會是一篇理論跟實作兼具的文章,敬請期待。

本文之完成,感謝以下參考資料:
Cargo guide: https://doc.rust-lang.org/cargo/guide/
Rust module guide: https://doc.rust-lang.org/book/second-edition/ch07-01-mod-and-the-filesystem.html
minisat-rust 專案,因為它編得過我編不過,它的複雜度又剛剛好夠複雜,就拿來研究了一番:https://github.com/mishun/minisat-rust

2018年3月18日 星期日

實用的gdb 指令

最近工作上大量使用到 gdb,想說來整理一下一些常用的 gdb 使用方式,以及對應的場景;當然,這絕對不是 gdb 完整的功能介紹,只是目前我遇到比較多的使用方式而已。

檢視原始碼:
gdb 的文字介面可以顯示四種視窗:命令,原始碼,組合語言跟暫存器,與視窗相關的鍵盤組合:
Ctrl + x + a 它會分成上原始碼下命令兩個視窗
Ctrl + x + o 切換焦點所在的視窗,如果焦點視窗放在原始碼那邊,命令視窗的一些鍵會無效,例如上下鍵會變成原始碼視窗的上下瀏覽原始碼,得用 Ctrl + P (previous) 跟 Ctrl + N (next) 才能瀏覽歷史命令。
使用Ctrl + x + 1,Ctrl + x + 2 可以設定原始碼視窗分為一個或兩個,連續 Ctrl + x + 2 會依序在原始碼+組合語言、組合語言+暫存器、暫存器+組合語言三種組合中切換。
這功能可以直接看到現在執行到哪裡,特別是進到除錯熱區時,gdb 用 list 指令都會自動加10 行,要印出當下除錯的程式總有點難度,用這個可以徹底排除這個問題;不過我也覺得還沒到除錯熱區的時候,配合編輯器來看原始碼即可。

快捷鍵(這個不止是 gdb,而是大部分 shell 都適用):
除了上述的 Ctrl + p, Ctrl + n,Ctrl + l 可以清空目前的 buffer,Ctrl +w, Ctrl + u 可以刪除命令列上一個單字或全部內容,也滿好用的。特別是 gdb 裡面 shell 下清空 buffer 的指令 clear 沒有辦法用,Ctrl + l 使用機會滿大的(前提是原始碼視窗沒開)。

中斷點設置:
有關gdb 裡面的四個點:breakpoint, watchpoint, catchpoint跟tracepoint,到現在我也只用過前兩個,99 %都是 breakpoint:
breakpoint 又分為永久跟暫時,對應 break/tbreak 後面接要中斷的位置,可以用函數名稱或者 <sourcefile>:<linenum> 兩種格式。
還可以在 breakpoint 的後面加上條件,例如 break <function> if <var> == 10,就能開始 debug 某個狀況下的執行,這在除錯有迴圈或多次呼叫函式的程式時非常好用。
start 指令,自動設置 temporary breakpoint 在主程式開始處,C/C++ 就是 main。
Watchpoint 則是用watch/rwatch 指令設置,可以監看一個變數什麼時候被動過,指令監看的目標可以是變數、記憶體位置(如 watch *0x12345678)或是幾個變數的運算也可以。
watch、rwatch、awatch 分別監看變數寫入、讀取跟讀寫。

無論是breakpoint watchpoint其實都是… breakpoint(watchpoint 有時叫 data breakpoint),可以用 info break 看到所有相關設定,還有例如它已經碰到幾遍之類。
有一個相關的技巧如下,可以計算某個函數究竟遇到幾次:
break foo
ignore <breakpoint num> 100000 //大到遠超過可能執行的數量
continue
等程式執行完就能用 info break 看到這個 breakpoint 被碰幾次。

另外 debug 時,可以利用save breakpoints <filename>把設好的breakpoint 存到檔案裡,下次可以直接source它們,save 的 breakpoint 最好只設在函數名稱上面,行數可能在debug 時變化,下次source 時就會break在不同的地方了。
我習慣上會存成 gdbinit 這樣的檔案,一進 gdb 時 source gdbinit 即可。

修改執行:
執行中可以用
set var <variable name>=<value>
set <memory location>=<value
的方式修改變數/記憶體位址內容。
例如我們發現某個條件被跳掉會導致錯誤結果,可以在 gdb 內用 set 修改變數,使它符合條件,省去重新編譯的麻煩(甚至一些狀況下,修改程式可能動到本來的邏輯,或很難使它符合條件)

跳出函數執行:
指令 finish,執行直到離開當下函數(當然遇到 breakpoint 還是會被擋)。

介面
上面的功能,有些因為最近比較常用 ddd 而非 gdb,也就沒有常用到。
另外強者我同學強強林有推一款 web-based 的 gdb gui:https://github.com/niklasb/webgdb
,據說 vscode 的 debug 功能也滿生猛的,也許找時間都來試試看。

2018年3月11日 星期日

<令人難以理解的軟體工程師生涯>心得

先前在 Facebook 上面看到這篇文章(因為怕有人沒 Facebook 權限,所以貼關鍵評論網的轉載),看了看有些心得,就打在這裡:
https://www.thenewslens.com/article/91122
話說回來,我看了關鍵評論網的引言<我們想讓你知道的是>,還是不知道它想讓我知道什麼……。
其實這篇文有點跟原文對幹的意思,身為資淺軟體工程師這麼做好像有點不識大體,不過…反正我這個小咖 blog 也沒人看,大概也沒差,而且大部分的內容,多半去看<人月神話>就有了XDD。

十倍軟體生產力是否存在?我的答案是:Yes,肯定的 Yes
這件事情不單純在軟體,各行各業都是如此,熟練的高手能得到比一般平庸的操作員數倍的生產力,軟體奇特之處在於,生產力可以高到十倍甚至更高之譜,遠超過其他行業頂尖高手和一般人之間的差距。
箇中原因,在人月神話裡面已經有解釋:軟體是人類有史以來發明過最複雜的東西,是邏輯和數學的直接表達,寫好軟體就是一次次表達腦中的虛擬結構,而頂尖的腦袋的虛擬能力,遠在一般腦袋之上;之前就有個<學長告誡>:不要去問數學高手(aka 拿了兩次數奧金牌)數學問題,他講的話你聽不懂--他們虛疑化的層次遠超過你,你要想三步的東西他一步就講完了。
學會寫程式之後(差不多就大學吧),認識的很多很強的高手,真的是活生生體會到所謂的十倍-百倍生產力這件事,這些人現在要不是在 Google 大殺四方就是創業去了。
自己有時多少也會懷疑自己到底能不能做到那個程度,而且我相信,諸位軟體工程師的生涯中,一定也遇到過非常多10倍生產力的高手,也因此原本這篇貼文,才會獲得了如此大的迴響。

於是我們回到文中的大哉問:如果已經有了頂尖、十倍生產力的軟體工程師,那為何需要平庸工程師(就像我這種)?
軟體世界不是人多好辦事,但人少不成事。
原作者用了三個月的時間,改寫數萬行的程式為數千行漂亮的程式碼,非常厲害。
但一個 LInux 核心到現在有兩千萬行程式碼,如果像他這樣三個月估且算一萬行好了,要花 6000 個月,也就是 500 年才能寫完,這是可以接受的嗎?chrome 瀏覽器 500 萬行,firefox 一千萬行,每個都要十倍工程師孜孜不倦花好幾年手工打造嗎?還不要提現下消費者是每半年到一年要看到一次改版噢。
https://www.quora.com/What-is-the-biggest-program-lines-of-code-ever-made
這還不算上自己腦袋打結的時間,更不用提即便是天才也會有他的盲點,學的知識的它的上限,懂CPU的不一定懂網路,會演算法的可能不善於實作,懂資訊安全的可能不會硬碟……,系統長大之後會出現許多測試整合的工作,單打獨鬥鐵定有一個上限存在。
大型軟體本來就要綜合眾人之力,這又回到本來的問題:集合眾人就要溝通問題本質的數學邏輯,然後發生誤解跟整合問題,就算團隊全部都是10倍生產力工程師也無可倖免,以前總以為一流的軟體公司,像什麼 Google, Amazon 什麼的,裡面的程式一定都是藝術品等級,後來問問任職的同學,才發現根本不是這回事,有點年紀的大公司,軟體總是變成一團屎,還聽說過有幾個檔案變成 magic code ,根本沒人敢動的。
在跟強者我同學一哥聊天時,就有說到:「公司花錢請你來是要解決問題,不是把公司的東西變藝術品」、「每家公司都有鳥事,所以沒方向的話就選薪水高的」聽起來很世儈,但現實如此。

其實這幾年來,一直覺得台灣軟體最大的問題,並不是我們沒有夠多的10倍生產力軟體工程師,10倍軟體工程師本身就是一個異數,也許培養一群人裡,比例也就這麼多;更何況,過度看重十倍軟體工程師,顯然把世界想得太簡單,以為不管什麼問題,只要派出一位10倍軟體工程師都能迎刃而解,但很多問題卻不是如此。
我覺得我們最缺的,是培育出許多平庸的軟體工程師之後,如何拉一位 10倍軟體工程師,把大家組織成部隊來打群架(順帶一提,所謂的平庸工程師, 是指:給定一個嚴謹的規格,可以四平八穩完成開發,不要寫出會 buffer overflow 之類的低級錯誤,足矣。),我們很喜歡強調個人能力不足,但現在這個時代,就是要靠打群架才能打勝仗,如何把 10 位平庸的工程師組織起來,搭配一位 10 倍生產力的工程師,變成 50 倍生產力的團隊?只靠單打獨鬥,我們要如何挑戰百萬行甚至千萬行的系統?
也許哪天我們會看到:原本千萬行的程式,大家一起重寫的只剩下百萬行,功能不變,效能更好,而且架構儼然。前幾天完成 Alpha 版之後,大家不禁開瓶慶祝,笑聲充斥整個辦公室。

這大概才是台灣要追求的方向。

話又說回來,其實寫程式就只是寫程式,就算不寫程式跑去教書,腦袋還是可以想程式邏輯;上班寫無聊的程式,下班還是可以繼續學有趣的東西;就算當管理職不寫程式,把軟體架構切好,交給下面的團隊幫忙開發,對專案就沒有任何助益?誰說只有寫程式,還要寫得快又寫得漂亮才能貢獻社會?
理論上我們可以用寫程式數倍的時間,一行一行驗證我們的程式碼有沒有問題,把程式改到完全不會出錯,但世界不鳥這些,<不吃飯不睡覺,打起精神數鈔票>比較重要,程式當掉資料飛了,跟客戶土下座就好,反正沒有一次土下座解決不了的問題,如果有,就兩次。
寫程式其實沒有這麼偉大。

我們持續寫下去,只是因為寫程式很快樂,解決問題很快樂,重新打造輪子很快樂(等等…),覺得自己又變厲害了很快樂,完成大系統裡的小螺絲,很快樂
每位程式設計師,其實都是無可救藥的樂觀主義者。

2018年3月4日 星期日

Coursera Introduction to Logic

前些日子開始修了 coursera 上 stanford 大學開的 Introduction to Logic,修完而且有學到東西,其實個人習慣上滿常亂加一些 coursera 上的課程,有些聽一聽覺得無聊就沒聽完,沒聽完的就不會在這裡推薦就是。

下面是基本資訊:
課程名稱:Introduction to Logic
開課學校:Stanford University
授課教授:Michael Genesereth
開課時間:10 周
教學方式:靜態講義
通過方式:每週完成指定的作業,下面會詳述作業內容。

課程內容涵蓋基礎邏輯的概念,符號介紹,邏輯證明跟歸納證明,沒有到太複雜的內容,如果在台灣的大學有修邏輯的話,應該也是差不多的內容,例如通識很熱門的<邏輯丙>,應該內容也差不多。
不像其他課程是教授親自上陣講課,這門課上課的方式是看靜態文字講義(似乎有簡體中文不過我是看英文的),講義看過之後會自動記錄看過,相對來說看靜態文字比看教授講解還要無聊一些,而且有點吃英文能力。
課程內容很大一塊是放在 fitch system,並且證明也都是用 fitch system 來證明,每周作業會出約莫 5 到 10 題的題目,有些是選擇題,選到正確的選項即可;有些則是證明題,要證出所要的結果;有幾週會加一些邏輯遊戲跟參考影片,例如邏輯踩地雷,或者看教授演示一個邏輯表達系統。
證明題使用的是一個 javascript 寫的證明系統,可以用滑鼠選擇敘述,還有要使用的運算來完成證明,一開始有一點難上手,不過熟練之後就會覺得設計真的非常厲害,For all 跟 Exist 的符號代換都會自動完成,點一點就發證明完成了。唯一卡比較大的是在第八週的歸納法,久違地動用紙筆在紙上釐清議義範例證明的思路,想通之後在系統上重現就清楚多了。

學完之後真心覺得有學到東西,我從來沒想過原來連 (p => q) => (~q => ~p), (p => q) => (~p | q) , (p | ~p) 這樣基礎的邏輯也可以證明,但是千真萬確,證過一次才知道這真的可以用邏輯推出來,所以以前說的那些:前題錯就可以推出任何東西,「如果月亮是起司做的,那麼月亮可以吃」都是真的。
其他要注意的事情:寫作業的系統不知道為什麼,用 chrome 開的話會有些問題,用 firefox 來操作就沒問題。
另外,我誠心建議大家睡前不要讀邏輯,讀邏輯當然要沐浴更衣正襟危坐有一次念完之後睡覺,結果在夢裡想歸納證明………,醒來累得半死。

2018年1月25日 星期四

使用 git submodule 管理 project 所需的其他模組

故事是這樣子的,最近在寫一些分析資料的程式,用的是 python 跟 numpy。
一開始改寫的時候,發現一開始 load 資料的地方,Python 實在太慢了,載入 20000 筆資料耗時超過 150 秒,後來決定用 C++ 改寫載入數據的部分,同時利用別人寫好的 cnpy 這個 project,寫出 numpy 檔案作分析,結果載入速度竟然一口氣降到 4.5s,加速 15 dB,太可怕了(yay。
為了要使用 cnpy 這個 project,順手研究了一下要如何給使用 git submodule,這篇文章就做個介紹:

基本上submodule 利用的場合,就如我上面說,我的 project 要用到其他 project 的程式碼,我希望讓我的使用者能直接拿到其他 project 的程式碼,這樣他們不用自己再去載,麻煩之外可能還會載到錯誤的版本。
另一方面,我們又不想把對方的程式全部加到我的 repository 裡面,這樣會帶來不好的後果,上游的程式碼修改,要自己手動更新,沒辦法用 git 的方式更新,增加錯誤的機會。
git 針對這個使用情景的解決方式就是 submodule:

遇到 submodule 的時候通常有兩種狀況,第一種比較常見的,是載了一個別人的project,發現裡面有用到 submodule,例如知名的補齊工具 YouCompleteMe ,裡面針對各種語言的剖析工具都是 submodule,這些專案載下來的時候, submodule 裡面都還是空的,要先用下列指令把 submodule 載下來:
git submodule init
git submodule update
或者可以用一行指令解決:
git submodule update --init --recursive
--recursive 會在 submodule 裡面還有 submodule 的時候,一口氣都設定好。
又或者可以在 clone 專案的時候就指定要一齊複製 submodule(不過通常在 clone project 的時候還不知道裡面有 submodule,所以…通常不會這樣下):
git clone --recurse-submodules url

第二種狀況如我上面所述,我們自己新增一個 submodule,我要做的就是新增 cnpy 為我的 submodule:
git submodule add git@github.com:rogersce/cnpy.git cnpy
後面的 cnpy 是指定 submodule 要放在哪個資料夾裡面,通常名稱都跟 project 本來的名稱相同,才不會搞混;這時候記得會開始把這個 project 下載下來,接著檢視 status 的話會看到下面的內容:
new file: .gitmodules
new file: cnpy
.gitmodules 檔案裡面記錄了 submodule 的名字,現在的路徑以及遠端 url,這是可以用 add 及 commit 將這個 submodule 保存下來。

在一個有 submodule 的專案裡面工作,會和一般的工作內容稍有不同,當進到 submodule 內部的時候;submodule 從外面來看只是一個參照,如果真的進到這個資料夾,用起來就會像另外一個 git repository 一樣,一樣會有 master 等等 branch,可以用 remote 拉別人的修改下來,或者自己送 commit 出去。
比較讓人疑惑的通常是在外面的 project,當內部的內容有修改的時候,外面會出現一些讓人很疑惑的訊息,例如當我們對 cnpy 這個 project 新增一個 commit,從外面會看到這樣的訊息:
git status
modified: cnpy (new commits)
這則訊息的意思是,cnpy 這個 submodule 有了修改,修改的內容是新增了 commits;可以把git submodule 想成一個快照,現在 submodule 的狀態已經脫離這個快照,從 git diff 就會看出差別,最下面是 commit 的修改訊息:
git diff
diff --git a/cnpy b/cnpy
index f19917f..8f997be 160000
--- a/cnpy
+++ b/cnpy
@@ -1 +1 @@
-Subproject commit f19917f6c442885dcf171de485ba8b17bd178da6
+Subproject commit 8f997be1f87279f09054acbdb896162b1e9d3963

這時對這個 submodule 做 add, commit,就會更新這個 submodule 的快照值;另外如果我們想要 submodule 維持在之前的快照上,用 git submodule update ,git 即會將 submodule 簽回到當初記錄的版本:
git submodule update
Submodule path 'cnpy': checked out 'f19917f6c442885dcf171de485ba8b17bd178da6'

不過 update 之後會有一些不好的效果,因為這時 submodule 被強制簽出 f19917 這個 commit ,裡面就出現了一些沒有 commit 的修改,在這裡有內容未被 commit,所以它會顯示:
git status modified: cnpy (untracked content)
從外面會看到 submodule 有修改,但要消掉這個 untracked content 的訊息,就要進到 submodule 資料夾裡面,用 checkout 或 clean 的方式,讓 submodule 的狀態回到 clean 才行。
但同時也要注意的,這時候 submodule 就處在 detach HEAD 的狀態(在上面的例子,submodule 落後 master 一個 commit ),這時進到 submodule 做些 commit,這些 commit 並沒有 branch 參照,下一次再下 submodule update 的時候,所做的修改就會消失,如果有要修改的話,建議要先在 submodule 裡面生成一個 branch 來保留修改。

另外一個比較需要注意的,大概就是在移動 submodule 的參照的時候,儘量可以用 git mv 的方式來移動,用 os 本身的 mv 似乎比較容易出問題。

我想 submodule 我們就講到這裡,下面這篇官方的參考資料:
https://git-scm.com/book/en/v2/Git-Tools-Submodules
裡面還有很多 git submodule 神奇的用法,例如從外面用 git submodule 指令一口氣更新所有 submodule 的狀態到最新,把所有 submodule 現下的狀態推送到遠端,等等。
但我個人認為 submodule 相對來說是比較偏門的指令,自己也是用了這麼久,最近才第一次用到 submodule,大家還是用到再來查文件比較實在;另外話又說回來, git submodule 能管理的相關 project 數量也是有個限度,數量多到一定程度,submodule 也會顯得捉襟見肘,因而 google android 才會另外推 repo 這樣大量 git repository 的管理工具吧。

Related Posts Plugin for WordPress, Blogger...