2019年9月8日 星期日

從 C 呼叫 Lua 函式

故事是這樣子的,小弟在公司裡面,主要是負責維護一個沒人在用的產品,遠觀來說這個產品滿複雜的,內建兩種不同的演算法實作,為的是要應對不同的狀況,有些狀況用第一種演算法比較快,有些用第二種。
那故事是這樣子的,我們的程式裡面有一個函式會在每筆資料結束之後,用上筆資料的結果來判斷下一次要選哪個演算法,問題是這個函式目前是直接寫在整個引擎的 C code 裡面,於是如果想要改變一下判斷的標準……sorry 重新 build,雖然公司弄了套分散編譯可以編很快但還是要幾分鐘。
上星期自己試了一下,成功把 Lua 編到公司的 code 裡面,就能把判斷邏輯寫在 Lua script 裡面,要改判斷標準只要改 Lua 就可以了;我一般聽到會這樣用的是遊戲公司,因為遊戲一樣涉及大量的邏輯判斷,例如血要扣多少之類的,而遊戲又會大量的去變動這些參數,使得彈性變得非常重要,總不能要改參數就把整個遊戲引擎全部重建構一次……說是這麼說我也不曾證實哪家公司真的這麼做就是,如果我的讀者真的是這樣搞的麻煩留個言讓我知道一下。

總之自己試過之後其實非常簡單,難怪大家都說 Lua 最厲害的就是嵌入到 C 程式當 Sup 角 ,我主要是參考這個網頁(看來是舊金山大學 CS 的課程頁面);下載 Lua 就從官網下載即可,哪一版應該是無所謂,或者是 Linux 的話安裝開發套件也 OK。
不愧是以輕量著稱的腳本語言,連 Makefile 看起來都是手寫的,直接下 Make 讓它編譯完成,雖然說我在這步被環境變數 TARGET_VAR 卡了很久,makefile 不知道為什麼自己把它加到編譯參數裡了。
再來做下面幾件事就能呼叫 Lua 函式了:

1. 引入 Lua 的標頭檔:

#include "lua.h"
#include "lualib.h"
#include "lauxlib.h"
然後在編譯的時候記得給一下 lua 標頭檔的位置,以及在連結的時候 -llua。

2. 生成 Lua state:

Lua 的 state 包含核心的函式,後面所有的函式都會需要這個 state;在 open 和 close 中間就能呼叫 Lua 函式了:
lua_State* L = luaL_newstate();
luaL_openlibs(L);
// write lua_call ... code here
lua_close(L);

3. 載入檔案,呼叫函式:

使用 luaL_dofile 打開 lua 檔案,等於是呼叫 lua 直譯器執行這個檔案,如果有直接執行的東西這時候就會有效果,像是 print("hello world") ,我們這裡只是定義變數 "add" 對應到相加的函式。
要呼叫 lua 函式,我們以函式 add 為例:
-- add.lua add function
add = function(a, b)
  return 42
end
那麼在 C 裡面就是:
luaL_dofile(L, "add.lua");
lua_getglobal(L, "add");
lua_pushnumber(L, a);
lua_pushnumber(L, b);
lua_call(L, 2, 1);  // 2 parameter, 1 return value
int sum = (int)lua_tointeger(L, -1);
lua_pop(L, 1)
簡單來說就是先用 lua_getglobal 拿到存在 global 裡面的函式 add(在 luaL_dofile 的時候建立的);把參數推到堆疊上;執行 lua_call,指定兩個參數跟一個回傳值,取出回傳值,把回傳值彈出堆疊。
如果函式有多個回傳值的話,會依序放在堆疊的 -1, -2 … 上;lua_pop 也要彈出更多值;Lua 的有一系列的函式來把東西推到堆疊上/彈出堆疊,簡單的應用,通常就是 lua_pushinteger/lua_tointeger, lua_pushnumber/lua_tonumber 來推/彈整數跟浮點數到堆疊上,詳情請參考文件

這裡只記錄最基礎的應用,實際上應該還有更複雜的應用,例如我要做決策的參數如果很多的時候該怎麼辦?或者其實我想要直接推一個 struct 進到 lua 是可以的嗎?
這兩個問題我目前都沒有答案,還有待研究,目前只知道 luajit 這個看起來好像停擺的專案有提供類似的東西,可以準備好 C 的 struct 來吃。
如果有大大們有答案的話麻煩教一下小弟,小弟現在很需要。

2019年9月4日 星期三

Rust 裡面那些 String 們

故事是這樣子的,最近把小弟自幹的編譯器加上 rust 的 llvm wrapper llvm-sys,經過一陣猛烈的攪動之後,自幹的編譯器終於可以 dump LLVM IR 了,雖然只會輸出一個空殼子…但有第一步總是好的。
不過小弟在綁定的時候遇到一個大問題,也就是 Rust 裡面的 String,到底怎麼會有這麼多種,因為寫的時候一直沒搞清楚,然後就會被編譯器噴上一臉的錯誤,覺得痛苦,於是決定來打篇整理文。
簡單來說,Rust 的 std 有四種 String,每個 String 都有動態記憶體模式跟沒有 size 資訊(不是 Sized)的靜態模式,他們是:
std::string::String <-> std::str
std::ffi:OsString <-> std::ffi::OsStr
std::path::PathBuf <-> std::path::Path
std::ffi::CString <-> std::ffi::CStr
還有一個比較少用,只能表示 ascii 128 字元組成的字串的 std::ascii::asciiExt,這裡就不介紹了。

一般的程式語言在數字型態通常都很固定,Rust 就很明確的分為 i8, i16, i32, i64 …,就偏偏字串是個大坑,因為從 ASCII 到 unicode,字串實在有太多分岐,儘管有 unicode 也不是到處適用。Rust 從設計上一開始就直接採用 utf-8 作為設計標準,原生的 String/str 就是 utf 8 字串。
可是呢,並不是所有作業系統都玩 utf8 這套,因此 Rust 有另一個使用 wtf8 的 OsString,wtf8 跟 utf8 的差異在於 wtf8 算是<格式比較差>的 utf8,會出現一些 utf8 不允許的位元組,偏偏規格沒有要求一定要完美格式,造成 windows 或 javascript 有時會出現這種格式不良的 wtf8 字串,因此 OsString ,跟專門用來表示路徑的 PathBuf 就是使用 wtf8。
有關 wtf8 請參考:https://simonsapin.github.io/wtf-8/

上面的字串都是在型態中記錄字串長度,結尾不會有 \0 字元,CString 則是最傳統的 null-terminated 字串,在呼叫 C 函式的時候,一定要用 CString 傳遞才行。
順帶一提,一般寫在 code 裡面的 let hello = "hello world" 的型態是 &'static str:生命週期為 static 的靜態字串。

