第 18 章 解構(gòu)

第 18 章 解構(gòu)

解構(gòu)(destructuring) 是賦值的一般形式。操作符?setq?和?setf?的賦值對(duì)象只是獨(dú)立的變量。而解構(gòu)把賦值和訪問(wèn)操作合二為一：在這里，我們不再只是把單個(gè)變量作為第一個(gè)參數(shù)，而是給出一個(gè)關(guān)于變量的模式，在這個(gè)模式中，賦給每個(gè)變量的值將來(lái)自某個(gè)結(jié)構(gòu)中對(duì)應(yīng)的位置。

18.1 列表上的解構(gòu)

從?CLTL2?開(kāi)始，Common Lisp 包括了一個(gè)名為 destructuring-bind 的新宏。這個(gè)宏在第 7 章里簡(jiǎn)單介紹過(guò)。這里將更仔細(xì)地了解它。假設(shè) lst 是一個(gè)三元素列表，而我們想要綁定?x?到第一個(gè)元素，y?到第二個(gè)，z?到第三個(gè)。在原始?CLTL1?的 Common Lisp 里，只能這樣表達(dá)：

(let ((x (first lst))
    (y (second lst))
    (z (third lst)))
  ...)

借助新宏我們只需說(shuō)：

(destructuring-bind (x y z) lst
    ...)

這樣處理，既短小，又清楚。讀者對(duì)于視覺(jué)形象的感受力比單純的文字要敏銳很多。使用后一種形式，x?，y?和?z?之間的關(guān)系可以一覽無(wú)余；而在前一種形式下，我們必須稍作思考才看得出來(lái)。

如果這樣簡(jiǎn)單的情形都能通過(guò)使用解構(gòu)而變得更清晰，試想一下它在更復(fù)雜情況下會(huì)帶來(lái)什么樣的改觀吧。destrucuring-bind?的第一個(gè)參數(shù)可以是任意復(fù)雜的一棵樹(shù)。想象

(destructuring-bind ((first last) (month day year) . notes)
  birthday
  ...)

如果用?let?和列表訪問(wèn)函數(shù)來(lái)寫(xiě)將會(huì)是什么樣子。這引出了另一個(gè)要點(diǎn)：解構(gòu)使得程序更容易寫(xiě)也更容易讀。

解構(gòu)在?CLTL1?的 Common Lisp 里確實(shí)也有過(guò)。如果上例中的模式看起來(lái)眼熟的話，那是因?yàn)樗鼈兒秃甑膮?shù)列表具有相同的形式。事實(shí)上，destructuring?就是就是用來(lái)處理宏參數(shù)列表的代碼，只不過(guò)現(xiàn)在拿出來(lái)單賣(mài)了。任何可以放進(jìn)宏參數(shù)列表里的東西，你都可以把它置于這個(gè)匹配模式中，不過(guò)有個(gè)無(wú)關(guān)緊要的例外(那個(gè)?&environment?關(guān)鍵字)。

建立各種綁定總的來(lái)說(shuō)是一個(gè)很有吸引力的想法。接下來(lái)的幾個(gè)小節(jié)會(huì)介紹這個(gè)主題的幾個(gè)變化。

18.2 其他結(jié)構(gòu)

沒(méi)有理由把解構(gòu)僅限于列表。解構(gòu)同樣適用于各種復(fù)雜對(duì)象。本節(jié)展示如何編寫(xiě)用于其他類型對(duì)象的類似 destructuring-bind 的宏。

下一步，自然是去處理一般性的序列。[示例代碼 18.1] 中定義了一個(gè)名為?dbind?的宏，它和destrucuring-bind?類似，不過(guò)可以用在任何種類的序列上。第二個(gè)參數(shù)可以是列表，向量或者它們的任意組合：

[示例代碼 18.1]：通用序列解構(gòu)操作符

