Reverse linked-list

剛才看了《The Guerrilla Guide to Interviewing (version 3.0)》，立即想重寫 Joel 提到的兩題面試關鍵題：“reversing a linked list” 和 “detect loops in a tree structure.”。後者很簡單，前者要更動指標內容，記得初學 C 時讓我奮鬥了很久，想來看看自己現況如何。

完成的程式如下（全文見這裡，記得用 gcc -std=c99 編譯）：

Node* reverse(Node *node) { if (!node || !node->next) return node; Node* head = reverse(node->next); node->next->next = node; node->next = 0; return head; }

若是以前的話，大概不能這麼自然地寫出簡潔的 code，看來學過 scheme 果然有差，變得較能從高階觀點堆砌程式，也就是將 function 看成基本單位，如此一來，遞迴是自然而然的事。得找個時間練練 functional language，這計畫不能放棄。

碩士研究生涯回顧 (4)

最近週末都在打 YsO，不小心就拖稿了。

上回提到碩一上的結束，我終於確定研究方向為 social bookmark。碩一下修指導老師開的 Data Mining 和必修課 Formal Language。由於我兩門課都有些背景知識，沒花太多時間在課業上。學期初滿認真地做研究，也在 delicious 的 tag 裡找到一些有趣的訊息，像是人們提到 usb 時，容易聯想到 portable [*1]，我猜這是因為隨身碟是最熱門的 USB 產品而帶來的印象。後來斷斷續續想了些相關點子，可惜沒足夠的時間做進一步的研究。

結果後來被會長拐去參加比賽，加上專題生的比賽，同一時間報了五六個比賽吧。原本想亂槍打鳥，看那些發展較好就做下去，結果都有過初賽，搞得寫完初賽報告就不想比了（一口氣寫太多報告把參加整個比賽的力氣用完了）。最後大多爛掉了，幸好還有一兩個有好成績，像是去西安參加微軟思源競賽，是滿有趣的經驗。這算是我參加過的比賽裡，自認為做得最有成就感的，開發速度快，demo 效果不壞，報告也滿成功的。我們做的產品 BNW （Brand New World）用來比較公司品牌或產品。輸入公司或產品名稱後，BNW 會彙集網路上的直述句，再計算出分數。

上圖是其中一個 demo 例子，比較四家公司的品牌。資料只是 web 上的一小部份取樣，不見得能反映實際情況，但不管怎麼說，我們是去向主辦單位 Microsoft 報告，這個結果還挺尷尬的，最後決定在簡報時快速帶過這張，免得被人誤認為是去拆台的。另外，當時看了相關研究「Opinion Mining」，主要是看 Bing Liu 的論文和書，滿有意思的。比賽結束後老師問我是否有意延伸這方面的研究，不過我覺得資料難以取得（比賽時有 MSRA 支援），而且我比較想做 social bookmark 的研究，就結束掉這個小插曲，而碩一下也這麼結束了。之後是碩士兩年裡最發光發熱的暑假衝刺時期，後來完成的兩篇論文，都是在這暑假內完成一半以上的內容。

ps

*1 我用 association rule，發現”usb” -> “portable” with confidence 80%，”portable” -> “usb” with 60%。

Haskell:The craft of functional

書藉基本資料： Haskell:The craft of functional

之前問大中，如果要玩functinoal language，比較推薦那一種？於是大中推薦我看這本學Haskell，浩然只有第一版，只好將就看了。

目前看完Part I Basic Functional Programming，目的是掌握functional language的思維，沒打算實際寫些什麼。2345章順著下來，一章介紹語法，下一章就介紹如何證明程式的性質（reasoning the programs, reasoning the lists），例子淺顯易懂，跟著書裡的範例思考，總算明白證明程式是怎麼一回事。

學PL的人應該會用更嚴僅無誤的方式說明，我針對我的認知說明「證明程式」是怎麼一回事。functional language沒有for, while這些”syntactic sugar”，只有if，剩下的邏輯控制都用遞迴搞定。這樣設計的結果，至少看起來和數學最為接近，程式本身就是數學式子的組合，舉例來說，對函數max(a, b)來說，數學上可以證明max(a, b)有以下的特性：

max(a, b) >= a, for any a max(a, b) >= b, for any b

只要分項討論a >= b和a < b兩個情況，就能證明上面這個性質。換成Haskell的情況，只是用Haskell的語法表示max(a, b)，證明推導的過程就用Haskell的語法表示，而不是數學式子。稍微複雜一點的，可以變成對max(L)，L為一list [A1,A2, A3, …, An]，證明：

max([A1, A2, …, An]) >= max([A1, A2, …, An-1]) >= max([A1, A2, …, An-2]) >= … >= max([A1])

或是

n*max([A1, A2, ..., An]) >= sum_up([A1, A2, ..., An])

其中sum_up(L)表示將list L的內容加總。由於控制流程只有if和遞迴，if 的情況就是分項討論，遞迴可以用數學歸納法。能證明程式性質的話，有機會進一步驗證程式的正確性，比方證明reverse(reverse(L)) = L，或是明白各段程式一定在那些值域內，找出控制語意上的錯誤，像是函數的有效輸入範圍是正數，但輸入的參數值域卻一定是負數。