知道了以上幾個區別之後,就來看看要怎麼使用它們:
String 最簡單,裡面一定要是 utf8,產生就是從 static str 產生,或者是 new 之後慢慢 push 進去:
let hello : String = String::from("hello");
let mut world : String = String::new();
world.push_str("world");
world.push('!');
OsString 是類似的,但只能從 String 轉過來(注意 String 的所有權會轉給 OsString),或者一樣 new 之後 push String 進去:
use std::ffi::{OsString, OsStr};
let oshello : OsString = OsString::from(hello);
let mut world : OsString = OsString::new();
world.push("world!");
PathBuf 其實就想成 OsString 就好,兩者也可以互相用 from 轉換:
use std::path::{PathBuf, Path};
let p1 : PathBuf = PathBuf::from(oshello)
let mut p2 = PathBuf::new();
p2.push("/dev");
上面說了,OsString 跟 PathBuf 用的是 wtf8,是 utf8 的超集,因此一般只能單向從 String 到 OsString,反向是不行的,呼叫 OsString::into_string() 得到的是 Result<String, OsString>,也就是有可能會轉失敗;或者就是用 into_lossy_string 把編碼不完整的地方變成 U+FFFD,utf8 的 replacement character。
PathBuf 則是沒有 into_string 可以用,只能先轉換成 OsString 再轉過去,我也不知道為什麼 core team 要這樣設計。

剩下的就是函式了,很有趣的是 String, OsString, PathBuf 都是動態容器,操作內容都要轉換到 str, OsStr, Path 上面去:
str 有操作字串用的 split_whitespace, starts_with 等等
OsStr 沒有任何特殊的函式XD。
Path 有很多對路徑的操作:is_absolute, parent, with_extension 等等,很多函式操作後都會得到 Path 或是 OsStr 讓你做接下來的操作。

CString 比較棘手一點,它要在 new 的時候代入 Vec<u8> (或者有實作 Into<Vec<u8>> 的型態)來建立 CString,new 會自動在後面加上 \0 ,因此這個 Vec 裡面不應該有 \0。
其實我覺得把 CString 想得 Vec<u8> 的另一種型態就好了,它本身也提供 into_bytes, as_bytes 等函式轉換成 Vec<u8> 的型態。
如果要從 String 跟 OsString 轉換過來的話,String 要用 as_bytes() 轉成 Vec<u8>,OsString 因為 unix 跟 windows 會有不同的 OsString 實作,不一定都能轉成 Vec<u8>,在 unix 要引入 std::os::unix::ffi::OsStrExt 就可以將 OsString 用 as_bytes() 轉成 Vec<u8>;Windows 則建議轉成 String 再轉成 bytes ,請參考這個網址

用上了 CString,最重要的就是要交給外部的 C 函式去用,要用 as_ptr() 取出字串部分的 pointer,得到的就是 * u8 了,有必要的話再加上 as *const i8 轉型一下。
例如我要呼叫這個函式:
LLVMPrintModuleToFile (LLVMModuleRef M, const char *Filename, char **ErrorMessage)
這個函式,我的檔案名稱是一個 OsString:
use std::ffi::{CString, CStr};
use std::os::unix::ffi::OsStrExt;
llvm::core::LLVMPrintModuleToFile(
           self.module,
            path.as_bytes().as_ptr() as *const i8,
            ptr::null_mut());
看了這麼多,簡單整理一下大概是這樣:

老實說每次只要在 Rust 裡面弄到 Path 都會弄到懷疑人生……

2019年8月28日 星期三

十年一覺 N1 夢

