Tag

2018年6月16日 星期六

實作麻雀雖小五臟俱全的程式語言

故事是這樣子的,很早以前曾經看過 understanding computation 這本書,這本書第二章的內容,是利用操作語義(operational semantic)的方式,自訂一款極簡程式語言,非常簡單但已經有 if 判斷式,while 迴圈等功能。
最近剛修完 coursera 上面的 programming language,其中有一個作業也是用 racket 的操作語義定義一款程式語言, 這個程式語言更複雜,在資料結構上支援 pair -> list,同時還支援函式,這是之前 Understanding Computation 沒有實做的部分。
花了幾天的時間,把過去的 code 擴展了一些,在那上面實作了函式,在這裡就簡單介紹一下相關的內容,還有一些個人的心得,心得內容可能有對有錯,如果有錯就請路過野生的大大們指教一下:
要看到原本的內容,可以參考之前發在這個 blog 的筆記,還有 Github 上面的原始碼。
https://yodalee.blogspot.com/2016/03/rust-recursive-structure.html
https://github.com/yodalee/computationbook-rust/tree/master/src/the_meaning_of_programs/simple
本次修改的程式碼則可見:
https://github.com/yodalee/simplelang

所謂操作語義,就是明白的定義程式的各指令實際執行起來是如何,實際執行的機器當然是一台虛擬機,模擬執行的過程。原本書裡面有兩種操作語義的方式,一種是小步 reduce,每次將程式的內容變小一些些;一種則是直接 evaluate,有什麼結果直接計算出來。
要實作函式的部分,我把 reduce 的實作刪掉了,因為我實在不知道要怎麼用 reduce 實作函式,reduce 每次只會拿一個指令,然後把它縮小一些些,但在處理 function 上,只要進到 function 內部就要代換成另一個環境給它,步步執行的 reduce 做不到這點。
因為我的程式是來自於 Understanding Computation,所以裡面有些 code 像 while, sequence 是來自書中,其實我們有了 function ,就可以用 recursive 的方式取代 while,sequence 也可以適度修改,例如把 assign 變成如 let var = val in expression 的形式,在環境裡將一個值賦值給變數之後,以這個環境執行第二個 expression,就不需要 sequence 這樣的語法了;這部分大家自己知道就好。

看一個最簡單的例子:加法。
首先我們定義我們程式的單位:Node,要實作加法需要實作兩種 Node,代表數字和代表加法運算的 Node,接著我們就可以用 Node::number(100) 代表數字,用 Node::add(Node::nubmer(3), Node::number(4)) 代表加法;另外要實做一個 evaluate 函式,讀入一個 Node 並做出對應的操作,例如加法是分別把兩個參數都 evaluate 過,用 value 取值,用我們熟悉的加法加起來;其他運算如乘法、判斷用的大於、小於,都是類似的實作。

再深入一點要實作變數,例如 x = 10,就會需要環境 (environment.rs),它是 evaluate 需要的參數,實作是一個簡單的 HashMap,將變數名稱映射到相對應的 Node 上面,注意是 Node 不是實際地址,在我們的實作下輸入地址都是虛擬化為 Node;如此一來就能定義 Variable 跟 Assign 兩種 Node,分別會從環境中拿出值和將某段程式賦予給某個變數 。

再來就是複雜一些的 Pair, List,先定義 pair 以及兩個輔助用的 fst, snd Node,一個 pair 其實就是把兩個程式組合在一起,之後可以用 fst 跟 snd 取出第一個和第二個的值。
在這裡我們偷懶一下,重複使用 donothing 這個 Node 來表示 list 的結尾,一個 list 即是表示為許多 pair 的嵌套,最後一個 pair 的第二個 Node 必須是 donothing。
使用 iter 搭配 fold 就能輕易將 rust 的 integer vec 轉成我們這個程式語言中的 integer list,從最後一個元素開始,一個一個用 pair 與上一次的結果組合起來。
pub fn vec_to_list(v: Vec) -> Box {
  v.iter().rev()
   .fold(Node::donothing(), |cdr, car| Node::pair(Node::number(*car), cdr))
}
結果:
pair (1, pair (2, pair (3, pair (4, pair (5, do-nothing)))))

