[Common Lisp] 程式設計教學：資料型態 (Data Type)

前言

資料型態規範電腦程式中特定資料的合法 (valid) 操作。本文介紹 Common Lisp 的資料型態。

由於 Common Lisp 的資料型態較龐雜，先大略看一下即可，不用硬背。寫一陣子 Common Lisp 程式後自然會熟悉。

漸進型態 (Gradual Typing)

在預設情形下，Common Lisp 是動態型態 (dynamically-typed) 語言。但 Common Lisp 允許程式設計者加上型態宣告。當程式碼加上型態宣告後，Common Lisp 的行為會相似於靜態型態 (statically-typed) 語言。

以下函式用來求階乘 (factorial)：

(defun fac (n)
  (declare (unsigned-byte n))
  (cond ((= 0 n) 1)
        (t (* n (fac (- n 1))))))

參數 n 為非負整數 (non-negative integer) 時，這個函式才有意義。因此，我們用 declare 指令將參數 n 的型態鎖定在 unsigned-byte (即非負整數)。

Common Lisp 中用來檢查型態的指令有 declare 和 check-type。兩者在行為上有一些差異，詳見下文。

Common Lisp 的資料型態

以下是 Common Lisp 的資料型態：

• 布林 (boolean)
• 數字 (number)
• 字元 (character)
• 符號 (symbol)
• 列表 (list)
• 陣列 (array)
• 雜湊表 (hash table)
• 套件 (package)
• 檔案路徑 (pathname)
• 資料串流 (stream)
• Readtable (註1)
• 隨機狀態 (random stats)
• 函式 (function)
• 結構體 (structure)
• 類別 (class)
• Condition (註2)

(註1) 儲存 Lisp 語法的物件，用來搭配輸出入指令，如 read。

(註2) 用於警告 (warning) 和錯誤 (error) 的物件。

除了 Common Lisp 現有的型態外，Common Lisp 保留使用者自訂型態的彈性，讓程式設計者可根據自己的需求來新增型態。以下是使用者可新增的型態：

• 使用 deftype 新增型態。詳見下文
• 使用 defstruct 新增結構體
• 使用 defclass 新增類別
• 使用 define-condition 新增 condition

布林 (Boolean)

Common Lisp 的布林數有兩個值，分別為 t 和 nil。前者為真 (true)，後者為偽 (false)。

除此之外，Common Lisp 還有 generalized boolean 的概念，即布林語境。在布林語境下，除了 nil 視為偽以外，所有的值都視為真。

數字 (Number)

Common Lisp 的數字資料型態如下：

• number (數字)
  • real (實數)
  • rational
    • integer (整數)
    • fixnum
    • bignum
    • ratio (有理數、分數)
  • float (浮點數、小數)
    • short-float
    • single-float
    • double-float
    • long-float
  • complex (複數)

基本上就是對應數學上常見的數字類型。但考慮電腦運算的議題，不同資料型態會有不同的精確度。

整數 (Integer)

Common Lisp 標準規範整數可達無限大及無限小。實務上，整數的大小會受到系統資源的限制。所以，Common Lisp 可用來實作大數運算相關任務。

在 Common Lisp 的整數中，又再細分為 fixnum 和 bignum 兩者。前者有範圍限制，後者則無。fixnum 實際的範圍委由 Common Lisp 實作品來決定，所以 fixnum 的範圍不是固定的。fixnum 會比 bignum 有效率，但 Common Lisp 會自動在兩者間切換，如同 Python 或 Ruby 等支援大數運算的語言般。

以下範例程式可求得宿主系統的 fixnum 的上下限：

(load "common.lisp")

(defun main ()
  (puts (format t "Maximum of fixnum: ~D" most-positive-fixnum))
  (puts (format t "Minimum of fixnum: ~D" most-negative-fixnum))
  (quit-with-status 0))

(main)

註：common.lisp 是筆者自製的小工具。在 cwchentw/cl-yautils 可見其內容，或是參考前文。

有理數 (Rational Number)

有理數是能表現成 p/q 型態的數字。在 Common Lisp 做整數運算時，若兩個 (或以上的) 整數無法整除，運算結果會自動轉為有理數。反之，若兩個 (或以上的) 有理數經相加或相乘後可整除，也會自動轉為整數。

由於整數間的運算不會自動轉浮點數，如果要把有理數轉為浮點數，可用 float 指令。像是 (float 1/4) 會得到 0.25。

反之，如果要把浮點數轉為有理數，可用 rational 函式或 rationalize 函式。兩者的差別在於前者會直接以浮點數的數值轉成相對應的有理數，後者會以浮點數的精確位數轉為有理數。例如，(rational 0.25) 會得到 1/4。

浮點數 (Floating-Point Number)

