2019年1月24日 星期四

閱讀程式碼的心得

許久以前曾經看過這篇,由傳說中在 appier 大殺四方的 PCMan 大神寫的閱讀程式碼教學

最近剛好因為小弟的工作上,也會需要在有一點點規模的程式庫裡面穿梭,雖然都在打混還是累積了一點點心得,在這裡分享一下,當然小弟還是遠不如傳說中的 PCMan 啦,大家從我這裡連過去上面的文章,看完就可以關掉回家了(誒
如果你還是想加減看一下,小弟比較熟的是 C/C++ 系的靜態語言,寫網頁什麼的小弟就不擅長了;然後個人的經驗是有極限的,例如 Linux Kernel 那種規模的 code 我就從來沒有弄懂過QQQQ。

1. 開 code 之前,先把專案編譯,跑起來:


編不起來的 code 就是垃圾,要怎麼知道你改的程式有沒有問題?要怎麼看到你的修改有發生實際效果?編不起來這一切都沒用,所以從網路上載了個 project 下來,第一步一定是先看說明文件把專案編起來或跑起來。
通常網路專案要不是 autotool 就是用 Cmake,個人是覺得 autotool 的機率還是高一點點,但通常都是下個 autoconf 再接 configure 就能生出 Makefile 了。

2. 看 code 是最後一步,先從高層次理解程式在做什麼:


這是工作一陣子之後的心得,原始碼最底層是一個很細緻層次的東西,例如模擬一個 x,y 的座標值,然後往上一層一層建構線、面、一群面的組合、一群組合的參考/一群組合的陣列參考等等,上層會用高層次在操作,把下面的實作都隱藏起來。
理解高層次的程式在幹嘛,遠比從低視角去理解實作重要(雖然 low angle 拍出來的照片比較香(炸)),沒理解想法跟目的之前,直接看程式碼是沒有意義的,看到函式做一個 loop,可是為什麼要 loop,在 loop 什麼?沒理解想法,連看著處理中的資料無法分辨對錯的時候,就只是看一堆無意義的資料飛過去而已。
比如說最近跟著強者我同學 JJL 大大在看 verilator 這個 project,這個 project 會把 verilog 吃進來,模擬的 C++ 送出去,verilator 發大財,直接進到 src 資料夾會看到滿滿的 V3xxxx 的檔案,但只要緊抓上面的概念,其實大部分都是 AST 的檔案,verilog 會先被 parse 成 AST,由程式對 AST 進行一些處理變形,再把成果寫出去;所以說至少會有 AST node 跟走訪 AST 的程式,從這點抓下去八九不離十了。
理解高層次的程式比較困難,一般函式至少會有註解,可以註記這個函式的功能,但高層次想法是一個比較難表述的東西,通常也不會訴諸文字,只會記在開發者的腦袋裡面,如果能有一個人帶領的話通常效率會快很多。

3. 調校好工具:


工具上的投資非常值得,好的工具能省下極大的時間,要不要用 IDE 個人沒什麼信仰,一般我都是用 vim,這部分請參考幾篇拙作:用 Vundle 安裝 vim 插件,還有用 ctags 幫助跳轉,Ctags 的程式碼跳轉是一定要的,效率直接天上飛。
終端機也是一個值得好好投資的工具,我一般工作都會開 5 個終端機的分頁,前三個用來編輯 code,第四個用來編譯(因為 C 專案通常程式碼跟編譯的 top 不會是同一個目錄),第五個用來執行程式(對因為通常程式碼、編譯跟執行檔不會是同一個目錄),用 Alt+12345 可以很快速的在分頁間切換,到 Alt+6 我覺得就太遠了。
至於多螢幕,我覺得有幫助但有限,最大的用處是在撰寫投影片跟筆記的時候,可以把 powerpoint 跟 word 拉到另一個螢幕去,跟 code 來回對照會快很多,但單純閱讀程式碼的時候是用不上的。
另外一些 shell 相關的部分,請參考拙作<那些在工作上看到的各種東西>的工具部分:

4. 邊看邊做點筆記:


說真的大型專案有些都會到很噁心的地步,還會有一些積非成是的地方,命名不佳的地方,可能當初寫好、修改,改到後來就沒人敢改了。
最近遇到還有印象的是這樣:我們會依序分解,一條線 x、x 的其中一個端點 S、S 的兩個端點 X1, X2,分別傳進去給函式 A, B, C 做處理,但函式 A 裡面 S 在 x 的 index 跟函式 C 裡面 X1 的 index,變數竟然都用 index,然後在函式 A, B 裡面,都用 i 變數來 pass 給下層的函式,變成裡面的 index。
搞到後來到底 index, i 在哪裡代表什麼都一團糟,這裡就很適合簡單畫個表格記錄一下;要隨手 refactor 一下也是可以,但在大型又缺乏維護的專案下,refactor 有可能會花很多時間,這部分就要自己取捨了。

5. 順手做點修改?


參照上一點,做點變數修改、加些註解,幫助自己理解程式碼是 OK 的;但要記得,一定要沉住氣,不要去改一些枝微末節的東西。
例如有些專案會是悲劇性的空白 tab 混用的狀態,這就不要改了,第一個這個會引發比無限之戰更慘烈的信仰之戰,第二是這種大範圍的修改很浪費時間;第三這種修改很難進入主線,設定一下 tab 的寬度讓程式碼排版回到容易看的狀態就好。
如果有一些區塊很難讀懂,可以用 vim 的 = 在區塊內做重新排版(雖然我覺得這個功能爛掉的機會滿大的)
再來是 syntax sugar,例如自從 C++11 的 range-based loop 出來之後,看到舊式的 iterator based loop 都會覺得癢癢的,是不是該順手改過去?個人認為是不需要。
syntax sugar 的本意就是:更易讀或表達更簡單的文法,本質上無關乎背後的實作,所以你動了手一方面對程式其實沒半點影響,通常 iterator-based 的 loop 也不會影響閱讀跟理解,還不如把精力省下來看懂程式想做什麼。

要知道大型或是正式的 project ,review 機制完善之後所有的修改都會需要審核,沒事沒頭沒尾的送一個修了一堆東西的 Pull Request 被接受的機率都很低,另外 syntax sugar 等級的 refactor 其實根本不影響程式效能,真正架構上、想法上的 refactor 才會,記住程式開發最浪費時間的東西就是程式人的腦袋,不要浪費時間在低層次的修改上面,專注在高層次的程式流程上。
大型的專案通常都橫跨十幾年,會有老舊語法跟 legacy code 是很正常的事情,我現在做的專案裡面還有 K&R C 的 parameter style 勒,就像下面這種:
int foo(bar, qux)
int bar,
stNode qux { … }
反正編譯器還支援的狀況下留著也沒差,我敢打賭這種 code 還會在公司的程式裡留 10 年以上;記得 syntax sugar 只能加在熱咖啡裡,咖啡冷了就不要浪費精力加糖,想辦法換杯新咖啡比較重要。

6. 從 main 下手:


不知道從哪裡開始,我個人的經驗是從 main 下去最快。
main 通常(通常就是有例外啦)會保留最多高層次的程式邏輯跟想法,如果在 main 裡面看到低層次的操作那也是滿抖的。
以 verilator 為例,main 位於 verilator.cpp,整個結構其實很單純:剖析傳進來的參數,讀檔,process,將結果 dump 出來。process 裡面就是對 verilog AST 進行處理的各個 visitor 呼叫,trace 一下就能清楚整個程式的大體流程了。
當然這個規則無法一體適用就是了,具體還是要看各 project 的架構,我也看過最上層是一套虛擬機的專案,實作功能都拆分為給這個虛擬機執行的函式,這時候進入點就變成各函式而不是 main 了。

以上大概就是幾個工作到現在累積的看原始碼心得,小弟班門弄斧,希望各位看倌大大有什麼意見都能多多回饋給小弟。

2019年1月12日 星期六

省錢是好事嗎

故事是這樣子的,最近有一位很紅的藝人 BBB 拍了高雄市拍了一部 MV,他的宣傳詞是這樣寫的:「BBB 自掏腰包為高雄拍攝的MV『來去高雄』,懇求大家幫助負債累累的高雄市政府不用花任何一毛宣傳費,就可以讓大家湧入高雄拚觀光!達到宣傳高雄的最大效果,請大家努力、用力的轉發分享MV,靠全民的力量達到最大成效!」
剛好最近,政府宣佈因為上半年的稅收有盈餘,同樣也引發一番爭辯,畢竟現在中華台北還有這麼多債務,稅收有多是不是應該先還債?對照組正好是台北市市長,在第一任任期中主打政績即是償還市府負債。

這一連串看完突然有一點感想,跟之前看書的心得結合一下來寫篇文章。

當然我本文無意支持或反對現下政府將稅金盈餘退,或者 BBB 的影片是好是壞有效無效,純粹就貼文背後的精神來評論。
我覺得這篇貼文剛好非常傳神的傳達了兩個概念:
1. 負債累累的高雄市政府需要幫助。
2. 不花政府一毛錢就是讚,大家要多鼓勵。
相對應到退稅議題上面,就是:
1. 負債累累的政府不應該再退稅。
2. 政府不該亂花錢,應該努力減少負債。
說起來有點華國人老一輩刻苦經營儲蓄的精神。

我們常被教導/認為的省錢就是好,負債就是壞,真的嗎?

假設我們地方政府一年歲入是 400 億元,而台北捷運第一期的工程就花了 4000 億,很明顯的如果政府是無法一口氣開工所有的捷運,而必須分年編列預算分年開工;相對的政府可以借債,一口氣先借 4000 億元把捷運蓋完,然後分年的慢慢還債。雖然後者利率會造成多一些成本,可是早點同時開工的話,可以在土地還便宜的時及早徵收,儘早擺脫交通黑暗期,減少道路車禍傷亡,這些都是獲利。
用個更簡單的例子,為何長輩當年都會貸款買房呢?負債不是不好嗎?更別提那個時候借錢利率高得嚇人呢。但借錢買房卻有它的道理在,可以更早享用住房,在房子便宜的時候先買,負債+房子也可能比滿手現金來得保值。
或者再簡單一點,假設今天持有台GG的股票,每年有 2% 的收益,而銀行的利率是 1%,請在「沒有負債沒有股票」跟「欠銀行 100 萬但有等值的台GG股票」兩者間做選擇,前者沒有負債,但以賺錢來看後者才是好的。

上面幾個例子,都在說明省錢是好負債是壞的概念,其實不一定正確,重點要看錢灑出去會換到什麼資產回來,然後評估那個資產合不合理。
我第一次意識到這個觀念,在之前閱讀<21世紀資本論>時裡面的一小段:「殖民時期英法兩國持有的國外資產和帶來的收益,足以使他們承受貿易赤字同時仍有收益……汲汲營營堅守貿易順差本身沒有任何意義,持有資本的根本目的就是能在不工作的狀況下,繼續消費、累積資本」。
同樣的,所有的資產應該要攤開來看,堅守黑字不是絕對,有錢無債只意味著持有「錢」這個資產,而放棄其他可能更高報酬,拿債滾錢的選擇;畢竟長期來看,隨著通膨錢這個資產可能是最沒價值的(你也可以說錢最不值錢XD),所謂保值,就是在比哪個資產價值流失得比錢還慢;政府可以把錢換成火車、航廈、或者乾脆一點換成未來的小孩也可能更賺,至少他們有機會在未來滾出更多小孩。

當然:省錢是好、負債是錯這是個很鐵的概念,直覺上來說很像真的,強者我同學台大財金系畢業一樣逃不過這觀念的束縛(雖然我私心認為他不是不懂,只是戴著有色眼鏡所以反對啦)。

另外一句:省錢是好的嗎?
同樣不盡然。
比如說,如果省錢很重要,為什麼我每天不走路回家呢?因為我搭公車 15 元車程大概 40 分鐘;走路 0 元大概 2-3 小時,搭公車多出來的時間,我可以多寫幾行程式多看一些書,都能比省下的公車錢更有生產力,在這裡,省錢意味著失去時間這項隱形的成本。
花錢可以換到一些隱形的東西,像是請老師是換他的經驗,買珍奶是換舌尖的快樂,或者那個讓人津津樂道的笑話:一個美國工程師拿一半的薪水請三個印度工程師,把工作都包給他們做,自己上班就可以爽爽過,買工程師是換自己的時間。
就像非常早非常早,當我剛被 Free Software 傳教的時候,都會有一段時間覺得為什麼不要整個社會、政府機關改用 Libre Office 就好了?作業系統全部換 Linux 啊,不是超省錢?碰久一點之後就會發現,要對應世界上這麼多、每個都不同規格的硬體,不像 Mac 筆電因為規格全是硬性規定,Windows 雖然沒事出點包然後使用上被大家幹到翻,在穩定、方便、統一規格上仍然把其他 Mac/Linux 壓在地上打,如果加上 Office 系列產品那又更不得了。
Window 可能要錢,但它有 Microsoft 在背後支持,有 bug 會幫你修,全系列的相容性他們會注意,花錢買得到服務;Linux 是免費的,但它沒有客戶支援,沒有相容性支援,整個體驗加上去可能是負的。
所以才有那句諺語:免費的最貴,不收錢表示它有缺點讓它不夠格收錢,那你看得透那個缺點嗎?花不花錢不是重點,重點是花了錢會換到什麼?權衡利弊,省不是一切。

事實上若綜觀國際商場的現況,諸如共享單車、網購平台、叫車服務等,這幾年都出現透過灑大錢補助來吸引使用者,負債買下市佔率,及早建立規模優勢排除競爭者的手法(當然排除之後活不活得下去是另一回事),這跟做好自己產品吸引消費者上門的手法大相競庭。
HTC 不就是一個血淋淋的例子,作為最早推出智慧型手機的廠商,後來卻慢慢在行銷、通路的資源戰上被對手壓了過去?
堅守省錢少舉債思維的中華台北,宛若二戰時日本拿全民精英射手對付美軍機槍的手法,賺到省下來的小利卻不一定擋不過人家用資源硬推出來的優勢,平常都稱讚中國狼性中國小確幸,來到行銷廣告的時候,眼下就來個標準的範例了,果然還是老話一句:一隻手指指著別人的時候,四隻手指指著自己。
啊不過話說回來我打了這麼多,個人資產配置還是都以現金為主,果然是:一隻手指指著別人的時候,四隻手指指著自己,啊哈哈哈…嗚嗚(誒。

落落長說了一堆不相干的東西,我想可以整理兩個 take-away:
  • 負債不是壞事,重點是要看負債換來什麼;錢只是資產的一個表現,要看整體資產是否有所增長,或者有機會成長。
  • 省錢不是好事,重點是花錢能換來什麼?能不能換到時間、方便、穩定、機會?省錢必有成本,你有沒有意識到呢?

2019年1月6日 星期日

用 PEG 寫一個 C parser 續

自從去年十月把 nixie tube clock 完工之後,好像都在耍廢之類的,結果 11/12 月兩個月都沒有發文,其實這兩個月裡面,有的時間都在改之前寫的 C parser,其實整體完成度愈來愈高了,今天發個文來整理一下到底做了啥。
這次做了幾個改變,主要的修正就是加上 expression, declaration, statment 的處理,也學到不少東西,這裡一一列一下:

macro

這是要對應之前寫的 parse_fail,本來 parse_fail 的用意,就是在剖析出錯的時候,把程式終結掉,然後丟一點錯誤訊息出來;本來我的實作是一個函式,利用 unreachable! 丟出錯誤:
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)
}
這樣的實作會有個問題,在程式終止之後的位置一律都會在 parse_fail 這個函式裡,而不是真正出錯的剖析函式,要除錯必須開 stack trace 才能做到。為了避免這個狀況,我們改用 macro 實作 parse_fail,這樣 unreachable! 就會在出錯的位置展開,在終止程式的時候給出正確的位置。
關於 macro 小弟在很早的時候有寫過一篇貧乏的介紹文,改起來也很簡單,把原本作為函式參數傳進來的 pair,由 macro 的 $x:expr 取代,然後用 $x 取代本來 code 裡面所有的 pair,如下文:
macro_rules! parse_fail {
  ( $x:expr ) => {
    {
      let rule = $x.as_rule();
      let s = $x.into_span().as_str();
      unreachable!("unexpected rule {:?} with content {}", rule, s)
    }
  }
}
這樣所有程式裡的 parse_fail(pair) 就會自動開展成下面的三行程式碼了。

