2015年11月9日 星期一

Rust computation book chapter 5完成

如上上一篇所寫的,最近在用Rust 重寫Understanding Computation 裡面的ruby code,愈寫Rust 愈覺得這是款設計精巧的語言,很多語法都可以寫得相當精巧

目前進展比較多的是chapter 5 ultimate machine,該章節已經寫完了,大概是因為結構簡單,相比chapter 1的syntax 要建AST好寫很多,該段的code也已經衍合進master:
https://github.com/yodalee/computationbook-rust

在這裡有幾個譔寫上的技巧
enum 要加上#[allow(dead_code)]
這好像是rust 設計上的…feature,因為enum的code 只要沒用到就會判定為dead_code,但通常是測試檔沒測到,或主程式沒用到
其實這樣也有負面效果,也許你的enum是真的有廢選項

寫到這邊我的code 跟原書的ruby code 已經開始有差了
例如裡面的tape function,每呼叫一次write, move_tape_left這類的function,都是用自身的狀態回傳一個新的Tape回來
不過我在Rust,改用call by reference的寫法,大概是感覺到每次都return 一個新的物件感覺很浪費資源吧,這樣就變成兩者執行行為不同的來源Orz
之後檢討並改進XD

附上要如何執行computation book 裡面的內容,我在archlinux 上是真的弄了一段時間,首先要裝Ruby,再裝bundle
sudo pacman -S ruby
gem install bundle
在shell 設定檔內加入:
export GEM_HOME=$(ruby -e 'print Gem.user_dir')
export PATH=$GEM_HOME/bin:$PATH
接著就可以在computationbook 的家目錄,執行
bundle exec irb -I.
>>>require 'the_ultimate_machine.rb'
如果出錯,好像要執行bundle install 把有缺的套件補上,再來的指令就只能用貼的了,測試的檔案都在資料夾下的irb.txt裡面。

感覺Rust 愈寫愈有手感,這種東西果然是要練習寫才會變熟,下次來直播寫rust 好了XD

使用python 爬蟲與pdf 函式庫產生網頁pdf 檔

之前聽傳說中的jserv大神演講,發現一個有趣的東西:
http://c.learncodethehardway.org/book/
簡而言之就是…呃…自虐…應該說用常人不會走的路來學C