做為了解程式證明的開始，看這本書頗輕鬆愉快的。

超越Java（Beyond Java） - 4 (Java以外的語言)

書藉基本資料：超越Java（Beyond Java）

ch9討論其它語言，決定一個語言是否成為主流（或著說，取代Java），可分成話題性、時機、語言特性、殺手級應用來看，比方Smalltalk一直被認為是很美的語言，但30年過去仍未能成為主流，它的時機已過，未來也難以流行。Ruby興起很快，話題性夠、時機也對，語言特性好，近年來的Rails更是Web開發的殺手級應用，所以作者在本書花了大幅篇幅說明Ruby、說明Ruby on Rails，我經驗不足，看不懂Ruby更強的功能，不過寫個一陣子後會有所體會吧。

對語言有興趣的人，可以直接翻ch9看幾位專家的看法，很有意思。除了語言外，平台也需要討論，Ruby只是語言，不是平台，降低它的推廣力。提及Java時，或多或少在指JVM、J2EE、J2SE、J2ME，提及C#時也多少涉及.NET Framework、.NET Compact Framework。換句話說，我們說Java好時，其實同時指語言特性好（OOP、安全、規範多）和平台好（write once, run everywhere），JVM成功和重要的原因，可以參閱之前寫的”談JVM跨平台，卻不談scripting language跨平台的原因”。

這代表其它語言也有機會參與這些優秀的平台，Microsoft一直積極(?)強調CLR（Common Language Runtime），Java也有些案例，但都不太成功，像是Jython和JRuby，如果有組織積極推廣語言和Java平台、.NET平台整合，對這些語言是一大優勢。

下面節錄ch9一些有趣的內容：

Lisp

這是一個不簡單的傢伙。Lisp是世界級僅存的古老技術，人們不斷地重新發明或重新發現它，但是Lisp也是一大群家族，許多彼此不相容的設計和實踐，沒有任何一個看起來像是我們的家。當然，Common Lisp需要大修，但是由委員會來重新計計 Common Lisp 在此刻來說相當不恰當。Lisp需要一個仁慈的獨裁者，具有好的偉大的執行力，以及偉大行銷，才可能成功。
p168, by Steve Yegge 

作者另在p172提到 Lisp 的社群總由聰明的programmer組成，校園內也很流行，像MIT就強調用Lisp學習可以讓學生快地抽象思考。也許最後的語言都會回歸 Lisp，但Lisp太與眾不同，需要很多時間和精力學習。

PHP

2005 年最不可思議的一件事之一是，IBM 宣稱要支援 PHP，此舉無疑是針對意圖擁抱 PHP 的中小企業而來。
．．．
就和 Visual Basic 一樣，隨著開發者在錯誤的地方尋找簡單性，PHP 將會被利用在某些不適合的地方。
p170, by Bruce A.Tate (book author) 

相信許多人深有體會，我懷疑在資工學生裡，課餘寫PHP的機會搞不好比其它語言多，寫PHP是賺外快的最好機會。

Perl

某些 Perl 編程員寧願斷掉手指也不願意多打四個字元，才不管這些字元是否可以提升可讀性，畢竟難寫的程式應該也會難讀。
．．．
而 Perl 具有相當多火星文般的語法捷徑，簡直是神祕的溝通方式 (secret handshake )
．．．
說來有趣，但是對照起 Java 則是截然不同，還是別去用 Perl 吧 !
p170, by Bruce A.Tate (book author) 

這裡應該是比較開發大型多人專案的情況，有用過Perl的人都很享受快速用Perl解決瑣碎雜小事吧。

Smalltalk

早在 Java 尚未在 James Gosling (Java之父) 的眼中閃爍時，聰明的開發者就已經使用 Smalltalk建立成功的物件導向應用了。而「不是很聰明」的開發者用 Smalltalk 建立某些有史以來最醜的物件導向程式。
p171, by Bruce A.Tate (book author) 

作者認為Java的成功造成Smalltalk元氣大殺，它們都是良好的OOPL，Smalltalk語法特殊，主流的C++不願嘗試，選擇改良C++的Java則成為贏家。

Functional Language

用Haskell寫費氏數列（Fibonacci series）：

fib 0 = 0 fib 1 = 1 fib n = fib (n-1) + fib(n-2)

Java

我沒說 Java 已死，或著 Ruby 即將接班，或著延續伺服器將會支配一切。我只知道：

• 我現在很受傷，我的顧客也是。我愈來愈難叫我的顧客要滿意 Java 的一切。
• ．．．

p174, by Bruce A.Tate (book author) 

讀了「Beyond Java」後，我覺得我又想學Common Lisp，但之前挑戰多次（包含Scheme在內）失敗，我真不懂為什麼Lisp要用這麼多括號，讀寫都很麻煩，最近會先玩Ruby和Haskell吧，哦，還有Python，別忘了Google內部喜歡用Python寫system management。