另外有一個要注意的是,假設我 parse_fail 的 macro 寫在模組的 helper.rs 裡面,那麼在寫模組的 lib.rs 時,mod helper 要在所有其他 mod 之前,並加上 #[macro_use] 修飾,這跟 rust 模組的編譯流程有關,macro 是跟順序有關的,在 mod helper 之後這個 parse_fail 的 macro 才有定義,後面的 mod 才能使用這個 macro,詳細可以參考這篇

如果想讓使用 extern crate 的人也能使用這個 macro,就要在定義 macro 的時候在前面加上 #[macro_export] 的標籤,每個 macro 都需要單獨 export 才行。

處理 expression 的正確姿勢:

如果有看上一篇,會看到我用 PEG 套件 pest 的 precedence climbing 的功能來完成對 expression 的剖析,但其實那是不完整的,原因在於我們把的做法是把 expression 直接導向 unary_expr (op_binary unary_expr)* 的組合,這樣我們看到 expression,把它展開來就可以得到一大串 unary_expr 跟 op_binary 交錯的序列,把這串東西丟進 precedence climbing 裡面就能建好 expression tree 了。
但實際上的 C 語言比這還要複雜,expression 下面還有 assignment expression,conditional expression 等等,這些 expression 是必須存在的,例如在變數 decl 的地方就會需要 assignment expression,我們本來的寫法把 assignment expression 等等都抹掉了要怎麼辦?把它們加回去要怎麼讓本來的 precedence climbing 的 code 還能正確運作?
後來發現的正確處理方法是這樣的,在文法的部分要把 assignment expression 等東西加回去,裡面用到的三元運算子 ?: ,assignment operator =, +=, -= 等等都從 op_binary 裡面排除,像是這樣:
logicalOR_expr = _{ unary_expr ~ (op_binary ~ unary_expr)* }
conditional_expr = _{ logicalOR_expr ~ ( op_qmark ~ silent_expression ~ op_colon ~ conditional_expr)? }
assignment_expr = _{ (unary_expr ~ op_assign)* ~ conditional_expr }
silent_expression = _{ assignment_expr ~ (op_comma ~ assignment_expr)* }
expression = { assignment_expr ~ (op_comma ~ assignment_expr)* }
原本的 expression 現在只剩 logicalOR_expr,其他的都要拉出來自立條目,讓其他的文法如 declaration 能使用它,但同時都使用 _{} 讓剖析後他們不會吐一個 node 出來,這樣看到 expression 之後,展開來仍然是一串 unary_expr 跟 operator 交錯的序列。