浮點數型態用來表示數學上的浮點數。Common Lisp 有四種精確度的浮點數型態。

複數 (Complex Number)

由於 Common Lisp 有原生的複數型態，程式設計者不需要再以其他的資料型態來模擬複數。複數使用 #C 做為前綴，像是 #C(5, -9)。

符號 (Symbol)

符號在 Common Lisp 中做為識別字 (identifier) 來用，用來表示物件。但符號本身也是一個物件，可做為字串印出，也有屬性 (property)。

列表 (List)

列表，又譯作串列，是 Lisp 家族語言的經典資料結構。在資料結構的概念中，列表屬於單向連結串列 (singly-linked list)。由於 Lisp 是高度抽象的語言，在 Lisp 中處理列表和在 C 語言中處理串列差異很大。Lisp 的列表可儲存任意的物件。

在 Lisp 中，列表由一連串的 cons 組成。 Cons 如同列表的節點，零至多個 cons 串接起來就成為列表。

除了用來組成列表外， cons 也可用來模擬其他的資料結構。由於 Common Lisp 提供多種資料結構，需要用列表模擬其他資料結構的機會就少了。傳統 Lisp 學習資料會著重列表的使用，但過度著重列表，會讓初學者誤認為寫 Lisp 程式一定要做複雜的列表操作。

由於歷史因素，nil 也視為空列表。參考以下範例程式：

