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,希望你能幫助下一件使用者再戰十年。
敬禮 <( ̄ㄧ ̄ )
Related Posts Plugin for WordPress, Blogger...