2018年10月27日 星期六

自幹世界線變動率探測儀(Nixie Tube Clock):後記

世界線變動率探測儀系列文終於接近尾聲了,能看到這邊想必大家也煩了,做一趟電路自己也學到很多,覺得非常值得;如果能讓看系列文的大家也學到東西,我想這前後加起來 8 篇快 14000 字的文章就有寫的價值。
是說自從我發了文之後,好像真的有不少人覺得世界線變動率探測儀是不是真的在探測什麼東西XDDD,其實它就只是個輝光管做的時鐘而已 (._.),真的很想知道它為什麼叫這個名字…就請去看 Steins;Gate

從8月左右開始動工,動工到現在連 Steins;Gate 0 都已經演完了,東西才做出來。

若說這次學到最大的教訓,就是:限流電阻很重要,限流電阻很重要,限流電阻很重要。說來漸愧,上路之前都沒好好看 spec 或是看人做的東西,有些地方一定要加限流電阻的都忘了加XDD。
例如 nixie tube 限流是 3 mA ,剛拿到高壓電路一時興起就給它直接打下去,當然 nixie tube 是沒壞啦(俄國管子真耐操www),但就高電流把管子內打出一堆電漿,還在疑惑怎麼拍起照來都是一團糊糊的,後來看看才發現要加 22K 限流電阻,小數點則是實驗後發現要 75 K 限流電阻。
然後 TLP521 也是,沒加 220 ohm 限流電阻 5V 直接灌下去,馬上就超過 arduino 的限流 40 mA,然後疑或為啥 arduino 電壓輸出到不了 5 V。
另外也不要偷懶,每個元件例如 LED, nixie tube ,限流電阻該加的每個元件都要加一個,共用電阻是絕對 NG,如同這裡說的:那是因為每個元件會有不同的特性,調小電阻的同時,就可能有元件吃到過大的電流導致燒毀,畫 layout 的時候一度把所有 nixie tube 的電阻用同一個,幸好有一天睡前躺在床上突然大徹大悟把它改掉了。