這樣做的好處是 precedence climbing 仍然可以沿用,所有的 operator 都算在 expression 頭下,壞處是我們必須依文法去調整一些文法要不要吐出 node,現在的實作在有兩個特例:
一個是如上面所示,conditional expression 的規定是 logical_OR_expression ? expression : conditional_expression,有一個 expression 在裡面,這會違反我們的假設:把 expression 展開來看都會是 unary_expr 跟 operator 的組合,因此我們要加上一個特別的 silent_expression 在剖析完之後不會生成 expression node ,而是完全展開。

另一個剛好是反過來的狀況,在 C 的 initializer 文法(6.7.9)是這樣定的:
initializer -> assignment_expression | "{" initializer-list "}"
但…我們的 assignment_expression 是不存在的,如果 initializer 真的剖析為 assignment_expression,展開 initializer 只會得到「一團 unary_expr 跟 operator 的組合」,會跟 initiailizer-list 搞在一起,所以反過來我新增了一個 initializer_expr,把 assignment expression 封起來:
initializer_expr -> assignment_expression
initializer -> initializer_expr | "{" initializer-list "}"
這樣拿到 initializer 就能放心展開,再看內容物是 initializer_expr 或 initializer-list 來決定下一步,如果是 initializer_expr 就能放心的丟給 precedence climbing 去建 expression 了。