(defmacro dbind (pat seq &body body)
  (let ((gseq (gensym)))
    '(let ((,gseq ,seq))
      ,(dbind-ex (destruc pat gseq #'atom) body))))

(defun destruc (pat seq &optional (atom? #'atom) (n 0))
  (if (null pat)
    nil
    (let ((rest (cond ((funcall atom? pat) pat)
            ((eq (car pat) '&rest) (cadr pat))
            ((eq (car pat) '&body) (cadr pat))
            (t nil))))
      (if rest
        '((,rest (subseq ,seq ,n)))
        (let ((p (car pat))
            (rec (destruc (cdr pat) seq atom? (1+ n))))
          (if (funcall atom? p)
            (cons '(,p (elt ,seq ,n))
              rec)
            (let ((var (gensym)))
              (cons (cons '(,var (elt ,seq ,n))
                  (destruc p var atom?))
                rec))))))))

(defun dbind-ex (binds body)
  (if (null binds)
    '(progn ,@body)
    '(let ,(mapcar #'(lambda (b)
          (if (consp (car b))
            (car b)
            b))
        binds)
      ,(dbind-ex (mapcan #'(lambda (b)
            (if (consp (car b))
              (cdr b)))
          binds)
        body))))

> (dbind (a b c) #(1 2 3)
  (list a b c))
(1 2 3)
> (dbind (a (b c) d) '(1 #(2 3) 4)
  (list a b c d))
(1 2 3 4)
> (dbind (a (b . c) &rest d) '(1 "fribble" 2 3 4)
  (list a b c d))
(1 #\f "ribble" (2 3 4))

#(?讀取宏用于表示向量，而?#\?則用于表示字符。由于?"abc" = #(#\a #\b #\c)，所以 "fribble" 的第一個(gè)元素是字符?#f?。為了簡(jiǎn)單起見(jiàn)，dbind?只支持?&rest?和?&body?關(guān)鍵字。

和迄今為止見(jiàn)過(guò)的大多數(shù)宏相比，dbind?儼然是個(gè)龐然大物。這個(gè)宏的實(shí)現(xiàn)之所以值得好好研究一番，原因不僅僅是為了理解它的工作方式，更是為了它能給我們上一課，課的內(nèi)容對(duì)于 Lisp 編程是通用的。正如第 3.4 節(jié)提到的，我們?cè)诰帉?xiě) Lisp 程序時(shí)，可以有意識(shí)地讓它們更易于測(cè)試。在多數(shù)代碼里，我們必須要權(quán)衡這一訴求和代碼速度上的需求。幸運(yùn)的是，如第 7.8 節(jié)所述，速度對(duì)于展開(kāi)器代碼來(lái)說(shuō)不是那么要緊。當(dāng)編寫(xiě)用來(lái)生成宏展開(kāi)式的代碼時(shí)，我們可以讓自己放輕松一些。dbind的展開(kāi)式由兩個(gè)函數(shù)生成，destruc?和?dbind-ex?。也許它們兩個(gè)可以被合并成一個(gè)函數(shù)，一步到位。但是何苦呢？作為兩個(gè)獨(dú)立的函數(shù)，它們將更容易測(cè)試。為什么要犧牲這個(gè)優(yōu)勢(shì)，換來(lái)我們并不需要的速度呢？

第一個(gè)函數(shù)是?destruc?，它遍歷匹配模式，將每個(gè)變量和運(yùn)行期對(duì)應(yīng)對(duì)象的位置關(guān)聯(lián)在一起：

(destruc '(a b c) 'seq #'atom) ((A (ELT SEQ 0)) (B (ELT SEQ 1)) (C (ELT SEQ 2)))

可選的第三個(gè)參數(shù)是個(gè)謂詞，它用來(lái)把模式的結(jié)構(gòu)和模式的內(nèi)容區(qū)分開(kāi)。

為了使訪問(wèn)更有效率，一個(gè)新的變量(生成符號(hào)) 將被綁定到每個(gè)子序列上：

> (destruc '(a (b . c) &rest d) 'seq)
((A (ELT SEQ 0))
  ((#:G2 (ELT SEQ 1)) (B (ELT #:G2 0)) (C (SUBSEQ #:G2 1)))
  (D (SUBSEQ SEQ 2)))

destruc?的輸出被發(fā)送給?dbind-ex?，后者被用來(lái)生成宏展開(kāi)代碼。它將?destruc?產(chǎn)生的樹(shù)轉(zhuǎn)化成一系列嵌套的?let?：

> (dbind-ex (destruc '(a (b . c) &rest d) 'seq) '(body))
(LET ((A (ELT SEQ 0))
    (#:G4 (ELT SEQ 1))
    (D (SUBSEQ SEQ 2)))
  (LET ((B (ELT #:G4 0))
      (C (SUBSEQ #:G4 1)))
    (PROGN BODY)))

注意到?dbind?，和?destructuring-bind?一樣，假設(shè)它將發(fā)現(xiàn)所有它尋找的列表結(jié)構(gòu)。最后剩下的變量并不是簡(jiǎn)單地綁定到nil ，就像?multiple-value-bind?那樣。如果運(yùn)行期給出的序列里沒(méi)有包含所有期待的元素，解構(gòu)操作符將產(chǎn)生一個(gè)錯(cuò)誤：

> (dbind (a b c) (list 1 2))
>>Error: 2 is not a valid index for the sequence (1 2)

其他有內(nèi)部結(jié)構(gòu)的對(duì)象該怎么處理呢？通常還有數(shù)組，它和向量的區(qū)別在于其維數(shù)可以大于一。如果我們?yōu)閿?shù)組定義解構(gòu)宏，我們?cè)鯓颖磉_(dá)匹配模式呢？對(duì)于兩維數(shù)組，用列表還是比較實(shí)際的。[示例代碼 18.2] 含有一個(gè)宏【注1】，with-matrix?，用于解構(gòu)兩維數(shù)組。

> (setq ar (make-array '(3 3)))
#<Simple-Array T (3 3) C2D39E>
> (for (r 0 2)
  (for (c 0 2)
    (setf (aref ar r c) (+ (* r 10) c))))
NIL
> (with-matrix ((a b c)
    (d e f)
    (g h i)) ar
  (list a b c d e f g h i))
(0 1 2 10 11 12 20 21 22)

對(duì)于大型數(shù)組，或者維數(shù)是3 或更高的數(shù)組來(lái)說(shuō)，我們就需要另辟奚徑。我們不大可能把一個(gè)大數(shù)組里的每一個(gè)元素都綁定到變量上。將匹配模式做成數(shù)組的稀疏表達(dá)將會(huì)更實(shí)際一些 只包含用于少數(shù)元素的變量，加上用來(lái)標(biāo)識(shí)它們的坐標(biāo)。[示例代碼 18.2] 中的第二個(gè)宏就采用了這個(gè)思路。這里我們用它來(lái)得到前一個(gè)數(shù)組在對(duì)角線上的元素：

;; [示例代碼 18.2]：數(shù)組上的解構(gòu)
(defmacro with-matrix (pats ar &body body)
  (let ((gar (gensym)))
    '(let ((,gar ,ar))
      (let ,(let ((row -1))
          (mapcan
            #'(lambda (pat)
              (incf row)
              (let ((col -1))
                (mapcar #'(lambda (p)
                    '(,p (aref ,gar
                        ,row
                        ,(incf col))))
                  pat)))
            pats))
        ,@body))))

(defmacro with-array (pat ar &body body)
  (let ((gar (gensym)))
    '(let ((,gar ,ar))
      (let ,(mapcar #'(lambda (p)
            '(,(car p) (aref ,gar ,@(cdr p))))
          pat)
        ,@body))))

> (with-array ((a 0 0) (d 1 1) (i 2 2)) ar
  (values a d i))
0
11
22

[示例代碼 18.3]：結(jié)構(gòu)體上的解構(gòu)

(defmacro with-struct ((name . fields) struct &body body)
  (let ((gs (gensym)))
    '(let ((,gs ,struct))
      (let ,(mapcar #'(lambda (f)
            '(,f (,(symb name f) ,gs)))
          fields)
        ,@body))))

通過(guò)這個(gè)新宏，我們開(kāi)始逐漸跳出那些認(rèn)為元素必須以固定順序出現(xiàn)的思維模式。我們可以做出一個(gè)類似形式的宏，用它來(lái)綁定變量到?defstruct?所建立的結(jié)構(gòu)體字段上。[示例代碼 18.3] 中就這樣定義一個(gè)宏。模式中的第一個(gè)參數(shù)被接受為與結(jié)構(gòu)體相關(guān)聯(lián)的前綴，其余的都是字段名。為了建立訪問(wèn)調(diào)用，這個(gè)宏使用了?symb?(第 4.7 節(jié))。

> (defstruct visitor name title firm)
VISITOR
> (setq theo (make-visitor :name "Theodebert"
    :title 'king
    :firm 'franks))
#S(VISITOR NAME "Theodebert" TITLE KING FIRM FRANKS)
> (with-struct (visitor- name firm title) theo
  (list name firm title))
("Theodebert" FRANKS KING)

18.3 引用

CLTL?自帶了一個(gè)用于解構(gòu)實(shí)例的宏。假設(shè)?tree?是一個(gè)帶有三個(gè)?slot?的類：species、age?和height?，而?my-tree?是一 個(gè)?tree?的實(shí)例。在

(with-slots (species age height) my-tree
  ...)

的里面我們可以像常規(guī)變量那樣引用?my-tree?的這些?slot。在?with-slots?的主體中，符號(hào)height?指向?height slot。height?并不是簡(jiǎn)單地綁定到了對(duì)應(yīng)?slot?里的變量，而是直接引用到那個(gè)?slot?上。所以，如果我們寫(xiě)：

(setq height 72)

那么也將給?my-tree?的?height?這個(gè)?slot?一個(gè)?72?的值。這個(gè)宏的工作原理是將?height?定義為一個(gè)展開(kāi)到?slot?引用的符號(hào)宏(第 7.11 節(jié))。事實(shí)上，symbol-macrolet?就是為了支持像?with-slots?這樣的宏才被加入到 Common Lisp 中的。

無(wú)論?with-slots?事實(shí)上是不是一個(gè)解構(gòu)宏，它在實(shí)際編程中所起的作用和d estructuring-bind 是一樣的。雖然通常的解構(gòu)都是按值調(diào)用(call-by-value)，這種新型解構(gòu)卻是按名調(diào)用(call-by-name)。無(wú)論我們?nèi)绾握{(diào)用它，它對(duì)我們都是有用的。還有其他什么宏，我們可以依法炮制呢？

[示例代碼 18.4] 序列上的引用解構(gòu)

(defmacro with-places (pat seq &body body)
  (let ((gseq (gensym)))
    '(let ((,gseq ,seq))
      ,(wplac-ex (destruc pat gseq #'atom) body))))

(defun wplac-ex (binds body)
  (if (null binds)
    '(progn ,@body)
    '(symbol-macrolet ,(mapcar #'(lambda (b)
          (if (consp (car b))
            (car b)
            b))
        binds)
      ,(wplac-ex (mapcan #'(lambda (b)
            (if (consp (car b))
              (cdr b)))
          binds)
        body))))

我們可以這樣做：將解構(gòu)宏展開(kāi)成?symbol-macrolet?而不是?let?，這樣，就可以為任何解構(gòu)宏創(chuàng)建出與之對(duì)應(yīng)的按名調(diào)用版本。[示例代碼 18.4] 給出了一個(gè)被修改成與?with-slots?行為類似的dbind?版本。我們可以像使用 dbind 一樣來(lái)使用?with-places?：

> (with-places (a b c) #(1 2 3)
  (list a b c))
(1 2 3)

但這個(gè)新宏還給我們?setf?序列位置的選項(xiàng)，就像我們?cè)?with-slots?里所做的那樣：

> (let ((lst '(1 (2 3) 4)))
  (with-places (a (b . c) d) lst
    (setf a 'uno)
    (setf c '(tre)))
  lst)
(UNO (2 TRE) 4)

就像在?with-slots?里那樣，這些變量現(xiàn)在都指向了序列中的對(duì)應(yīng)位置。盡管如此，這里還有一個(gè)重要的區(qū)別：你必須使用?setf?而不是?setq?來(lái)設(shè)置這些偽變量。with-slots?宏必須引入一個(gè)code-walker(第 20.3 節(jié)) 來(lái)將其體內(nèi)的?setq?轉(zhuǎn)化成?setf。這里，寫(xiě)一個(gè)?code-walker?將需要寫(xiě)很多代碼，但是帶來(lái)的好處卻不大。

如果?with-places?比?dbind?更通用，為什么不干脆只用它呢？dbind?將一個(gè)變量關(guān)聯(lián)一個(gè)值上，而?with-places?卻是將變量關(guān)聯(lián)到一組用來(lái)找到一個(gè)值的指令集合上。每一個(gè)引用都需要進(jìn)行一次查詢。

當(dāng)?dbind?把?c?綁定到?(elt x 2)?的值上時(shí)，with-places?將使?c?成為一個(gè)展開(kāi)成?(elt x 2)的符號(hào)宏。

所以如果c 在宏體中被求值了 次，那將會(huì)產(chǎn)生 次對(duì)elt 的調(diào)用。除非你真的想要 setf 那些由解構(gòu)創(chuàng)建的變量，否則dbind 將會(huì)更快一些。

with-places?的定義和?dbind?([示例代碼 18.1]) 相比僅有輕微的變化。在?wplac-ex?(之前的dbind-ex) 中那些?let?變成了?symbol-macrolet?。通過(guò)類似的改動(dòng)，我們也可以為任何正常的解構(gòu)宏做出一個(gè)按名調(diào)用的版本。

18.4 匹配

正如解構(gòu)是賦值的泛化，模式匹配是解構(gòu)的泛化。"模式匹配" 這個(gè)術(shù)語(yǔ)有許多含義。在這里的語(yǔ)境中，它指的是這樣的操作：比較兩個(gè)結(jié)構(gòu)，結(jié)構(gòu)中可能含有變量，判斷是否存在某種給變量賦值的方式使得它們倆相等。例如，如果??x?和??y?是變量，那么這兩個(gè)列表

(p ?x ?y c ?x)
(p a b c a)

當(dāng)??x = a?并且??y = b?時(shí)匹配。而列表

(p ?x b ?y a)
(p ?y b c a)

當(dāng)??x = ?y = c?時(shí)匹配。

假設(shè)一個(gè)程序通過(guò)跟外部數(shù)據(jù)源交換信息的方式工作。為了回復(fù)一個(gè)消息，程序必須首先知道消息的類型，并且還要取出它的特定內(nèi)容。通過(guò)一個(gè)匹配操作符我們可以將這兩步并成一步。

要寫(xiě)出這種操作符，必須先想出一種區(qū)分變量的辦法。我們不能直接把所有符號(hào)都當(dāng)成變量，因?yàn)樾枰尫?hào)在模式中以參數(shù)的形式出現(xiàn)。這里我們規(guī)定：模式變量是以問(wèn)號(hào)開(kāi)始的符號(hào)。如果將來(lái)覺(jué)得不方便了，只要重定義謂詞var? 就可以改變這個(gè)約定。

[示例代碼 18.5] 包含一個(gè)模式匹配的函數(shù)，它跟一些 Lisp 入門(mén)讀物里的匹配函數(shù)樣子差不多。我們傳給?match?兩個(gè)列表，如果它們可以匹配，將得到另一個(gè)列表，該列表會(huì)顯示它們是如何匹配的：

> (match '(p a b c a) '(p ?x ?y c ?x))
((?Y . B) (?X . A))
T
> (match '(p ?x b ?y a) '(p ?y b c a))
((?Y . C) (?X . ?Y))
T
> (match '(a b c) '(a a a))
NIL
NIL

在?match?逐個(gè)元素地比較它的參數(shù)時(shí)，它建立起來(lái)了一系列值和變量之間的賦值關(guān)系，這種關(guān)系被稱為綁定。這些變量是由參數(shù)?binds?給出的。若匹配成功，match?返回其生成的綁定，否則返回nil?。由于并非所有成功的匹配都能生成綁定，所以和 gethash 一樣，match?用第二個(gè)返回值來(lái)表示匹配成功與否：

> (match '(p ?x) '(p ?x))
NIL
T

[示例代碼 18.5] 匹配函數(shù)

(defun match (x y &optional binds)
  (acond2
    ((or (eql x y) (eql x '_) (eql y '_)) (values binds t))
    ((binding x binds) (match it y binds))
    ((binding y binds) (match x it binds))
    ((varsym? x) (values (cons (cons x y) binds) t))
    ((varsym? y) (values (cons (cons y x) binds) t))
    ((and (consp x) (consp y) (match (car x) (car y) binds))
      (match (cdr x) (cdr y) it))
    (t (values nil nil))))

(defun varsym? (x)
  (and (symbolp x) (eq (char (symbol-name x) 0) #\?)))

(defun binding (x binds)
  (labels ((recbind (x binds)
        (aif (assoc x binds)
          (or (recbind (cdr it) binds)
            it))))
    (let ((b (recbind x binds)))
      (values (cdr b) b))))

當(dāng)?match?像上面那樣返回?nil?和?t?時(shí)，它表示一個(gè)沒(méi)有產(chǎn)生任何綁定的成功的匹配。

和?Prolog?一樣，match?也把?_?(下劃線) 用作通配符。它可以匹配任何東西，并且對(duì)綁定沒(méi)有任何影響：

[示例代碼 18.6]：慢的匹配操作符

> (match '(a ?x b) '(_ 1 _))
((?X . 1))
T

(defmacro if-match (pat seq then &optional else)
  '(aif2 (match ',pat ,seq)
    (let ,(mapcar #'(lambda (v)
          '(,v (binding ',v it)))
        (vars-in then #'atom))
      ,then)
    ,else))

(defun vars-in (expr &optional (atom? #'atom))
  (if (funcall atom? expr)
    (if (var? expr) (list expr))
    (union (vars-in (car expr) atom?)
      (vars-in (cdr expr) atom?))))

(defun var? (x)
  (and (symbolp x) (eq (char (symbol-name x) 0) #\?)))

有了?match?，可以很容易地寫(xiě)出一個(gè)模式匹配版本的?dbind?。[示例代碼 18.6] 中含有一個(gè)稱為if-match?的宏。

像?dbind?那樣，它的前兩個(gè)參數(shù)是一個(gè)模式和一個(gè)序列，然后它通過(guò)比較模式跟序列來(lái)建立綁定。不過(guò)，它用另外兩個(gè)參數(shù)取代了代碼主體：一個(gè)?then?子句，在新綁定下被求值，如果匹配成功的話；以及一個(gè)?else?子句在匹配失敗時(shí)被求值。這里有一個(gè)簡(jiǎn)單的使用?if-match?的函數(shù)：

(defun abab (seq)
  (if-match (?x ?y ?x ?y) seq
    (values ?x ?y)
    nil))

如果匹配成功了，它將建立??x?和??y?的值，然后返回它們：

> (abab '(hi ho hi ho)
  HI
  HO

函數(shù)?vars-in?返回一個(gè)表達(dá)式中的所有匹配變量。它調(diào)用?var??來(lái)測(cè)試是否某個(gè)東西是一個(gè)變量。目前，var??和用來(lái)檢測(cè)綁定列表中變量的?varsym??([示例代碼 18.5]) 是相同的，之所以使用獨(dú)立的兩個(gè)函數(shù)是考慮到我們可能想要給這兩類變量采用不同的表示方法。

像在 [示例代碼 18.6] 里定義的那樣，if-match?很短，但并不是非常高效。它在運(yùn)行期做的事情太多了。我們?cè)谶\(yùn)行期把兩個(gè)序列都遍歷了，盡管第一個(gè)序列在編譯期就是已知的。更糟糕的是，在進(jìn)行匹配的過(guò)程中，我們構(gòu)造列表來(lái)存放變量綁定。如果充分利用編譯期已知的信息，就能寫(xiě)出一個(gè)既不做任何不必要的比較，也不做任何?cons?的?if-match?版本來(lái)。

如果其中一個(gè)序列在編譯期已知，并且只有這個(gè)序列里含有變量，那么就要另做打算了。在一次對(duì) match 的調(diào)用中，兩個(gè)參數(shù)都可能含有變量。通過(guò)將變量限制在 if-match 的第一個(gè)參數(shù)上，就有可能在編譯期知道哪些變量將會(huì)參與匹配。這里，我們不再創(chuàng)建變量綁定的列表，而是將變量的值保存進(jìn)這些變量本身。

[示例代碼 18.7] 快速匹配操作符

(defmacro if-match (pat seq then &optional else)
  '(let ,(mapcar #'(lambda (v) '(,v ',(gensym)))
      (vars-in pat #'simple?))
    (pat-match ,pat ,seq ,then ,else)))

(defmacro pat-match (pat seq then else)
  (if (simple? pat)
    (match1 '((,pat ,seq)) then else)
    (with-gensyms (gseq gelse)
      '(labels ((,gelse () ,else))
        ,(gen-match (cons (list gseq seq)
            (destruc pat gseq #'simple?))
          then
          '(,gelse))))))

(defun simple? (x) (or (atom x) (eq (car x) 'quote)))

(defun gen-match (refs then else)
  (if (null refs)
    then
    (let ((then (gen-match (cdr refs) then else)))
      (if (simple? (caar refs))
        (match1 refs then else)
        (gen-match (car refs) then else)))))

在 [示例代碼 18.7] 和 18.8 中是?if-match?的新版本。如果能預(yù)見(jiàn)到哪部分代碼會(huì)在運(yùn)行期求值，我們不妨就直接在編譯期生成它。這里，我們生成的代碼僅僅完成需要的那些比較操作，而不是展開(kāi)成對(duì)?match?的調(diào)用。

如果我們打算使用變量??x?來(lái)包含??x?的綁定的話，怎樣表達(dá)一個(gè)尚未被匹配過(guò)程建立綁定的變量呢？這里，我們將通過(guò)將一個(gè)模式變量綁定到一個(gè)生成符號(hào)以表明其未綁定。所以?if-match?一開(kāi)始會(huì)生成代碼將所有模式中的變量綁定到生成符號(hào)上。在這種情況下，代替了展開(kāi)成一個(gè)?with-gensyms?，在編譯期做一次符號(hào)生成，然后將它們直接插入進(jìn)展開(kāi)式是安全的。

[示例代碼 18.8] 快速匹配操作符(續(xù))

(defun match1 (refs then else)
  (dbind ((pat expr) . rest) refs
    (cond ((gensym? pat)
        '(let ((,pat ,expr))
          (if (and (typep ,pat 'sequence)
              ,(length-test pat rest))
            ,then
            ,else)))
      ((eq pat '_) then)
      ((var? pat)
        (let ((ge (gensym)))
          '(let ((,ge ,expr))
            (if (or (gensym? ,pat) (equal ,pat ,ge))
              (let ((,pat ,ge)) ,then)
              ,else))))
      (t '(if (equal ,pat ,expr) ,then ,else)))))

(defun gensym? (s)
  (and (symbolp s) (not (symbol-package s))))

(defun length-test (pat rest)
  (let ((fin (caadar (last rest))))
    (if (or (consp fin) (eq fin 'elt))
      '(= (length ,pat) ,(length rest))
      '(> (length ,pat) ,(- (length rest) 2)))))

其余的展開(kāi)由?pat-match?完成。這個(gè)宏接受和?if-match?相同的參數(shù)；唯一的區(qū)別是它不為模式變量建立任何新綁定。在某些情況下這是一個(gè)優(yōu)點(diǎn)，第 19 章將把?pat-match?作為一個(gè)獨(dú)立的操作符來(lái)使用。

在新的匹配操作符里，模式內(nèi)容和模式結(jié)構(gòu)之間的差別將用函數(shù)?simple??定義。如果我們想要在模式里使用字面引用，那么解構(gòu)代碼(以及?vars-in) 必須被告知不要進(jìn)入那些第一個(gè)元素是?quote?的列表。在新的匹配操作符下，我們將可以使用列表作為模式元素，只需簡(jiǎn)單地將它們引用起來(lái)。

與?dbind?相似，pat-match?調(diào)用?destruc?來(lái)得到一個(gè)將要在運(yùn)行期參與其參數(shù)調(diào)用的列表。這個(gè)列表被傳給?gen-match?來(lái)為嵌套的模式遞歸生成匹配代碼，然后再傳給?match1?，以生成模式樹(shù)上每個(gè)葉子的匹配代碼。

最后出現(xiàn)在一個(gè)?if-match?展開(kāi)式中的多數(shù)代碼都來(lái)自?match1?，如 [示例代碼 18.8], 這個(gè)函數(shù)分四種情況處理。如果模式參數(shù)是一個(gè)生成符號(hào)，那么它是一個(gè)由?destruc?創(chuàng)建用于保存子列表的不可見(jiàn)變量，并且所有我們需要在運(yùn)行期做的就是測(cè)試它是否具有正確的長(zhǎng)度。如果模式元素是一個(gè)通配符 (_)，那么不需要生成任何代碼。如果模式元素是一個(gè)變量，那么?match1?會(huì)生成代碼去匹配，或者將其設(shè)置成，運(yùn)行期給出的序列的對(duì)應(yīng)部分。否則，模式元素被看作一個(gè)字面上的值，而 match1 會(huì)生成代碼去比較它和序列中的對(duì)應(yīng)部分。

讓我們通過(guò)例子來(lái)了解一下展開(kāi)式中的某些部分的生成過(guò)程。假設(shè)我們從下面的表達(dá)式開(kāi)始

(if-match (?x 'a) seq
  (print ?x)
  nil)

這個(gè)模式將被傳給?destruc?，同時(shí)帶著一些生成符號(hào)(不妨簡(jiǎn)稱為?g?) 來(lái)代表那個(gè)序列：

(destruc '(?x 'a) 'g #'simple?)

得到：

((?x (elt g 0)) ((quote a) (elt g 1)))

在這個(gè)列表的開(kāi)頭我們接上?(g seq)：

((g seq) (?x (elt g 0)) ((quote a) (elt g 1)))

然后把結(jié)果整個(gè)地發(fā)給?gen-match?。就像?length?(第 2.8 節(jié)) 的原生實(shí)現(xiàn)那樣，gen-match?首先一路遞歸到列表的結(jié)尾，然后在回來(lái)的路上構(gòu)造其返回值。當(dāng)gen-match 走完所有元素時(shí)，它就返回其?then?參數(shù)，也就是?(print ?x)【注2】。在遞歸回來(lái)的路上，這個(gè)返回值將作為?then?參數(shù)傳給?match1??，F(xiàn)在我們將得到一個(gè)像這樣的調(diào)用：

(match1 '(((quote a) (elt g 1))) '(print ?x) '<else function>)

得到：

(if (equal (quote a) (elt g 1))
  (print ?x)

<else function>)

然后這些將成為另一個(gè)?match1?調(diào)用的?then?參數(shù)，得到的值將成為最后的?match1?調(diào)用的?then參數(shù)。這個(gè)?if-match?的完整展開(kāi)式顯示在[示例代碼 18.9] 【注3】中。

[示例代碼 18.9] 一個(gè)?if-match?的展開(kāi)式

(if-match (?x 'a) seq
  (print ?x))

展開(kāi)成：

(let ((?x '#:g1))
  (labels ((#:g3 nil nil))
    (let ((#:g2 seq))
      (if (and (typep #:g2 'sequence)
          (= (length #:g2) 2))
        (let ((#:g5 (elt #:g2 0)))
          (if (or (gensym? ?x) (equal ?x #:g5))
            (let ((?x #:g5))
              (if (equal 'a (elt #:g2 1))
                (print ?x)
                (#:g3)))
            (#:g3)))
        (#:g3)))))

在這個(gè)展開(kāi)式里有兩個(gè)地方用到了?gensym?(生成符號(hào))，這兩個(gè)地方的用意各不相同。在運(yùn)行時(shí)，一些變量被用來(lái)保存樹(shù)的一部分，這些變量的名字是用?gensym?生成的，目的是為了避免捕捉。而變量?x?在開(kāi)始的? 時(shí)候被綁定到了一個(gè)?gensym，以表明它尚未被匹配操作賦給一個(gè)值。

在新的?if-match?中，模式元素現(xiàn)在是被求值而不再是被隱式引用了。這意味著 Lisp 變量可以被用于模式中，和被引用的表達(dá)式一樣：

> (let ((n 3))
  (if-match (?x n 'n '(a b)) '(1 3 n (a b))
    ?x))
1

還有兩個(gè)進(jìn)一步的改進(jìn)，是因?yàn)樾掳姹菊{(diào)用了?destruc?([示例代碼 18.1]) 而出現(xiàn)?，F(xiàn)在模式中可以包含?&rest?或者?&body?關(guān)鍵字(match?是不管這一套的)。并且因?yàn)?destruc?使用了一般的序列操作符?elt?和?subseq?，

新的?if-match?將工作在任何類型的序列上。如果?abab?采用新版本來(lái)定義，它也可以被用于向量和字符串：

> (abab "abab")
#\a
#\b
> (abab #(1 2 1 2))
1
2

事實(shí)上，模式可以像 dbind 的模式那樣復(fù)雜：

> (if-match (?x (1 . ?y) . ?x) '((a b) #(1 2 3) a b)
  (values ?x ?y))
(A B)
#(2 3)

注意到，在第二個(gè)返回值里，向量的元素被顯示出來(lái)了。要想使向量以這種方式被輸出，需要將\*print-array\*?設(shè)置為?t?。

在本章，我們開(kāi)始逐步走進(jìn)一個(gè)嶄新的編程領(lǐng)域。以一個(gè)簡(jiǎn)單的用于解構(gòu)的宏作開(kāi)端。在?if-match的最終版本中，我們有了某種看起來(lái)更像是它自己的語(yǔ)言的東西。接下來(lái)的章節(jié)將要介紹一整類程序，它們秉承的都是相同的理念。

備注:

【注1】譯者注：這里稍微修改了一下原書(shū)的代碼，原書(shū)中沒(méi)有定義?col?變量就直接使用了?(setq col -1)，這里仿照?row?的處理方法用?let?建立了一個(gè)?col?的局部綁定。

【注2】譯者注：原文中說(shuō)返回的?then?參數(shù)是??x?，這應(yīng)該是個(gè)筆誤。

【注3】譯者注：原書(shū)里有一個(gè)筆誤，展開(kāi)式代碼中的?(gensym? x)?應(yīng)為?(gensym? ?x)。