2016年3月30日 星期三

Rust 中實作型別運算子重載

最近在實作computation books第九章,用到很多Rust運算子重載的部分
運算子重載嘛,可以對自己定義的struct 或是enum 使用運算子,這樣就能寫出Vec3 + Vec3 這樣比較漂亮的寫法,不用Vec3.add(Vec3),啊雖然兩個本質上沒什麼兩樣啦
這章定義一個Sign的類別,分為<正>、<負>、<零>和<未知>,我們要實作他的乘法和加法:
enum Sign {
  POSITIVE,
  NEGATIVE,
  ZERO,
  UNKNOWN,
}

Rust可重載的運算子可以在這裡找到:
https://doc.rust-lang.org/std/ops/index.html
另外是比較運算子,包括PartialEq 跟PartialOrd:
https://doc.rust-lang.org/std/cmp/

例如我們要重載乘法運算子,以下是網站上的定義:
pub trait Mul<RHS = Self> {
  type Output;
  fn mul(self, rhs: RHS) -> Self::Output;
}

實作時當然就是先以use這個trait,然後實作這trait並加入相關的函式:
use std::ops::Mul;
impl Mul for Sign {
  type Output = Sign;
  fn mul(self, rhs: Self) -> Self {
    if self == Sign::ZERO || rhs == Sign::ZERO {
      Sign::ZERO
    } else if self == Sign::UNKNOWN || rhs == Sign::UNKNOWN {
      Sign::UNKNOWN
    } else if self == rhs {
      Sign::POSITIVE
    } else {
      Sign::NEGATIVE
    }
  }
}
這樣就完成了,現在我們就能這樣寫了:
assert_eq!(Sign::NEGATIVE, Sign::POSITIVE * Sign::NEGATIVE);

另外常遇到的問題是,將運算子重載和Rust 的泛型一起用時,例如,我們定義sum_of_square 這個function,並希望使用泛型:
fn inner_product<T: Copy>(lhs: T, rhs: T) -> T {
  lhs*lhs + rhs*rhs
}
這樣編譯並不會過,因為泛型T 並不適用乘法跟加法,我們需要告訴編譯器,只有實作Mul跟Add trait的型別才能通過。同時指定Output 型別同樣為T,文件上並沒有講如何實作這部分,我忘記是在哪找到要這樣寫的,就為了那個Output=T花了我超多時間RRRRR,反正Rust 的文件就是這樣…
fn inner_product<T: Mul<T, Output=T>+Add<T, Output=T>+Copy>
如果你要不同的實作,例如我要能夠跟i32 相加,那就是:
fn foo<T: Add<i32, Output=T>>(x: T) -> T { x+1 }

個人覺得:相較之下,C++運算子重載的語法真的相當的複雜(事實上我覺得我已經不會寫了Orz),rust 簡潔不少,使用trait 中的function name來實作也比C++ 用 operator+, operator* 好讀很多。

有關於文中所提Sign 的實作,可見:
https://github.com/yodalee/computationbook-rust/blob/master/programming_in_toyland/signs/sign.rs

2016年3月23日 星期三

Rust recursive structure

之前實作Computation book的範例程式碼,一直卡關的第2章原始碼解析的部分,最近突然有了大幅的進展(因為在網路上找到一個別人寫好的相關原始碼),讓我突然頓悟rust 相關的設計,這裡解釋一些常用的技巧。

在建tree的部分,C++ 可能會定義介面用的base class ,再定義下面的derived class,這樣就能用base class 作為介面建tree,Rust 中我們可以用enum 做到這點,enum 除了像C like 的用法,也能指向物件,內含匿名或是有名的物件,我在這裡都是用匿名物件來實作:
https://doc.rust-lang.org/book/enums.html
#[derive(Clone)]
pub enum Node {
   Number(i64),
   Add(Box<node>, Box<node>),
   Multiply(Box<node>, Box<node>),
   Boolean(bool),
   LessThan(Box<node>, Box<node>),
   Variable(String),
   DoNothing,
   Assign(String, Box<node>),
   If(Box<node>, Box<node>, Box<node>),
   Sequence(Box<node>, Box<node>),
   While(Box<node>, Box<node>),
}
之所以要Box<Node> 而不是Node,在rustc --explain E0072 中有介紹,大體是recursive structure 裡,子物件若要包含父物件,一定要是Box 或是Reference &,否則程式算不出Node 需要多大。

