Boost to Python

前陣子費了番功夫評估可用於複雜網路模擬實驗的工具。這些實驗，除了圖論用得特別兇外；一些隨機抽樣的東西也會用上；此外，實驗數據，也要有工具幫忙繪製圖表。

我先後評估了 Java, C/C++, Pyhon 等開發環境，看看它們有哪些 Library 可用？這些 Library 的成熟度如何？架構優不優雅？說明文件完不完整？使用方不方便？

一開始，我評估了下列的 Graph Theory Library:

1. Boost Graph Library, BGL (C++)
2. Graph Template Library, GTL (C++)
3. LEDA graphs (C++)
4. The Standford GraphBase (C)
5. JGraphT (Java)
6. Java Universal Network/Graph Framework, JUNG (Java)
7. Java Graph Editing Framework, GEF (Java)

上列中，個人較偏好 BGL 及 JGraphT。這兩者我選擇了 BGL ，因為就這個應用，Java 的語法沒 C++ 優雅，執行效率不如 C++ ，且 Boost 擁有一整族質優、高效的 Libraries ，裝來玩玩是一定要的啦，更遑論令人激賞的 Boost.Random 也極切合這次需要。

選定了 Boost ，這就開始安裝 :)

在瞄幾眼安裝說明文件後，假如頭腦還維持一絲清醒，記得要把 Boost 裝到自己的 C++ 開發環境，必定會去拜拜 Google ：

• Quick Howto : Building Boost C++ lib under windows with mingw
• Building on Windows

安裝步驟如下：

1. 安裝 MinGW（也可以安裝 DevCpp 或 CodeBlocks ，它們有附 MinGW 的版本）。
   • 我的 MinGW 裝在 I:\LinuxOnWin\MinGW 目錄。
2. 安裝 Python （非必要）
   • 我裝在 I:\Python24 目錄
3. 下載 Boost Sources
4. 下載含 Bjam 執行檔的壓縮檔。
5. 解壓縮 Boost sources
   • 我解壓到 J:\ftp\develop\Boost\boost_1_33_1 目錄
6. 把 Bjam 執行檔解壓縮到同一個目錄
7. 執行一個 shell，例如 cmd
8. 切換到 Boost sources 的目錄去，然後敲進
   bjam "-sMINGW_ROOT_DIRECTORY=I:\LinuxOnWin\MinGW" "-sTOOLS=mingw" "-sPYTHON_ROOT=I:\Python24" "-sPYTHON_VERSION= 2.4" --prefix=I:\Boost install

註：

• 如果 MinGW 不是裝在 I:\LinuxOnWin\MinGW ，只要修改 MINGW_ROOT_DIRECTOR 參數即可；
• 如果 Python 不是裝在 I:\Python24 ，也是改一下 PYTHON_ROOT 參數就好了；
• 用不到 Python 的，只要把 "-sPYTHON_ROOT=I:\Python24" 和 "-sPYTHON_VERSION= 2.4" 拿掉就好了；
• --prefix=I:\Boost 是編譯好的 Boost 安裝的位置，這個例子是放在 I:\Boost
• 其他設定可以參考這裡

裝好後，可以到 A Quick Tour of the Boost Graph Library 剪貼一些例子來玩玩。

補充說明：

• Compiling 選項要加上 Boost include 檔的搜尋路徑，例如 -II:\Boost\include\boost-1_33_1
• Linking 選項要加上 Boost lib 檔的搜尋路徑，如 -LI:\Boost\lib

在時空兩個方面，C++ 都是高效率的語言，藉著豐富的語言元素和通透的延展性，C++ 可用來表述形形色色的軟體系統，且 Boost 的架構也很優雅。

另一方面，就「作實驗」而言， C++ 稱不上合適的工具。我們要能更快、更方便、更隨性地撰寫、修改程式，要能更動態地控制程式流程。評估後，最後我選擇了 Python ，它是很好的膠合（glue）語言，可以很方便將各個語言撰寫的程式沾粘起來。

令人激賞地， Boost 也提供了 Boost.Python 介面，BGL 也有專門的 Python Bindings 。

Tags: [programming] [Cpp] [Boost] [BGL] [Python] [Graph]

我的 Linux on Windows 體驗

Linux-like 環境下許多好用的工具被熱心的使用者移植到 Windows 上。剛開始人們先移植的是上面的程式開發環境，慢慢的其他實用的軟體也陸陸續續被移植過來。我在 Linux 下接觸了 GNU toolset 後，也在 DOS 下找來了 DJGPP ，企圖讓程式可達到 source code portable 的目的。然後又用了好一陣子的 Cygwin ，也都是用來開發 DOS-based 的程式。在試用了 MinGW with MSYS 後，覺得比 Cygwin 順手多了，就一直沿用至今。 去年才聽說的 coLinux ，更進一步讓我們可以直接在 Windows 上安裝的 Linux ，省掉了許多從前需要移植程式的場合。