故事是這樣子的,8/27 剛公佈 2019 年第一次日文檢定的成績,經過了三次不合格之後,這次通過 N1 ,天氣好不用再散步可以跑步啦(什麼。


先來個有圖有真相:
配個歷年成績,一開始真的是慘不忍睹……:
2016/12:語言知識 23/60  讀解 32/60  聽解 22/60   77/180   Not Passed
2017/07:語言知識 26/60  讀解 33/60  聽解 30/60   89/180   Not Passed
2017/12:語言知識 36/60  讀解 32/60  聽解 31/60   99/180   Not Passed
2019/07:語言知識 38/60  讀解 58/60  聽解 33/60  129/180  Passed

上次就已經來到只差一分合格,理應再準備一下就可以過關,但認真應考還是太累,年初工作剛到任還在適應中,決定一口氣延一年半到今年 7 月,還很幸運的在台灣大學新的大樓應考(不過新教室有一點問題,之後再說),這次總算通過啦。
這次的準備沒有特別久,如果我沒記錯的話應該是四月初開始認真準備,不過真要說的話其實是沒多認真啦…,我覺得投的時間比之前考前都還要少,下面會提一下各區塊的準備方式,有些可能會有業配嫌疑,不過我保證沒有,反正這個小 blog 跟現在工作做的產品一樣都沒人在意(欸:
  • 語彙、閱讀
語彙跟閱讀這次是放在一起……沒有準備,這次是從閱讀下手,在上班通勤時間陸續看了utsuki 給我的<哪啊哪啊~神去村>,還有許久以前從 BookOff 搬回來都沒看的<嫌疑犯X的獻身>,兩本都是看過中文再看日文,避免日文看不懂的狀況,一開始的單字量會比較大一點,看多頁之後就會比較順,還會發現一些作者愛用字,像是神去村作者很喜歡用うなずく;題庫只有寫一本<全攻略新日本語能力試驗N1讀解問題集>,這本我覺得題型跟真的考試的 correlation 有點差異。

以這次的結果論,閱讀我覺得是有效的(我現在反而超好奇我是錯了哪題www),至少不合格的三次閱讀題寫得滿抖的,趕在最後一分鐘的時間寫完;相對的這次閱讀題看得滿順,寫完還剩 40 分鐘,我還一度以為 N1 是不是變簡單了,還回去推敲了文法排序的幾題(以結果來看效果沒有很好就是);單字的話可能效果不如預期,畢竟言語知識分數沒往上,但文法有被評為 A,所以很可能是單字被扣。
言語字彙年輕的時候可以用 anki 之類的背單字軟體,不過我是覺得老了之後有點用不起來,一直盯手機太累了,還不如輕鬆看小說,然後買個迷你記事本把不會的單字記下來,在走路的時候拿出來複習。
  • 文法
文法在自我學習上是用之前用過的兩本:<TRY!日本語能力試驗從文法掌握N2> 跟 <TRY!日本語能力試驗從文法掌握N1>,這兩本文法的好處是有附 10 篇含所教文法的短文跟CD,很早以前考 N2 時是自己讀,那時還是拿奇怪的文法整理手冊在背,現在看來覺得效果沒有很好,這次乾脆把 CD 倒出來,然後反覆的聽跟跟讀到熟,像是睡覺前就放一篇聽到睡著、或是在工作中重複播放,我猜兩本書的 CD 我至少聽過 50 遍以上 。

課程的話,這次是在 utsuki 推薦的 Cafetalk 上面找老師,基本上只要是日文老師都會開 JLPT 專門的課程,結算是上了 28 堂,平均下來大約一週上兩次 50 分鐘的課程;老師是用<日本語パワードリル N2>跟<日本語パワードリル N1>,寫大量的題目跟講解,基本上絕對是有練有差,有些題目用的文法是同一個,錯兩遍就記下來了;而且意外的發現自己在<選出最符合文章的文法選項>這大題非常的弱。
另外老師有用一本<日本語総まとめ N1 語彙>,裡面有整理疊字詞跟副詞,在考前背過一陣,我覺得多少是有用的。

考試結果來看至少文法的評定結果是 A,不過我個人覺得在<重組文法>這題上面,做過的練習題難度都不到真正考試的難度,Correlation 很差,平常寫練習題都很順手,上場考試卻排不太出來,我也不知道該怎麼改善就是了。
  • 聽力
聽力的話…就真的是放水流了……沒有認真準備啊結果也變醬糊,考試結束就覺得跟之前比沒有脫胎換骨的感覺…還是一樣,沒 Fu,聽一聽就是會掉字,偏偏在日文掉關鍵字很致命;然後第四大題真的是我的罩門,真的不知道要回什麼,每個 3 都好像是答案……;這次的聽力還證實了我的閱讀跟聽力是連不上的,有一題聽力講了一堆 りんぎょう,我就一直在想りんぎょう 是啥……見鬼<林業>啦…,,真的是愧對我還看完神去村小說。

準備上我是建議把字幕丟掉,小弟也是 2016 考爆之後,從 2017 的<動物朋友>開始遮字幕看動畫,至現在雖然不是內容 100% 聽得懂,像搖曳露營有關千元鈔票的地方就沒聽懂,但意思都能抓個大概,如<Lovelive Over the Rainbow>跟<紺青之拳>在電影院也盡量遮字幕看。
動畫之外就是把比較紅的<逃避雖可恥但有用>、<半澤直樹>、<房仲女王>的日劇,一樣看完中文之後遮字幕看日文同時跟讀、在上班重複聽上面幾部日劇,或是狂聽 NHK 之類(不過 NHK 其實重複的內容很多,像是颱風、天氣、股市一直重複,其實不算太好的素材);其他就是強者我同學 GGM 大大借我的<新日檢聽解一本搞定>,有意思意思聽過一輪。

綜觀練習狀況,我覺得這次比上次還要穩定許多,我會給的建議,也是我第二次不合格之後,在 N1 衝刺班上老師給的學習建議:
  1. 從聽開始:把字幕丟了,聽動畫、日劇跟綜藝節目,看過中文再聽一遍也可以;反正一定有足夠簡單的內容,比如說動物朋友(O。
  2. 跟讀:超痛苦,但是是讓舌頭聽話的有效方法,必要的時候像房仲女王,可以考慮用 0.8 倍速跟讀,也比較輕鬆一點。
我覺得先不管日檢,至少這兩年練下來耳朵是有變靈敏的,至少看動畫會知道在講啥,練習題會莫名的知道它想講什麼,甚至聽沒聽過的歌也能聽出一些單字,這邊引用研究好像是吊書袋,但之前看過的研究是指出:沒字幕對學語言的效果最好,有其他語言的字幕有一點效果,有字幕基本上就沒效果了(如果有人知道這個研究的話煩請讓我知道一下)。

考場上也沒什麼太大問題,就是新教室比較大,有人反應聽力的聲音不夠大聲,讓大家聽了 8 遍<天氣好的話去散步吧>,真的很靠北……


細數從大三的時候心血來潮(?)修了日文一,到今天通過 N1,差不多也要十年了,十年間進進退退,修完日文一之後停了一年,接著修了日文二跟後續的一些進階課程;13 年 7 月第一次挑戰N3,那時候在實驗室忙得要死要活,考前一天還失眠睡不著,準備不週又完全沒睡上場考試(回想起來沒考到睡倒真是奇蹟),結果 97/180 比及格高2分浮過去了。
14 年 12 月通過N2,那次準備比較充足些,總分:107/180;後來因為兵役的關係,從 15 年到 16 年進去當個兵出來什麼都忘了,以致連續三次被 N1 壓在地上打QQ。

N1雖然及格了,但從聽說讀寫來看,也只有讀算勉強過關:
現在的口說帶有一種奇怪的口音,重音位置超奇怪,被真的會日語的人指稱她完全聽不懂我在說啥,之前參加多國語言交換咖啡,也是被一位日本人瘋狂糾正,每說一句都有文法上的錯誤,跟 Cafetalk 的老師對話也是零零落落的,他能聽得懂我想講什麼根本奇蹟;試著跟讀也是很吃力,舌頭沒辦法動這麼快的感覺。

俗話說:「N1 考過了只是剛開始」。
誠哉斯言,個人經驗來講,所謂的多益、N1,其實都是能夠訓練的,就像軟體公司面試要刷題,文法、閱讀也能透過刷題解決,這次考前文法粗估應該刷了 300-400 題吧。但除去考試,語言能力或者任何能力,除了實際上場幹架之外,有什麼是考試考得出來的呢?考過了其實什麼都沒有;不過,現下已經知道了進步的方法,剩下就是慢慢努力,務求聽說讀寫能力俱備了。

十年一覺 N1 夢,夢醒時分繼續努力。

2019年8月19日 星期一

第一次在 COSCUP 當講者就上手

故事是這樣子的,在上周結束了兩天的 COSCUP 行程,總算達成人生成就:參加 COSCUP (欸。
這次是以講者的身分去的,畢竟搶票什麼的實在是太難了,就跟搶普悠瑪一樣難,當講者好像比較簡單(True Story)。

這次準備的題目其實都是準備許久的,一個是本次 COSCUP 有開 Rust 議程軌,就把之前寫 computationbook-rust 裡面當範例的 simple language ,配上研究一小段時間的 PEG parser 挑出來,攪一攪投出去。本來這是想要去年的 MOPCON 投的,但畢竟 MOPCON 是以網路為主體,跟這 programming language 還是格格不入被拒絕了。

下面是投影片:


blog 的話,可見實作麻雀雖小五臟俱全的程式語言剖析表達文法 PEG 簡介使用 rust pest 實作簡單的 PEG simple 剖析器使用 procedence climbing 正確處理運算子優先順序幾篇。

另外一個議題則是去年 8-10 月做的 Nixie Tube Clock,COSCUP 有非常適合的硬體議程軌,老實說 Rust 議程軌我覺得不一定會上,硬體議程軌我就真的滿確定會上,畢竟講硬體的本來就少,Nixie Tube Clock 也滿完整的,果然最後就上了一場。
投影片在此:


blog 筆記總計有十篇:
0. 前言
1. 材料取得
2. 自組高壓電路
3. 驅動電路
4. 控制電路
5. 電路板基礎
6. 電路板實作 layout
7. 焊接
8. 寫 code
9. 後記

個人小小的體悟是,先不要想 COSCUP,先想著把某件事情做好,時候到了投稿自然會上;就像會上一位大大說的,因為沒搶到票決定每周用 golang 寫一個 project,52 週之後就當講者了。
這次投上的題目,無論是 PEG + programming language,還是 Nixie Tube Clock,都是一年前甚至兩年前開始的嘗試,PEG 還搞了個失敗的 C parser,blog 寫了好幾篇的題目,做到這種程度才能換到 40 分鐘的上台時間;也許現在就該來想一下要做什麼新題目了。

----

第一次參加 COSCUP ,這次真的融合了超多議程軌人超級多,據說直接突破 2000 人,大拜拜的意味滿重的,像 Pycon 這樣同時段 3 場的都很常兩場一定要選的,COSCUP 同時開 14 場議程,從一開始聽議程就不是目的了。
實際下來比較像:三分聽議程,七分面基友。
細數一下我到底遇到多少在網路上見過面的大大:像是從荷蘭遠道而來的呂行大大、台灣軟體界照世明燈郭神大大、久未見面的 jserv 大大、好高興教授大大、TonyQ 大大、在會前酒會遇見上海大殺四方的 Richard Lin 大大、曾經在高雄氣爆的時候幫我提升 Google Map 權限的 pingooo 教授大大;認識了台灣 maker 社群、Python HsinChu User Group - PyHUG。
不過我覺得比較扯的還是呂行大大,走一走每個攤位都能遇到人,真的是神猛狂強溫爽發。

記得以前參加 PyCon,總會在那邊要求自己盡量的聽,連可能不知道在講什麼的、 lightning talk 都聽完之類的,這幾年終於改掉這樣的習慣,發現時間寶貴,聽一些跟自己太遠的東西其實是浪費時間,還不如放點時間出來跟大家聊聊天,真的沒想聽的就早早離開會場沒差;網路上常講:
小孩子才做選擇,成年人當然是我全都要。
但其實,成年人才知道自己要什麼、不要什麼、有能力要什麼、沒能力要什麼,我覺得是反過來的:
成年人才做選擇,小孩子才是我全都要。

我想最後還是要感謝一些人,像是強者我同學 JJL 大大幫小弟 review 投影片;強者我同學 wmin0 大大幫小弟生出一個 Nixie Tube 的講題,這個題目應該給大大講才是。
明年希望大家也都能成為 COSCUP 講者。

2019年8月3日 星期六

Minecraft 火車站相關系統的設計

小弟玩 Minecraft 一段時間,其實一直想蓋一個大型火車站,然後連續兩次因為伺服器更新所以蓋不完XDD,不過在蓋火車站的期間,還是累積了一些火車站相關系統的設計,蓋不完還是可以介紹一下:
1. 快速向上電扶梯
2. 驗票閘門
3. 平面停開車系統
4. 礦車減速系統

快速向上電扶梯:


快速向上電扶梯其實跟火車站沒什麼關係,但就…火車站常有的東西,這版是用一組向上活塞跟向前活塞交錯推進做成,小心控制紅石信號的延遲就能把人快速的往上推。
當然其實好像沒什麼必要啦…畢竟在 Minecraft 裡面把樓梯又快又不浪費體力,而且電扶梯一堆活塞運作起來其實很吵…。

驗票閘門:

第一版:
第二版:

驗票閘門是腦洞大開做出來的,基本概念是像真的驗票閘門一樣,讓使用者必須投入指定的物品閘門才會開啟,通過之後閘門關上,不小心一口氣就設計了兩個版本:
第一種是投票之後就會開閘門
第二種使用者要從另一個 dropper 裡面取票閘門才會開,更像真實的驗票機

這部分用文字跟圖片說也說不清楚,也許最簡單的還是看影片。

系統的核心如下圖,第二個漏斗裡的東西是裝滿的,這樣使用者只能投入特定的東西(車票);比較器比較投入漏斗跟參考漏斗物品數量是否相同,就能感知<使用者是不是投入車票>這件事,利用這個信號控制漏斗下的另一個漏斗,就能夠控制每次只通過一個物品。

因為我們要求的是投入物品的漏斗,放入物品之後發出的訊號要跟參考值一樣,查一下 wiki,投入物品的漏斗的物品數量要是 22 個,參考漏斗則是 23 個,放入東西之後訊號強度會升到 2,讓比較器打開。

後來就只是基本電路的操作,把物品通過的訊號截出來設定 SR latch,過閘門的踏板重設 SR latch,藉此控制閘門活塞的動作 現在的 SR latch 除了可以用標準的 2x4 雙火把之外,也可以用雙漏斗的 SR latch 設計,如下圖所示,兩者都是 SR latch。

差別在於兩個漏斗的版本,兩個控制信號必須是 1,設定的時候短暫變為 0 來釋放漏斗內的東西;火把設計則是反過來。

平面停開車系統:


這個是很以前設計的東西,因為以前在 Minecart 上是完全不能移動的,所以一定要有一個發車的系統,最一般的就是用凹洞或凸起構成的斜面,加速鐵軌就會朝下加速,不然在平面上加速鐵軌就算有電也不會加速。
這個平面的系統利用活塞,在車子開過去之後把停車位置的背面從鐵軌換成方塊,這樣加速鐵軌就能在平面上讓車子啟動,中間要注意的只有活塞進推的時序問題;不過說起來只是為了改善使用者體驗,不然簡單斜坡就有一樣的效果了。

礦車減速系統:

當初採用減速系統是在火車站的入口,讓使用者能選擇要進站或過站不停。
其實這部是很早以前也是從 Youtube 看到的,但後來完全找不到,幸好當時有先複製一份到測試 server 裡,現在才能蓋出來。
這個系統真的是非常巧妙,利用了比較器來計時,還有將脈衝保持在一個迴圈中來讓鐵軌進到減速模式,整個就是我自己做不出來的設計(yay,所以大家還是看影片吧

目前火車站大概是有這些設計,不過話說回來現在好像也沒什麼時間可以蓋火車站了(yay。

2019年7月10日 星期三

到東京玩 B777-300ER 飛行模擬器

故事是這樣子的,因為一些個人因素,小弟會常常需要來往東京,幸好現在亞洲廉航選擇多,兩個月左右飛一次還可以承受。
在大概是今年一月回台灣的 Vanilla Air 上,看了它們的機上雜誌,內容是由 Vanilla Air 的員工介紹去東京有什麼可以玩的,裡面有一個 Skyart Japan 的介紹,還滿有趣的,服務是可以操縱貨真價實的 B777-300ER 模擬器,在擬真的機艙裡面拍照之類的。

今年六月的時候,預約了一趟飛機模擬的行程,寫篇文來介紹一下這個冷門的旅遊地點:

其實這家除了開模擬器,還有一些其他的服務,像是機師衣服出租、機艙空間出租、寵物攝影(?之類的,但這篇就專注在操縱模擬器上。
首先,這是真的 B777-300ER 的模擬器,所以玩起來其實不便宜,大家可以上官網看它的 plan 列表,最基本的體驗課程,30 分鐘要價是 11,000 JPY,最高開到 120 分鐘 36,000 JPY,有一些特別的方案,像是看富士山,雙人方案、開趴方案、四季景色方案、克服飛行恐懼症…,或者是可以附加的,像是機師制服出借、登機證、從啟動 engine 開始之類的。
順帶一提,它們是可以讓機師做模擬機訓練,像是起飛降落、惡劣天侯,我不確定是網頁(他們的網頁其實很亂,資訊太多沒有整理好)還是現場,有看到相關的規定:「如果你有機師的執照,是必須要出示的」,當然專業機師的方案會比較貴一點,比普通方案每 30 分鐘多 5,000 JPY,所以 120 分鐘就要 56,000 JPY 了。

從預約開始,他們官網有個詢問預約時間有沒有空的表單,不過我記得我填了之後也沒有人理我,直接 plan 選一選下訂比較乾脆,下訂之後就會有人來信跟你確認預約的時間,如果真的很怕訂了之後預約的時間沒空的話,也是可以去信詢問:info@skyart-japan.tokyo,寄信就真的有人會回了。

公司的地址在東京都品川区北品川6-7-29 ガーデンシティー品川御殿山,最近的車站就是品川站,走路大概要 15 分鐘,請自行參考 Google 街景,在一棟很氣派的建築物裡面。

很奇妙的我翻遍手機發現沒有他們客艙內景的照片,可能自行搭配官網的小圖,中間的桌子疑似是用引擎尾部改造而成,噢然後這個是 A320 的客艙,雖然是 A320 的客艙卻長了個 B777-300 的機頭
我們預約的方案是 1 小時的普通模擬方案,附加從停機坪發動引擎跟後推,總價是 26,000 JPY,在下訂的時候就用信用卡附款完成,模擬的時候會有一位真的機師在旁邊當副駕,可以用日文或是英文輔助駕駛,不過畢竟是在日本,一開始詢問方案的時候還是要用日文,我們 1 小時方案可以選擇的有:
* 從羽田機場起飛,繞一圈回到羽田機場降落
* 從羽田機場起飛到成田機場降落
* 從羽田機場起飛到世界上任一個機場降落,當然中間的巡航會省掉,瞬間移動到當地上空

女友選了從羽田起飛/降落三次(兩次 GA)的方案,這樣操作到最多東西。


這張應該就是羽田後推時的照片,一開始先是一位日本機師當副駕用日文帶飛,基本上什麼都不會也沒差,副駕會幫你搞定一切(好啦開引擎他會讓你開一邊),呆呆的看著他跟電腦對話就行了;上跑道飛機自己會緩速前進,正駕駛用一根桿子控制方向。

起飛之後真的能感受到模擬機的厲害,大型的建築物都是建模出來,能看到晴空塔跟迪士尼樂園,夜間飛行還可以加上煙火XDD;不過這台模擬機只有畫面,不會有真正的前後傾斜。

飛完第一圈之後,換旁邊待機的土耳其(? 機師上去,用英文帶飛。我這時跟日本機師問東問西,順便玩我女友:

Q:為什麼雷達圖上面沒有飛機?
A:喔,那只是我們沒開:(轉一個開關)飛機就顯示出來啦wwww
會顯示編號,比我們高,正在下降之類的資訊,故意飛太近的話還會有碰撞警告

Q:剛剛跟後推車的對話是真人還是錄音?
A:錄音,要的話我們也可以(轉另一個開關)機艙內開始放 ATC 跟飛機對話的錄音,好像是紐約那邊的 ATC,播下去之後真的超有實感

其他一些雜雜:
現在飛機都全自動了,三個儀表版可以設定速度、高度跟方位,高度跟方位只會影響儀錶版上的顯示,提醒你要飛到多高跟往哪裡飛,速度設下去電腦會自動接手引擎,所以會看到油門把手自己在那邊動來動去OAO,連降落都是到最後一刻才解除自動駕駛。
轉彎如果超過 35 度,會跳警告:Bank Angle ~ Bank Angle ~,其實我比較想聽 Pull Up ~ Pull Up ~,我滿好奇 35 度到底急不急… 看航跡圖的轉彎半徑都超級小,在旁邊看轉彎半徑還沒有照著航跡圖轉過 owo

總之體驗一下是滿有趣的,如果真的不知道在東京想幹啥,或者想要體驗看看開噴射飛機的話,可以到 Skyart 試試看,預約跟一進去多少需要一些日文對話能力,但我猜他們英文會話應該是能通的。
沒開飛機還是坐個駕駛座過過乾癮,這張是降落之後停在滑行道上,結束時拍的,看看這複雜的儀錶板:

2019年4月22日 星期一

第一次教召就上手

我想是這樣子的,如果你進到這個頁面,有很高的機會你是因為收到後備指揮部寄來的神祕信件,很不巧的機票又沒有訂下去,開始無助的在網路上收集各種相關資訊,或者已經到了鬼門開的前一天,要準備好收行李的時候。
其實小弟也差不多,我是在 2 月底的時候接到後備指揮部確認資料的電話,過不久通知書就寄到家裡,4/15-4/19 要被教召,看看反正就進去國軍養個肝,在那邊躲來躲去的也不是辦法,反正雖然是南部但 4 月中還不算太熱,就乖乖的去召一下保衛台灣獨立。

從拿到召訓說明書開始說起,其實召訓說明書上已經寫清楚要準備什麼了:
  • 身分證/健保卡/駕照三選一,身分證當然是最好,但只要能證明身分的都OK。
  • 私章,領薪餉用:沒帶也可以簽名所以沒差。
  • 個人所需藥品:有病就該吃藥(欸。
  • 盥洗用具:要不要用新訓那種洗頭髮洗身體二合一的看個人,教召洗澡時間比較多沒必要洗戰鬥澡;大概就是沐浴乳、洗髮精、牙膏跟牙刷,刮髮刀想帶就帶一支。
個人衣物,這部分可能是大家最想知道的?當初我有查這個查了一下:
基本上進去會領到公發的兩雙黑襪、兩件內衣、兩件內褲跟一條毛巾,我的策略就是衣服完全不洗,時間省下來看書,我是這樣帶:
  • 一套離營時穿的衣服:星期一報到的時候身上穿的衣服褲子,到營區之後就脫掉放進塑膠袋裡包好,因為天氣熱的話,星期一的衣服吸飽到營區的汗水,放到星期五會非常的臭(我服役的時候試過一次會有像大便的味道,然後我還穿那個去搭捷運回家wwww),簡單作法就是密封起來不再穿了。
  • 保暖用的外套:我是沒帶畢竟南國 4 月就不用再穿外套了。
  • 毛巾:公發的就省下來,解召前繳回去,少浪費一點資源。
  • 五件內衣:同理,不過我日常沒內衣所以就是兩件公發的穿五天這樣。
  • 五件內褲:公發的我繳回去了。
  • 五雙黑襪:公發的我繳回去,如果要自備的話建議買好一點,或是用已經穿舊的,我買了新的結果非常咬腳,覺得沒有很舒服,襪口上面一點有腫起來,雖然我不確定會不會是有跳蚤。
  • 睡覺穿的短褲:這次我忘了帶,只好都穿迷彩褲睡覺…。
衣服之外就是要帶塑膠袋裝髒衣服。

其他:
  • 書:殺時間用的(其實跟同袍哈啦也很殺時間),輕小說我就覺得不錯,小本又可以看很久,像隔壁的大兵帶了<刀劍神域 18、19>,五天下來也快看完了。
  • 充電線:如果你手機續航力不夠,應該會開放中山室讓大家在使用時間充點電,但如果保持關機手機應該不至於每天用幾小時就沒電啦。
  • 水壺:裡面會發保特瓶的腰間水壺,我自己的水壺是晚上在寢室用的。
  • A4 資料夾:裝教召令跟手機三聯單等文件,進去會發一個牛皮紙袋不過我覺得資料夾比較好用。
  • 手錶:我的手錶進去前壞掉了,體會到各種不方便,要一直跟人借錶看時間。
我這次有個第三次被召的自備延長線跟電扇,這就看個人有沒有需要了,如果是 7, 8 月也許有需要。
教召基本上沒有髮禁跟鬍子的要求,裡面也有看到染金髮跟馬尾,要不要剪三分頭的答案應該很明顯了,我是順道去剪短一些,這樣比較不會熱。
連著教召單寄到的包含一張交通兌換券,填好之後可以換台鐵的票,理論上只能換莒光但我換到自強號他也沒跟我收錢owo,而且明明薪餉的錢是來回都有算,那我去程票用換的不是變成國家補助了召員兩次車錢?

教召其實就輕鬆過就好了,稱謂從新訓的編號->部隊的姓名->各位伙伴,一開始聽到怎麼聽怎麼不習慣XD;協訓幹部對大家也很客氣,大家至少都20多歲也都成熟多了,反正大家都當過兵也知道要怎麼做,撐一下五天就過去了。雖然如此教召也不是在玩,該練的都有練,該打靶的就打 25/175 的靶,打完該擦槍的就擦槍,砲操該跳的就連跳三天。
生活上來說下課可以投飲料(我覺得軍中的販賣機一定超級賺…),可以上營站,上下午20 分鐘的下課也會有小蜜蜂販售熱食冷飲,小心不要吃胖了。
手機收繳放養機場之後,每天中午跟晚上兩次有三個時段可以用手機,我自己是覺得領手機麻煩,統一在晚上用手機。
這次的飯(不知道為什麼)很難吃,跟新訓、通校、前運隊、部隊比起來,就教召的飯最難吃,醃漬品特多,新鮮的菜很少很像伙房在省錢,偏偏炒菜又很常燒焦變臭灰搭口味,如果真的忍不住就買營站的泡麵來吃,出來之後我現在吃什麼都覺得是人間美味wwww。

其實教召跟其他人聊一下,也是不錯的體驗,每個人各有不同的退伍年次,服役時的單位也都不同,有的人真的超級操,下部隊遇到聯勇,打完之後一個月再接漢光,結束一周後開始準備聯信(名字跟順序我不確定),幸好在開打前他退了;跟我這種在部隊上做九個月文書退伍的不一樣,這次都是另外兩位下過基地的人在罩我,動作做起來超純熟的。
可能就跟這部微電影說的一樣吧:一次當兵下過聯勇,一生回憶抬頭挺胸。

這次教召小弟的公司那邊正好要發新版軟體,正在緊鑼密鼓的測試跟解 bug,我一被召就躲了五天的工作 lol,然後久違的得到一堆時間可以專心做自己的事,就把很早以前拿到的<時間管理-給系統管理員>給看完了,雖然說一次把書看完好像不是作者的本意啦XDD。
不管怎麼樣進去養個肝也不錯,出來我晚上 10 點眼皮自動變沉重,倒下去一覺到天亮,健康到肝臟都會發光呢。

2019年4月6日 星期六

自幹發光眼鏡

故事是這樣子的,去年十月跟傳說中的幣圈大佬小新大大弄完 Nixie Tube Clock,從小新大大那邊拿到一團剩餘零件,剛好裡面有一批 1206 的白光 LED,想說丟回收前還是可以利用一下,不如就來做個發光眼鏡好了。

準備材料:不要的眼鏡一副、描圖紙、1206 白光 LED、電線、強力膠、220 Ohm 電阻、供電用的 arduino、焊接工具。

首先要把 1206 發光側貼在眼鏡周邊,我試過一定要用強力膠才能黏得住,保麗龍膠跟雙面膠都無法,焊上電線之後扯 LED 的力道出乎意料的強,光電線本身的彈力就能把 LED 再扯下來,其實就算是強力膠用力扯還是會脫下來,使用上要小心一點。
註:強力膠與保麗龍膠感謝強者我室友贊助。
鏡面的部分要貼上描圖紙,才能把光擋下來做出發光的效果,當然貼上描圖紙之後眼鏡就看不到東西了…;最後是把 LED 上焊上電線,焊上之後就要特別小心別把 LED 扯下來了。
最後接上電源,記得 LED 要串聯 220 Ohm 的限流電阻,這樣發光眼鏡就完成啦。

成品:

來看看效果:
啊發光有點不均勻……不過就算了,真的要均勻就要多一點 LED 才行,至少內側也要一組,接線會變很麻煩,直接買燈條應該會簡單很多啦,連焊接都省了,但燈條就是比較貴一點就是…。
至於醜醜的電線…如果有閒的話是可以拉去後面,但有點懶得弄,總之有效果了,我們可以來玩一些東西,像是:

認真發光:

眼神閃爍(物理)
眼神高頻閃爍(物理)

好啦…其實這個東西只是來亂的,大家可以不用這麼認真XD。

2019年3月19日 星期二

維基百科上繁簡內容的修訂

故事是這樣子的,最近小弟在看 github 上一個 os 的教學,跟 jserv 大大的 mini-arm-os 有點像,都是教你從頭幹一個作業系統出來,只不過這個是幹在 X86 處理器上,某種程度上我覺得在 X86 上寫開機程式根本是各種考古,還要從 real mode 一路開上來(yay
最近剛寫好小弟第一個 X86 kernel ,結果因為在 link kernel 的時候,object 檔案的順序寫錯,害我 de 了一輪搖曳露營 OST的 bug,超白痴。

扯遠了,其實這篇是要講 wiki 的,在寫作業系統的時候不免會去查一些 wiki 資料,然後就發現某些條目充滿了中國風格的用語,當然上面選擇台灣正體也不是看不懂但就是煩,於是把過去註冊密碼忘了的 wiki 帳號找了回來,自己來做個編輯,這裡記錄一下流程,希望大家有看到類似的狀況也可以順手修正一下。
我看到的文章是這篇:X86 呼叫慣例

參考用的資料:wiki 繁簡處理說明

首先先打開上例的 X86 呼叫慣例的頁面,會發現網址的部分,其實是 zh-tw/X86调用约定,這是因為 wiki 的規定是所有的中文頁面都是同樣的內容,再用之後會提到的轉換方式,轉換為中國(zh-cn)、新加坡(zh-sg)及馬來西亞(zh-my)三種簡體中文;台灣(zh-tw)、香港(zh-hk)和澳門(zh-mo)三個繁體中文。
所以在條目上變成先佔先贏,也就是有了「X86调用约定」的頁面的話,就不能新建「X86呼叫約定」的條目,必須只能編輯這個頁面,請見繁簡轉換的條目標題
然後編輯內容也不能隨意將簡體轉成繁體或反向轉換,否則會被視為破壞;另外文中的異體字、日本漢字也都有自己的處理方式,不過這裡我們今天不會提到。

這麼做的好處,就是無論簡體或繁體都會貢獻中文的所有頁面,壞處就是用語、行文等習慣,會需要花費時間轉換,而且我很懷疑能不能轉得好,像是文字轉過去了文法卻沒法用轉換的,對編輯者來說也很麻煩,像我如果要編輯簡體先到先得的頁面,就得要用簡體編輯才行,我個人是覺得壞處是大過好處的…但總之這是現下 wiki 的政策,再怎麼智障也只能先遵循(我其實找不太到這個政策形成的過程,也許有知道的人可以補個脈絡)。

再來就要到所謂地區詞處理了,請見wiki 地區詞處理說明:例如 stack 繁體為堆疊,中國簡體則是堆栈或栈,現下 wiki 的做法就是本文一律先到先得,編輯者是簡體中文就寫簡體中文,讀者選擇台灣正體的時候,再轉換成繁體頁面。
這裡的系統畫成階層圖大概是這樣:

愈下面的地區碼針對性就愈強,指定 zh-mo 就只會在澳門繁體頁面才會轉換,但指定繁體中文就會在下面三個語言都轉換;另外 wiki 有幾個不同階層的轉換:由上而下為全域轉換、全文轉換、公共組轉換、單獨轉換來處理。

  • 全域轉換就是超暴力所有 wiki 範圍內的文字都轉換,誤殺率很高,只有非常針對絕對不會誤殺的詞才能進去,例如台灣正體轉換表的:米芝蓮=>米其林。
  • 全文轉換雷同,只是在一篇文章內通殺。
  • 公共轉換組應該是最實用的,也就是針對資訊科技,定義好一系列的對照表,這些對照表就能套用到跟資訊科技相關的文章中。
  • 單獨轉換就是用來針對固定位置的詞來做轉換

我在看到 X86调用约定的時候,就是因為沒上資訊科技的公共轉換組:IT,以致雖然是繁體頁面內容卻都是中國用語(例如標題轉換成 X86調用約定),修正方式也很簡單,在原始碼的部分加上 NoteTA 的轉換模版就好:
{{noteTA
|T=zh-hans:X86调用约定; zh-hant:X86呼叫慣例;
|G1=IT
}}

其中 T 表示標題的轉換
G1~Gn 則是引用公共轉換組,這裡引用一個 IT 的,至於你說為什麼我知道要引用這個…呃…目前我只知道從類似條目去找,或者從全部的列表裡去找(yay

其實只要加上公共轉換組,看起來就會順眼很多了,自然會有一些詞沒修正到,只能之後手動下去修,像公共轉換組只定義堆栈要轉成堆疊,但原始碼有人只寫栈就轉不過去了。
大概就是這樣,要讓 wiki 用詞跟習慣一樣,還是需要大大們多多動手做點小修改,我個人還是覺得把簡體跟繁體頁面合併滿白痴的,你看我們定義了這麼多的公共轉換組,其實連個 X86呼叫慣例都轉換不好,說到底簡體中文跟繁體中文已經不是文字上的差別,而是連文法上都有差異了吧

2019年2月12日 星期二

關於費式數列的那些事

最近費式數列實在有點紅,讓小弟忍不住也來玩一下。
費式數列給一個初學程式的人都能寫得出來,例如早年我忘了哪位大大在推坑我 python 的時候,就寫了個只要 4 行列出費氏數列的 python 程式,一方面展現 python 在大數運算上的實力,一方面展視了它的簡潔,像是 a , b = a+b, a 這種寫法。
a = b = 1
while b < 1000000000000:
  print(b)
  a, b = a+b, a
當然會寫是一回事,深入進去就沒那麼簡單了,詳細請參考這個網頁
最簡單、最直覺的遞迴寫法,但這其實是會噴射的,每次遞迴都會做重複的計算,於是計算以指數的方式成長,比如說我用 python 的 timeit 去測一個遞迴的費式數列函式,很快執行時間就會爆炸,大概到了 fib(30) 以上就會跑得很吃力了。
如果我們用單純的加法,從 1 開始往上加,其實只要進行 n 次的加法就能得到 fib(n) 了,執行複雜度為 O(n);如果再套用更快的 fast fibonacci,更可以把執行時間拉到 O(lg n) 的程度,只要 fib(94) 就超過 64 bits 的整數的情況下,用 O(lg n) 的演算法其實跟常數時間所差無幾。
不過呢,費式數列還有一個公式解呢,也就是:
$fib(n) = \frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^n-\frac{1}{\sqrt{5}}(\frac{1-\sqrt{5}}{2})^n$
為什麼不用這個算式算呢?公式解不是常數時間嗎?

數學上來說:是的,但實際上會遇上一些問題,例如我們看看 64 bits 整數裡面最大的 fib(93) 為例,整數算的解為:
12200160415121876738
如果是 python 寫的公式解呢?
def fib(n):
    return (math.pow((1+math.sqrt(5))/2, n) - math.pow((1-math.sqrt(5))/2, n)) / math.sqrt(5)
print(int(fib(93)))
12200160415121913856
登登,問題大條了,答案不一樣。
何以致此,問題就來到浮點數的不精確問題,這時候就要先來一張經典的漫畫了:
我們在計算完 sqrt(5) 之後,只能用一個近似的值來表達結果,在 python 內預設是以雙精度浮點數在儲存,它跟真正的 sqrt(5) 還是有細微的差距,在隨後的 n 次方、除法上,這個細微的誤差都會被慢慢的放大,最終導致這個巨大的誤差。

幸好我們不是沒有解法的,參考了 C/C++ 版上,傳說中的 Schottky 大大曾經分享如何使用 gmp 或 mpfr 兩個函式庫,算出 e 到小數點下一億位pi 到小數點下一億位,這兩個 gnu 函式庫是所謂的<無限>位數的整數跟<無限>精確度的浮點數,當然他們不是真的無限,只是完全壓榨記憶體來記錄儘可能多的位數以求精確,理論上記憶體撐上去就能把精確度逼上去,只是有沒有那個必要就是,像是把一些無理數算到一億位(欸。
究竟這個函式庫有多麼的強大呢?我們可以來寫個簡單的,例如來算個黃金比例,只要這樣就結束了:
mpfr_t phi;
unsigned long int precision, x=5;
uint64_t digits = DIGITS;

precision = ceill((digits+1)*logl(10)/logl(2));
mpfr_init2(phi, precision);
mpfr_sqrt_ui(phi, x, MPFR_RNDN);
mpfr_add_ui(phi, phi, 1.0, MPFR_RNDN);
mpfr_div_ui(phi, phi, 2.0, MPFR_RNDN);
mpfr_printf("%.10000Rf\n", phi);
mpfr_clear(phi);
唯一要注意的是 mpfr 內部用的 precision 是以 2 進位為底,所以我們在十進位需要的精確度,要先換算為 2 進位的位數,再來就能直接算出 phi 啦,試著算過 50000 位數再對個網路上找的答案,數字是完全一樣的。
這個 library 算得非常快,一百萬位的 phi 也是閃一下就出來了,一億位在我的 64 bit Linux, 2 GHz AMD Ryzen 5 需時 37s,相比 e, pi 這類超越數,phi 只需要 sqrt(5) 真的是非常簡單的了。

扯遠了拉回來,如果我們要用 mpfr 這個函式庫,利用公式解來算 fib(93),要怎麼做呢?
fib(93) 到底有多少位數呢?我們可以用 2^n 作為 F(n) 的上界,最後所需的位數至少就是 ceill(n*log(2)),相對應的我們運算中的浮點數精確度的要求,2^n 這個上界有點可恥粗糙但有用,頂多會浪費點記憶體,最後除出來的小數點後面多幾個零而已,如果能套用更精確的上界當然更好。
mpfr 的函式庫設計精良,呼叫上非常直覺,這段程式碼其實就是寫公式解,應該滿好懂的,程式碼在此。有了這個就可以亂算一堆 fib 了,基本上要算費式數列第一億項 fib(100,000,000) 也是 OK 的(好啦我不保證答案是對的XD,至少 fib(10000) 是對的)。

But,人生最厲害的就是這個 But,公式解真的有比較快嗎?
我個人認為答案是否定的,我們同樣可以用 fast-fibonacci 搭配 gmp 函式庫來計算,因為都是整數的運算可以做到非常快,我的測試程式碼在此

同樣是計算 fib(100,000,000):
formulafib.c: 57.39s user 2.04s system 97% cpu 1:01.09 total
fastfib.c: 4.70s user 0.20s system 75% cpu 6.524 total
O(lg n) 的 fast-fibonacci 遠比<O(1)>的公式解來得快。
問題就在於,到了所謂的大數區域,本來我們假定 O(1) 的加法、乘法都不再是常數時間,而是與數字的長度 k (位元數)有關。而上面我們有提到,基本上可以用 2^n 作為費式數列的上界,也因此費式數列的數字長度 k ~= n,加法、乘法複雜度就會視實作方式上升到 O(n) 跟 O(n^2) 或 O(n lg n) 左右。
在 fast-fibonacci,我們需要做 lg n 次的 iteration,每次三個乘法兩個加減;公式解雖然沒有 iteration,但需要計算兩次次方運算,也等於是 lg n 次的乘法跟加法,然後還有除法,我們運算的又不是整數而是浮點數,這又需要更多的成本,一來一往之間就抵消了公式解直接算出答案的優勢了。

在通常的應用上以及現今電腦的實作,我們還是可以假設整數的加減乘都能在近乎常數時間內結束,這樣我們才能好好討論資料結構與演算法的複雜度,進而把複雜度學好。費氏數列的問題在於,在數字小不用考慮運算複雜度的時候,公式解和 O(lg n) 的 fast-fibonacci 看不出差異,等到 n 終於大到看得出 O(lg n) 跟 O(1) 的差異時,已經要把運算複雜度納入考量了。
理論上我們當然可以假設有個計算模型,無論有多少位的數字,無論浮點數有多少精確度要求,四則運算與次方都能在常數時間內結束,這時公式解就能來到 O(1),但這樣的假設不像停機問題假設的萬能機器,在學術討論上看來不太有意義。
利用 gmp, mpfr 這樣的函式庫,插滿記憶體甚至把硬碟當記憶體來用、把記憶體當 cache 用,浪費幾個星期跟一堆電力,我們可以把無理數算到小數點下一億位、十億位,這是前人們精心為我們建的巨塔,可是數字還是無窮無盡,站在巨塔上反而才看得出我們跟無限有多麼遙遠,誠然人腦可以透過思考一窺數學之奧妙,但不代表我們能超脫數學的嚴格限制浮空而起,妄想記錄無限,我認為是對數學的一種褻瀆。

看了這麼多碎碎念大家想必也累了,總而言之本文透過兩個實作,讓大家體會一下所謂 O(1) 公式解並不一定是 O(1),背後一定有對應的成本;還有就是把費式數列算到一億位真的有點爽,不過我想是沒什麼公司在實務上有在賣 fibonacci 相關的產品啦,除非你想像日本一樣出個寫滿 e, pi 到一百萬位的書讓人當亂數表來用。

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 的斜率呢?這就要看平常是不是很常需要算斜率了。存更多的東西自然可以方便做些處理,但線段更新時也要更新更多的資訊。

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

Related Posts Plugin for WordPress, Blogger...