上面兩個例子都沒什麼道理可言,基本上就是見招拆招,大致就是兩條好像在說廢話的規則:
  1. 會展開的 rule 裡面出現這團 rule 的開頭,則開頭的 rule 代換成自動展開的版本。
  2. 會展開的 rule 跟其他 rule 並列,要再多包一層不會展開的版本。

! tag for = and ==

在這次修改之前都沒什麼機會用到 ! tag,也就是 PEG 裡的 Not predicate,這次在處理更複雜的 expression 遇到,某些狀況 = 的優先權高過 == 以致 == 先被剖析成 = 了。
這時候 op_assign_eq 就要改為:
op_assign_eq = { "=" ~ !"=" }
來確保 = 之後沒有接著其他的 =。

comment

comment = _{ "/*" ~ (!"*/" ~ any)* ~ "*/" | "//" ~ (!"\n" ~ any)* ~ "\n" }
comment 也是這次的修改之一,同樣利用了 ! 的特性,上面兩條其實都滿直覺的:
開頭是 /* 再來只要不是 */ 的內容,就可以匹配任何字元;開頭是 // 再來只要不是換行就可以匹配任何字元。
這兩個例子都使用了 Not predicate,功能很類似 C 裡面的 peek,偷看一下後面的東西而不消耗任何東西。