十多年前剛接觸 C++ 時，是在 DOS 下開發程式的，當時費了一個暑假的時間完成的〈天線場型電腦繪圖〉程式，就是利用 Borland C++ v3.1 這套工具來開發的。所以接觸 DJGPP 後，我也找了一套叫 RHIDE 的， 除了跟 Borland C++ v3.1 的 IDE 簡直是同一個模子刻出來的外，還是 open source 的。在參考了其他 library 後，我發現可以很容易把〈天線場型電腦繪圖〉程式移植過來，移植後也可以在 re-compiling 後就讓它在 Linux 下跑。

隨著 Windows 及 GUI 的興起， DOS 及其下的 console-based 開發介面慢慢地不能滿足我的胃口，所以就改採 Dev-C++ ，用了一陣子後在 CSZone 聽到有人介紹 MinGW Developer Studio 把 Scintilla 的 code folding 功能整合進去後，也第一時間試用。後來在 Parinya Software 網站的 Resources 上發現它介紹的 Code::Blocks Studio ，一用之下，驚為天人，雖然還有很多改進的空間，但整個設計非常合我胃口。如果你有使用 make 這類 project manager 的習慣，你一定會欣賞 CodeBlocks ，不但支援 multi-project 還支援 multi-target ，且可以跟 makefile 及 shell script 整合得很好。更讓人高興的是它還是 cross platform 的。

如果你想開發或移植程式到 DOS 來，那可以試試 DJGPP 。如果你只是單純的想利用 GNU toolset 開發跨平台的程式，那 MinGW/MSYS 是不二的選擇，再搭配 Code::Blocks Studio 這套跨平台的 IDE 後，更是如虎添翼。如果你想玩玩 XWindow 或 Linux 下其他 open source 的東西，但又不想裝 Linux ，那需要的會是 Cygwin 。 coLinux 則更省事，直接把 Linux 裝在 Windows 上，省了移植的功夫，概念上類似在 Windows 裝上 VMWare ，然後再於上面灌 Linux 。很多 coLinux 的使用者也是 Cygwin 的重度使用者，兩者可以透過 XWindow System 通訊。 Cygwin 下的中文問題可以參考這篇。要在 coLinux 下跑 XWindow ，那一定要看看這篇。

在中文維基百科也有提到一段 Cygwin 的歷史：

Cygwin始於 1995 年，最初作為 Cygnus 工程師 Steve Chamberlain 的一個項目。當時 Windows NT 和 Windows 95 將 COFF 作為目標代碼，而 GNU 已經支持 x86 和 COFF ，以及 C 語言庫 newlib。這樣至少在理論上，可以將 GCC 重定向，作為 cross compiler，從而產生能在Windows上運行的可執行程序。在後來的實踐中，這很快實現了。

在這裡也有相關的討論：

Cygwin 的發展方向是盡最大可能在 Windows 上模擬 UNIX 的 POSIX ,因此採用這套系統編譯出的軟件基本上需要 cygwin 的 POSIX 模擬模塊。唯一的例外，給編譯器賦予-mno-cygwin指令同時安裝有 mingw 運行時庫則可以直接生成原生win32編譯結果直接使用。這麼做如同在 Mingw 下編譯同一個程序一樣，但是要注意如果 mingw 本身都無法編譯這個程序在cygwin 下加 -mno-cygwin 也是沒有意義。

Tags: [GNU] [Linux] [porting] [CPP] [IDE] [freeware]

The Prolog Interpreter

這學期加入 AI 助教群，我打算讓學弟妹從實作中瞭解 Unification Algorithm ，但又不想為他們帶來太大的負擔。從眾多 Prolog language 的 open source 中，我選出了 Peter Bouthoorn 所開發的版本，它原本就是被用於教學，可惜其程式架構實在稱不上漂亮。在無法坐視不理下，我一次一小步地 refactor 它，改了幾百個回合，並將其中好幾個關鍵的地方整個重寫，才有一個適用的 Prolog Interpreter 。這真是個不錯的練習。

接下來是將這個動過手術的 Prolog Interpreter 版本當中的 Unify, OccrCheck, and UnifyVar 等 functions 挖空，要學弟妹參照 AI 課本的 Unification Algorithm 後，為這些挖空的 functions 補上血肉。