這裡有個小小的心得是,程式和資料其實是不可分開的,當我們在組合程式的過程,定義一些特定的組合方式就能將程式轉為資料,反之亦然;雖然這是我偷懶的關係,但 DoNothing 可以是程式,表示不做任何事情,也可以是資料,用來表示 pair 的結尾;程式和資料其實是一體兩面,端視我們執行的時候怎麼處理它。

我們來看一下函數,我們創了三個相關的 Node:
  • Fun:參數是一個 string 作為函數名稱,一個 string 作為變數名稱,還有一個 Node 是函式內部的程式碼。
  • Closure: 我一直很好奇 closure 到底有沒有標準中文翻譯,看到有些翻譯稱為閉包,Closure 是執行時遇到 Func 產生的東西,包含函式內的程式碼,以及 evaluate Fun 時的環境。
  • Call:以給定的參數傳給一個 Closure 並執行。
把 Fun 丟進 evaluate 會把當下的環境打包起來,生成一個 Closure;如果是 Closure 的話就不會特別做什麼。
Call 是最複雜的,它有下列幾個步驟:
  1. 把 closure 跟參數 evaluate 過,如果拿到的不是closure 就會發生錯誤。
  2. 將 closure 儲存的環境跟函式取出來。
  3. 在這個環境中加上兩個新的變數:一個是函數名稱指向自己這個 closure,這樣在函式內 Call 自己的名字就能做到遞迴呼叫的效果; Fun 的參數名稱指向傳進來的變數值。
  4. 用新的環境去 evaluate Fun 所帶的程式。
其實如果寫過 closure ,了解相關的概念之後,再去看下面這個 functionalC 的 repository 就滿好懂的了,如果要實作 Functional Programming 裡面的概念,函式都要自帶一個執行的環境,才能把函式像 first class member 一樣丟來丟去,由於 C 的函式並沒有強制要求這點,所以這一個 repository 裡面才會自己定義 closure 這個 struct ,基本上和我的定義一樣,都包含一個真正要執行的函式,還有執行的環境。
struct closure {
  void *(*fn)(list *);
  list *env;
};
再深入一點,假設程式一開始先設定 1000 個變數,然後再定義一個函式,這個函式要包含的環境是否需要這 1000 個變數?如果完整複製所有環境,太浪費空間了,實際上我們只需要記下函式中真正需要的變數即可,以下面這個函數為例子:
let x_add_y = Node::fun(
  "add1", "y",
  Node::add(Node::variable("x"), Node::variable("y")));
它接受一個參數 y 並將它和變數 x 相加 ,這時只要記錄 x ,其他變數都不需要保存,連變數 y 也不需要,因為 y 一定會在呼叫函式的時候被參數 y 給蓋掉(Shadow)。
變數 x 我們稱之為 free variable ,沒有被程式中的 assign 賦值或是以參數的方式掩蓋掉,它在執行時可視我們的環境設定自由變動。