用了enum 之後,其他function 的實作也就是在enum 上實作,並用match 來處理所有enum 可能出現的結果,例如我的reducible() 實作:
fn reducible(&self) -> bool {
  match *self {
    Node::Number(_) | Node::Boolean(_) | Node::DoNothing => false,
    _ => true,
  }
}
另外一個要注意的,是用了Box之後,前一篇我這樣寫:
http://yodalee.blogspot.tw/2015/11/rust-understanding-computation_5.html
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,
 }
}
……reduce會將原本的node 替換掉,只能用self 當參數(好其實是我用&self就會出一些很詭異的錯誤,我還不知道怎麼解)
這個問題出在,我的寫法是Add(l, r) => ………
這樣的意思是,如果我們match Add,裡面的l, r的所有權<有可能>會被轉移掉,例如return l,或是return Box<l>,reduce function 又是寫 reduce(&self) 的話,表示我self 是跟人用reference 借來的,我不能又把self的所有權又送出去,所以rustc 會警告match *self這行:
cannot move out of borrowed content
即便你的code 沒有這麼做,rust 還是不允許這麼寫。
如果是 match self 當然沒這問題,但就如上所述,這會變成文中所述<reduce 就只能呼叫一次,之後原本持有的變數就不能再用>的結果,因為match self 的時候self的所有權就轉移掉了。
可編譯的寫法是:Add(ref l, ref r),表示我l, r 仍然是借用,而借用的內容是傳不回去的,這樣一路從self下來都是借用,就沒有所有權轉移的問題;要傳回一個跟l 或r 一樣的內容,就要在Node 的屬性加上#[derive(Clone)],用 l.clone()複製一個新的物件,試圖去dereference l 或r(*l, *r)同樣都會被rust 拒絕。

使用trait:
在本來的範例中他是將程式碼分到不同的資料夾,並用require_relative '../syntax/add' 的方式來擴展原有的程式,Rust不允許使用在上層資料夾裡面的程式碼,我這裡是利用trait 來達成模組化的目的。
Syntax.rs 中只定義AST 裡所需要的物件。
其他的function 我們都用trait 來定義,如果我們要用small_step 的reduce,就use reduce::{Reduce},裡面就實作相關的function,好處是若main不需要reduce 的功能,不要use 這個trait 即可。

相關的原始碼可以看這裡:
https://github.com/yodalee/computationbook-rust/tree/master/the_meaning_of_programs

2016年3月21日 星期一

Minecraft 農場

花了一些時間打造的Minecraft 糧食作物農場總算完工了。

三層樓建築都是同樣的構造,分別種wheat、potato跟carrot,每分地大小為9x9,中間留一格水濕潤土地用,每單位可種植80格地,一層樓共16 單位,可種植1280格,等於是收割一次就飽了XD。

萬頃良田,十分壯觀:


天花板設有dispenser放水收割,利用H tree (學以致用的概念X)同步所有的放水時間,這樣設計缺點就是全部同時放水很消耗運算能力,不過lag只有一瞬間所以還好。
放水 H tree design:



同時內部設有箱子跟漏斗,把東西送到外面的可堆疊儲存空間,不然一次收割東西太多了身上放不下:
可堆疊儲存空間,這個有機會再專文介紹好了


外牆主體是以2x2 的bricks 立柱跟大樑,外層用玻璃牆,讓太陽光透進來…比較有農場的感覺,雖然我覺得現實中真有農場長這樣裡面植物大概早就死光了。
前面收集室的部分則是白羊毛為底,主結構參考Odakyu Shinjuku 的百貨外牆XD



蓋完這棟…我覺得我短時間不想再蓋其他大型建案了正好 Minecraft 1.9 也出了
短時間fastbuild plugin 不能用,就先來嘗鮮1.9 的新功能吧

2016年3月20日 星期日

用Rust 重寫 Raytracer From Scratch

最近看到傳說中的jserv 大神所開的2016系統軟體課程,用C寫了一個Raytracing 的程式,就想我也用rust 也一遍,原本的作者是用C++(註1)寫的,相關資源如下:

