第 15 章返回函數的宏 · On Lisp 中文版

## 第 15 章返回函數的宏第五章已經介紹了如何編寫返回函數的函數。宏的應用使得組合操作符這項工作的難度大幅降低。本章將說明如何用宏來構造抽象結構，這些結構和第 5 章里定義的那些抽象是等價的，但是用宏會更清晰和高效。 ### 15.1 函數的構造若?`f`?和?`g`?均為函數，則?`f ○g(x) = f(g(x))`。第 5.4 節曾介紹過把?`○`?實現為 Lisp 函數的方法，這個函數名叫?`compose`： * * * **[示例代碼 15.1] 通用的用于構造函數的宏** ~~~ > (funcall (compose #'list #'1+) 2) (3) (defmacro fn (expr) '#',(rbuild expr)) (defun rbuild (expr) (if (or (atom expr) (eq (car expr) 'lambda)) expr (if (eq (car expr) 'compose) (build-compose (cdr expr)) (build-call (car expr) (cdr expr))))) (defun build-call (op fns) (let ((g (gensym))) '(lambda (,g) (,op ,@(mapcar #'(lambda (f) '(,(rbuild f) ,g)) fns))))) (defun build-compose (fns) (let ((g (gensym))) '(lambda (,g) ,(labels ((rec (fns) (if fns '(,(rbuild (car fns)) ,(rec (cdr fns))) g))) (rec fns))))) ~~~ * * * 在本節中，我們將思考如何用宏來定義更好的函數構造器。[示例代碼 15.1] 中是一個名為?`fn`?的通用函數構造器，它能夠根據復合函數的描述來構造它們。它的參數應該是一個形如`(operator . arguments)`?的表達式。 `operator`?可以是一個函數或宏的名字，也可以是會被區別對待的?`compose .Arguments`?可以是接受一個參數的函數或宏的名字，或者是可作為?`fn`?參數的表達式。例如， ~~~ (fn (and integerp oddp)) ~~~ 產生一個等價于: ~~~ #'(lambda (x) (and (integerp x) (oddp x))) ~~~ 的函數。如果把?`compose`?用作操作符(operator)，我們就得到一個所有參數復合后得到的函數，但不需要像 compose 被定義為函數時那樣的顯式?`funcall`?調用。例如， ~~~ (fn (compose list 1+ truncate)) ~~~ 展開成： ~~~ #'(lambda (#:g1) (list (1+ (truncate #:g1)))) ~~~ 后者允許對?`list`?和?`1+`?這種簡單函數進行內聯編譯。`fn`?宏接受一般意義上的操作符名稱；`-`?表達式也是允許的，就像: ~~~ (fn (compose (lambda (x) (+ x 3)) truncate)) ~~~ 可以展開成: ~~~ #'(lambda (#:g2) ((lambda (x) (+ x 3)) (truncate #:g2))) ~~~ 毫無疑問，這里由`λ`–表達式表示的函數會被內聯編譯，要是換成用?`sharp-quoted`?的`λ`–表達式作為參數，傳給?`compose`?，那就只得通過?`funcall`?調用了。第 5.4 節還展示了另外三個函數構造器的定義：`fif`?，`fint`?，以及?`fun`。這些函數現在被統一到了通用的?`fn`?宏。使用?`and`?操作符將產生一個參數操作符的交集： ~~~ > (mapcar (fn (and integerp oddp)) '(c 3 p 0)) (NIL T NIL NIL) ~~~ 而?`or`?操作符則產生并集： ~~~ > (mapcar (fn (or integerp symbolp)) '(c 3 p 0.2)) (T T T NIL) ~~~ 并且?`if`?產生的函數，其函數體是條件執行的： ~~~ > (map1-n (fn (if oddp 1+ identity)) 6) (2 2 4 4 6 6) ~~~ 不過，我們可用的函數不僅僅限于上面三個： ~~~ > (mapcar (fn (list 1- identity 1+)) '(1 2 3)) ((0 1 2) (1 2 3) (2 3 4)) ~~~ 并且?`fn`?表達式里的參數本身也可以是表達式： ~~~ > (remove-if (fn (or (and integerp oddp) (and consp cdr))) '(1 (a b) c (d) 2 3.4 (e f g))) (C (D) 2 3.4) ~~~ 這里雖然?`fn`?把?`compose`?作為一種特殊情況單獨處理，但是這樣做并沒有增加這個宏的功能。如果你把嵌套的參數傳給?`fn`?，那就可以得到函數的復合。例如， ~~~ (fn (list (1+ truncate))) ~~~ 展開成： ~~~ #'(lambda (#:g1) (list ((lambda (#:g2) (1+ (truncate #:g2))) #:g1))) ~~~ 這相當于： ~~~ (compose #'list #'1+ #'truncate) ~~~ `fn`?宏把?`compose`?單獨處理的目的，只是為了提高這種調用的可讀性。 ### 15.2 在?`cdr`?上做遞歸第 5.5 和 5.6 節顯示了如何編寫構造遞歸函數的函數。接下來兩節將介紹指代宏是如何給我們在那里定義的函數提供一個更清晰的接口的。第 5.5 節顯示了如何定義一個稱為?`lrec`?的扁平列表遞歸器。通過?`lrec`?，我們可以將下面這個函數： ~~~ (defun our-every (fn lst) (if (null lst) t (and (funcall fn (car lst)) (our-every fn (cdr lst))))) ~~~ 而把 oddp 的調用表示成： ~~~ (lrec #'(lambda (x f) (and (oddp x) (funcall f))) t) ~~~ 在這里，宏可以讓我們事半功倍。為了表達一個遞歸函數，最起碼應該說清楚哪幾件事情呢？如果用 it 來指代當前列表的 car，并用 rec 指代遞歸調用，那么我們就可以把它表示成： ~~~ (alrec (and (oddp it) rec) t) ~~~ [示例代碼 15.2] 中定義的宏，就允許我們這樣做。 ~~~ > (funcall (alrec (and (oddp it) rec) t) '(1 3 5)) T ~~~ 這個新宏把第二個參數給出的表達式轉化成傳遞給 lrec 的函數，用這種方式實現其功能。由于第二個參數可能會通過指代引用 it 或 rec ，因此，在宏展開式里，函數的主體所處的作用域必須含有為這些符號建立的綁定。事實上，[示例代碼 15.2] 中有兩個不同版本的 alrec。前例中使用的版本需要用到符號宏(symbol macro，見第7.11 節)。由于只有較新的 Common Lisp 版本才支持符號宏【注1】，所以[示例代碼 15.2] 里也提供了一個相形之下不那么方便的?`alrec`?版本，其中?`rec`?被定義成一個局部函數。代價是，rec 作為函數將不得不被包在括號里： ~~~ (alrec (and (oddp it) (rec)) t) ~~~ 在支持?`symbol-macrolet`?的 Common Lisp 實現里，推薦用最初的版本。 Common Lisp 有獨立的函數名字空間，這使得通過這些遞歸構造器定義有名函數略有不便： ~~~ (setf (symbol-function 'our-length) (alrec (1+ rec) 0)) ~~~ [示例代碼 15.2] 中最后一個宏的目的就是為了把這一過程變得更抽象一些。借助?`on-cdrs`?，我們可以只需這樣寫： * * * **[示例代碼 15.2] 遞歸列表的宏** ~~~ (defun our-length (lst) (on-cdrs (1+ rec) 0 lst)) (defun our-every (fn lst) (on-cdrs (and (funcall fn it) rec) t lst)) (defmacro alrec (rec &optional base) "cltl2 version" (let ((gfn (gensym))) '(lrec #'(lambda (it ,gfn) (symbol-macrolet ((rec (funcall ,gfn))) ,rec)) ,base))) (defmacro alrec (rec &optional base) "cltl1 version" (let ((gfn (gensym))) '(lrec #'(lambda (it ,gfn) (labels ((rec () (funcall ,gfn))) ,rec)) ,base))) (defmacro on-cdrs (rec base &rest lsts) '(funcall (alrec ,rec #'(lambda () ,base)) ,@lsts)) ~~~ * * * **[示例代碼 15.3] 用 on-cdrs 定義的 Common Lisp 函數** ~~~ (defun our-copy-list (lst) (on-cdrs (cons it rec) nil lst)) (defun our-remove-duplicates (lst) (on-cdrs (adjoin it rec) nil lst)) (defun our-find-if (fn lst) (on-cdrs (if (funcall fn it) it rec) nil lst)) (defun our-some (fn lst) (on-cdrs (or (funcall fn it) rec) nil lst)) ~~~ * * * [示例代碼 15.3] 用這個新宏定義了幾個已有的 Common Lisp 函數。通過使用?`on-cdrs`?的表達方式，這些函數化簡成了它們最根本的形式，同時，若非這樣處理，我們恐怕很難注意到它們間的共同點。 [示例代碼 15.4] 中有一些新的實用工具，我們可以很方便地用?`on-cdrs`?來定義它們。前三個分別是：`unions`?，`intersections`，和?`differences`?，它們分別實現了集合的并、交、以及差的操作。雖然 Common Lisp 的內置函數已經實現了這些操作，但它們每次只能用于兩個列表。這樣的話，如果我們想要找到三個列表的并集就必須這樣寫： ~~~ > (union '(a b) (union '(b c) '(c d))) (A B C D) ~~~ 新的?`unions`?的行為和?`union`?相似，但前者能接受任意數量的參數，這樣我們只需說： ~~~ > (unions '(a b) '(b c) '(c d)) (D C A B) ~~~ 和 union 一樣，unions 并不保持初始列表中的元素順序。在 Common Lisp 的?`intersection`?和更通用的?`intersections`?之間也有著同樣的關系。在這個函數的定義里，為了改善效率，在最開始的地方加入了對于宏參數的?`null`?測試；如果集合中存在空集，它將短路掉整個計算過程。 ~~~ (defun unions (&rest sets) (on-cdrs (union it rec) (car sets) (cdr sets))) ~~~ * * * **[示例代碼 15.4] 用 on-cdrs 定義的新實用工具** ~~~ (defun intersections (&rest sets) (unless (some #'null sets) (on-cdrs (intersection it rec) (car sets) (cdr sets)))) (defun differences (set &rest outs) (on-cdrs (set-difference rec it) set outs)) (defun maxmin (args) (when args (on-cdrs (multiple-value-bind (mx mn) rec (values (max mx it) (min mn it))) (values (car args) (car args)) (cdr args)))) ~~~ * * * Common Lisp 也有一個稱為?`set-difference`?的函數，它接受兩個列表，并返回屬于第一個集合但不屬于第二個集合的元素： ~~~ > (set-difference '(a b c d) '(a c)) (D B) ~~~ 我們的新版本處理多重參數的方式和?`-`?同出一轍。例如，`(differences x y z)`?就等價于?`(set-difference x (unions y z))`?，只是不像后者那樣需要做?`cons`。 ~~~ > (differences '(a b c d e) '(a f) '(d)) (B C E) ~~~ 這些集合操作符僅僅是作為例子。對于它們沒有實際的需要，因為內置的?`reduce`?已經能處理上面這些例子所示的列表遞歸的簡單情況。例如，不用: ~~~ (unions ...) ~~~ 的話，你也可以說: ~~~ ((lambda (&rest args) (reduce #'union args)) ...) ~~~ 雖然如此，在一般情況下?`on-cdrs`?比?`reduce`?的功能更強。因為?`rec`?指向的是一個調用而非一個值，所以我們可以用?`on-cdrs`?來創建返回多值的函數。[示例代碼 15.4] 中最后一個函數，`maxmin`?，利用這種可能性在一次列表遍歷中同時找出最大和最小的元素： ~~~ > (maxmin '(3 4 2 8 5 1 6 7)) 8 1 ~~~ 后面章節中的代碼也可以用上?`on-cdrs`?。例如，`compile-cmds`?(第 23.4 節) ~~~ (defun compile-cmds (cmds) (if (null cmds) 'regs '(,@(car cmds) ,(compile-cmds (cdr cmds))))) ~~~ 可以簡單地定義成： ~~~ (defun compile-cmds (cmds) (on-cdrs '(,@it ,rec) 'regs cmds)) ~~~ ### 15.3 在子樹上遞歸宏在列表上進行的遞歸操作，在子樹上也一樣可以用遞歸的方式完成。本節里，我們用宏來給 5.6 節里定義的樹遞歸器定義更加清晰的接口。在5.6 節里我們定義了兩個樹遞歸構造器，分別名為?`ttrav`?和?`trec`?。前者總是遍歷完整棵樹；后者功能更為復雜，但它允許你控制遞歸停止的時機。借助這些函數，我們可以把?`our-copy-tree`?: ~~~ (defun our-copy-tree (tree) (if (atom tree) tree (cons (our-copy-tree (car tree)) (if (cdr tree) (our-copy-tree (cdr tree)))))) ~~~ 表達成 ~~~ (ttrav #'cons) ~~~ 而一個對?`rfind-if`: ~~~ (defun rfind-if (fn tree) (if (atom tree) (and (funcall fn tree) tree) (or (rfind-if fn (car tree)) (and (cdr tree) (rfind-if fn (cdr tree)))))) ~~~ 的調用，例如?`oddp`?，可以表達成： ~~~ (trec #'(lambda (o l r) (or (funcall l) (funcall r))) #'(lambda (tree) (and (oddp tree) tree))) ~~~ `Anaphoric`?宏可以為?`trec`?做出一個更好的接口，就像前一節中它們對?`lrec`?所做的那樣。要滿足一般的需求，這個宏將必須能夠同時指代引用到三個東西：當前所在樹，我們稱之為 it；遞歸下降左子樹，我們稱之為?`left`?；以及遞歸下降右子樹，我們稱之為?`right`?。有了這些約定以后，我們就應該可以像下面這樣，用新宏來表達前面的函數： ~~~ (atrec (cons left right)) (atrec (or left right) (and (oddp it) it)) ~~~ [示例代碼 15.5] 包含有這個宏的定義。在沒有?`symbol-macrolet`?的?`Lisp`?版本中，我們可以用 [示例代碼 15.5] 中的第二個定義來定義`atrec`。這個版本將?`left`?和?`right`?定義成局部函數，所以?`our-copy-tree`?就必須寫成： ~~~ (atrec (cons (left) (right))) ~~~ 出于便利，我們也定義了一個?`on-trees`?宏，跟前一節里的?`on-cdrs`?相似。[示例代碼 15.6] 顯示了用?`on-trees`?定義的四個在 5.6 節里定義的函數。正如第 5 章里提到的，那一章里的遞歸生成器構造的函數將不是尾遞歸的。用?`on-cdrs`?或?`on-trees`?定義出的函數不一定是最高效的實現。和底層的?`trec`?和?`lrec`?一樣，這些宏主要用于原型設計以及效率不是關鍵的那部分程序里面。盡管如此，本章和第 5 章的核心思路是：我們可以先編寫函數生成器，然后為它們設計出簡潔清爽的宏接口。同樣的技術也一樣可以用在構造那些能夠產生特別高效代碼的函數生成器上。 ### 15.4 惰性求值惰性求值就是說，只有當你需要表達式值的時候，才去求值它。使用惰性求值的方式之一是構造一種叫?`delay`?的對象。`Delay`?是某個表達式的值的替代物。它代表著一個承諾，即：如果今后需要的話，就要給出表達式的值。同時，由于這個承諾本身是個 Lisp 對象，因而它代表的值所有的功用，它都責無旁貸，一肩挑起。所以，一旦有需要，`delay`?就能返回表達式的值。 * * * **[示例代碼 15.5] 在樹上做遞歸的宏** ~~~ (defmacro atrec (rec &optional (base 'it)) "cltl2 version" (let ((lfn (gensym)) (rfn (gensym))) '(trec #'(lambda (it ,lfn ,rfn) (symbol-macrolet ((left (funcall ,lfn)) (right (funcall ,rfn))) ,rec)) #'(lambda (it) ,base)))) (defmacro atrec (rec &optional (base 'it)) "cltl1 version" (let ((lfn (gensym)) (rfn (gensym))) '(trec #'(lambda (it ,lfn ,rfn) (labels ((left () (funcall ,lfn)) (right () (funcall ,rfn))) ,rec)) #'(lambda (it) ,base)))) (defmacro on-trees (rec base &rest trees) '(funcall (atrec ,rec ,base) ,@trees)) ~~~ * * * **[示例代碼 15.6] 用 on-trees 定義的函數** ~~~ (defun our-copy-tree (tree) (on-trees (cons left right) it tree)) (defun count-leaves (tree) (on-trees (+ left (or right 1)) 1 tree)) (defun flatten (tree) (on-trees (nconc left right) (mklist it) tree)) (defun rfind-if (fn tree) (on-trees (or left right) (and (funcall fn it) it) tree)) ~~~ * * * Scheme 內置了對 delay 的支持。Scheme 的操作符 force 和 delay 就是為此服務的。用 Common Lisp 的話，可以用 [示例代碼 15.7] 中的方法來實現這兩個操作符。其中，把 delay 表示成了一個由兩部分構成的結構體。第一個字段代表 delay 是否已經被求值了，如果是的話就被賦予這個值。第二個字段則是一個閉包，調用它就能得到該 delay 所代表的值。宏 delay 接受一個表達式，并返回一個代表該表達式值的 delay： ~~~ > (let ((x 2)) (setq d (delay (1+ x)))) #S(DELAY ...) ~~~ 若要調用 delay 里的閉包，就得 force 這個 delay。函數 force 接受任意對象：對于普通對象它就是 identity 函數，但對于 delay，它是對 delay 所代表的值的請求。 * * * **[示例代碼 15.7] force 和 delay 的實現** ~~~ > (force 'a) A (defconstant unforced (gensym)) (defstruct delay forced closure) (defmacro delay (expr) (let ((self (gensym))) '(let ((,self (make-delay :forced unforced))) (setf (delay-closure ,self) #'(lambda () (setf (delay-forced ,self) ,expr))) ,self))) (defun force (x) (if (delay-p x) (if (eq (delay-forced x) unforced) (funcall (delay-closure x)) (delay-forced x)) x)) ~~~ * * * ~~~ > (force d) 3 ~~~ 無論何時，只要需要處理的對象有可能是 delay ，就應該用 force 對付它。例如，如果我們正在排序的列表可能含有 delay ，那么就要用： ~~~ (sort lst #'(lambda (x y) (> (force x) (force y)))) ~~~ 像這樣直接用 delay 顯得有些笨拙。要是在實際應用中，它們可能會藏身于另一個抽象層之下。備注：【注1】譯者注：這些問題現在已經不復存在，幾乎所有的現行 Common Lisp 實現(除了GCL，GNU Common Lisp) 都支持 ANSI Common Lisp 標準。和 CLTL2 相比，幾乎沒有變化。