librep 簡介

動機

我為了教「程式語言」這門課, 需要選一個與 c, pascal, java, perl, ... 系列的語言差異大, 但又具有代表性的語言. 很自然地想到 lisp -- 它是 functional programming languages 當中使用最廣泛的; 而語系內眾多方言 (dialects) 又模糊了不同語言之間的界限. (這有助於學者跳脫「語言聖戰」的迷思, 回到技術層面了解到: 不同的取捨標準自然會造成多樣化.)

Lisp 的眾多方言之中, common lisp 算是主流, 但我個人偏好輕薄簡潔的設計; scheme 符合輕薄簡潔的要求, 可惜只有 lexical scoping, 無法展示 dynamic scoping. 所以我打算四處去找其他方言, 但先決條件是: 該方言必須有自由軟體的 interpreter -- 私底下是否要用自由軟體是每個人的自由; 但站上講臺的老師總不好意思默許甚至間接鼓勵非法拷貝吧? 很幸運地, modem 都還沒有開, 就在 CLE 光碟上發現了 librep -- 真是「擁有得多, 不如使用得巧」 向外求不如向內求.

librep 除了輕薄簡潔且支援 dynamic scoping 之外, 與 gtk+ 及 libglade 也已經整合, 並且是 sawmill 所使用的 scripting language. 雖然這幾套程式庫/軟體我都不會使用, 但它們在 X-Window 的世界都有相當的重要性, 因此從實用的角度來看, librep 似乎也相當有前景.

試車

請先看看你的 cdrom 上面是否已有 librep. 如果沒有, 可以上 RPMFIND 搜尋編譯好的版本; 如果你用的是其他 distribution 或 *BSD, 就要自己從 source 編譯囉.

安裝完畢後, 可以打 info -f librep 看手冊; 如果不習慣用 info, 建議另外下載 html 版的手冊

你可以把 librep 當做一個交談試的 interpreter 來使用: 打 rep 就可以進入這個 interpreter. 然後試著打:

        (+ 1 2 3 4 5)           ; 1 加到 5 是多少?
        (setq x (* 3 7))        ; 把 3*7 的結果存到 x
        (- x 2)                 ; x-2 是多少?
        x                       ; 那麼 x 現在的值是多少?

