Monday, May 12, 2008

Parser Generators

The practice of programming

在軟體開發過程,我們很可能得寫大量的程式碼來完成一些繁瑣、平凡的工作,避開這個窠臼的辦法就是「自動化」。誠如 Kernighan 和 Pike 在 The Practice of Programming 一書所闡述的,優秀的軟體設計運用幾個基本原則:簡單(simplicity)、清晰(clarity)、一般性(generality)、自動化(automation)。

舉個例子, IC designers 常會跟 f/w 人員一起關起門來,私下協調出各種用途的 registers (memory mapped I/O),這些開放給 f/w 人員使用的 register 介面,會有一份以 Verilog 形式存在,另一份則以 C code 的形式存在,在 IC 開發過程,這些 registers 會經歷多次的變更(例如改名字、改位址、添加 registers、刪減 registers 等)。可以想見,要手動讓這些 registers 在 Verilog 及 C 間維持一致,是件繁瑣、容易出錯的事。

電腦在處理這類格式轉換工作時,得有個 parser 來剖析源文件;偏偏要建構 parser 也有好些瑣碎的東西必須處理。幸好 Compiler 是門發展已久的學問,有許多 parser generators 可以讓這些繁瑣的建構過程自動化。

早期的 parser generators (例如: Yacc )幾乎都是 LR 系列的,一個主要的原因是,教科書告訴我們 LL parser 是不切實際的,只有 LR parsers 才能有高效的表現;另一個理由是, LR parsers 想要手寫,大概也很難 :)

好玩的是後來出現了幾個廣為流行的 parser generators (例如: JavaCC, ANTLR, Boost.Spirit),都走 LL 風。這勾起我的好奇心,細查下才發現 LL 風的 parser generators 在 90 年代有了新的技術突破,我該 update 一下之前教科書塞進我腦袋的資訊了 =.="

如果大家也想複習一下學校教的 Compiler 技術,可以不用翻箱子找課本了,因為維基百科對這方面的資料,紀錄還滿完整的。文末附上我為相關條目所作的分類,相信可以為大家省卻一些時間。

Tags: [] []

Sunday, April 13, 2008

Phases of a Compiler

先前曾經探討,像我們這種靠寫程式混吃的,最好備有兩把刷子,當發現其中一把刷子無法刷掉問題時,趕緊換上另一把刷刷看。通常一次只要用上一把,就可以把問題刷掉,偏偏有些問題比較棘手,要同時用上兩把刷子,左右開弓,才刷得乾淨!

這些要左右開弓的問題中,有個最典型的例子,那就是實作一個程式語言的編譯器(Compiler),它運作時恰好要經歷「分析」及「合成」兩個階段,這實在太妙了,所以我將它整理整理,簡述如下:

  • Analysis Phases
    • Linear Analysis
      • alias: scanning, lexical analysis
      • output: token stream
      • language: Regular Expression
    • Hierarchical Analysis
      • alias: parsing, syntax analysis
      • output: syntax tree
      • language: Context Free Grammar
    • Semantic Analysis
      • e.g. type checking
      • output: syntax tree
      • language:
        • Syntax Directed Definitions
          • 為每個 syntax production rule ,以 CFG 撰寫對應的 semantic rule
        • Translation Schemes
          • 將 semantic actions 嵌入既有的 syntax production rules 中
          • parser generator 常用的方法
  • Synthesis Phases
    • Intermediate Code Generation
      • built after the analysis phase
      • output: intermediate representation
        • e.g. three-address code
    • Machine-Independent Code Optimization
      • output: intermediate representation
    • Code Generation
      • output: target-machine code
    • Machine-Dependent Code Optimization
      • output: target-machine code
Tags: [] []

Two Ways to Solve a Problem

這些年下來,我反覆觀察到一個現象:程式員各有一套慣用的方法來克服自己遭遇到的問題,這些解題習慣可區分成兩種,工程師多只專精其一,只有少數能任意在兩者間自在地切換。