我在 evaluate.rs 另外寫了一個 cal_free_vars 的函式來計算一段程式內的自由變數,它會生成兩個 HashSet 記錄出現過的變數跟自由變數,然後丟給 helper 函式處理。
大部分的處理方式都差不多,就是一路遞迴往下呼叫,像加法就是分別對兩個 Node 計算內部的自由變數;比較不一樣的是 Variable, Assign, Fun;在 Assign 跟 Fun 的地方,分別要把變數名稱、函數名稱跟參數名稱加到變數名單中,如果 Variable 取用的變數還沒在變數名單內,這個變數就是自由變數。
最後修改 evaluate Fun 的地方:
let free_vars = get_free_vars(self);
let mut new_env = Environment::new();
for var in free_vars {
  new_env.add(&var, env.get(&var));
}
用 get_free_vars 得到函式內的自由變數,生成一個新的環境,從現在的環境取得自由變數的值,用新的環境產生 closure;如果環境中沒有自由變數的值,環境的實作會直接崩潰,強制在執行函式的時候,環境中必須要有它的記錄。
以上大概就是一個有函式的程式語言會需要的實作,基本上這個語言能做到一些相當複雜的事,例如遞迴跟 currying 等,在 evaluate.rs 裡有一些相關的測試,例如階乘的遞迴實作:
fn test_simple_big_function_recursive() {
    let factor = Node::fun("factor", "x", Node::if_cond_else(
            Node::gt(Node::variable("x"), Node::number(1)),
            Node::multiply(Node::variable("x"),
              Node::call(Node::variable("factor"), 
              Node::subtract(Node::variable("x"), Node::number(1)))),
            Node::number(1)));
    let statement = Node::sequence(
        Node::assign("entry", factor),
        Node::assign("result", Node::call(Node::variable("entry"), Node::number(10)))
    );
    let mut env = Environment::new();
    println!("{}", statement.evaluate(&mut env));
    assert_eq!(3628800, env.get("result").value());
}
寫完這款程式語言,我開始覺得其實我是在寫個虛擬機,或者說有點像在實作一台電腦。
我們先把所有的資料:數值、真假值虛擬化為 Node 這個單位,一切的操作都是在 Node 上進行;就像真實的 CPU,也是將數字轉化為記憶體內部的 0, 1,在加法這個指令被執行的時候,會拿出記憶體的內容,通過一連串的邏輯閘變成輸出,再存回記憶體。 記憶體就好比我們的 Node,邏輯閘實作則是 evaluate,CPU 執行 x86 指令這款「語言」對應我們自訂的程式語言,只是CPU是真實的機器,我的程式是一台虛擬機 。
程式其實根基於數學,加法是一個概念,我們只是透過 CPU/電腦的實作,亦或是這篇文的操作語義,用虛擬機模擬出加法這個概念,所謂「程式語言」應是數學之神座下超凡的存在。 我們用上人類智慧的極致,打造 CPU,打造電腦,試著去追趕的這神聖的目標,追之求之,卻稱這款模倣的玩意兒為「程式語言」,何等自傲?想想不禁啞然失笑。

2018年6月9日 星期六

東京區知性學習之旅

故事是這樣子的,四月看完了上季霸權之一<比宇宙更遠的地方>,隨意瀏覽相關資料時,發現第三集的極地科學館在東京立川,而且初代南極探測船宗谷,一直都擺在台場的船之科學館進行公開展示,之前去的時候竟然都不知道,點進船之科學館的網站看到正好到 6/10 有特展,當下感到一陣衝動,就訂下五月底為期四天的東京宅爆聖地巡禮知性學習之旅。

機票:
機票選用香草航空,它的好處是有紅眼班,可以最大化旅行的時間效率
去程 JW100 0150 台北 -> 0610 成田
回程 JW107 2200 成田 -> 1255 台北
因為是五月初訂機票,加一件行李來回加起來 9000-10000,其實沒有特別便宜,頂多省個2~3000, 不過記得我跟朋友有這段經典的對話:
A: 都這個價格你幹嘛不搭華航或是長榮?
B: 因為傳統航空的時間都比較差。
A: 原來那個叫做時間比較差喔
反正現在年輕還可以燃燒新鮮的肝來換旅遊時間,再過個幾年大概就不能這樣玩了,特別是去程 0150 的飛機,我幾乎睡不到 2 hr 就被窗戶射進來的陽光照醒了,如果不是在 skyliner 上有睡一下,第一天早上搞不好只能呆在飯店大廳補眠。

住宿:
三個晚上的住宿,下塌ホテルマイステイズ上野イースト,離上野車站走路大概10分鐘,如果是地下鐵就是銀座線稻荷町站。
個人建議在東京玩的話,住宿可以選擇東京車站以北、上野、日暮里、王子、往西到池袋、往東到淺草。
東京車站附近因為比較貴通常不選;上野到日暮里是最理想的,因為從成田機場搭京成 skyliner,在東京的兩個停靠站就是上野跟日暮里,王子和池袋分別可以透過京濱東北線和山手線在15分鐘內抵達日暮里,轉搭 skyliner 非常方便,當然再遠一點也不是不行,山手線沿線時間算好就是了。