(assert (equal nil '()))

陣列 (Array)

陣列和列表都是線性的資料結構，但陣列的記憶體是連續的，所以在隨機存取上比列表有效率。此外，建立陣列時，可指定陣列元素的型態，在記憶體使用上會比較有效率。

Common Lisp 的一維陣列 (one-dimensional array) 又稱為 vector。這裡的 vector 並非數學上的向量，而是指一維陣列。除了 Common Lisp 外，有些語言也用 vector 來稱呼一維陣列，像是 C++。

除 vector 外，common Lisp 也支援多維陣列 (multidimensional array)，其最高維度委由 Common Lisp 實作品自行決定。Common Lisp 的維度限制儲存在變數 array-dimension-limit 中。

雜湊表 (Hash Table)

雜湊表是以鍵值對 (key-value pair) 儲存的非線性資料結構。其優點為快速存取值，不需逐一走訪資料結構。Lisp 的雜湊表可儲存任意物件。

套件 (Package)

Common Lisp 的套件並不是函式庫或物件庫，而是命名空間 (namespace) 的概念。套件的目的是避開命名空間的衝突 (name collision)。

在撰寫 Common Lisp 函式庫時，強烈建議設置套件名稱，讓該函式庫的函式使用獨立的命名空間，而不是讓一堆函式汙染函式庫使用者的命名空間。

Common Lisp 預設的套件有 :cl (Common Lisp) 和 :cl-user (Common Lisp User)。在撰寫程式時，若未指定套件，會自動使用 :cl。

檔案路徑 (Pathname)

由於不同系統的檔案路徑的表示法相異，Common Lisp 的檔案路徑提供和平台無關 (platform-independent) 的路徑物件。

資料串流 (Stream)

資料串流是處理輸出入 (input and output) 的物件。由於資料串流是抽象化的物件，程式設計者不需處理底層細節。

Readtable

Readtable 是儲存語法的物件。在預設情形下，會以 standard readtable 為準來解析 Lisp 命令稿。但 Common Lisp 允許使用 standard readtable 以外的 readtable。由於修改 readtable 會更動語法，平常不太會去動到 readtable。

隨機狀態 (Random State)

隨機狀態物件儲存亂數種子 (random seed)，搭配生成偽隨機亂數 (pseudo-random number) 的函式來生成亂數。

函式 (Function)

在 Common Lisp 中，函式可做為物件 (值) 來傳遞。程式語言支援函式物件是可使用函數式程式設計 (functional programming) 的先決條件。

以下的範例程式就有用到函數式程式的概念：

(assert (notevery #'evenp '(1 2 3 4 5)))

notevery 函式有兩個 (以上) 的參數，第一個參數是函式物件，第二個 (以上) 的參數是序列。本範例程式將 evenp 函式做為參數傳入。該程式的意思是列表 '(1 2 3 4 5) 的元素中，並非每個元素都是偶數。

函數式語言有 Lisp 和 ML 兩大類。兩者的差別在於前者為動態型態，後者為靜態型態。Lisp 家族語言中較著名的有 Common Lisp 和 Scheme，而 ML 家族語言中較著名的有 SML (standard ML) 和 OCaml。

結構體 (Structure)

Common Lisp 的結構體類似於 C 語言的結構體 (structure) 或 Pascal 的記錄 (record)，是使用者自訂型態。結構體可用來表達純量資料型態無法表達的概念，或是做為動態資料結構的基礎。

以下結構體用來表達平面的 (2-dimensional) 點：

(defstruct point
  "Point in 2-dimensional spance"
  (x 0.0 :type float)
  (y 0.0 :type float))

類別 (Class)

Common Lisp 的類別是另一種使用者自訂型態。如同結構體，類別可用來表達純量資料無法表達的概念。乍看之下，類別和結構體很相似，但類別支援更多的語法特性，像是多重派發 (multiple dispatch)、多重繼承 (multiple inheritance)、MOP (Meta Object Protocol) 等。

由於結構體的效能比類別好一些，程式設計者應視需求選擇最合適的特性。

承上節，我們將平面的點以類別改寫如下：

(defclass point ()
  ((x :initarg :x
      :initform 0.0
      :type float)
   (y :initarg :y
      :initform 0.0
      :type float))
  (:documentation
     "Point in 2-dimensional space"))

Condition

Condition 是 Common Lisp 用來處理例外 (exception) 的資料型態。例外是在程式因種種外部因素無法正確運行時，跳脫一般程式運行流程的語法機制。

和資料型態相關的指令

Common Lisp 支援數個和資料型態相關的指令。當程式設計者需要在程式中處理物件的資料型態時，這些指令就很方便。以下是一些常見的指令：

• typep：檢查是否符合特定型態
• check-type：檢查是否符合特定型態，不符合時引發錯誤
• subtypep：檢查是否符合特定子型態
• type-of：取得資料的型態
• deftype：定義新的資料型態

除此之外，許多型别都有 predicate (註) 來檢查型態。以下是一些例子：

(註) predicate 是檢查物件是否為真的函式。相當於「xx 是否為真？」。

• numberp：檢查物件是否為數字
• stringp：檢查物件是否為字串
• listp：檢查物件是否為列表 (或串列)
• arrayp：檢查物件是否為陣列
• hash-table-p：檢查物件是否為雜湊表

以下範例使用 deftype 指令建立自然數 (natural number) (註) 型態：

(註)：即非負整數。

(defun non-negative-p (n)
  (<= 0 n))

(deftype natural-number (&optional n)
  `(and (satisfies integerp)
        (satisfies non-negative-p)))

(defun main ()
  ; A floating-point number is not a natural number.
  (assert (equal nil (typep 1.0 'natural-number)))
  ; A negative integer is not a natural number.
  (assert (equal nil (typep -1 'natural-number)))
  ; Zero is a natural number.
  (assert (typep 0 'natural-number))
  ; A positive number is a natural number.
  (assert (typep 1 'natural-number))
  (quit))

(main)

在這個範例中，我們用數個資料來確認該範例所定義的型態可正確運作。這個範例程式用到巨集，目前我們還沒學到巨集，先大概看一下程式碼的寫法即可。

承上，在定義好 natural-number 型態後，就可以把該型態用在自己的程式中。像是以下求 Fibonacci 數列的函式：

(defun fib (n)
  (declare (natural-number n))
  (cond ((= 0 n) 0)
        ((= 1 n) 1)
        (t (+ (fib (- n 1)) (fib (- n 2))))))

在這個函式中，我們用 declare 指令確保參數 n 為自然數。

(選讀) declare 和 check-type 的差異

declare 指令和 check-type 指令都可用來檢查型態，但兩者在行為上有一些差異。

declare 實際的行為委由 Common Lisp 實作品自行決定。根據 Common Lisp 標準，Common Lisp 實作品可以忽略 declare 的結果。根據 optimize 的 safety 設置，Common Lisp 實作品有可能把 declare 當成斷言 (assertion) 來用，或是僅把 declare 做為增進編譯器效能的標註。declare 指令會在編譯期運作，影響程式的優化。

以下指令可以全域地調整 optimize 的行為：

(declaim (optimize (speed 0) (safety 3)))

相對來說，check-type 指令偵測到型態不符合時，會拋出錯誤物件，這個行為明確記載在 Common Lisp 的 API 文件中。所以，在偵測型態這項任務上，check-type 指令會比 declare 指令來得安全。但 check-type 指令是在執行期才進行檢查，多多少少會影響效能。

將前一節的 Fibonacci 函式用 check-type 改寫如下：

(defvar *safe-mode* nil "Validate data at runtime")

; Define `natural-number` here.

(defun fib (n)
  (when *safe-mode*
    (check-type n natural-number))
  (cond ((= 0 n) 0)
        ((= 1 n) 1)
        (t (+ (fib (- n 1)) (fib (- n 2))))))

在上述範例中，只有在旗標 *safe-mode* 為 t (真) 時，才檢查資料是否正確。我們可以把 *safe-mode* 做為套件的全域變數，用來影響函式的運行期行為。

這個討論串有更多的相關內容，有興趣的讀者可以看一下。