在很多情況下,無論程式員採用哪種作法,都可輕易把問題解掉;但是另有一些問題,卻不是這樣隨性而為就解得掉的--這就值得我們好好玩味了……

以 1..n 的正整數相加這個例子來說,我知道程式員應該利用現成的副程式,以爬說語來寫,應該要長成這樣:

n = 100
y = sum(range(1, n+1))

假裝我們沒有現成的,像 sum 這樣的副程式可用。那麼,一種可能的寫法如下:

y = 0
for i in range(1, n+1):
    y += i

這是標準的合成(Synthesis)法。以這個例子來說,如果不考慮時間複雜度要 O(n) ,這個方法其實沒什麼不好,畢竟它非常直覺,寫起來也很簡單。

大部分資訊背景的,甚至其他工程背景的,都傾向以這種「合成」的策略來克服問題。

由於這是個已經爛掉的例子,我們當然知道有個時間複雜度只要 O(1) 的作法:

y = (1+n)*n/2

這是典型的以分析(Analysis)手段來解題的例子。通常數學或物理等理科背景的人,比較慣用這種「分析」的手段來解決問題。

大部分的工程問題都牽連太廣、太複雜了,很難找到分析解;所以工程師們很習慣採用 trial and error 的合成策略,只求找到一個可行的作法。

這種「先兜出一個作法,看著它如何失敗,然後再兜另一個作法試試,不行的話再兜另一個……」的合成策略,陪伴我們度過無數個夜晚,也解決了不少問題,但如果每次「歪打」都沒有任何「正著」甚至「歪著」的跡象,這種策略就完全失靈了。

在合成策略無效或顯得白費功夫時,也許可以學著適應理科背景的慣用手法:「靜心分析問題,用數學精確地描繪出問題,建立模型,擴充內容,增大視界」,據此提供新的想法和嘗試的途徑。

推薦文選:

Tags: [] [] []

Saturday, April 12, 2008

Make a Secure Code Server

來這混吃也七個月有餘了,初到公司時正逢新 IC 開發,我受命寫了工具程式以驗證功能,完成了 Boot Loader 以執行外部程式,也開發了應用產品的 firmware 以提供下游客戶 total solution ~~

接單量產、功能穩定後,準備接手的同事人竟然在新竹--先前架的 code server 一直都只在台北這邊的內網使用,安全無虞,現在既然要跨到外網了,當然得提防封包被監聽……

原先架設的版本控制系統 SVN 及搭配的問題追蹤系統 Trac ,兩者都是透過 HTTP 協定和用戶端連線,現在為了隱密地傳輸資料,最直接的方案就是改走 HTTPS (HTTP over SSL)協定。

要讓我們的網頁伺服器 Apache 支援 HTTPS ,最省事的作法就是安裝 Apache 時就採用整合了 SSL 的安裝包。很不巧的是我之前用的安裝包是 no_ssl 的版本,所以得重新安裝 Apache 。另一方面,這一段日子以來, 無論 Apache 或 SVN 等,都陸續推出了新版,索性就把它們都再安裝一次(記得要先 uninstall 喔),相關步驟整理如下:

  1. SVN 及 Trac 的安裝,可以參閱我先前的 Blog SVN & Trac Installation 備忘
  2. SVN 及 Trac 的設定,可參閱我利用 wikidot 作的整理:
  3. SSL 設定範例,我也 wiki 了:
Tags: [] []

Sunday, April 06, 2008

Fingering of Keys

按鍵是很普遍的人機介面,也常用於內嵌系統(Embedded Systems)。既然大家那麼愛用按鍵,很自然地, Embedded Systems 軔體開發人員就常常得處理按鍵的偵測、編碼等議題。此外,為了按鍵操作流暢,我們還必須為按鍵設計適當的指法(fingering)及明確、統一的功能定義(function definition)。

不久前筆者設計了一款相框產品,它雖然只有三個按鍵,但除了要能執行基本操作,如上一張、下一張、設定自動換張的間隔時間等;也要能夠流暢地切換功能,如手動換張、自動換張、顯示日期時鐘、功能設定等;此外,最好還能透過這些操作,讓使用者充分感受到它優越的秀圖速度。