然後功率的部分也要認真對待,為了這個 project 久違的把我的工程計算機拿了出來,幾個元件電阻的功率都要算一下,不過 IN-14 相對來說,1.5 mA 的電流不算大,這上面所有的電阻都能用 0603 解決,比較危險的只有陽極驅動的 470k 電阻。
所有設計都在 github ,主要就是 code 跟電路板 gerber layout,高興的話拿去跟板廠說要洗板他就會幫你洗板子出來,買個元件插一插,就能做出自己的世界線變動率探測儀,或者其實我有多洗一些板子,要的話也可以跟我買(誤。
最終整體成本大概如下:電路板 4000 元,輝光管 2000 元,元件加一加約莫 800 元吧,當然跟外面賣的產品比還是便宜一半,花自己時間就是了。

其實這版 1.01 問題不少,包括先前提過的:
  • 腳太近:控制 180 V 的 MPSA42/92 選了 TO-92 的 footprint,它的腳位間距只有 0.25 mm,不及 180 V 建議需要的 0.4 mm,某種程度上可能會有危險。
  • 看錯輝光管的腳位,導致數字 1-9 全部反過來,該打屁股。
  • LED 關不掉又太亮了,這個可能是最輕微的啦,而且可以再買電阻修正。
  • Layout 不夠緻密,浪費面積
以上未來可能出一個 v1.02 來修正吧,但我說真的沒實際驗證過,出個 v1.02 做錯了害大家噴錢我又不能負責(yay,而且 easyEDA 改 layout 好麻煩,想到就不想做XDDD。

如果未來哪天我想不開,也許有可能會做個第二版,不過我是覺得不會這麼快啦,我目前給自己第二版的目標,包括至少要有:
  • 雙層板,下層控制上層放燈管,挑戰總面積最小,不然像這版寬度達到 10 幾公分,根本不能像動畫裡面那樣拿起來。
  • 使用 MC34063 以外,高頻一點的開關電路,做到更高頻、效率更好的升壓方式,例如網路上有人販售的高壓電路板,可以做到非常小,效率又高,用電池就能推得動一堆管子。
  • 嘗試使用 SMT 的晶片,元件能用平面的就用平面,縮小面積。
我猜至少要幾年以上吧,現下有第一版就非常滿意了,有機會的話想找人做個木盒跟壓克力盒把它裝在裡面www。

本作品的完成,有許多要感謝的人:
  • 強者我同學 小新大大 起了頭,讓我們有動力完成製作。
  • 強者我同學 強強林大大 在過程中給予幫助,出借工具、焊接空間。
  • 戀戀科技的 Marten 大大給予硬體電路板製作的指導。
  • 強者我學妹 昱廷大大 幫買淘寶高壓電路板。
  • JKL 代購幫助我買到 ebay nixie tube。
  • 在製作過程中大量參考 復古咖啡大大 的製作。
  • 工作狂人大大 的網站助我學到許多 PCB 相關的知識,有一次整個週末都在刷大大的網站。
還有瀏覽了許多網站,幫助我解除設計上疑惑,像是 Arduino 官網、論壇,都多少幫了點忙,在此不一一介紹。

回首開工的日子,果然能好好做好一件事,會需要時間,但回頭來看,也非常值得,我想就用一張藍光的 Steins;Gate 世界線來收個尾吧。

這張超明顯的顯示 LED 太亮的問題呀(yay

自幹世界線變動率探測儀(Nixie Tube Clock):寫 code

到了這邊木已成舟(無誤,電路板沒做好的話,程式寫再多都沒有用www,只能硬著頭皮去修或者認命掏銀子出來重洗了),再來就是不斷的寫 code 跟燒 code,在洗板的時候已經預留了燒錄程式碼的接點,只要把對應的針腳從作為燒錄器的 Arduino 板子接到電路板上就能燒錄了。
寫Code的時候要注意,如果一不小心把所有的燈管都打開,高壓電路有可能會推不動,淘寶上買的高壓電路板是推得動,我的不行,我猜跟電感的好壞有關;這版電路因為有用上 74HC238跟 74CD4514,原則上來說是不會發生這種事。

建議可以先從低壓的部分先測試,因為我們在 78M05 輸出到所有需要 5V 的電路上有斷路器,這樣就可以先斷路,用外接的 5V 驅動整個電路了。
測試 LED,把 LED 腳位輪流打開就行了:

靠北,超級炫砲……
LED 5050 RGB,我藍、紅是用 270 歐姆,綠色用 620 歐姆,結果他爸還是超級亮…我個人是覺得有點太亮,測程式的時候都快被閃瞎了,有點妨害看燈管,如果可以的話應該要再換大一點的電阻,把光度調小一點。
Github 裡面有附上 74HC238 跟 74CD4514 的測試程式,可以執行後一個一個量測兩個晶片的輸出,看看有沒有正常動作。

軟體中燈管要顯示的數字存在 Byte 裡面,0-9 對應 0-9,左點跟右點分別是 10 跟 11,照著 Byte 的位元寫給 74CD4514,12-15 則是會把 74CD4514 的 INH 降下來把燈管關掉。
void writeNum(byte num) {
  if (num >= 12) {
    digitalWrite(DISPLAY_E, HIGH);
  } else {
    byte mappedNum = mapNum(num);
    digitalWrite(DISPLAY_E, LOW);
    digitalWrite(DISPLAY_3, (mappedNum >> 3) & 0x1);
    digitalWrite(DISPLAY_2, (mappedNum >> 2) & 0x1);
    digitalWrite(DISPLAY_1, (mappedNum >> 1) & 0x1);
    digitalWrite(DISPLAY_0, (mappedNum >> 0) & 0x1);
  }
}
這裡要特別注意一下,如果要取出數字裡某個 bit 的時候,要用的運算符號是 & bitwise and ,不是 ^ bitwise xor 噢 ^.<
為什麼會有那個 mapNum ,其實是我 v1.01 的 layout …畫錯了,不確定是不是用的 footprint 的問題還是我自己蠢,總之陰極控制的接線是錯的,從 1-9 的接線完全反過來了,幸好這個 bug 可以用軟體修正回來,寫一個函式去轉數字就好了,這個也是 v1.02 修正。我覺得機率最高的原因,是我在看參考資料的圖的時候,沒有注意到它是 Bottom view,在設定 schematic to layout 的時候寫反了,最後 layout 也就錯了。
燈管的選擇 writeTube 和這裡一樣,0-7 各 bit 送給 74HC238 的三個腳位,就能開關某一支燈管,很簡單可以打包成一個函式來選擇燈管,首先我們就先寫一個掃描的程式,用 for loop確認每個燈管每隻腳位都有正常運作。
正常。
有了這兩個小函式,可以把燈管的值保存在全域變數陣列 display,然後用一個函式來更新它,只要這個函式在 loop() 中,燈管就會不斷顯示 display 的值;delay 只能是 delay(1) 或 delay(2) ,算是實驗得到的經驗值,不放 delay 的話切換速度太快,所有管子的數字會混在一起,delay(3) 的話則是看得出有點在閃。
void updateTube() {
  for (int tube = 0; tube < NTUBE; tube++) {
    writeTube(tube);
    writeNum(display[tube]);
    delay(2);
  }
}

使用 DS1307 記錄時間:

知道如何顯示數字之後,再來就是去接 RTC 時間,這裡我是使用別人包好的 DS1307RTC,照著範例把 library 引入之後,在 setup 呼叫 setSyncProvider(RTC.get);
即可和 DS1307 同步,之後就可以很方便的用 year(), month() 等函式拿到現在的時間值,非常方便。

DS1307 Interrupt:

DS1307 的 SQW 腳位能設定穩定輸出方波,搭配 arduino interrupt 就能每秒呼叫函式做點事情,我們已經把 DS1307 的 SQW 腳位接給 ATmega328p 的 digital pin 2,只要透過 Wire 向 ds1307 設定(請參考 ds1307 datasheet),其中 DS1307_ADDR 是 DS1307 的 I2C 位址 0x68,再對偏移 0x7 的位址寫入設定 0x10 即可,DS1307 可以設定輸出 1kHz, 4.096 kHz, 8.192 kHz 和 32.768 kHz 的方波:
Wire.begin();
Wire.beginTransmission(DS1307_ADDR);
Wire.write(0x07);
Wire.write(0x10);  // Set Square Wave to 1 Hz
Wire.endTransmission();
設定完 ds1307 就會輸出頻率 1Hz 的方波,我們可以把這個方波接給 ISR 來做計算開機秒數的工作:
void ISR_RTC() {
  toggle = !toggle;
  ++secCount;
}
attachInterrupt(digitalPinToInterrupt(RTC_SQW), ISR_RTC, RISING);
後來發現算秒數好像不能幹嘛XDDD

使用 DS1307 NV RAM 記錄資訊:

為了記錄世界線的資料,我們要用 DS1307 上面 56 bytes 的 NVRam 記錄資訊,不知道為什麼 DS1307 library 都不支援這功能,參考 arduino 論壇包了兩個函式來讀寫 NVRam,RAM_OFFSET 是 0x8,這樣就能把世界線的資料記錄在 NVRam 裡面了。
void writeNVRam(byte offset, byte *buf, byte nBytes) {
  Wire.beginTransmission(DS1307_ADDR);
  Wire.write(RAM_OFFSET + offset);
  for (int i = 0; i < nBytes; i++) {
    Wire.write(buf[i]);
  }
  Wire.endTransmission();
}

void readNVRam(byte offset, byte *buf, byte nBytes) {
  Wire.beginTransmission(DS1307_ADDR);
  Wire.write(RAM_OFFSET + offset);
  Wire.endTransmission();
  Wire.requestFrom( (uint8_t)DS1307_ADDR, nBytes);
  for (byte i = 0; i < nBytes; i++) {
    buf[i] = Wire.read();
  }
}
剩下的好像就是把上面的 code 猛攪一陣,就可以做出各種不同功能了。
要讀取按鈕的動態,可以參考官方文件 Debounce
整個 loop 裡面的流程,大概就是保存一個 state 的變數:然後依序
檢查 button 1 有沒有按下,有的話做一點事 -> 檢查 button 2 有沒有按下,有的話做一點事;再來依不同的 state ,設定 LED 跟輝光管顯示值的 display 陣列,最後呼叫 updateLED() 跟 updateTube() 顯示資訊。
我是設計有五個模式:自動切換/時間HH.MM.SS/日期YYYYMMDD/世界線顯示/全關省電模式,詳情請參考 github repository,這樣把自己寫的爛 code 展現在大家眼前感覺真是羞恥。

整體 code 差不多就是這樣啦,硬體能動之後改軟體什麼的都不算太難了,想玩的話可以弄一些,像是發送第一封 D-Mail:

2018年10月25日 星期四

自幹世界線變動率探測儀(Nixie Tube Clock):焊接

靜候三天,板子終於送到了,我在等的週末去光華把 BOM 表印出來去光華搬了一批元件,最貴的還是 LED 跟 BJT,其他買一堆電阻不過小錢…。
空板照,我是選藍色的阻焊,如果照動畫設定應該是黃色的,不過不管啦我喜歡藍色。

正面照:
背面照:

板子回來發現意外的順利,所有插件的腳位都沒問題可以直接穿過。
另外也有一些錯誤,中間高壓陽極的控制電路,MPSA92 的 footprint,我不小心用成 TO-92 腳位,以致焊點間的距離只有 0.25 mm,應該要用 TO-226 的腳位會比較好;第一個是焊接的時候很容易不小心就糊在一起,第二是高壓離這麼近其實有點危險,我覺得某幾個地方是真的有點漏電,即便管子控制全關的時候,還是會看到管子有很微弱的發光,可能升到 v1.02 的時候改進吧。
在焊接的時候有一位神級大大幫忙,才知道原來不小心焊錫糊在一起,用助焊劑一抹就開了,太神啦,對助錫劑刮目相看。

銲接之前工具要準備好,除了必備的烙鐵之外,推薦要買一隻好的尖頭鑷子,尖到可以刺人穿刺傷害 +20% 的那種,因為我們用的零件如 0603 尺寸都非常小,要好好的焊它就需要一支尖頭鑷子才行。

因為是二手管的關係,我們要對付的就是那該死的針腳,不知道到底是從哪裡拆/怎麼拆的,可以拆成這樣每支腳的長度都不一樣?甚至還有一支腳短到不能用的,因為我們沒有管座可用(它那腳位的狀況大概也不能用管座),我這裡的解法是去買 1 * 40 圓孔排針長腳,可以一支一支用鉗子剪開來,再一支一支,這樣我們就可以隨意插拔輝光管。
不能用普通的排母,輝光管的針腳太細,在排母裡面無法固定,圓孔排針裡面的彈簧才固定得住;也有人會用杜邦端子,用夾的把針腳夾住也是可以,只是杜邦端子要解開也沒那麼容易,不符合我們快速插拔的本意。


總之就是先把輝光管像上圖一樣插滿排針,接著將圓孔 IC 座一一插進 PCB 孔中,很不巧圓孔 IC 座的尺寸,跟我畫的 PAD 大小 0.914mm 超接近,然後這批管腳又塗了某種膠,讓它不像一般的元件一樣好折,在那邊用尖嘴鉗喬啊喬的,光插管子就插了快 1 hr 左右吧,說實在 Nixie Clock 愈做愈覺得這東西真是淘汰的好呀,要高壓驅動、浪費電、體積大、腳位又多又呈圓形很難安裝,真的還是懷古就好。
好不容易插好之後,一樣將 IC 針腳焊到電路板上,本來是不想焊的,不過發現不焊多少有點接觸不良。

其他部分大概都沒什麼,焊接只有一個要點就是:焊錫會黏在熱的東西上面,我的操作一般的拿烙鐵、焊點、焊錫三點相對位置呈三角,烙鐵頂住焊點加熱,焊錫輕碰烙鐵融化後就會自然流到焊點上了,如果是 SMD 元件的話簡化的步驟大概如下:
  • 在要放元件的一端先上一點焊錫。
  • 用鑷子夾起元件一端插入剛才上好的焊錫內(重新加熱焊錫讓它包住元件),拿開烙鐵,焊錫冷卻之後元件就被固定住;切記一定要先拿開烙鐵再放開鑷子,如果先放開鑷子,元件就會因為焊錫的表面張力而立起來或歪掉
  • 接著焊元件另外一端,因為元件已被固定這裡簡單焊就好了。
如果有助焊劑的話,上點助焊劑可以焊的比較漂亮一點,但也比較花時間。
還有一個常見的…直覺?一般而言通常是由烙鐵融化焊錫,讓焊錫自然流到焊點上,不過有時候,因為角度之類的關係,焊錫就是不會流過去,只會一直留在烙鐵上面;這時候的直覺反應就是不斷的給焊錫,但其實愈給只是停愈多在烙鐵上面,它不上到焊點只是角度不對而不是焊錫不夠多,這時候把烙鐵抹乾淨換角度重來會比較好。

這樣全焊完大概兩個工作天,趁著國慶假日借強者我同學強強林的實驗室把元件都焊完,全部粗估大概有 600 個焊點吧 (yay),幸好回家上電之後:
拿鱷魚夾夾二極體的輸出點,高壓電路正常動作:


用外接 5V 測試,LED 電路正常動作,也可以用 TX/RX 介面燒 code 進去跑:


測試過後,高壓電路、5V 電路、控制電路、LED 電路、RTC 電路都有正常運作,兩天的辛苦都值得了。

自幹世界線變動率探測儀(Nixie Tube Clock):電路板實作

下面就真的要開始用 easyEDA 畫 Layout 了。
EasyEDA 能做簡單的模擬,不過基本上功能非常的弱,只能模擬一些節點的電壓,大部分的元件也沒有模型可供模擬,所以請放棄在 easyEDA 模擬的念頭。

第一步:畫 schematic,調整 footprint

是在 easyEDA 上面畫 schematic ,如前幾篇文章出現的高壓電路的 schematic;在畫 schematic 的時候,就可以想想 Layout 大概要用什麼元件,簡單的元件如電阻、電容、電感、二極體等等會出現在左邊的選單裡,並且可以選擇所要的型號,像電阻就有 0201, 0402等平面元件跟插件 Axial 0.3-1.2 等 16 種可選。
比較複雜的元件可以從上面的選單 Place -> Component,打入關鍵字,插入找到的元件,通常同一個元件都能搜尋到 SMD 跟 DIP 兩種版本,記得要插入正確的;插入元件之後要取一個好的名字,方便在 Layout 跟焊接的時候,能夠快速知道是哪一個元件。

編輯中也能在上面的選單找到 Footprint Manager,裡面可以編輯每一個元件對應的 footprint,還有元件符號跟 footprint 腳位的對應,來跟真實元件對應;例如不知道為什麼,我買到一批 5050 RGB LED,腳位跟預設的腳位就是不一樣,因此用 footprint manager 調整過;另外像是0603的電阻因為預設的 footprint 有一個 silk 框,我想畫得密集一點就換了個沒有 silk 的 footprint。

建議上每畫一個區塊的 schematic ,就定時按一下 Update to PCB,讓 easyEDA 把 schematic 上的元件放到 PCB 上,然後安排一下 layout footprint 的位置;因為如果等畫完再一次轉換,會造成所有的 footprint 都擠在一起,讓你分不出誰是誰,一次轉一些安排位置,或至少分個群,之後在 layout 會方便很多。

第二步:擺放 footprint 

在 Layout Editor 上面畫 PCB,進到 Layout Editor 之後,首先先設定 Design Rule 跟網格等資料。
網格可以用 mm 或是 mil 當單位(用 inch 當單位是有一點太大了),easyEDA 預設是用 mil 當單位,如果要用 mm 當單位的話記得一定要把 grid size / snap size 從 0.254 mm 換成比較好看的數字,如 0.1mm
Design Rule 請參考廠商給的資料,例如下面是我選用的 JetPCB 的製程資料;easyEDA 畢竟是免費軟體,提供的規則檢查只有線寬、線距、鑽孔大小、線長;不像 kicad 除了這些,還能做更多的像是各層獨立規則。
只截取 DRC 部分的規範:
  • 線寬 0.25 mm
  • 線距 0.25 mm
  • Via 直徑 0.5mm
  • Via 鑽孔直徑 0.3mm
畫好 schematic 之後,Layout Editor 上面應該已經有所有元件的 footprint,先做好放好位置、調整方位等,如果看到有 footprint 不是自己想要的,也可以隨時回 schematic 修改然後再 update。
個人經驗是,因為 easyEDA 功能不全的關係,一但畫了走線之後如果又修改 footprint 的腳位對應,要再改走線就非常費工,所以畫走線之前,一定要確認好 footprint 腳位跟 schematic 都已經是正確的。

第三步:畫 Layout 走線

放好位置之後就能開始畫走線,雖然 easyEDA 有提供 auto router,但我個人不建議使用,它只會儘量畫最短路徑畫,反而沒什麼規則,例如我的輝光管部分,因為輝光管的陰極同數字是全部接在一起的,它就真的給我照最短路徑畫得亂七八糟。
不過 auto router 也可以當一個指標,如果你的 layout 開了 auto router 跑不到 90% 以上,表示你的 layout 還不夠簡單,可以看看 auto router 都是哪裡繞不出來一直在重試;簡而言之:easyEDA 的 AutoRouter 只會繞出一堆垃圾,請還是乖乖用手畫。

在 easyEDA 裡面用 track 畫走線,照著 ratlines 用走線連起來就行了,在輝光管部分的畫線要點在於分開上下板,我是下板走垂直線、上板走水平線,這樣子上下板的線就不會打架,如下圖所示:

另外有一些其他 layout 的注意事項:
  • 為了燒錄,要把 5V, GND, TX, RX, Reset 拉出來
  • 用個 jumper 隔離外接 5V 跟 78M05 的輸出,這樣可以單獨測試所有控制電路的功能。
  • 這個是我做的時候沒想到的,在通往 LED 的 5V 電源線上加上 jumper ,這樣覺得 LED 太亮的時候,可以用硬體的方式關掉 LED。
  • 電阻、電容、LED 可以的話儘量選 0603 省空間,我覺得 0603 是覺得可以輕鬆焊的極限,0402 或更小就很抖了。
  • 在 MC34063 那邊的限流電阻,因為在最大電流下,功率可能會升到 100 多 mW,所以我是用 1206 的電阻;我也是現在才知道原來電阻的尺寸是跟它能承受的功率有關。
  • 高壓電路的地方,依這個論壇所言,讓電感與二極體還有MOS位置最短。
  • 所有的晶片,在 VCC 的接點前都保留一個 0603 約 100n 的電容做為穩壓。
  • 依照晶體振盪器 datasheet 的建議,在振盪器周圍一個範圍要鋪地,避免信號線出現,以免影響時脈的準度。
JetPCB 也有提供一些參考規範,我大致整理一下這次畫 Layout 的規則:
  • 電源線寬為︰1 mm - 1.2 mm,如果有更大電流的應用,請參考線寬計算機
  • 信號線寬建議為︰0.2-0.3 mm,我是用 0.4 mm;其實 PCB 承受電流的能力很大,1oz 的銅、0.25 mm 差不多就能走 1A 了,所以畫細一點是沒差的。
  • Via 有兩種,外徑/內徑為 1mm/0.5mm 跟 1.6mm/1mm ,分別用在訊號線跟電源線的 via。
  • 鋪銅間距:因為我們的電路板會走高壓電,在網路上找到一款間距計算機,我們最高的電壓應該是200 伏特,算出來的安全間距是0.4 mm ,因此我是用 0.6 mm 作為鋪銅間距。

第四步:鋪銅與 DRC, LVS 與他

Layout Editor 左邊的 Design Manager 打開,裡面有三個選項:Components,Nets 跟 DRC Errors
Component 方便你找元件用,比較沒這麼重要;Nets 跟 DRC Errors 分別是 LVS 跟 DRC;完成走線的時候, Nets 裡面應該只有 GND 是錯誤的,因為我們還沒有鋪銅,把整個地連起來。
鋪銅選擇工具的 Copper Area,把要鋪銅的部分框起來,easyEDA 就會自動完成鋪鋼,正反兩面都需要鋪銅,鋪完之後再從工具列選 Copper Area Manager 去調整鋪銅間距。
鋪完銅的時候,LVS 就要可以通過了;DRC 的話在鋪銅前跟鋪銅後都要跑過一次,第一次是要修掉走線的錯誤,第二次的是要確認整個 layout 沒有問題,畫完大概會像這樣:

上板走線:

下板走線:

上下板走線:

基本上我是畫的超寬鬆的,寬度因為受限於輝光管比較難縮,高度其實可以再縮一點,元件排更密一點,我覺得縮 1-2 cm 不是問題,不過第一次畫 layout 自然是小心為上。
個人經驗是不要讓焊點間的距離小於 0.7 mm 左右,再小第一個焊的時候容易短路,烙鐵也可能不小心戳到不該戳的地方。

第五步:收尾下單

做完這些,就可以匯出 layout 成 Gerber 檔下單製造了,最後還有一些,像是留下未來打銅柱的鑽孔,留一些文字等等。
在真正下單之前一定要再次檢查,把 Top Layer 跟 Bottom Layer 匯出成 pdf,用印表機 1:1 分別印出,對照有沒有哪裡有問題,手邊買好的元件是否能正確的對到印出來的穿孔,畢竟板子做了就是做了,做壞要用暴力修的難度也很高,多檢查幾次不吃虧,我就有對照的時候發現 schematic 的地方有畫錯,差點整塊板子變廢物,Board is dead, mismatch
洗板選用戀戀科技 Marten 大大推薦的 JetPCB,好到連日本人都來用?(雖然說他們的問答版上,有一個回答就是不服務台灣以外的顧客owo),不過他們的網站需要先註冊為會員才能下線。

easyEDA 下載好的 gerber 檔,裡面的 PasteMask 可以直接刪掉沒關係,其他的打包送給 JetPCB,工程人員會再次幫你檢查電路板,看看有沒有太大的問題,我是選三天到貨的方案, 電路板尺寸 264 mm X 104 mm,總價是 4200 NTD。
可…可惡,早知道當年在學校的時候就該來做 nixie clock,在學校就能用學校的洗板機免費自己洗驗證板了,現在都要花大錢去外面洗板子,畫錯錢就直接噴飛QQQQ。

總之電路板最後終於成功下線,之後就是靜待三天,等電路板寄到就可以開始焊電路啦。

2018年10月23日 星期二

自幹世界線變動率探測儀(Nixie Tube Clock):電路板基礎

介紹了這麼多,我們終於要進到電路板了,之前介紹的許多東西在這邊一口氣要全部發揮出來,我是沒有很確定輝光管用洞洞板會不會有問題,不過要整合起來還是洗電路板比較潮。

電路板 - 也就是 Layout - 這種東西一定要用軟體幫忙輔助,例如小畫家,專業人士跟企業可能會用 altium ,我們沒錢的當然也有沒錢的玩法:例如開源軟體 kicad、網路的電路板軟體 easyEDA(需要註冊,可用 Google 帳號)、Eagle(需要註冊),其他兩個都要註冊,真正開源自由使用的其實是 kicad。

在這裡我是選用 easyEDA 來進行 layout,原因很簡單,因為 easyEDA 允許大家自由分享他們畫的元件跟 layout,我用的輝光管 IN-14 已經有人畫好插孔的 layout,我可以直接引入使用,不像 Kicad 還要自己下載其他人分享的描述檔匯入,方便性上比 Kicad 高一些。
當然 easyEDA 也是有壞處的,相比 Kicad 它的功能少了不少,像是 DRC,能檢查的只有基本的線寬、線距、鑽孔大小,用 electron 實作的網頁介面,進行一些大量操作的時候速度會明顯慢下來(例如大量元件 lock/unlock 會很明顯的頓一下),我個人的體驗是 Firefox 跑得明顯比 chrome 還要快跟穩www。

Layout 就請參考這個連結,裡面有完整介紹 pcb layout 的詳細步驟。
Layout 有兩種可能的設計:放在一塊板子或是把控制板跟插管板分成兩塊,我最後是選擇縮在一塊板子裡面,這樣只要洗一塊比較便宜(yay),不過相對來說也畫得沒那麼漂亮,從上面看除了輝光管之外還有一堆電子零件會比較醜,其實我不確定能不能兩塊畫在同一塊然後請板廠幫我切開,如果板廠是算面積計價,這樣對他們來說應該也沒差太多才對。

下面簡單介紹一下 easyEDA 在 Layout Editor 層的設定,還有跟 Layout 共同的概念,下一章再來提真正的實作,其實這篇我一直在考慮怎麼分成兩篇,畢竟內容太相關了,但合在一章內容好像又太多了:
  • Top/Bottom Layer
走線的部分,分別是正面金屬跟背面金屬,用這兩層畫連線。
隨著大家對小型化的要求,像我這樣單層、雙層的 layout 已經無法再微縮,市面的產品就有更多層…我查到最多六層的板子,easyEDA 也有支援 4 個 inner layer,不過我們只要雙層板就很夠啦。
  • Top/Bottom Silk Layer
正面文字/背面文字,用來寫字、元件名稱等,通常都是把元件集中在正面,背面文字是不需要用的。
  • Top/Bottom Paste Mask Layer
  • Top/Bottom Solder Mask Layer
Paste Mask 跟 Solder Mask 分別是焊膏防護層跟阻焊層
看到 Mask 這個關鍵字城鎮中心的鈴鐺就要噹噹一下,這表示這兩個東西畫的是負片,跟上面幾個正片相反,正片是哪裡畫東西,哪裡有東西;負片是哪裡有畫東西,就表示哪裡沒東西。
阻焊層應該比較好理解,哪裡有畫東西,哪裡就不會上阻焊層。
焊膏防護層它的目的是要在機器生產的時候貼 SMD 用的,因為我們是手焊所以可以不要管它,這層是在上錫膏的時候,依照這層的負片做成鋼板,把鋼板放在電路板上面之後塗錫膏再移除鋼板,所以造成錫膏層是正片的結果,詳細可以參考這部影片

  • RatLines:

這個是畫完 schematic 的時候 easyEDA 自動幫你產生的,標示哪個節點要走去哪個節點,理論上再畫完所有走線之後,應該只有 GND 的 Ratlines 會顯示出來;上完鋪銅之後則是完全不會有 RatLines。

  • BoardOutline

標示整個電路板的製造邊界。

  • MultiLayer

在 easyEDA 裡面,有三種不同的孔:Pad, Via 跟 Hole,這幾個有機會用到 MultiLayer。
相關內容可以參考工作狂人(這個網站幾乎找 PCB 資料一定會找到,超專業的硬體生達達人),我猜這純粹是用詞不統一的關係,總之他們的關係是這樣的:
Hole:正式名稱是(NPTH,Non Plating Through Hole,非電鍍通孔):單純的用鑽針在電路板上鑽一個洞,不做任何事,洞裡只有玻璃纖維,上下層亦不導通,事實上 easyEDA 最後鋪銅的時候,會自動繞過 Hole 以免短路,它的用途也就只有鎖銅柱固定電路板。
Pad:可選擇 Top/Bottom/Multi layer,如果選 Top, Bottom 的話就是一塊裸露沒上 solder mask 的金屬,easyEDA 會在 Solder Mask Layer 加上 Pad 的部分,讓這塊最後不上阻焊層;如果是 Multi layer 的話,則是正式名稱的 PTH(Plating Through Hole,電鍍通孔),鑽孔之後會在內部鍍鋼導通上下層,所有 DIP 元件的腳位都是走 Multi Layer 的 Pad,因此焊接只要焊背面,畫走線的時候無論 Top/Bottom 都能導通。
Via:Via 只有 Multi layer 的選項,和 Multilayer Pad 的差別,在於 Via 不會有 solder mask 的對應,也就是說它最後會被 solder mask 的綠漆蓋住,如果是高價位一點板子還會用把 Via 塞起來以免焊錫流進去,因此不能在 Via 焊東西,它只是用來導通電流的。
如果是多層板,還會有如埋孔跟盲孔等東西,不過這已經超出本文的範圍了。

我們上面提了這麼多,其實 easyEDA 在帶入元件的 footprint 的時候,他就幫我們畫好元件接腳 MultiLayer 的 Pad,只要用上下層金屬把各接點連起來就好,所以真正要編輯的層,其實也就只有 Top/Bottom Layer 連線,打一些 Via 來連接走線,加上 Top/Bottom Silk Layer 的註解;其他包含阻焊層、PTH、NPTH 鑽孔資訊,easyEDA 都會在匯出 Gerber 的時候幫我們處理好,除非有特別設計不然在 easyEDA 上阻焊層是留空就好。

整個電路板實作的流程大概是這樣:

  1. 依照元件,畫 schematic。
  2. 將 schematic 轉成 layout ,代入元件 footprint。
  3. 擺位置,各元件放到容易繞線不打架的位子上。
  4. 畫走線,鋪銅,上元件之外其他說明文字
  5. 列印 layout 檢查,匯出 gerber 檔下線製作

下篇文章就來走一次這個流程吧。

2018年10月22日 星期一

自幹世界線變動率探測儀(Nixie Tube Clock):控制電路

現在我們進到本作品除了輝光管之外最貴的部分了,輝光管貴是因為它老舊了,用一支少一支,控制電路的部分就是在買它智慧財的價格了。
買電子零件的時候,平常用量最大的電阻電容那種,都是稱斤論兩一條 10 個 5 元在賣的,更貴一點的是二極體跟 LED,大約 5-10 元左右,最貴的就是晶片了,愈複雜的愈貴,一般邏輯晶片 74HC238: 20,74CD4514: 40,DS1307 跟 ATmega328p 就衝到 120 跟 150 了。

電源:

首先要先處理電源的部分,我所用的晶片基本上都是用 5V 驅動。
產生 5V 的方法也很簡單,用一顆 78M05 的穩壓 IC ,輸入 12V 輸出 5V,外接接地的 10K 電阻和穩壓 104 陶瓷電容;真的進到晶片的地方設一個 jumper ,這樣我們可以在測試的時候先用外部的 5V 來供電;每個晶片的 Vcc 之前,也都加上一顆 100n 的 0603 電容作為穩壓。

控制:

自從 2014 年 arduino 橫空出世,開始攻佔台灣之後,幾乎成了微控制器的第一首選,低階到高階全包;我們手頭邊沒有熱風槍、錫膏等工具的話,要焊接 SMT 封裝的元件難度太高,最適合的控制器自然是 ATmega328P 了,arduino 的標準晶片,DIP 封裝容易安裝,軟體工具鏈也很完備。
請參考下面這個網址,讓 ATmega328p 可以吃內部的 8MHz 晶體振盪器(裡面的 8MHz bootloader 下載點只有到 1.6,雖然現在都 1.8 了但燒 1.6 的還是會動)。畫個晶體振盪器的位子也不會太複雜,如果喜歡外接振盪器的,就自己在 layout 上留個晶體振盪器的位子,不過 16 MHz 運作下也會比較耗電就是。
在 layout 上,記得要把 pin 1-3, 5V, GND 拉出來,未來只要用排線接上去就可以從外部,利用拔掉晶片的 arduino 進行燒錄,或者可以(不確定)保持在燒錄 bootloader 時的接線,在 upload sketch 的時候用 upload using programmer 來燒錄。

RTC:

RTC 的功用是在 Arduino關機的時候,能用電池供電計算時間,這個時鐘應用下 RTC 是必須的,不然一關機時間就重設了;精密設計下,RTC 晶片維持時間所需要的電力非常少,如我選的(也是最常見的) DS1307 為例,只需要 500 nA 的電流就能維持時間,正常使用,隨便一顆鋰電池都能撐到 10 年以上,買兩顆就能撐到 2036 年了
RTC 也可以直接買 DS1307 的 arduino 模組,不過他會吃掉全部的 analog 腳位,不然就參考下面這個網頁,在 layout 上面加上 DS1307 所需的元件;和這裡不同的是,我 DS1307 SQW 腳位有拉出來接給 ATmega328p 的 pin4 作為未來 interrupt 控制使用。
如果要求精準的話,可以用高精度的 DS3231 ,跟 DS1307 吃外部 32.768 kHz 晶體振盪器不同,DS3231 把整個晶體振盪器放到晶片裡,以達到高精確度。相對的 DS1307 如果晶體振盪器 layout 跟焊接不夠好,就會影響到精確度。
我這裡是用 DS1307,因為 DS3231 一顆要 16 支腳,比 DS1307 多了八支 NC 腳位不知道是幹嘛用的,何況我這個只是一般的時鐘,不是要做 GPS。

腳位:

一切問題在於腳位,像是復古咖啡那樣用 LPC1343 這種含著金湯匙出生的晶片,光 GPIO 就有42 隻當然隨便拉,ATmega328p 上了 arduino 只有 14 個數位 pin ,加上 analog 也只有 20 隻,自然不能亂來,這也是為什麼我們會需要 74HC238 跟 74CD4514,用來減少控制輝光管需要的 pin 腳,不然陽極 8 隻陰極 12 隻就超過 ATmega328p 的數量了,如果方便的話,也可以直接上一顆 PLD 代替這兩顆很難買的邏輯晶片。

以下是設計的腳位表,搭配下面 schematic 的截圖跟網路上找來的 ATmega328p 腳位圖給大家參考:
一般必要:
Pin 7, 20:VCC, AVCC。
Pin 8, 22:GND。
Pin 2, 3:TX, RX 保留給燒晶片使用。

開關,這裡請接一個 5K-10K 的電阻到 5V,並接開關到 GND,按下開關就能把腳位的電壓拉下來。
Pin 1 Reset:Reset Button。
Pin 23, 24:Analog Pin 接拿來作為設定用的開關。
Reset,5V,GND,TX,RX 五支腳要拉去一個排母,之後就能插線燒錄了。

RTC:
Pin 4:SQW for interrupt control,注意 interrupt 只能裝在 Pin4, 5 兩個 INT 腳位。
Pin 27, 28:I2C SCL, SDA

LED:
Pin 5, 6, 11:管子背光 LED G, R, B,接 2N2222 的 Base。
Pin 25:用來顯示 ATmega328p 狀態用的 LED,例如收到信號的時候閃一下之類的,無論如何至少都接一顆,不然 ATmega328p 在幹嘛你都無法知道,別忘了限流的 270 歐姆電阻。

輝光管:
Pin 12 - 14:陽極控制搭配 74HC238 需要 3 隻腳。
Pin 15 - 18:搭配 74CD4514 ,陰極控制需要 4 隻腳位。
Pin 19:多留一隻腳位給 Enable (CD4514 的 INH),才能把管子給關掉,做到更多樣的控制。

除了 Pin 26 Analog 腳位沒用之後,可以用的腳位都用上啦(yay,當然我把晶體振盪器去掉,等於多加了 Pin 9, Pin 10,我是沒用就是,也沒預留晶體振盪器的位子,所以就是浪費掉了,要的人可以多接幾個 LED 來幫助 debug 之類的。

2018年10月21日 星期日

自幹世界線變動率探測儀(Nixie Tube Clock):驅動電路

有了高壓電源之後下一步是驅動電路,如何控制 180 伏特的高壓電源開關?

查資料的時候發現有些人是用 TLP521 光耦合器,不過我看 spec 之後是不建議用這顆,第一是它很貴,光華商場一顆單價 15 元,甚至有 30 元的;第二是它 VCEO 只有 55 V,實測的時候 TLP521 關掉還是會吃到 130 V,遠超過 VCEO,實際上是沒有怎麼樣,但不知道用久了會不會有問題,到如壽命減短,或是漏電愈來愈大最後關不住之類,搞不好也是沒有問題只是多漏一點電。
我個人是保險一點,同樣參考復古咖啡,用 MPSA42 跟 MPSA92 兩顆對稱的高壓 BJT 來控制,這兩顆單價只要 3 元,便宜得多,耐壓高達 300 V 絕對夠。

設計的部分我基本上和復古咖啡是一樣的,就請大家參考那邊,這裡就不細講了,幾個不一樣的地方是電阻,IN14 操作的電流是 1.5 mA 左右,限流電阻大約是 22k;左、右小數點的限流電阻則是 75k 左右,所以我是在陽極上一顆共用的 22k 電阻,左、右小數點的陰極加上一顆 51k 的電阻,schematic 畫起來像這樣: 

另外一個不同的電阻是 NPN 的驅動電阻,在陰極驅動的地方,要驅動的電流是 1.5 mA,MPSA42 的 β 值大約是 50-100,保守一點算 50 基極電流只需要 0.03 mA 就夠了,加上我用的控制器 ATmega328p 的驅動電壓又是 5V 而不是 3.3V,扣掉 Vbe = 0.9V,用 100K 的電阻就足夠打開 MPSA42 了,我在設計上是用 51K 的電阻;陽極驅動電路也是,只要驅動 0.38 mA 的電流的話,電阻用到 500K 都沒有問題,我為了採購方便還是買 51K 的電阻就是。

高壓的部分有些人也許買得到蘇聯制的K155ID1 之類的高壓 BCD to decimal 驅動 IC 之類的也是可以,但我是覺得沒什麼必要,一方面它也只是個 BCD-to-Decimal 的晶片,要控制小數點還是要靠高壓 BJT,而且要買個 K155ID1 也不容易,不像高壓 BJT 電子零件行隨便買,這也是難得 IC 反過來被離散元件取代的地方呢。

74HC238 跟 74CD4514 (如果有 74HC4514 當然是最好啦)是網路上搜尋找到的邏輯閘,分別是 3-8 demultiplexer 跟 4-16 demultiplexer,要注意他們跟 HC138,HC4515 很像,但其實完全不一樣,一個是選到的輸出 high 一個是 low,小心不要買錯了。

另外還有一部份是操控 LED 的驅動電路,現下流行在管子下面放 LED 打光,看起來就會很潮,潮到發光(X。
LED的部分我是選用 5050 RBG SMD LED,也可以用 3528 尺寸會比較小,參考 5050 的電路圖,RGB 分別要接 270, 680, 270 歐姆的限流電阻,測試的電流我記得是 10 mA 左右,不必到規格要求的 20 mA,就已經可以發出滿亮的光了(而且綠色的特亮,為了讓它暗一點才把電阻調大了),真的要 20 mA 的話電阻可能會小到 180 歐姆左右,我在想那個光度應該足以閃瞎人的眼睛,甚至現在這個亮度我都覺得太亮,可以再選大一點的電阻。

另外還有一個問題是控制的驅動能力,因為我們選用的控制 IC ATmega328p,數位 Pin 腳的電流最大只有 40 mA ,總和最大是 200 mA,一支腳位不太可能驅動得了 8 個 LED,我們也不可能生得出 8 支 Pin 腳來控制 LED。
在這裡我們選用簡單的 NPN 2N2222 控制大電流,參照 datasheet,在我們的條件下,2N2222 的電流增益可以到 100-200,基極只需要大概 1-2 mA 就夠了,用 2.2k 的限流電阻應該非常安全,用到 5 K 左右也還是 OK 的,用 2.2k 單純因為控制電路那邊有 2.2k 的可以用,一起買比較方便。

2018年10月20日 星期六

自幹世界線變動率探測儀(Nixie Tube Clock):自組高壓電路

一般自組輝光管時鐘都要配高壓電源,當然從 110V 變壓到 180V 再經過整流、穩壓也是一招,但這樣很難調整電壓,自己繞變壓器其實也比直流升壓麻煩,體積跟重量也都大得多。
我們之前買的高壓電板板,要直接用也是 OK,只要在最後 layout 的時候,依照板子的規格在上面鑽洞來接銅柱,接線的地方預留接腳即可。
我的設計是自己接 MC34063 的直流升壓電路(因為好玩),MC34063 算是非常…古老的晶片,它年紀可能足夠當我老爸,網路上一搜可以搜到許多不同人的實作,不過通常蠻簡略的,也會用到一些比較不常見的元件。
這裡是參考強者我同學小新大大所找到的復古咖啡(一)的內容,自己接一個 MC34063 的高壓電路。

這是電路圖:

Boost Converter 的原理請大家自己上 Wiki 說明頁(當初好像是在電機機械實驗遇到這玩意兒),簡單來說我們在電路上加上一個開關,開關接通的時候會對電感充電,關閉的時候則由電感放電到負載,利用電感釋放能量把電壓飆上去,利用二極體把高壓鎖在負載,輸出放一個電容在開關打開的時候維持電壓。
這個開關必須的高速開關,與 boost converter 搭配的,就是 555 或是我們所用的 MC34063 晶片,其實 MC34063 的設計非常簡單:

它做的事情也很簡單,MC 34063 內部會產生 1.25 V 的電源,不斷和 5 腳位的輸入比較,如果輸入低於 1.25 V,就會將內部震盪訊號送出去,使開關不斷開關(這什麼饒口的說法)。
震盪訊號的頻率是由 3 腳位接的電容決定,可以從幾 10 KHz 可以到最高 100 KHz 左右,我接 2.2n 的電容,頻率大約是 20 kHz。
MC 34063 有一個安全機制,因為對電感充電的時候,當電感充電完成時電流會急遽增大(電感變導線了,等於電源直接接地),MC34063 (推測)會用 7 腳位去偵測電壓,如果電壓相比 6 腳位的 VCC 掉太多的時候,表示電感已經飽和,MC34063 就會提早結束充電;這個偵測電壓是 330 mV,使用 330 mV 除以限流就能得到限流電阻值,規格書上的建議最小電阻是 0.2 歐姆(意即限流是 1.65 A),因為市面上買不到小於 1 的電阻,我在這裡就用並聯五個 1 歐姆做到 0.2 歐姆,如果希望限流小一點,可以不要並聯這麼多個電阻。

與 MC34063 搭配的是 MOS 外部開關,讓 MC34063 壓力不會這麼大,這邊就是照復古咖啡的建議選元件,MOS 開關選 IRF840,往高壓的二極體用 FR104;開關 MOS 的二極體要選速度快的,例如 1N914;輸出電容用 250V, 10u 的電解電容。
復古咖啡有提到,增加一路 PNP 2N2907 放電路徑的重要性,我在電路板上驗證的時候有測試過,在輸出 170 V, 1.7 mA 在狀況下,有放電路徑的電路只需要 12V, 62 mA 的輸入,沒放電路徑的電路卻需要 100 mA。

這裡使用的電感千萬不能用色碼電感(電阻式電感),我曾經試過結果它就冒煙了XDD,一定要選銅線繞的電感,在光華也只有一家地下室的源達有在賣,或者也有人用軸向的電感(?),我最後是選銅線繞的電感,感覺比較保險(光華商場買不到參考設計的大顆軸向電感,工字電感有點小顆怕怕的)。
感值的部分應該用 68 - 100 uH 的電感,就可以推動兩到三支管子(沒實際測試過,至少 68 uH 是 OK 的),和直覺相反的,如果這裡要推更大的電流,其實電感要用更小,利用小電感快速放電的特性跟高頻率的振盪把電流逼上去,但因為 MC34063 100 kHz 的振盪頻率不算太快,用太小顆的電感沒事就會飽和,因此 MC34063 的升壓跟輸出電流都有一定限度。

回授電路的部分就是用 511K 和 3.3K 電阻分壓,加上 2k 的可變電阻,這樣分壓的可調範圍是 511K/3.3K -> 511K/5.3K,也就是 193V - 120V,這裡對電阻值比較敏感,因此選用誤差值 1% 的五環精密電阻。

最後在電路板上的完成照,其實我 lay 得滿稀鬆的,外購的高壓板同樣的 48 x 41 mm^2 裡,在麵包板上測試的版本則是忘了照了XDD:

除了 MC34063 之外,下面這個連結也有人有其他效率更高的設計,不過因為他沒有提到更詳細的設計內容,只能當個參考;當然裡面提到的一些 Layout 技巧還是用得上。
我在插麵包板測試的時候,我的電路效率不知道為什麼一直上不去,大約卡在 40 %,外購的高壓板效率可以到 68% 左右;雖然有點懷疑是不是電感品質的問題,或者是 layout 的問題,只要到 PCB 上就解決了?但我在 PCB 上沒有預留量電流的地方,也因此無從驗證了。

2018年10月19日 星期五

自幹世界線變動率探測儀(Nixie Tube Clock):材料取得


一般材料表:

請參考 Github 連結,hardware 下有直接從 layout 軟體匯出的 BOM 表跟我手記錄的表格,注意兩份內容是有出入的,手記錄的應該是比較完整一點,因為像 IC layout 軟體就只會匯出 IC ,手記錄就會記上還要 IC 座,然後匯出的 BOM 表有些元件如 0603 電阻,選擇不同的 footprint 導致同樣阻值的電阻沒有在同一列,也要注意一下,省掉採購時的麻煩。
基本上零件都是光華商場買得到的東西,元件除了電阻跟一些電容外,都是以 DIP 的為主(其實光華商場也買不太到 SMD 的晶片元件),如果在 layout 上想要簡單一點,或者畫小一點,可以自己上…例如貿澤電子之類的電子元件網購,我是有點懶,家裡也沒有適合上 SMD 晶片的工具,就直接畫 DIP 版本了。
手記錄表格裡,有些元件是測試需要,但如麵包板、單芯線、焊錫之類的,如果你家有的話也可以不用買。

另外, 74HC238 跟 74CD4514 兩個晶片,光華商場跑遍了都沒有在賣,反而在高雄的長明街一家店 - 應該是禾樺電子 - 買到了,證明我海港市大長明街才是真正的電子一條街,另外台北車站裡面的台灣金電子也有看到在賣,光華商場根本廢物ㄏㄏ。

下面是比較特殊的東西:

輝光管:

我是在 ebay 上訂的 IN-14 輝光管,12 支要價 48 USD,因為沒 ebay 帳號,從 ptt helpbuy 版上選一個看得順眼的 JKL 代購,含運費等等公道價八萬一新台幣兩千多元,平均一支管子比七段顯示器貴個十倍吧。
會選 IN-14 是因為它有小數點,因為是二手管,大概從某些神祕儀器上拆下來的,一大問題是每支座腳不等長,上面還黏有奇怪棕色的膠,也不知道怎麼處理,總不能丟去洗吧。

如果大家想要做個高端的時鐘,或是你真的要做世界線變動率探測儀的話,也是可以買新管,通常價格會再翻一倍不止;在製作過程中也有看到下面這個網站 daliborfarny,有一位捷克的人兄還有在持續生產新管,但他的管子也沒有小數點,一根新管單價就要 145 USD(也可能是其他幣值,但機率不高),這個還是給有錢的大大去買就好OwO

高壓電源:

這應該是輝光管取得管子之後的頭號問題,取得管子簡單,但誰家裡沒事會出現 180 V 的直流電源?
強者我同學強強林是在淘寶上買了一片升壓電路板:「辉光管直流升压电路,MC34063方案,12V输入,大电流,带5V输出」,大家應該把這個標題拿去搜就可以搜到連結了,回來把它的電路翻一翻看一看畫一畫,其實就是標準的 MC34063 的升壓電路(不然勒,人家標題都寫了),5V 則是用 78M05 從 12V 轉下來。
我覺得買升壓電路板是有好處的啦,買回來再買點線材就能先讓管子亮起來,之後專注在控制上面就好,總比管子都買好了卻缺個高壓電路什麼都不能做好,不然光想到高壓電路就懶,然後就會沒進度。

如果決定直接要用高壓電路板當高壓電源的話,材料表裡面的高壓電路部分的材料就可以不用買了,相對來說,用高壓板的問題就是最後板子後面會有一塊凸起的小電路板,能不能接受就看個人了。
全部材料買起來,扣掉輝光管其實也要 400-500,完全就是積少成多(yay),下一步馬上來自組 MC34063 升壓電路。

2018年10月18日 星期四

自幹世界線變動率探測儀(Nixie Tube Clock):前言

總之先秀個成品:



看過 Steins;Gate 一直想自幹一個世界線變動率探測儀,這個點子其實有點久了,不過也就只是一直放著而已,畢竟學生時代沒什麼錢也沒什麼時間下手。
直到最近因為 Steins;Gate 0 開始播送,強者我同學小新大大跟強強林大大也生出想來做一個的念頭,手頭上也比較寬裕了些,於是三人一起怒做一陣,所以整個九月跟十月初除了看書之外都沒有在寫 code,功力退步十年 QQQQ,這裡也沒在發文都要長草了。
不過大家放心,接著就是開發過程記錄的 N 連發,保證把這裡的草都除到連基岩都露出來。

輝光管(nixie tube,或譯數碼管,好像沒有統一的譯法,但我覺得輝光管比較符合它的發光原理)總之就是個1950年代的玩意,現在大概只有懷舊狂會去用它,都買不太到了,ebay 上有一些舊蘇聯國家的賣家在賣,大部分都是拆下來的二手管,價格都貴到靠北,我買的已經算比較便宜的,如果是新管會貴上一倍。
細看輝光管的內部,會看到許多數字型狀的細金屬線,中間以陶瓷材料隔開,作用是當作陰極,陽極則是網狀包在陰極外。陰極不像日光燈一樣會被加熱射出熱電子,而是在兩極上加上170-180 伏特的高壓使氣體游離,離子再撞擊其他氣體跟電極而發光,電極溫度會保持在40度左右,有人覺得這樣發光挺迷人的。
輝光管要高壓驅動,相較現今成熟的顯示技術,消耗功率大、體積大、可視角度窄、還要高壓驅動,七段顯示器出來之後都被淘汰光了,可預期這東西的價格會一路走高(其實我很懷疑2036年還買得到這種東西)。在找相關資料的時候,是有在 kickstarter 上看到有人要製造新的輝光管,但出貨之後似乎沒有持續製造販售。

做這個會遇到一籮筐的問題,決定就在這裡記錄一下開發流程,按照所謂的開源慣例,本作品所有內容都公開在 Github 上面,包括硬體的 Layout Schematic、Layout Gerber 檔跟軟體的 Arduino 程式碼,歡迎大家來提意見,如果有什麼問題也歡迎提出。

下面是本系列所有文章的連結:
1. 材料取得
2. 自組高壓電路
3. 驅動電路
4. 控制電路
5. 電路板基礎
6. 電路板實作 layout
7. 焊接
8. 寫 code
9. 後記

2018年9月20日 星期四

黃禍

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

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

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

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

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

總評:2/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。
Related Posts Plugin for WordPress, Blogger...