考慮到修課的人數眾多，為了讓自己在批改作業時不會哭出來，必定得把這個作業批改的流程盡量自動化。

於是我就為學弟妹準備了一對 .txt 檔: input.txt 及對應的 output.txt 。為了怕有些學弟妹過份聰明地以 printf 將 desired output 直接印出，在批改作業時另外準備其他 input 及 desired output是一定要的。這部分我以 Unit Test 的工具來自動比對，只有在比對出錯才要告訴我出錯的地方在哪，否則它只要簡單打個點代表程式還活著，並在通過所有測試後吐出 OK 就好了。

為了更省事，我在 Windows XP 下裝了 MinGW with MSYS 來模擬 Linux 的 terminal ，並寫了一個 BASH 的 script 來將這一百餘份程式作業自動作執行、比對及歸類的動作。

Unit Test tool 在 Java 下有 JUnit 可以用，無奈這裡用於開發的程式語言是 C++ ，所以勢必要另外找一套對應的工具。我最先注意到的是其中最有名的，移植自 JUnit 的 CppUnit ，進一步瞭解後，發現它 Java 味太重了，感覺很不純，而顯得有點礙手礙腳（唉呀，我是不是太偏執了），於是我最後選擇使用專為 C++ 打造的 Unit++ 。嗯，這次用起來果然很順手 ^___^

Tags: [project] [software] [AI] [prolog] [compiler] [unit test] [cpp] [refactoring] [functional]

又遇 N Puzzle

針對 N Puzzle，之前以 CLIPS, C Language Integrated Production System 求解過，那是專家系統的課，所以我也很配合地，以 heuristic 的方式，寫起一條條的 production rules 。

這次研究所的 AI 課則要求分別利用 BFS (Breadth-First Search), DFS (Depth-First Search), Iterative Deepening DFS 及 A* Search 這四種方式來求解，並比較結果。

無論在 AI searh 理論方面，或是 OOA/OOD 上，這都是個有趣的練習，所以我自告奮勇要打頭陣，完成 framework, BFS, DFS, 和最後的整合及 CUI (Character-based User Interface) 等。

設計的目標有：

1. Correctness
   最起碼要能通老師指定的兩個 case 的試驗。
2. Clarity
   系統架構設計要清晰、簡單、易理解，以方便對軟體作追蹤、審閱、除錯、細部調整、功能刪減等。
3. Performance
   在滿足了correctness 及clarity之後，還要考量程式的高階效率和低階效率。舉凡底層資料結構的選擇、和高層抽象表示法連結上的介面設計等，都是考量重點。
4. Flexibility
   我們在設計時還希望對系統架構能保持一定的彈性。如，不要只針對 8-Puzzle 設計，而更進一步粹取出N-Puzzle的表達方式。

由於分析及設計階段就是採用 OOA/OOD 的方式，所以很自然地要採用支援 OO 的程式語言來實作。經討論，我們決定採用 ANSI C++ 來實作這份設計，並利用 GNU Compiler Collection 來製作可執行檔。

雖然我們只在 Windows 下的 DJGPP 搭配 rhide 的 IDE 及 Linux 下的 g++ 搭配 make 試著編譯過我們的源碼。但理論上應可以適用於任何支援「完整」ANSI C++ 語法的平台。除了 STL 外，還使用了namespace，所以古老的 C++ 編譯環境可能無法順利編出可執行檔。

※請參閱附件：

1. The Report
2. Its UML diagram

Tags: [project] [software] [AI] [search] [puzzle] [OO] [CPP] [Linux]

Re: 請問在何種狀況下會考慮使用exception?

　　就大部分的軟體系統而言，想在程式還沒完成時就知道效率的瓶頸在哪？無異是緣木求魚！

　　在應該使用 Exception 時就使用，在程式還沒正確之前，效率再高都是枉然。

　　在設計之初，最重要的是程式的高階效率，所謂高階效率，就是要求撰寫易於找出錯誤、易於日後陸續修改、具備高度重複使用性的程式碼。

　　程式的架構要清爽、明確且具彈性。才可在未來應付以上這些變局。

　　以設計一個函式庫為例，函式庫的設計者知道如何偵測例外，卻無法預知函式庫的使用者要如何處理這個例外，這時就是 Exception 使用的時機了。

　　換言之，當你設計的軟體系統可以區分為設計者及使用者時，也就是你在設計給未知使用者使用的軟體時，你就可以在偵測到例外時，將之丟出。而且盡量不要使用傳統上應付這種情形的其他任何方法，如：傳回錯誤代碼等。