老實說,把這些操作通通塞進三個按鍵內並不是多困難的事,比較需要我們傷腦筋的是怎麼讓使用者覺得操作是簡單流暢、符合預期的。

這裡不是要跟你扯怎麼設計美美的畫面,雖然美美的畫面很重要,但畫面設計還是交給專業的美術人員,我們只要想辦法讓「程式的行為與使用者的期望完全一致」就好了。

為了達成這個目標,我在上面規劃了單擊、長壓、自動重複、組合鍵等操作指法(fingering):

  • Single Click -- 單擊
    • to go to Previous/Next slide
    • to Decrease/Increase values
    • mode switch (AUTO/MANUAL/CLOCK)
    • confirm (mode key)
  • Long Press -- 長壓
    • Power On / Power Off
  • Auto-repeat after a long press -- 自動重複
    • to go to Previous/Next slide
    • to Decrease/Increase values
  • Composite Keys (Shift + Prev/Next) -- 組合鍵
    • menu and menu item switching

在決定了這些指法及其使用場合後,緊接著是要定義各個按鍵在不同指法及情境下所對應的功能(function definition),一個可能的定義如下:

  • Prev:
    • Previous Slide
    • Value Decreasing
  • Next:
    • Next Slide
    • Value Increasing
  • Mode/Power/Confirm/Shift:
    • Mode Switch: AUTO / MANUAL / CLOCK -- 單擊
    • Power On <-> Power Off -- 長壓
    • Confirm (for Menu) -- 單擊
  • Shift + Prev (Shift + Next): Menu Prev (Menu Next)
    • for MANUAL mode of Slide Show:
      • Delete?
        • press mode key to confirm
        • auto-cancel (and return) after 3 sec
    • for AUTO mode of Slide Show
      • Interval (1~60 sec)
        • click Prev/Next key to Decrease/Increase the value
        • auto-confirm (and return) after 3 sec
        • press mode key to confirm
    • for CLOCK mode:
      • Switch between digital clock and analog clock

最後,關於按鍵的處理,我之前還整理了一篇 Keypad Algorithm 大家可以順便去逛逛 :)

Tags: [] []

Tuesday, September 25, 2007

The Art of Design

為甚麼好的設計會來自於差的設計呢? Scott 在 Why Good Design Comes from Bad Design 提到攻讀 CMU Computer Science 博士時選了門介面設計課,第一堂課上他發現一位年輕人素描著隨身聽的各種變異版本,而且圖紙上已經堆積了三、四十種不同考量的版本了。 Scott 於是湊過去問這個小伙子「幹嘛費勁畫那麼多草稿?」,小伙子發楞了好一會才笑著回說:

I don't know what a good idea looks like until I've seen the bad ones.
經過時日洗煉, Scott 後來也體會到當初認為多餘的作法,其背後的精神,他提到:
Each new idea I sketched out was more informed than the last. Each bad idea illustrated some important aspect of the problem that I hadn't thought about before. Out of every five or six ideas, I'd have one or two that might be feasible.
I learned the right way to present ideas–you have to show the other candidates in order to help support the good ones.
When the design student showed me his sketches, he was showing me that he was a designer. All creative, talented people recognize the value of process, and have no concerns about revealing to others that it takes many bad ideas to obtain good ones.
這讓我想到 C++ 的老爸 Bjarne Stroustrup 也曾經提到:
At the start of an ambitious development project, we do not know the best way to structure the system. Often, we don't even know precisely what the system should do because particulars will become clear only through the effort of building, testing, and using the system. How - short of building the complete system - do we get the information necessary to understand what design decisions are significant and to estimate their ramifications?
-- ref. The C++ Programmming Language, p710
這段 William 翻譯如下:
偉大的軟體開發專案開始之初,我們並不知道什麼才是最好的系統組織方式,甚至連應該做出什麼樣的系統都不知道;因為唯有透過打造、測試、使用系統的過程,一切才會明朗。如果尚未打造系統,該如何才能獲得必備資訊以事先瞭解有哪些重要的設計決定?
-- ref. 中譯本, p930
至此,應該不難體會:無論是要創造一個好的設計或成就一項偉大的專案,非常重要的就是要畫出許多「草稿」、進行多項測試及「實驗」。
知道要「作實驗」是個好啟發,卻不夠充分,因為我知道只有能很容易進行實驗的情況下,來談多作實驗才顯得實際。實驗容易進行,人們才有耐性多嚐試,一次又一次、反覆、輕快地測試各個主意,如此,設計才有機會趨於完善。這也是為甚麼大家開發軟體時會找個合用的 framework 來執行 Unit Testing 。
人們進行設計時,常常將一個大系統拆成一塊一塊,然後一次一小塊,個別考量。每一小塊都琢磨得差不多了,再把它們組一組,最後「啪」一聲,整個系統就完成了 :)
唉,事情要是都那麼順利那就好了。實際上我們會遇到許多困難,例如:怎麼把一團模糊的設計概念拆卸成小塊?每一小塊要如何進行設計,將來才兜得起來?每個小塊怎麼兜成一個整體才會穩固?為了無礙進行實驗、兜出想要的設計,還得想法子讓每個小塊都易於抽換。
一個個小塊,就是我們慣稱的一個個模組,而模組設計的目標就是讓每個模組要
  • 夠獨立,不會互相干擾。
  • 夠彈性,滿足抽換的需求。
例如設計自走車時,我們不將輪子的輪軸跟馬達的傳動軸直接連起來,而是在兩者中間放個聯軸器(a shaft coupling)的裝置,如此抽換馬達或輪子時都可以省許多功夫。
又例如設計電子元件時,要求有高輸入阻抗(Zin),及低輸出阻抗(Zout);前級元件的輸出阻抗(Zout)要遠低於後級元件的輸入阻抗(Zin),兩者最好相差十倍以上(以達成最大電壓傳輸),如此我們可以致力於前後級個別的設計,不用憂心它們訊號彼此干擾。
也許剛好自己較熟這塊,總覺得軟體的模組設計花招更多,以 OO 領域來說,相關準則有:
  • Open-Closed Principle
    • Software entities should be open for extension, but closed for modification
    • Principle of Encapsulation of Variation
  • Liskov Substitution Principle
  • Dependence Inversion Principle
    • Abstractions should not depend upon details. Details should depend upon abstractions.
    • Program to an interface, not an implementation
  • Composit/Aggregate Reuse Principle
  • Law of Demeter -- Least Knowledge Principle
    • Only talk to your immediate friends. Don't talk to strangers
  • Interface Segregation Principle
優秀的程式師總是在思索、尋求「一勞永逸」的作法。學習時不妨從具體案例開始;學成應用時,要改而著重背後的精隨,才不會被細節淹沒。這些年下來,我體會到這個精隨就是「因應變化而設計(Design for Change)」。
要明白 Design for Change ,這裡強烈推薦翻翻 Refactoring 裡提出的壞味。個人認為其中又以下列兩個壞味最為深刻:

Monday, September 17, 2007

SVN & Trac Installation 備忘

上週一(9/10)公司要我把 Subversion 環境架起來。除了很高興公司也打算採行版本控制環境來幫助程式開發外,我還打算一併把 Issue Tracking 系統掛上去。

說起 Issue Tracking System,要跟 Subversion 搭配良好,且一樣是 freeware 的,當然非 Trac 莫屬。細查之下,乖乖, Trac 竟然要裝那麼多相關套件,且各個套件還要挑正確版本,才可運作良好。

為了避免大家(或將來的自己)白走冤枉路,這裡把要安裝的東西及安裝步驟條列於後:

Download

反正就把下列連結清單中的檔案都抓下來,待會再一口氣安裝。