不過呢這東西目前來說只有html file,如果要印成一本可以看的文件,畢竟還是pdf檔比較方便,該怎麼辦呢?這時候用python 就對了。
概念很簡單,用一隻爬蟲爬過網頁,然後轉成pdf檔:
爬蟲的部分我是選用強者我同學,現在在Google Taipei大殺四方的AZ大大所寫的Creepy (https://github.com/Aitjcize/creepy),雖然好像沒在維護,不過我們要爬的頁數很少,不需要太複雜的爬蟲程式。
Html轉pdf選用pdfkit (https://pypi.python.org/pypi/pdfkit),這需要ruby的wkhtmltopdf,可以用gem install wkhtmltopdf安裝;再用pypdf2 (https://pythonhosted.org/PyPDF2/)將文件全合併起來,兩個程式寫起來40行就了結了,輕鬆寫意,內容如下:

爬網頁:
from creepy import Crawler
import pdfkit

class C_Hard_Way_Crawler(Crawler):
  def process_document(self, doc):
    if doc.status == 200:
      filename = doc.url.split('/')[-1].replace('html', 'pdf')
      print("%d %s" % (doc.status, filename))
      pdfkit.from_string(doc.text, filename)
    else:
      pass

crawler = C_Hard_Way_Crawler()
crawler.set_follow_mode(Crawler.F_SAME_HOST)
crawler.crawl('http://c.learncodethehardway.org/book/')
合併檔案:
from PyPDF2 import PdfFileMerger

names = ['index', 'preface', 'introduction']
for i in range(53):
  names.append("ex%d" % (i))

merger = PdfFileMerger()
for name in names:
  f = open("%s.pdf" % (name), 'r')
  merger.append(f, name, None, False)
  f.close()

f = open("Learn_C_the_hard_way.pdf", 'w')
merger.write(f)
f.close()

我承認我code 沒寫得很好,各種可能噴射的點,不過至少會動啦,信Python 教得永生;轉出來的pdf檔超醜的,感覺跟之前一些在網路上找的pdf風格有點像,每頁的標頭有些重複的內容應該要去掉,連結也全壞了,就…有空檢討並改進XD
pdf檔放在dropbox(過一段時間應該會失效):
https://dl.dropboxusercontent.com/u/3192346/Learn_C_the_hard_way.pdf

2015年11月6日 星期五

使用Rust 實作Understanding Computation

Understanding Compuation (http://computationbook.com/) 是一本滿有意思的書,它很純粹的介紹<計算>這件事,第一從程式的syntax、DFA、Deterministic Pushdown Automata到Turing Machine,第二部分則從Turing Machine 開始,列舉了很多的種運算模型都能達到和Turing Machine 同樣的運算能力;相反的,從Halting problem跟所有衍生的問題,它也告訴你運算就是有它的極限。

書裡的範例都附有Ruby code,全部放在作者的github 上面,讓人隨時可以測試:
https://github.com/tomstuart/computationbook

最近興起一個念頭,把這上面的code 全部用Rust 重寫一遍,順便當Rust的練習,現在還在實作一開始的syntax 部分;之前針對這部分寫了有關trait 的內容,不過後來被我刪掉了,因為我發現在Rust 裡面其實有更好的實作方式。
之前我說的是,設定trait 為base object,下轄的node impl這個trait,這樣Box<base>就可以容得下所有有實作這個trait 的struct,就像:
trait Expr {
  fn to_s(&self) -> String
}

struct Add {
  l: Box,
  r: Box,
}

impl Expr for Add {
  fn to_s(&self) -> String {
    self.l.to_string() + “ + ” + &self.r.to_string()
  }
}
但其實這樣根本寫不出來(要不就是極度麻煩),在reduce 的時候,要把Add裡面的box 換成另一個value,或是Add reduce 到一個Number,受限於Rust pointer的Owner設計,操作Box需要一層又一層的檢查,這裡就不細講那悲劇性的結果,事實上根本就沒有結果,code 根本不到能動的地步。

反思一下,多看了幾個Rust by Example,突然發現新的寫法:
註:主要是這篇rust 裡linked list 的寫法:
http://rustbyexample.com/custom_types/enum/testcase_linked_list.html
利用Rust 的enum,把相關的struct 都收進一個enum裡面,這個寫法還滿鮮的,而且跟書裡Ruby 的寫法比較不同。
用Ruby若要實作每個node 的reducible function,因為Ruby 偏向OO語言,書中是在每個struct …或class裡面實作reducible function;Rust 因為所有的種類node都由enum管理,會變成這樣寫:
pub enum Syntax {
  Add (Box, Box),
  Number (i32),
  Nil,
}

impl Syntax {
  pub fn reducible(&self) -> bool {
    match *self {
      Number(value) => false,
      Add(ref l, ref r) => true,
      Nil => false,
    }
  }
}

pub fn reduce(self) -> Option {
  match self {
    Number(value) => Some(Number(value)),
    Add(l, r) => match (*l, *r) {
      (Number(i), Number(j)) => Some(Number(i+j)),
      (_, _) => None,
    }, 
    Nil => None,
  }
}
註:其實我也不知道需不需要Nil 這個type。

我們要針對每個不同的型態去實作它們的函式,有些相對簡單,例如reducible(),只有variable 跟number兩樣會是false,其他就用 '_' 全部消掉,雖然所有型態的function 擠在同一個impl 裡面感覺很煩躁,不過好像沒更好的實作方式,這某種程度上來說也是語言設計上的限制吧?

另外上面也可以看到,在reducible跟reduce上,我們的寫法有些許不同,reducible使用的是&self當參數,它不會持有這個syntax的所有權;相反的reduce會將原本的node 替換掉,只能用self 當參數(好其實是我用&self就會出一些很詭異的錯誤,我還不知道怎麼解)
在使用上這會有點差別,reducible 可以一直呼叫,reduce 就只能呼叫一次,之後原本持有的變數就不能再用,我們必須用let將它的所有權轉給另一個變數,如下:
let a = Add(Box::new(Number(1)), Box::new(Number(2)));
println!("{}", a.reducible());
println!("{}", a.reducible());
let m = Add(Box::new(Number(4)), Box::new(Number(10)));
//println!("{}", m.reduce());
let m = m.reduce();
println!("{}", m.reducible());
上面註解的那行不能這麼做,之後m不再持有回傳值的所有權,之後呼叫m.reducible()會形成compile error。
其實這樣滿奇怪的,總覺得這樣用起來限制也太多;當然我們可以把syntax 再封裝到一個struct裡面,每次reduce就自動做一次let m = m.reduce(),使用者就無法亂用reduce()讓編譯爆掉,再研究要怎麼寫比較好囉…

我的code 都會放在這裡,雖然說現在真的沒什麼內容,現在還在實作ch1 的內容,而且感覺還沒進到Rust 的思考領域,寫的東西感覺大有問題……
https://github.com/yodalee/computationbook-rust

2015年11月2日 星期一

Coursera cryptography 1

在陰間為了殺時日,總要找點書來看,因為自知不能看一些會變的東西,例如程式Rust;這種東西等我返陽搞不好都翻了兩翻,現在我主力放在兩個方向,一是修coursera 的cryptography 課程,二是閱讀Logan 大大推薦的Enginnering a compiler,前一個cryptography 1 課程剛結束,這裡記錄一下心得。

這門課不算太難,帶過密碼學上幾個重要的概念:Stream cipher, Block cipher, Asymmetirc cipher,人人都怕的數學只在非對稱式加密前帶過一些。
上課的內容還有授課方向,跟這本<understanding cryptography>非常相似,打書名就能找到這本書的全文電子檔;兩者搭配來看,可以補線上課程內容的不足。

程式作業有6題,只有一個是要求用現有的AES lib 來實作CBC 跟CTR 加密,另外五個都是利用已知的漏洞去破解某些密文,就跟教授上課不斷提醒的:”Don’t invent your own ciphers or modes”,作業藉實際攻擊讓大家了解,即使數學理論上安全的加密,在不正確的實作下,仍會導致安全性流失,寫程式會需要一些底子,不過只要會python 或C++應該不算太難。
從程式作業,真的可以體會密碼的設計是一門高深的學問,倒也不是說不要去實作和修改,否則一些知名的lib 像openSSL是誰在維護?而是要先學好基本概念,了解可能的弱點與攻擊方式,多和大家討論分享實作方式,有討論才有進步。

俗話說得好:「三個臭皮匠勝過一個諸葛亮」,密碼學因為攻擊方式千變萬化,絕非一位天才能掌握全部面向,許多科技領域也是如此,在這個年代作為一個工程師,我認為最有效的學習是先學會基本概念,用一些簡單的例子實作驗證這些概念,再去找其他一流的project參與,之所以不要一口氣去跳進一流的project,是因為那裡一定藏了一堆實作細節,會遮掩掉基本概念;千萬不要閉門造車,分享你的想法,才有更大的進步空間。

2015年11月1日 星期日

錢的聯想

最近筆者在部隊中擔任行政/預財,工作內容大抵就是管部隊的收支:採購連上所需物品、管理銀行國庫帳目、上支出收入簽呈、登連隊收支帳本等,額外任務包括洽公時幫弟兄們買飲料回營XD
預財當久了,其實有種感覺,覺得我管理的不是金錢,而是一種信任:連長會簡單看過簽呈隨即批可,是基於對我學長和我用錢的信任;連隊保險箱的國庫支票和櫃存現金會由連隊行政保管,也是對行政專業的信任;就算是弟兄們放心將錢交給我,讓我去幫他們買東西或是到銀行換成幾袋可以砸死人的硬幣,也是信任的表現。

太多人看到錢就是錢,其實錢只是信用的表現。
歷史證明,人類可以對各種亂七八糟的東西產生信心、貴金屬、貝殼、植物種子甚至是數學加密演算法(bitcoin),大家投入的信心多寡會決定那樣貨品的價值,價值又會反過來影響大家對它的信心。彭淮南說比特幣是一種貴金屬,的確,貨幣本身也像一種貴金屬,在傳遞信用這項功能,貴金屬、貨幣並沒什麼兩樣。

如果我們把金錢=信用這個概念延伸出去,現在國際間的貨幣戰爭,其本質其實是一場信任的戰爭,俗話說貨幣是一個國家的股票,股票價值取決於投資人對公司未來獲利的信心,貨幣價值則取決於人們對未來該貨幣價值--也就是該國家存在的信心。
一但人們對貨幣價值失去信心,便會想方設法將貨幣脫手,換成更能保值的東西,像是iPad(X)
http://technews.tw/2015/07/09/greece-mac-header/

現代的貨幣體系,其實完全是基於信心,紙幣不過是印上防偽功能的防水特殊紙,硬幣則是鑄上肖像的金屬片,物質不重要,重要的是國家擔保的公信,如果今天國家想要,我們也可以換用子彈當貨幣,只是就攜帶性、分割能力、辨識度來說,鈔票硬幣難以取代。
如果失去了擔保的公信,貨幣會在一夜之間化為廢紙、廢五金。

現在先進國家競推的量化寬鬆其實是在稀釋大眾的信心,可見的未來,該貨幣的價值會一直被稀釋,但只要國家擔保長期保值性存在,信心一直稀釋下去也無傷大雅;美日QE 推得之兇,卻也沒多少人認為美國、日本會突然放棄美元日幣,這當然是因為美國、日本背後龐大的資產在支撐它的價值;儘管今日十美元一年後可能只剩九美元,美國擔保的信用仍然可信;相反的,率巴威就算印製10^14 元的紙幣,價值仍比不上幾顆雞蛋。
曾經看到2016 年的總統大選,有人的政見是每人發100億元,的確以國家的力量,我們真的可以這麼做,就像消費券每人可以領3600元;但這政見沒有意義,台灣的信用擔保不了每人發100億元的信用,那時100億元的價值大概跟現在1000元相差無幾。

各國競推量化寬鬆,我覺得是一場「踩煞車遊戲」,量化寬鬆讓貨幣價值降低,逼使大家將貨幣換成貨物,藉此催出貨品需求成長,這樣的下場是,推動的國家最終可能會:
  1. 該國決定踩煞車,退出競推量化寬鬆的行列:這會導致貨幣催生的成長減緩,需要改處理國內的分配問題。 
  2. 推到一定程度,大眾擔心國家無法再擔保這麼多的貨幣,導致大家開始拋售該國貨幣與國債,導致該國債率大升,貨幣一夕間失去價值。 
這就像一堆人開車衝山谷,先踩煞車的會被眾人羞辱,不踩的會摔死;又像是藥癮,停掉會很難過,但繼續吃有可能會吃壞身體,而且吃愈久停掉就會愈難過,要更久才能恢復回來。
台灣是否應該跟著跳下去玩?該是持續寬鬆催生成長,還是該反其道而行,改用所得重分配對付衰退?我覺得這個問題真的滿難答的;但我相信,持續寬鬆推動的成長有其極限,與其跟大家一起玩到累死,我們也可以走一條新的路,想辦法在衰退中,也能過得舒適優雅一點。

不過說回來,我覺得我想得太遠了,只能說「管錢的」其實管的是大家的信任,坐在這位子上,能不戒慎恐懼,把每一筆帳都管得清清楚楚嗎?