　　在 C++ 中，你還可以利用 assert 敘述，在這裡建議 assert 敘述使用於內部供軟體設計者偵錯用；而 exception 用於公開的介面部分，供軟體元件使用者例外處理用。──當然啦！這也不是絕對的標準，端看您對自己設計的元件作何假設而定。


※ 引述《AskaLee2 (Aska)》之銘言：

請問各位先進，在何種狀況下使用exception機制最適當？？
使用exception必須付出一些效能上與空間上的代價，
應該有某些狀況非常適合使用exception。

Tags: [programming] [CPP] [exception] [debug]

Re: 有沒有好的機制來判斷物件是否已被 delete

　　如果整個程式都是由我一個人開發的話（包括使用的 Library），通常是不必動用到這類的工具。

　　因為，預防勝於治療嘛！──良好的介面設計，可以杜絕很多記憶體方面的臭蟲。當然啦！再加上正確的運用觀念，那就更萬無一失了。

　　如果你發現程式中不使用類似的工具，就很難避免記憶體方面的臭蟲的話。我建議在條件許可的情況下，可以考慮將相關的介面重新設計。

　　關於這方面的議題，可以參考這個link：
http://www.research.att.com/~bs/bs_faq2.html#memory-leaks

　　當然啦！世界不總是完美的，否則也不會有類似的工具問世：
http://www.andreasen.org/LeakTracer/
ftp://ftp.crpht.lu/pub/sources/memdebug/
http://www.perens.com/FreeSoftware
http://reality.sgi.com/boehm_mti/gc.html

　　如果你的開發環境是 VC 的話，強烈建議使用 NuMega 的 BoundsChecker:
http://www.numega.com/devcenter/bc.shtml

Tags: [programming] [debug] [CPP] [tools]

Assertion

Assertion 的使用目的，就是要防止客戶對程式庫的誤用。以 Design by Contract 的原則再加上 OOP 的術語，簡單說來：就是要確保物件在執行操作或行為後還要維持其內部狀態的正確。

假設描述物件這個行為的程式本身正確無誤，而作業系統也沒來找碴，那使物件狀態脫軌的必定來自物件使用者傳入錯誤的引數。

就如同程式行為發生“例外”一樣，程式庫的使用者知道如何偵測錯誤的物件狀態，但卻不知如何處理...

傳統 C 語言的 assert 做法，就是一偵測到要確認的條件不成立了，就立刻終止整個程式的執行，並列印一些偵錯訊息出來。

但是，在這個愈來愈趨向動態的程式世界。有時連客戶都無法確保傳入的引數是正確的，原因可能不是客戶不夠小心，而是在動態的世界裡，這是無法避免的。

這時，在 C++ 中可行的個解法，就是丟出“例外”。被丟出的例外可以被客戶捕捉，並作一些處理措施。萬一客戶不處理，才將程式終結掉。

我這裡使用的，就是裹著 Assertion 的例外，並利用 template 來讓客戶決定要丟出的例外種類：

From: "Jiang Yu-Kwan"
Sent: Monday, June 18, 2001 4:40 PM
Subject: Re: Fw: JavaOne特別報導

我再看了一下，它支援的是 generic programming，而 template 只是在C++下的實作方式。

以 JAVA 設計的哲學，它可能把GP搞得跟 C++ 的 template 語法很像，但骨子裡卻不必preprocessor處理，而是直接在 run time support。

而 assertion 的支援，只是為了支援 Design by Contract ，其支援的完整性，可能更勝 C。

因為 C++ 對 assertion 沒有更進一步的支援（直接沿用C的做法）。所以， JAVA 在這點有很大的改進空間。

以下我就舉例說明一下，如何製造一個 C++ 版本的 assertion 功能：

 1: // assertion.h
 2: //...
 3: 
 4: template <class Exception> void Assert( bool assertion )

 5: {
 6:     if (! assertion) throw Exception();

 7: }
 8: //...
 9: 

經修改後，我現在實際使用的 assertion 版本如下：

1: // Assertion for C++ version.
2: template <class Exception> inline void Assert( bool assertion )

3: {
4: #ifndef NO_CPP_ASSERTION
5:     if (! assertion) throw Exception();

6: #endif
7: }

 1: // user.c
 2: #include "assertion.h"
 3: //...
 4: class Date {

 5: public:
 6:     class Bad_arg{};
 7:     setMonth( int mon );

 8:     //...
 9: private:
10:     //...
11: };
12: 