Basic install

  1. Run the installer for the latest TortoiseSVN (e.g. TortoiseSVN-1.4.5.10425-win32-svn-1.4.5.msi)
  2. Run the installer for Apache 2.0.xx (e.g. apache_2.0.59-win32-x86-no_ssl.msi)
    • # 讓 SVN client 可以透過 http protocol 連上 SVN server
  3. Run the installer for the latest 1.4.x subversion server(e.g. svn-1.4.5-setup.exe)
    • 順便把 D:\AppServ\Apache2\bin 加入系統變數 PATH 裡,以方便之後的操作

上面安裝順序只要 Apache2 先於 Subversion 即可,因為 Subversion 安裝程式會認得執行中的 Apache2 ,並自動完成一些設定,讓人省很多功夫。

如果只是個人使用,且不打算搭配 Trac ,那裝 TortoiseSVN 即可,而 Apache2 只有下列情形下才需要安裝:

  • 想走 http:// 協定來執行 import, check out, commit, export... 等操作,不想走 Subversion 內定的 svn:// 協定。
  • 想要有 MD5 加密的使用者通行口令認證。
  • 想要 Apache2 代為管理讀取權限。
  • 想要搭配 Trac 使用。

Install SVN Python-packages for Trac

  1. Run the installer for the latest Python 2.4.x (e.g. python-2.4.4.msi)
  2. Run ez_setup.py
    • # 會自動下載 setuptools.exe, 透過此工具以簡化後續的安裝步驟
  3. 開 DOS 窗,切到 Python24\Scripts ,待會的 ezsay_install 都在這執行
  4. Install Python bindings for Subversion
    easy_install -Z http://subversion.tigris.org/downloads/1.4.5-win32/apache-2.0/svn-python-1.4.5.win32-py2.4.exe
    • # 安裝成功會出現 "Finished processing dependencies for svn-python==1.4.2"; 這個步驟需要一段明顯的等待
    • # 讓我們透過 Python 操控 SVN
  5. Install ClearSilver
    easy_install -f http://clearsilver.net/downloads clearsilver==0.9.14
    • # 樣板引擎
  6. Install the latest PySQLite
    easy_install pysqlite
    • # 讓我們透過 Python 操控 Sqlite
  7. Run the installer for SilverCity (SilverCity-0.9.7.win32-py2.4.exe)
    • # 程式碼上色

以上只要 Python24 先安裝即可。

Install Trac

  1. Run the installer for Mod_python (mod_python-3.2.10.win32-py2.4-apache2.0.exe)
    • # An Apache module that embeds the Python interpreter within the server (for Apache/Python Integration)
    • # 用於整合Trac 和 Apache Web Server
  2. Run the installer for Trac 0.10.4 (trac-0.10.4.win32.exe)
    • 把 trac-admin 和 tracd 少掉的副檔名(.py)給加上去:
      cd Python24\Scripts
      ren trac-admin trac-admin.py
      ren tracd tracd.py
      • # 如此,以後在命令列執行時可以直接執行(e.g. tracd.py),不用多打 python (e.g. python tracd)
      • # An enhanced wiki and issue tracking system for software development projects
  3. Install optional Trac plugins
    • Install AccountManagerPlugin (for Trac 0.10.x)
      easy_install http://trac-hacks.swapoff.org/svn/accountmanagerplugin/0.10
      • # 若安裝失敗,則直接對 .egg 執行 easy_install 例如
        easy_install D:\Python24\lib\site-packages\tracaccountmanager-0.1.3dev_r2548-py2.4.egg
      • # 來管理 Trac 專案的成員帳號

WebAdmin, AcdountManager, iniAdmin 這三個 Trac plugins ,可以讓我們直接在 Browser 上操作 Trac 設定,減少於命令列下指令的必要,強烈建議安裝。

如果還有其他需求的,可以到 Trac Hacks 看看有沒有人提供現成的。

此外,有 Trac 中文化需求的,可以到下列網站上逛逛:

Module Loadings of Apache2

首先要先以文字編輯器開啟 Apache2\conf\httpd.conf ,然後搜尋到

#LoadModule dav_module modules/mod_dav.so

