Tag

2018年5月10日 星期四

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

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

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

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

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

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

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

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

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

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

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

2018年5月6日 星期日

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2018年5月1日 星期二

剖析表達文法 PEG 簡介

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

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

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

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

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

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

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

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

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

2018年4月27日 星期五

西方憑什麼

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

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

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

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

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

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

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

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

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

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

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

2018年4月6日 星期五

整理 rust module 的安排方式

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

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

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

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

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

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

函式更多,可以把整個 module 移到另一個檔案,lib.rs 裡面只留下 mod 宣告:
mod modulename;

內容移到 modulename.rs 裡面;或者有足以獨立出來的功能,可以放到 modulename 資料夾下,並加上 modulenmae/mod.rs 來表示這個資料夾是一個 module。

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

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

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

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

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

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

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