Hidden grammar:

這點比較不是程式的問題,而是 C 規格的問題,注意以下這些都符合 C grammar,但在工作上千萬別這麼寫,大概有十成的機率你會被電到天上飛
  • volatile, restrict, const 隨便加,加幾個都沒關係
  • 其實可以不用 type,這是符合文法的,gcc 在這裡會直接給你一個 int。
  • 也可以宣告型別,儲存類型什麼的,最後…沒變數。
所以可以寫像是:
int const volatile const volatile const volatile const volatile const volatile const;
const * restrict restrict restrict a;
說真的,看到這樣寫 code 我也會把人電到天上飛,其實我也不知道為什麼 C grammar 要允許這樣的文法就是,看到 gcc 編譯過我差點笑死。

現在離大致完成還有一個最大的難關,就是 declaration 那邊還有 struct, union, enum 等著處理,文法上是還好,更大的問題是不知道怎麼寫轉出來的 AST,之前我大部分都參考強者我學長 suhorng 大大的 haskell 實作,或者參考一些 LLVM 的 IR 實作…當然是沒辦法到 LLVM 那麼複雜啦QQ。
總之最近進度嚴重卡關,這才是我為什麼在這裡打住寫篇文的原因(誒。

自己自幹 AST,配上最近工作上做的一些改動,讓我有了下面這個體會:
資訊源自於數學,本身是無窮的,正如數線上有無數的正整數,無窮的有理數,比無窮更無窮的無理數;數學這個「概念」本身就有無限的資訊
但有了電腦一切就不一樣了,我們只有有限的位元能夠近似數學的概念,所以就有了取捨。
用 64 位元可以表示到 18446744073709551615,大約是 10^19,於是 10^19 -> ∞ 的資訊就被捨去了;同理我們決定浮點數用 IEEE 754 表示,有些小數就是無法表示,無窮的資訊對上有限資源,其間的差距令人絕望。

就如我們把 C code parse 成 AST,AST 裡面要保留多少資訊?像我這樣基本上只保留了簡單的 AST node,隨便建顆樹而已;LLVM 的 IR 就是許多嚴僅設計的物件,保留程式語言的繼承關係跟內部的屬性設計,在處理上就有更多能運用的資訊。
工作上需要的是用電腦處理幾何的資訊,像是點、線、四邊形,那麼一個線段的物件要儲存什麼資訊?可以用起點終點來表示一條線,基於效率跟空間考量,我們可能可以存一下線段是不是垂直的、水平、甚至是不是斜上跟斜下,但要不要存一個 double 的斜率呢?這就要看平常是不是很常需要算斜率了。存更多的東西自然可以方便做些處理,但線段更新時也要更新更多的資訊。

捨去是面對資訊時的必要,資訊工程處理的問題一直都不是資訊太少而是資訊太多,而要捨去什麼資訊、保留什麼,這不是科學而是技藝,這些都不是數學,不會有一個標準的答案,而是視需求去選擇,需要經驗、工具、模擬、除錯、測試……用實驗跟說理得到一個最佳近似的解;正如大學學系的名字:資訊<工程>學系。