以上分號後面是註解, 不需要真的敲進去; 當然敲進去也不會出錯, 因為根本沒有作用. 在 rep 的 interpreter 裡面, 可以用 readline 功能鍵 (例如方向鍵, ^a, ^e 等) 來快速編輯; 其中 tab 鍵的功能不是 file name completion, 而是 function name completion. 我們用 ceiling 做例子: ceiling 是「天花板函數」, 與 floor 相反, 所以 (ceiling 1.03) 的答案是 2. 先敲 3 個鍵就好:

        (ce

然後按 tab 鍵, 就會變成:

        (ceiling

最後再把後面的數字與括弧敲完. 試車完畢後, 可以按 ^d 離開 rep.

另一個使用 rep 的方式是先用 vi 或 nano 建好一個程式檔, 例如建一個檔 factorial.jl 內容如下:

        #!/usr/bin/rep
        !#

        (defun factorial (n)                    ; 定義計算 n! 的函數
            (if (<= n 1)
                1                               ; 1! 就不必算了
                (* n (factorial (1- n)))        ; 其他情況 n! = n * (n-1)!
            )
        )

        (format standard-output "number:")      ; 印到螢幕上, 提示使用者
        (setq x (read standard-input))          ; 從鍵盤輸入入資料, 存入 x
        (format standard-output "%d! = %d\n" x (factorial x))

並用 chmod a+x factorial.jl 開放執行權限, 然後就可以在 shell 命令列上, 把它當做一個命令來執行: ./factorial.jl

還可以同時開一個 rep interpreter, 又開一個 editor 修改檔案 (例如叫做 factorial.jl), 然後在 rep 當中下 (load "factorial") 每次修改一點程式, 就重新載入所有函數的定義, 並在 rep 當中測試. 注意: 使用 load 時, 不要加附檔名.

Lisp 的思考方式

在 lisp 裡面, 一串東西用空格分開用小括弧括起來, 就叫做一個 list. 所有的程式, 及大部分的資料結構, 都是 lists -- 所以才叫做 LISt Processing language. 一個 list 裡面的東西, 叫做這個 list 的 elements.

閱讀 lisp 程式時, 可以從一個 list 的第一個 element 看出來作者在呼叫什麼函數; 而後面的其他 elements 就是這個函數的參數, 例如 (expt 3 5).

參數本身如果又是一個 list, 表示這個參數是由另外一個函數算出來的, 例如 (* (+ 3 2) (+ 3 4 5)). 當然這「另外一個函數」的參數本身又可以是其他函數算出來的答案... 例如: (* (+ 3 2) (+ 3 (* 2 2) 5 )). 這種寫法類似運算式的 prefix notation, 只不過i比一般的 prefix notation 多了一些括弧.

Lisp 語系屬於 functional programming languages, 意思是說, 盡量把所有的函數都想成/寫成數學上的函數. 具體地說, 就是要盡量避免使用 setq 之類有 side effects (副作用) 的指令, 而要用 (沒有副作用的) 函數的傳回值來計算你要的答案.

所以 遞迴 的思考方式變得非常重要; 而你所寫出來的函數, 看起來也就很像數學家所寫出來的定義, 例如上面 n! 的例子. 遞迴的精神: 想辦法把一個很複雜/困難的問題, 拆成一個或好幾個「與原問題類似, 但小一號」的問題, 把這些小一號的問題以不負責任的態度發包給其他人去解決, 你只要負責從這些小一號問題的答案湊出原問題的答案就可以了.

有一些問題, 原本用迴圈就很容易解決; 用遞迴解反而浪費時間與空間. 但我們暫且只強調 lisp 程式設計的精神, 而把效率問題留到後面談 tail recursion 時再討論.

基本資料型別

  1. 整數: 53 可以寫成 #b110101, #o65, 或 #x35
  2. 分數: 試試看 (- 7/6 9/8) 不要把這裡的 / 想成是除法函數, 而要把整個 7/6 看成是一個不可分割的元素 (所以 / 前後不可有空格)
  3. 浮點數: 例如 -2.3e-2
  4. 字串: 用雙引號括起來. 需要表達特殊的字元 (例如換列), 請到手冊當中找談論 escape sequences 的地方.
  5. symbol: 像「試車」一節當中用 setq 設定的 x, 或是 factorial 函數的形式參數 n 都是 symbols. (其實就是變數啦)

在一個 symbol 或一個 list 之前放一個單引號, 這個動作叫做 quoting, 表示「我就是要這個 symbol 或 list, 請不要把它的值算出來」. 例如 cdr 函數可以取得一個 list 「除了第一個 element 之外的剩下所有元素」, 要這麼用: (cdr '(a b c d)) 如果不加 quote 像這樣 (cdr (a b c d)) 用, rep 會以為你要先呼叫 a 這個函數, 把 b c d 的值拿來當參數, 算完之後產生的 list 才要餵給 cdr 吃 -- 當然會出錯, 因為 b c d 都沒有值, 而 a 也不是一個函數. 注意錯誤訊息: rep 抱怨說 a 是一個 unbound variable, 而不是說它是一個 undefined function. 那是因為在 lisp 裡面, 函數與變數具有同等的地位. 以後再談. Q: 請在 rep 提示符號下分別打下列四句, 並解釋其輸出:

        'ceiling
        ceiling
        (ceiling 1.2)
        '(ceiling 1.2)

與 quoting 相反的是 eval 函數, 它把後面 (原本當做資料來用的) list 拿來當做 lisp 程式來運算. 例如 '(+ 1 5) 是資料 (一個 list 裡面有三個元素), 但 (eval '(+ 1 5)) 就會算出 6. 可以把 quoting 想成是冷凍, 把 eval 想成是解凍.

另外, 在 lisp 裡面需要用到真假值的地方, 空的 list 表示假, 其他任何東西都表示真. 試試看 (if '() 3 5) 和 (if 'zzz 3 5) 注意這裡要 quote, 不然 ... 為了讓程式看起來更清楚, 有兩個 symbols 專門用來表示真假值: t 是真, nil 是假 (其實就相當於 '()). 這兩個 symbols 都有內建的值, 所以使用的時候不必加 quote.

簡單函數

第一次看不必記, 只要知道有那些函數可以用, 需要的時候查得到就可以了. (從手冊的 "Function index" 單元查起)

  1. 數學運算: + - ... 1+ 1- quotient mod max min abs sqrt expt ...
  2. 數字比較: < <= = /= ...
  3. 詢問是否為某型別: numberp stringp functionp symbolp
  4. 邏輯: and or not

注意:

  1. 這樣子不可以: (mod (floor 14.5) (floor 3.1)) 要這樣才可以: (mod (inexact->exact 14.5) (inexact->exact 3.1))
  2. 請分別用 stringp functionp symbolp 詢問 sin 'sin "sin"

產生/處理 List

car 函數可以取得一個 list 的第一個元素; cdr 函數則可以取得後面剩下的 (小一號) list; cadr 相當於 (car (cdr ...)) 而 cdar 相當於 (cdr (car ...)) 例如請解釋: (cadr '((a b c) (d e f) (g h i))) (cdar '((a b c) (d e f) (g h i))) 的結果.

list 函數可以用來建造 list. 啥? 我們先前不就已經建造好多 lists 了嗎? (list 3 5) 的效果和 '(3 5) 的效果一樣, (list 'a 'b) 的效果和 '(a b) 的效果一樣, 要這個函數做什麼用? (很好, 這是正確的學習態度!) 因為有時候我們想要建造的 list, 裡面想填的值需要用算的, 像這樣: (list (- 7 4) (/ 35 7)) 當然真正的情況絕對不像 7-4 或 35/7 這麼簡單; 總之無法直接把答案寫出來的場合, 會需要用 list 函數, 動態地製造出 list.

如果你習慣一般程式語言, 用 list 函數一口氣把整個 list 建起來似乎比較順手; 但是要融入 lisp 文化, 就要用它的方式來思考: 很多時候我們的 list 是一點一滴堆積起來的 ("從小一號問題的答案湊出原問題的答案"), 這時要用 cons 函數把一個元素塞到一個 list 的最前面, 像這樣: (cons 'w '(x y z)) 可以把 cons ("把頭接到身體上去") 想成是 car ("取得頭") 與 cdr ("取得身體") 的反函數.

其他簡單的 list 函數: length append reverse nth last member 請自己測試. (注意 librep 內建的 sort 函數會破壞 原來的 list, 建議初學 functional programming 的讀者不要使用).

何謂相等? equal 是指長相一模一樣; eq 是指根本就是同一個人. 試試看 (eq 'x 'x) 與 (eq '(x y z) '(x y z)) 再用 equal 試試看. (所以簡單的情況下, 用 equal 的機會似乎比較多)

作業: 看手冊, 研究 reverse 函數怎麼用, 然後用遞迴的方式自己寫一個同樣功能的函數 (叫做 z-reverse 好了). 答案在本頁原始碼某處.

幫助你撰寫 lisp 函數的一些想法與技巧

請參考 程式範例

  1. 先用中文把你想做的步驟寫出來 (例如要做 (z-remove a x) 先判斷 x 是否已是 nil, 如果是的話...不是的話...), 再翻譯成 lisp.
  2. 遇到複雜的大問題, 即使簡化出來的 小一號問題 有好幾個, 甚至其中有些與原問題長得不一樣, 也沒有關係. 可以另外寫輔助函數來解決不一樣的小問題.
  3. 同樣使用遞迴的思考方式 ("從小一號問題的答案湊出原問題的答案"), 有時簡化的對象不同, 寫出來的程式會不一樣; 但都可以解決問題. 多寫就會知道 "從那個方向" "化簡那個參數" 比較方便.
  4. 同樣的運算式重複出現很多次時, 可考慮使用 let 替這些運算結果取名字, 以簡化後面的程式. (例如求二次方程式的根) 再次強調: let 不是用來改變變數的值, 而是像數學證明當中的 "設", "令", 只是為一些 (不會改變的) 運算結果取名字. Lisp 基本上是一種 functional programming language.

作業: 請自己把系統內建的一些函數實作一遍, 例如處理 lists 的 length n-th last member 及處理數字的 expt gcd 等等. (你定義的函數當中只准使用 car cdr cons + - * / ... 等簡單的函數).

Tail Recursion 與其他效率問題

上面的範例程式為簡單起見, 並且為了強調 functional programming 的思考方式, 都採用最直接的寫法; 但從執行效率的角度來看, 大部分都不甚理想.