將上面的註解 ( # 字號) 去除(如果依照上述的步驟安裝,註解應該被安裝程式拿掉了)。

然後在整個 LoadModule 區段的下方加入以下設定:

# For Subversion
LoadModule dav_svn_module modules/mod_dav_svn.so
LoadModule authz_svn_module modules/mod_authz_svn.so

# For Trac
LoadModule python_module modules/mod_python.so

這樣 Apache 重新啟動時,就會載入 DAV, SVN 和 Python 等模組。

Tags: [] []

Sunday, September 09, 2007

Machine to Transcendent Mind

Robot: mere machine to transcendent mind

前些日子把讀過的機器人書整理上來後,網友 HuaHua 留言推薦了《機器人:由機器邁向超越人類心智之路》。後來我特地跑一趟政大書城,翻閱後才想起幾個月前也在這翻過。如今再次翻閱,還是沒抱回去好好端詳,最大原因是此書主要內容,我在其他諸如書、網路、或論文等,幾乎都涉獵過。

昨天到國家圖書館,無意間發現該書竟躺在那,頻頻向我招手……嗯,這次當然不能再錯過 ^__^

與其說這是本講機器(人)的書,不如說它是探討人造智能(AI)或電腦及機器智慧(Machine Intelligence)發展潛能的書。

Autonomous Mobile Robots

這本書最合我胃口的是第二章〈小心!前有機器車〉,探討作者對機器自走車的實務經驗。裡面提到作者 Hans Moravec 在 Mobile Robot Laboratory 接受 Denning Mobile Robotics 委託,研究如何以二十四個聲納組成的障礙偵測裝置,量測、取得的距離資料,完成自主機器車導航的任務。

聲納是藉由發射一束以三十度角展開的超音波反射回來的聲波來推測距離的,其得到的距離很精確,回音由哪反射回來卻是未知的(因為有三十度的範圍)。所以採用追蹤影像突出特徵的作法無法適用。

作者和學生 Alberto Elfes 合作設計了個新方法解決這個問題。該方法不嘗試找出物體的位置,改而累積計算每個位置所擁有的物性(objectness):

  • 這個架構下,機器人對周遭「物體」的確切身份、甚至存在與否都存疑,但對周遭「位置」的存在卻不容置疑。
  • 因此每個位置被視為一個個永遠存在的水桶,時時刻刻接受並存積著像是小雨般不斷落下、顯示物體佔據該位置的證據。

其具體的作法如下:

  • 將機器人四周的區域以格線劃分,每一小格都紀錄一個數字,代表目前為止,累積對該位置擁有物體(或是該位置空白)的證據。
  • 每當聲納發射一束新的探測聲波,其掃過區域所涵蓋格子的數據,便不斷修正。
  • 格子若位於回聲源,將獲得更多證據,證明有物體存在該範圍內。
  • 格子若位於回聲源與機器人間,將失去這樣的證據(因為若有任何物體存在其間,回聲會從更近的距離傳回)。
  • 由探測聲源往外,聲波強度及其探測準確度,隨距離遞減。所以證據的修正幅度,也要取決於探測聲波在空間中掃過體積(或面積)的大小。

對自主移動機器人有興趣的,想知道機器人如何知道自己身在何方(Localization),如何藉由路徑規劃(Planning),由某個地方到達目的地(Navigation),強烈建議好好翻翻我之前在 Robot Book 閱讀清單也推薦過的 Introduction to Autonomous Mobile Robots 一書。

Power and Capacity

第三章 Power and Presence 主要探討計算能力與機器心智間的關係。曾經關注過電腦發展的人,對這章的推論應該不會太過驚訝:作者一開始先提提怎麼樣能力(如運算速度及記憶容量等)的電腦能達成怎麼樣的任務,然後粗估了人腦運算速度及記憶容量,既然電腦運算能力每年都要倍增,所以估出 2020 年時,個人電腦的能耐會達到人腦級。無論對這議題感到興趣或心存懷疑的,都非常建議也翻翻《心靈機器時代》,當中提到的時間與渾沌的定律(The Law of Time and Chaos),很值得一讀。

作者還在這章提到一個非常有意思的主題--電腦史上不同時間點 PC 的記憶容量(megabytes)與運算速度(MIPS)相除,會粗略維持一個常數,約 1 秒鐘(大概等於電腦將整塊記憶體掃一次需要耗費的時間),原因是電腦跟外界溝通的主要對象是人類,所以要受人類的速度感所束縛,原文對這部份描述得很生動:

The megabyte/MIPS ratio seems to hold for nervous systems too! The contingency is the other way around: computers are configured to interact at human time scales, and robots interacting with humans seem also to be best at that ratio.
On the other hand, faster machines, for instance audio and video processors and controllers of high-performance aircraft, have many MIPS for each megabyte.
Very slow machines, for instance time-lapse security cameras and automatic data libraries, store many megabytes for each of their MIPS.
Flying insects seem to be a few times faster than humans, so may have more MIPS than megabytes.
As in animals, cells in plants signal one other electrochemically and enzymatically. Some plant cells seem specialized for communication, though apparently not as extremely as animal neurons. One day we may find that plants remember much, but process it slowly.

Universal Robots

電腦是 Universal Turing Machine, UTM 的一個良好近似,和 UTM 對應的是 Universal Robots, UR 。不同的是 UTM 專職在虛擬的數位空間發揮運算能力, UR 則落實到現實世界裡的感官及行動上。

萬用機器人是第四章的主題,看看作者對這個議題的看法還滿有趣的。而第四章之後的章節雖很讓人眼界大開,但扯得有點遠了,現在還是將它當作科幻小說的情節,看看就好 :p

Suggested Readings

Tags: [] [] [] []

Tuesday, July 31, 2007

Robot Book 閱讀清單

也許拜大廠效應(例如 Google、微軟及鴻海等相繼投入)所賜,也或者只因為熱門 Robot 商品接續問市所致,總覺得這陣子 Robot 愛好者有增多的趨勢。

碰巧這陣子我也 K 了好些 Robot 相關的書,內容包括理論及實作,涵蓋了電子、電機、機械、機構等,趁空檔把這些書整理整理,上來和大家分享 ^__^

要買 Robot 書,原文部份,天瓏那有專櫃,大家可以去翻閱翻閱;此外,若水堂那有許多相關簡中書,許多甚至是日文或英文書的中譯本,強烈建議去那瞧瞧,絕對不會讓您失望的。

以下就把我認為值得一讀的幾本列出來供大家參考:

更詳細的購買資訊,可以參考我利用 Google Docs and Spreadsheets 所作的整理。

Tags: [] []

Sunday, July 15, 2007

Python 與 CSV

許多資料,像通訊錄或試算表之類的,很適合列表呈現。而 comma-separated values, CSV是微軟牌視窗軟體存放表格資料常用的檔案格式。這種純文字的檔案格式是以逗號(comma)來為每筆(record)資料的欄位(field)作分隔。

舉個實際的例子,不久前我因論文需要,由 Davis 那取得了 1999 年美國千大企業的董事會成員資料。內容包括這些董事(directors)的公司、職稱、年齡等等。

由於我只關心每間公司的董事有哪些,所以就輕快地以 Python 語寫了一個 function ,要電腦讀入這個 CSV 檔後,順便吐出各公司的董事們:

def LoadBoards_v0(fn='direct99.csv'):
    """Loads directors of companies from a CSV file and
    returns a dictionary to lookup directors for a company board (version 0).
    Field Names:
        Company name, Director name, Title, Age, Salary, Boards, HQ city, HQ state
    """
    lines = open(fn).readlines()
    field_names = lines[0].split(',')
    records = [dict(zip(field_names, line.split(',')))  for line in lines[1:]]
    boards = {}
    for record in records:
        boards.setdefault(record['Company name'], []).append(record['Director name'])
    return boards

這段 code 只用到 Python 最標準的開檔讀檔 functions 及內定的資料結構,短短幾行就把事情搞定!什麼?這 code 竟然無法正確執行?哎呀,原來董事的 second name 及 first name 間竟然也出現逗號(至少在這個例子中,我們不想把名字拆成兩個欄位)。微軟應付這件事情的方法是把整個 second name, first name 用引號(")括起來。

還好在咒罵完微軟害人要寫煩人的「引號配對碰」程式後,我想起了 Python 也提供了 CSV 模組,於是將程式改寫如下:

def LoadBoards_v1(fn='direct99.csv'):
    """Loads directors of companies from an Excel CSV file and
    returns a dictionary to lookup directors for a company board (version 1).
    Field Names:
        Company name, Director name, Title, Age, Salary, Boards, HQ city, HQ state
    """
    import csv
    reader = csv.reader(file(fn), dialect="excel")
    reader.next() # cast away the field-name tuple
    boards = {}
    for tuple in reader:
        boards.setdefault(tuple[0], []).append(tuple[1])
    return boards

如果有人覺得還要去算欄位順序是一件很蠢的事,可以改採 CSV 的 DictReader:

def LoadBoards_v2(fn='direct99.csv'):
    """Loads directors of companies from an Excel CSV file and
    returns a dictionary to lookup directors for a company board (version 2).
    Field Names:
        Company name, Director name, Title, Age, Salary, Boards, HQ city, HQ state
    """
    import csv
    boards = {}
    for record in csv.DictReader(file(fn), dialect="excel"):
        boards.setdefault(record['Company name'], []).append(record['Director name'])
    return boards
Tags: [] [] []

Sunday, July 01, 2007

Logo 也 3D

Welcome to StarLogo TNG

前陣子 survey 描述機器動作的程式語言時,看到幾個賣像不錯的 Robot 產品,竟不約而同地,都說 Logo 語。

經過一連串的 google 、到處點閱後發現:原來 Logo 早已跳出原先的認知,不再只是給小朋友玩的烏龜繪圖了!

一直以來,我對 Logo 語言並不陌生,因為手邊好些科普書都有提到,例如:

  • 《電腦如何思考》p53 ,Hillis 以 Logo 為例子,說明程式語言的威力;
  • 《沙地上的圖案》p136 ,〈作為藝術家的烏龜,The turtle as artist〉這節說明了 Papert 的 Logo 及其 Turtle Geometry ;
  • 《MIT 媒體實驗室》p181 ,提到了控制 LEGO 積木的 Logo 語言;
  • 《遊習世紀》p101 ,提到用 Logo 控制的實體機器烏龜如何幫助小孩子學習;
  • ……

Logo 語言我原先比較有印象的,就是它的烏龜繪圖。其最早的版本是一隻地板上亂逛的同時,還會以隨身攜帶的畫筆留下足跡的實體機器龜;後來這隻機器烏龜離開了地面,爬上了螢幕,變成一隻賣弄光影的傢伙。

現在一些 Logo 版本(例如 StarLogo 或 NetLogo 等),允許同時有成百、上千隻烏龜。這些烏龜還可以依行為不同而有不同族系(例如:有些化身成兔子,有些化身成狐狸等)。這下子可以拿 Logo 來跑有大量 agents 的模擬實驗了,這裡是一些例子。

此外,最新的 Logo 方言(例如 StarLogo TNG),已經讓烏龜的生活環境,由原本 2D 的平面,躍升到 3D 立體空間了。這下子光是搞搞模擬就太遜了,乾脆拿來寫些小遊戲,豈不是更酷!

如果現在還有人覺得 Logo 是小孩子玩意,是個跟不上時代的古董。這裡建議一定要去看看 Elica ,它是 Logo 另一個方言,支援 OOP ,不但有優雅的語言內涵,且也用於精緻的 3D 繪圖。

如果還覺得意猶未盡的,強烈建議去閱讀閱讀 Brian Harvey 的《Computer Science Logo Style》。這本書共有三卷,且有電子檔可供下載:

  1. Symbolic Computing
  2. Advanced Techniques
  3. Beyond Programming