第 13 章 編譯期計算

第 13 章 編譯期計算

前面的章節(jié)描述了幾類只能用宏實現(xiàn)的操作符。本章將介紹用函數(shù)可以解決，但用宏能更高效的一類問題。第 8.2 節(jié)列出了在給定情形下使用宏的利弊。有利的一面包括 "在編譯期完成計算"。有時，如果把操作符實現(xiàn)成宏，就可以在展開時完成部分工作。本章會著眼于那些充分利用這種可能性的宏。

13.1 新的實用工具

[示例代碼 13.1] 求平均值時轉移計算

(defun avg (&rest args)
  (/ (apply #'+ args) (length args)))

(defmacro avg (&rest args)
  '(/ (+ ,@args) ,(length args)))

第 8.2 節(jié)里提出，通過宏就可能把計算轉移到編譯期完成。在那里，我們曾經(jīng)把宏?avg?作為例子，它會返回其參數(shù)的平均值：

> (avg pi 4 5)
4.047...

在 [示例代碼 13.1] 中先把?avg?定義成函數(shù)，然后又用宏實現(xiàn)它。當把?avg?定義成宏時，對length?的調用可以在編譯期完成。在宏版本里我們也避免了在運行期處理?&rest?參數(shù)的開銷。所以在許多實現(xiàn)里，寫成宏的?avg?會更快。

[示例代碼 13.2] 轉移和避開計算

(defun most-of (&rest args)
  (let ((all 0)
      (hits 0))
    (dolist (a args)
      (incf all)
      (if a (incf hits)))
    (> hits (/ all 2))))

(defmacro most-of (&rest args)
  (let ((need (floor (/ (length args) 2)))
      (hits (gensym)))
    '(let ((,hits 0))
      (or ,@(mapcar #'(lambda (a)
            '(and ,a (> (incf ,hits) ,need)))
          args)))))

這種優(yōu)化省去了不必要的計算，它的實現(xiàn)歸功于在展開期就知道參數(shù)的數(shù)量。它還可以和我們在?in(11.3 節(jié)) 中進行的另一類優(yōu)化結合起來，后者甚至可以避免求值一些參數(shù)。[示例代碼 13.2] 中有兩個版本的?most-of?，它在多數(shù)參數(shù)都為真的時候返回真：

> (most-of t t t nil)
T

和?in?一樣，宏版本展開成的代碼只求值它需要數(shù)量的參數(shù)。例如:

(most-of (a) (b) (c))

展開的等價代碼：

(let ((count 0))
  (or (and (a) (> (incf count) 1))
    (and (b) (> (incf count) 1))
    (and (c) (> (incf count) 1))))

在最理想的情況下，只對剛過半的參數(shù)求值。

[示例代碼 13.3] 使用編譯期知道的參數(shù)

(defun nthmost (n lst)
  (nth n (sort (copy-list lst) #'>)))

(defmacro nthmost (n lst)
  (if (and (integerp n) (< n 20))
    (with-gensyms (glst gi)
      (let ((syms (map0-n #'(lambda (x) (gensym)) n)))
        '(let ((,glst ,lst))
          (unless (< (length ,glst) ,(1+ n))
            ,@(gen-start glst syms)
            (dolist (,gi ,glst)
              ,(nthmost-gen gi syms t))
            ,(car (last syms))))))
    '(nth ,n (sort (copy-list ,lst) #'>))))

(defun gen-start (glst syms)
  (reverse
    (maplist #'(lambda (syms)
        (let ((var (gensym)))
          '(let ((,var (pop ,glst)))
            ,(nthmost-gen var (reverse syms)))))
      (reverse syms))))

(defun nthmost-gen (var vars &optional long?)
  (if (null vars)
    nil
    (let ((else (nthmost-gen var (cdr vars) long?)))
      (if (and (not long?) (null else))
        '(setq ,(car vars) ,var)
        '(if (> ,var ,(car vars))
          (setq ,@(mapcan #'list
              (reverse vars)
              (cdr (reverse vars)))
            ,(car vars) ,var)
          ,else)))))

如果僅僅知道宏的部分參數(shù)值，也一樣有可能把計算工作轉移到編譯期進行。圖 13.3 就給出了這樣的一個宏。函數(shù)?nthmost?接受一個數(shù)?n?以及一個數(shù)列，并返回數(shù)列中第?n?大的數(shù)；和其他序列函數(shù)一樣，它是從零開始索引的：

> (nthmost 2 '(2 6 1 5 3 4))
4

函數(shù)版本寫得非常簡單。它對列表排序，然后對排序的結果調用?nth?。由于?sort?是破壞性的，nthmost?在排序之前先復制列表。這樣實現(xiàn)，使得?nthmost?在兩方面影響效率：它構造新的點對，而且對整個參數(shù)列表排序，盡管我們只關心前 個。

如果我們在編譯期知道?n?的值，就可以從另一個角度分析這個問題了。[示例代碼 13.3] 中的其余代碼定義了一個宏版本的?nthmost?。這個宏做的第一件事是去檢查它的第一個參數(shù)。如果第一個參數(shù)字面上不是一個數(shù)，它就被展開成和我們上面看到的相同的代碼。如果第一個參數(shù)是一個數(shù)的話，我們可以采用另一個辦法。

比方說，如果你想要找到一個盤子里第三大的那塊餅干，那么你可以依次查看每一塊餅干同時保持手里總是拿著已知最大的三塊，用這個辦法達到目的。當你檢查完所有的餅干之后，你手里最小的那塊餅干就是你要找的了。如果 是一個小常數(shù)，并且這個數(shù)字遠小于餅干的總數(shù)，那么和 "先對它們的全部進行排序" 的方法相比，用這種技術可以讓你更方便地得到想找的那塊餅干。

[示例代碼 13.4] nthmost 的展開式

(nthmost 2 nums)

展開成：

(let ((#:g7 nums))
  (unless (< (length #:g7) 3)
    (let ((#:g6 (pop #:g7)))
      (setq #:g1 #:g6))
    (let ((#:g5 (pop #:g7)))
      (if (> #:g5 #:g1)
        (setq #:g2 #:g1 #:g1 #:g5)
        (setq #:g2 #:g5)))
    (let ((#:g4 (pop #:g7)))
      (if (> #:g4 #:g1)
        (setq #:g3 #:g2 #:g2 #:g1 #:g1 #:g4)
        (if (> #:g4 #:g2)
          (setq #:g3 #:g2 #:g2 #:g4)
          (setq #:g3 #:g4))))
    (dolist (#:g8 #:g7)
      (if (> #:g8 #:g1)
        (setq #:g3 #:g2 #:g2 #:g1 #:g1 #:g8)
        (if (> #:g8 #:g2)
          (setq #:g3 #:g2 #:g2 #:g8)
          (if (> #:g8 #:g3)
            (setq #:g3 #:g8)
            nil))))
    #:g3))

這是一種當在編譯期已知時采取的策略。在它的展開式里，宏創(chuàng)建了 個變量，然后調用?nthmost-gen?來生成那些求值成查看每一塊餅干的代碼。[ 示例代碼 13.4] 給出了一個示例的宏展開。除了不能作為 apply 的參數(shù)傳遞以外，宏?nthmost?在行為上和原來的函數(shù)一樣。這里使用宏的理由完全是出于效率：宏版本不在運行期構造新點對，并且如果是一個小的常數(shù)，那么比較的次數(shù)可以更少。

難道為了寫出高效的程序，就必須興師動眾，編這么長的宏么？對于本例來說，答案可能是否定的。這里之所以給出兩個版本的?nthmost?，主要的原因是想舉個例子，它揭示了一個普遍的原則：當某些參數(shù)在編譯期已知時，你可以用宏來生成更高效的代碼。是否利用這種可能性取決于你想獲得多少好處，以及你可以另外付出多少努力來編寫一個高效的宏版本。由于?nthmost?的宏版本既長又繁，它可能只有在極端場合才值得去寫。盡管如此，就算你寧愿不利用它，編譯期已知的信息總還是一個值得考慮的因素。

13.2 舉例：貝塞爾曲線

就像?with-?宏(第 11.2 節(jié))，用于編譯期計算的宏更像是為特定應用而寫的，而不是為通用目的設計的實用工具。通用的實用工具在編譯期能了解多少信息？它的參數(shù)個數(shù)，可能還有某些參數(shù)的值。但如果我們想要利用其他的約束條件，這些條件也許就只能是程序自己才懂得使用的信息了。

本節(jié)將作為一個實例，展示宏是如何加速貝塞爾曲線的生成的。如果對曲線的操作是交互式的話，那么它們的生成速度必須得非?？觳判??？梢钥闯?，如果曲線的分段數(shù)是已知的，那么大多數(shù)計算就可以在編譯期完成。把曲線生成器寫成一個宏，我們就可以將預先算好的值嵌入到代碼中。這應該比把它們保存在數(shù)組里，這種更常規(guī)的優(yōu)化方式甚至還要快。

一條貝塞爾曲線由四個點確定 — 兩個端點和兩個控制點。在兩維平面上，這些點定義了曲線上所有點的 和 坐標的參數(shù)方程。如果兩個端點是 (x0, y0) 和 (x3, y3)，以及兩個控制點 (x1, y1) 和 (x2, y2)，那么曲線上點的方程就是：

如果我們用?u?在?0?和?1?之間的?n?個值來求值這個方程，我們就得到曲線上的?n?個點。舉個例子，如果我們想把曲線畫成?20?條線段，那么我們將用?u = .05, .1, ..., .95?來求值方程。對于u?在?0?或?1?上的求值是不需要的，因為如果?u = 0?它們將生成第一個端點?(x0, y0)，而當?u = 1?時它們將生成第二個端點 。

有個顯而易見的優(yōu)化方法是令?n?為定值，并提前計算?n?的指數(shù)，然后將它們存在一個?(n - 1) x 3?的數(shù)組里。通過把曲線生成器定義成一個宏，我們甚至可以做得更好。如果?n?在展開時已知，程序可以簡單地展開成?n?條畫線指令。那些預先計算好的?n?的指數(shù)，可以直接作為字面上的值插入到宏展開式里，而不必再保存在數(shù)組里了。

[示例代碼 13.5] 中有一個實現(xiàn)了這一策略的曲線生成宏。它拋棄了立即畫線的策略，而是將生成的點保存在數(shù)組里。當交互式地移動一條曲線時，每一個實例必須畫兩次：一次顯示它，還有一次是在畫下一個實例之前清除它。在兩次畫線之間，這些點必須保存在某個地方。

當?n = 20?時，genbez?展開成 21 個?setf。由于 的指數(shù)直接出現(xiàn)在代碼里，我們省下了在運行期查找它們的開銷，以及在啟動時計算它們的開銷。和?u?的指數(shù)一樣，數(shù)組的索引以常量的形式出現(xiàn)在展開式中，所以對那些?(setf aref)?的邊界檢查也可以在編譯期完成。

13.3 應用

后面的章節(jié)將會提到其它一些宏，它們也使用了編譯期的已知信息。其中一個很好的例子是?if-match?(第 18.4 節(jié))。在這個例子里，模式匹配器會比較兩個序列，序列中可能含有變量，在比較的過程中，模式匹配器會分析是否存在某種給這些變量賦值的方式，可以讓兩個序列相等。if-match的設計顯示：如果序列中的一個在編譯期已知，并且只有這個序列里含有變量，那么匹配可以做得更高效。一個辦法是在運行期比較兩個序列，并構造列表來保存這個過程中建立的變量綁定，不過我們可以改成用宏，讓宏生成的代碼嚴格按照已知的序列來一一對照比較，同時可以在真正的 Lisp 變量里保存綁定。

第 19-24 章里描述的嵌入式語言，也在很大程度上利用了這些可在編譯期獲得的信息。由于嵌入式語言就是編譯器，利用這些信息是其唯一自然的工作方式。這是一個普遍規(guī)律：越是精心設計的宏，它對其參數(shù)的約束也就越多，并且你利用這些約束來產(chǎn)生高效的代碼的機會也就越好。

[示例代碼 13.5] 生成貝塞爾曲線的宏

(defconstant *segs* 20)
(defconstant *du* (/ 1.0 *segs*))
(defconstant *pts* (make-array (list (1+ *segs*) 2)))

(defmacro genbez (x0 y0 x1 y1 x2 y2 x3 y3)
  (with-gensyms (gx0 gx1 gy0 gy1 gx3 gy3)
    '(let ((,gx0 ,x0) (,gy0 ,y0)
        (,gx1 ,x1) (,gy1 ,y1)
        (,gx3 ,x3) (,gy3 ,y3))
      (let ((cx (* (- ,gx1 ,gx0) 3))
          (cy (* (- ,gy1 ,gy0) 3))
          (px (* (- ,x2 ,gx1) 3))
          (py (* (- ,y2 ,gy1) 3)))
        (let ((bx (- px cx))
            (by (- py cy))
            (ax (- ,gx3 px ,gx0))
            (ay (- ,gy3 py ,gy0)))
          (setf (aref *pts* 0 0) ,gx0
            (aref *pts* 0 1) ,gy0)
          ,@(map1-n #'(lambda (n)
              (let* ((u (* n *du*))
                  (u2 (* u u))
                  (u3 (expt u 3)))
                '(setf (aref *pts* ,n 0)
                  (+ (* ax ,u3)
                    (* bx ,u2)
                    (* cx ,u)
                    ,gx0)
                  (aref *pts* ,n 1)
                  (+ (* ay ,u3)
                    (* by ,u2)
                    (* cy ,u)
                    ,gy0))))
            (1- *segs*))
          (setf (aref *pts* *segs* 0) ,gx3
            (aref *pts* *segs* 1) ,gy3))))))

<span class="str" style="color: rgb(128, 0, 0);"> </span>