Youtube channel:
https://www.youtube.com/playlist?list=PLHm_I0tE5kKPPWXkTTtOn8fkcwEGZNETh
C++ source code:
https://sourceforge.net/projects/rasterrain/
Rewritten in C:
https://github.com/purpon/raytracing_c

這次決定全用cargo 的方式來維護我的project,第一步當然是先用cargo 產生project
Cargo new raytracing-rust –bin

它會建好一個Hello world 的小程式,我們就從這個小程式一步一步往上加。
用了cargo 的好處就是想要什麼,crates.io(https://crates.io/) 上可能都有,例如我們要測量程式執行時間,只要在Cargo.toml 裡加上
[dependencies]
time = “0.1”

主程式就可以加上:
extern crate time;
use time::precise_time_ns;

let t1 = precise_time_ns;
let t2 = precise_time_ns;
即可使用相關的function ,跟C裡面include<time.h>是類似的,只是cargo 會幫你管好相依的套件,執行cargo build 就行了。

要寫入bmp 檔也是,完全不用手爆savebmp function,一樣加上
[dependencies]
bmp = “0.1.4”

extern crate bmp;
use bmp::{Image, Pixel};
相當方便,最大的麻煩其實是crates 上面的文件有時候很少…根本是幾乎看不懂的地步,另外crates的碎片化也有點嚴重,有些常用的模組有複數個可以選擇時,很可能根本不知道要選哪一個比較好。
同樣道理,影片的4/9 有很大一塊被 nalgebra的Vec3 做掉,根本不用手爆Vect.h跟那一大串線性Vect 運算;顏色也是直接用crates.io palette 的Rgba,不造輪子了直接造車子去。

寫的時候深覺Rust 的型別系統真的是嚴僅過剩,看看這段:
let fx = x as f64;
let fy = y as f64;
if ASPECT > 1.0 {
  xamnt = ((fx+0.5)/FWIDTH)*ASPECT - ((FWIDTH-FHEIGHT) / FHEIGHT / 2f64);
  yamnt = ((FHEIGHT - fy) + 0.5)/FHEIGHT;
} else if ASPECT < 1.0 {
  xamnt = (fx+0.5)/FWIDTH;
  yamnt = (((FHEIGHT - fy)+0.5)/ FHEIGHT)/ASPECT - ((FHEIGHT-FWIDTH)/ FWIDTH/2.0);
} else {
  xamnt = (fx+0.5)/FWIDTH;
  yamnt = ((FHEIGHT - fy) + 0.5)/FHEIGHT;
}
FWIDTH跟FHEIGHT都是已經轉成f64 的width, height,Rust 在四則運算上,就限制了float 不能跟int, unsigned int 之類的運算,你一定要自己轉型不然它就跟你該該叫。

Rust 也能用一些相當高階的寫法,很多C/C++裡的index based for loop 在這裡都可以簡化(當然這樣寫是不是比較快?有沒有必要這樣寫倒不一定),例如要求某個陣列中的最大值,如果是for loop 寫法會是這樣:
let mut max = 0.0f64;
for intersect in intersections.iter() {
    if *intersect > max {
        max = *intersect
    }
}
但我們可以改成一行文:
let mut max = intersections.iter().fold(0.0f64, |max, &x| x.max(max));

又或者,下面是對所有物件呼叫它的findIntersection() 函數,並尋找其中是否有物件有交點,與交點的距離又要小於和光源的距離,正規方式先建Vec,再去Vec中尋找:
let mut second_intersect :Vec = Vec::new();
for obj in scene_obj.iter() {
    second_intersect.push(obj.findIntersection(&shadow_ray));
}
for d in second_intersect {
    if d > ACCURACY && d <= light_dis {
        // object between light and intersect point
        shadowed = true;
        break;
    }
}
但我們可以省下建Vec的步驟,直接用迭代的方式:
let shadowed = scene_obj
  .iter()
  .map(|x| x.findIntersection(&shadow_ray))
  .any(|x| x>ACCURACY && x< light_dis);

當然我得承認我功力不到家,這份main.rs裡面有很多地方混合了迭代器的寫法跟index based 的寫法,看起來整個很怪。

不過會動啦,以下是輸出的圖:

整體的code 323行,和C version 1500行比起來短小精悍得多(當然我有很多功能還沒有實作就是了);執行時間的話,我用rust time 去算執行時間是 0.08,雖然C version 是1.53s,但考量它有開AA,可能讓運算量倍數成長,就先不去考慮效率不效率了

結語:
其實某種程度上這也是興趣使然而寫的,也算當做練習Rust,我覺得寫Rust 有個要點要把握,能找到crates 就用,不要沒事就鑽下去認真打造基礎零件,在這個上面認真你就輸了。

其實我這個也可以算重造輪子,拔拔你看人家造的車子都已經上太空啦~~
https://github.com/gyng/rust-raytracer

原始碼都放在這裡,歡迎大家來fork:
https://github.com/yodalee/Raytracing-rust

後記:
* 寫這個就會覺得我當初3DMM 沒學好,對不起簡教授QAQ
* 算是小小吐槽一下好了,原本的那部影片用的根本是用了Class 跟Vector 的C,我邊看邊Murmur: 你這樣寫你到底會不會寫C++ 呀幹 然後有些地方的寫法,例如它Sphere 的findIntersection(),把各個vector 翻出來開腸剖肚的寫法,你真的有想過這些東西都是向量運算,之前你就實作過了,你寫了20 行的東西我兩行就寫完了耶XD

2016年3月13日 星期日

AlphaGo 擊敗人類之後

最近資訊界、圍棋界最火紅的新聞,大概就是Google DeepMind AlphaGo 對戰李世乭,而且還連勝三場取得勝利,在博弈遊戲中公認難度最高的圍棋上擊敗人類高手,開始時還有人覺得是李世乭表現失常,現在我們可能要承認:AlphaGo 真的技勝一籌。

的確,我們這一代站在歷史的奇點,電腦的運算能力不斷增強,打敗人類是遲早的事,我們見證了深藍擊敗西洋棋王,現在輪到圍棋了;李世乭能站在人類的頂點被電腦擊敗,我想也是一種光榮,他和AlphaGo五場競技,想必也將名留青史。

電腦打贏人類:

對於這樣的新聞,有人看了興奮(我先承認我就是興奮的那位),有人看到危機,有人覺得難過(註),其實這樣的新聞根本不是新聞,在很多困難的問題上,電腦早就把人類壓得死死的,比如Compiler在程式最佳化上,老早就已經醬爆人類了,那時候好像也沒人悲鳴:「人類輸了~~~」
我也不認為AlphaGo 擊敗圍棋棋王跟電腦擊敗人類是同一回事,找一下網路上,有很多解釋AlphaGo背後程式原理的文章,它是針對圍棋這個問題去做精細調校,用上各種策略去求一個解,這跟編譯器去逼近register allocation這樣的NP-complete 問題最佳解的概念是一樣的。
我看AlphaGo 打贏人類的真正意義在於:給予大量資料,透過自我進化、類神經網路、大量平行的隨機演算,電腦能夠在可以接受的時間內,對於圍棋這樣PSPACE-hard 的問題,給出一個相當良好的解,過去受限於運算能力、演算法、硬體成本,我們總認為電腦做不到,現在AlphaGo 證實是有這個可能性的。
未來這樣大型運算,包括它的演算法、運算架構、基礎設備,應用在一些極困難問題,很可能會提供一些深具洞見的解答,就如今日我們見到AlphaGo 對圍棋下出了令所有人驚異的下法。

人工智慧會取代人類嗎?

看到AlphaGo 擊敗李世乭之前,我被值星官叫去營區大門押補販賣機的廠商卡車進來;我邊看著相關的新聞,旁邊的補貨阿伯抱著6瓶飲料,流利的用雙手將飲料一瓶瓶咔鏘咔鏘的丟進補貨口;他補了四台販賣機就這樣補了一個小時,頓時間,我體會到一種難以言喻的趣味,遠在天邊的人工智慧正將人類大卸八塊,而我這裡生活仍然依舊。
很多人看了電腦擊敗人類就覺得Skynet 要來了,雖然筆者是沒看過終結者系列,不過以個人意見AlphaGo 差那種機器文化統治人類的社會太遠了。
現代社會其實是奠基在許許多多的物質上面,比如手中拿的一隻手機,機殼用的塑膠需要探勘石油,掘井(喔喔喔噴石油啦~~~),裝船運送,在六輕那樣巨大的廠房裂解成原料單體,經過射出成型才造得出來;然後探勘石油掘井需要機具、潤滑油blah;化工廠的管線有數千公里,層層交疊、互相交錯,管管相接之處都要特殊處理,可能要上金屬接合劑或用防漏膠布;射出成型又是一套巨大的廠房,這還只是塑膠喔,如果是裡面的處理器和射頻晶片,可能要開採矽、鉮、鎵等元素,經過純化、製晶柱(下略一千字) 許多步驟,才能製造出來。
塑膠、金屬、晶片,這些材料更是實現AlphaGo 不可或缺的需求,現代社會是一個由人群、資訊、物質結合成的複合體,從任何一樣東西往下延伸,都能像Tree 一樣拉出一大團必需品,這一切適切的運作才能達到養活這麼龐大人口的巨大生產力,就像在變形金剛3裡面,狂派金剛佔領並破壞了城市,用神奇的方法把他們壞掉的機械行星傳送過來,然後聲稱要「利用地球的資源並奴役人類來修復它」嗯…你把人類社會都打得七零八落,現在連他們嚇到拉出的屎都不知道怎麼清運出去了,是要怎麼弄出「修復一顆行星等級的資源和勞動力」?就衝著這個目的,你不覺得像博派一樣和人類合作是個比較好的選擇?

試著走進一家水電五金行,就能體會到機器世界如此複雜,怎麼會有這麼多令人目不暇給的零件,連保養用的油都有這麼多種;或者試著保養一把剛打完靶、跑完訓練的槍,把所有細縫裡卡住的細砂都清理乾淨,槍管積碳都刮乾淨,就不知道要一個人多少時間和各種不同的工具了,我很好奇當科幻故事裡機器文明嘗試取代人類時,它要如何幫自己換零件、自己保養自己,還有更難的:他們的零件要如何製造出來?只要少一些,機器最終只是廢鐵。

電腦決策跟一支工具沒什麼兩樣,它只會視當下的狀況給你結果,賦予狀況意義、視結果採取行動,這都還是人類的事,AlphaGo 只是一支經過精巧調較,會檢視當下圍棋的盤面,透過它的一系列演算,指出勝率最大落子點的程式,除了這個它什麼東西都不會做。
比較可怕的是有人濫用電腦決策,例如把每個人的作為當成狀況,指出某人成為恐怖份子有多大可能,的確,電腦是冷血的,他只知道算出來的結果,但它不知道意義,從棋盤上取子是一回事,如果今天是從城市裡奪人性命呢?我相信對程式來說,這不過是它記憶體裡一個變數的錯動,但它意義卻大不相同。這也是老生常談了:電腦程式從來就不是問題,錯的是運用它的方式。

而這樣的運用很可能是現在進行式。

電腦決策勢必會進到生活之中,但在它太過深入之前,我們需要設法畫條紅線出來。

--

說遠了,先拉回來,在AlphaGo大戰時,網路上各種搞笑的作品,例如發文:「我叫李世乭,我是一名來自韓國的棋手,今天早上出門前我在網上各大投注點用盡家財下了巨額賭注買我自己輸,我想,這就是人類比人工智能強的地方 」或者把李世乭的照片上面加上「Google 高級軟體測試工程師」、仿葉問電影寫出「李師傅,不要跟他拼棋,嘗試切他電路 」、「第一手,電源」種種令人噴飯的創意作品,人類腦袋相比電腦演算法,畢竟多了那份幽默感和趣味。
AlphaGo 戰勝人類之後,什麼事情都不會發生,圍棋仍然是圍棋,下棋的樂趣也不會有任何減損。
更有甚者,人腦重1400公克估計消耗功率12.6 瓦,無論是當年擊敗西洋棋冠軍的深藍電腦或是今天「分散式」的AlphaGo,都是吃電怪物;人腦雖小,可是能利用工具解各種問題,甚至發明電腦在圍棋上擊敗人類。
我會說:「這場勝利並不是電腦勝過人類,而是人類勝過了自己」

--

註:其實反應還有一種:毫無反應
我在用餐時看到新聞,很興奮的跟旁邊的弟兄說「喔喔喔人類又輸了」他們一點反應都沒有的看著我…然後轉頭繼續看電視QAQ