13: void Date::setMonth( int mon )
14: {

15:     // 確保設定的月數在正確的範圍，否則，
16:     // 就丟出Bad_arg的例外。
17:     Assert<Bad_arg>(1<=mon && mon<=12);

18:     //...
19: }
20: //...
21: 

更進一步的探討可以參考 C++ 之父， Bjarne Stroustrup 所著的 《The C++ Programming Language 3rd Edition》。

Tags: [programming] [CPP] [assertion] [debug] [exception]

The Thread Class Library for Linux

在設計應用程式時，一些需要並行處理（concurrent processing）的功能，已經很少人使用中斷（interrupt）的方法解決，也不必再自行利用一個輪詢迴圈（Round-robin loop）來達到並行的效果──因為現在作業系統的設計，都已經支援執行緒（thread）了。一個程式可以透過許多執行緒達到並行處理的作用。

一個執行緒的產生，是在應用程式開始執行之後，而執行緒所能運用的系統資源是應用程式可用資源的子集；在應用程式結束前，執行緒就要被銷毀。因為執行緒是應用程式執行時的一個子功能，程式結束後，執行緒就沒有存在的必要。

Linux 作業系統核心提供了 clone() 這個 system call 來支援 thread 的功能。此外， Linux 的共用函式庫中，也利用了 clone() 來實作了 POSIX thread, PThread 標準的 C 語言 thread 應用程式介面。不過在現在到處充斥著物件的後 OO 時代裡，一個傳統 functional 的 C Language API 似乎顯得有些礙手。

這個類別庫（classes' library）主要目的是利用一個 C++ Thread Classes Library ，來提供一個容易使用的物件式介面（object interface），以方便日後在 Linux 系統下開發多執行緒的程式。

“一個具體的問題描述是與一千個尚未運用的抽象觀念等值的”，所以接下來，就先描述一下我們要的 Thread 是長成怎麼樣的：

一個多執行緒類別庫要考量的功能最基本的當然就是要能做好執行緒的內部管理，舉凡執行緒的識別、出生、狀態、行為和死亡等都要照料妥當。

如果執行緒之間要作通訊（communication），當然也要提供一個通訊的管道（channel）;此外，還要考慮到執行緒共用資源時所可能引發的同步（synchronization）問題和避免因互相等待而產生的死鎖（dead-lock）問題。

為了方便多個執行緒的管理，還可以提供執行緒分組的功能，分成一個個的 Thread Group，以方便整組一起操作。

當然，在更完備的功能設計下，每個執行緒和執行緒群組還可以設定個別的執行優先權（priority）。並納入凍結（blocked）後的執行排班（scheduling）設計。

※完整的說明請參閱：

1. 《Linux 系統 MultiThread 類別庫設計》
2. 《Linux 系統 MultiThread MMS 類別庫設計》

Tags: [project] [software] [OO] [CPP] [Linux] [MultiThread]

Graphing for the Pattern of Antenna Field

專四下學期至專五上學期延續一年（1994-1995）的專題課。我選了任教工程數學及電磁學的柯盟卿老師開授的“天線場型電腦繪圖”作為畢業專題。
原先的動機是想藉此磨練自己程式設計能力，又可藉由專題對電腦繪圖有一定的探究，再加上柯教授對於學生的要求：只要學生照規定行事、得到成果，其餘的細節絕不過問；當然啦！有任何疑問時，也可以隨時得到他耐心的解說。

當時我選擇了 Borland C++ v3.1 作為軟體開發的整合發展環境，並將內定的語法語意檢查功能全開，以期保障軟體最基本的強固性。此外，於程式撰寫的過程也力求完全利用 C++ 對物件導向程式設計的擴充功能，以達到最佳的學習效果。
這個專題最主要的內涵是要將天線電磁場強度的空間樣式（pattern）以電腦繪圖的型式呈現出來。
其用途除了可用作電磁學課堂上的教學展示外，還可以對於有心研發天線產品的人員建立方便的觀測模型，以減少反覆試作成品而造成不必要的浪費。
最基本的功能要能在給定了軟體關於天線的參數後，把天線四周的電磁波強度顯示出來。
經由分析，在工程實務上，只注重天線電磁場的場型（field pattern）。所以在圖形繪出前要先經過正規化（normalization）的處理。
又天線場型強度，其電場和磁場僅相差一個常數，故我們只選定了電場的部分著手。
最後，也決定了讓程式的執行平台最基本的要求在當時最普遍的 286AT 配合 DOS v3.3 的作業系統版本。不過為了繪圖的效果，程式被設計成必須在 640*480 VGA 模式下執行。
※請參閱《天線場型電腦繪圖》

Tags: [project] [software] [antenna] [graphics] [CPP]