通訊:
因為這次可能會和同行者分開行動,所以我們分別申請了網路漫遊,我是使用中華電信 7 天 1G 168 的方案,不貴而且網路速度不差;有了這個基本上已經打爆市面上所有 SIM 卡了,不用插卡,價格也算實惠,1GB 省著點也不是一般人在一個星期用得完的量。

交通:
從成田進到東京市的交通,選擇京成 skyliner ,搭配後兩天的行程選配東京地鐵兩日券,地下鐵跟都營都可以搭,隨意轉乘任我行,如果沒有一日券就要注意在兩個系統間切換的話要另外付錢;另外通常從地下鐵系統換去都營都有一點距離,必要的時候請使用 hyperdia 這類路線規劃軟體,不然隨便走個 700 公尺轉車也不是不可能的。
還有手線跟中央線是 JR 的,換車也要付錢(不同系統的路線也不玩轉乘優惠那一套)。

大致行程與景點,我實際的路線有些許差異,第一天下午我跑去找之前來東京認識的人了,這裡綜合我跟同行者的行程,大致記錄一下:

第一天:
因為上午 06 才飛到,視飛機上的睡眠狀況而定,睡眠狀況不佳可以在飯店大廳多休息一下,排行程的時候有料到這個狀況,所以第一天行程只排台場,累的話就 1500 可以 check in 之後早早回飯店休息。

成田機場第三航廈飲食部:早餐
築地市場 :海鮮午餐,有興趣的話可以加逛築地本願寺。

台場:船之博物館宗谷開放<比宇宙更遠的地方>,特展到 6/10,除了前甲板和輪機室進不去,其他的地方包括主控室都有開放參觀,又是免費上船,值得一看。
回程的時候可以走一小段路去看台場的鋼彈,已經換成新機型了,待到晚上有燈光秀。
東京車站:<Lovelive Snow Halation>,這是我同學去的,不是他說我壓根不知道原來 snow halation 的場地是在東京車站。或者直接拉去秋葉原神田明神社<Lovelive>也可以,這次因為我們兩個都去過就跳過這個點。

交通除了台場之外,都搭配上面的地鐵/都營1-3日券;說實在台場沒有什麼特別好玩的東西,兩家交通線都不是都營或者地下鐵系統,百合海鷗線又超級貴,每次去都要大噴錢…後來就很不想去。

第二天:
淺草:雷門、淺草寺(嚴格來說 lovelive 也來過這裡),這裡大概是大眾景點了我們就跳過介紹吧

鷲宮:鷲宮神社<Lucky Star>,其實就是個鄉間神社,要不是 lucky star 我猜沒多少人會特別排這個點吧,此行真正的目的是東武動物公園,只是鷲宮正好就在旁邊就順便來一下

午餐在東武動物公園站吃連鎖餐廳解決。

東武動物公園<動物朋友>:來這裡看 fururu。來的時候剛好東武動物公園在跟動物朋友進行第二波合作到 7/1,各種動物都有插動物朋友的立牌,不過立牌的尺寸非常的小,有些還藏到非常奇怪的地方,一不留神就會錯過

秋葉原:Game Center 打 Lovelive AC 機台<Lovelive>:打機台也是很重要的,特別是 Lovelive AC 機台台灣都沒有進
簡單來說就是把手機的遊戲畫面變成機台畫面,打節奏改用按鈕打,再怎麼暴力打都沒關係(X,比較要注意的大概是介面設計,九個打節奏的按鈕只是選擇,要按右下角的藍色按鈕跟左下角的紅色按鍵才是確認跟取消;100塊錢可以打三首歌,非常便宜,機台也都有支援電子票證付款,推廣期間優惠五塊錢,想積少成多可以多多用電子票證付款。
由於不是每間遊戲中心都會有,最好先查閱官網稼動站舖一覽確認一下,當然秋葉原地區店舖是最多,這家沒有換下一家就是了。

交通在市內的移動,如早上上野到淺草,晚上去秋葉原,都用 skyliner 買到的一日券。
去鷲宮跟東武動物公園則是用東武鐵道,從淺草搭車。在曳舟跟久喜間要改搭急行,車程大約 40 分鐘。往久喜也有 JR 鐵道可以選擇,一般來說 JR 都會比私鐵便宜一丁點,這樣大家就自己選擇
晚上的行程也可以排晴空塔,這次我們都沒興趣所以沒有上去看夜景,但其實晴空塔的夜景應該是我看過數一數二好的。

第三天:立川

國立極地研究所南極、北極科學館<比宇宙更遠的地方>:來的時候剛好也遇到跟<比宇宙更遠的地方>的合作,不過距離合作開始已經有一段時間,有些立牌跟看板都開始撤掉了,這裡展品內容十分豐富,資料、模型、體驗一應俱全,又是免費入場,超級划算的展場景點。
午餐:三井立飛 lalaport,在單軌立飛站,因為有單日票怎麼搭都沒差,這裡週末人會非常多要注意一下(把它想成林口三井就是了)

 多摩動物公園,藪貓<動物朋友>:大老遠跑來這裡就為了看藪貓,如果要看他們的藪貓跳躍表演,就要關注一下他們的官網,左邊的日曆可以看每日的活動,下一次的表演是 6/23。
晚餐:新宿風雲兒沾麵,本次吃到最好吃的一餐,雖然要排一點隊不過非常值得。
新宿都廳夜景:看免錢的夜景,同時可以看到晴空塔跟東京鐵塔,就是視野被新宿附近的大樓所遮蔽,沒有晴空塔夜景那種一望無際的感覺,但反正是免錢的,不要要求太多。
新宿 SEGA 遊戲中心,Lovelive AC 機台<Lovelive>:因為六月開始有東條希生日活動,活動剛開放馬上來打XD。

立川其實不算近的景點,比一般人會去的吉祥寺、三鷹等再遠許多,遠到想用 JR 東京近郊一日券都沒辦法,只能乖乖刷電子票。我們是從上野先到神田,再換中央線快速到立川,單程 640 元,只要搭上急行或特快,基本上是一小時內可到。
在立川可以利用當地的立川 monorail,一日券搭配多摩動物公園入場券只要1000元,再搭去極地博物館絕對值回票價。

第四天:川越
這天只是找個一日遊景點填時間,倒是沒有一定要去哪裡。

川越冰川神社,關東有名的結緣神社之一,可以在這裡用釣魚抽籤,看看滿滿的風車。川越也有不少租和服浴衣體驗,不去關西也能體驗和服浴衣,算是東京近郊一個想體驗古風不錯的一日遊景點;午餐就在川越老街上的餐廳解決。
池袋,Lovelive AC 機台<Lovelive>,昨天還沒達成東條希活動的條件,今天怎麼能放過?再打兩場XD,打完就要回去啦。
成田機場第三航廈飲食部晚餐

交通我們從池袋出發,用東武東上線的 700 元一日券(或搭配公車 950 元),可以來回池袋跟川越間一次,同樣搭急行的話只要約 40 分鐘就會抵達川越,在川越就全程換步行。
回程就搭山手線到日暮里搭回程的 skyliner。

四天的行程大概就是這樣,算是會走滿多路的行程,必要時請評估自己腳力,特別是兩個動物公園佔地廣闊,東武動物公園從東走到西要 2km,應該一天破 10000 步都算滿簡單的。
在日本搭火車絕對不要搭各停,會快非常多,東京特別是如此,第二天到第四天的東武、立川、川越,搭上急行列車大約 40 分鐘都會抵達,如果搭各停可能就會超過一小時;不過通常(只是通常,不保證),他們都會安排各停列車在某一站等急行列車,這時只要走去對面換車即可。

ps. 以上照片部分由強者我同學 JJL 提供
Related Posts Plugin for WordPress, Blogger...