《第 13 章 编译期计算》由会员分享，可在线阅读，更多相关《第 13 章 编译期计算（7页珍藏版）》请在金锄头文库上搜索。
1、第 13 章 编译期计算第 13 章 编译期计算前的章节描述了类只能宏实现的操作符。本章将介绍函数可以解决，但宏能更效的类问题。第 8.2 节列出了在给定情形下使宏的利弊。有利的包括在编译期完成计算。有时，如果把操作符实现成宏，就可以在展开时完成部分作。本章会着眼于那些充分利这种可能性的宏。13.1 新的实具例代码 13.1 求平均值时转移计算(defun avg (&rest args)(/ (apply #+ args) (length args)(defmacro avg (&rest args)(/ (+ ,args) ,(length args)第 8.2 节提出，通过宏就可能把计算
2、转移到编译期完成。在那，我们曾经把宏 avg 作为例，它会返回其参数的平均值： (avg pi 4 5)4.047.在 例代码 13.1 中先把 avg 定义成函数，然后又宏实现它。当把 avg 定义成宏时，对length 的调可以在编译期完成。在宏版本我们也避免了在运期处理 &rest 参数的开销。所以在许多实现，写成宏的 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)(defma
3、cro 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)这种优化省去了不必要的计算，它的实现归功于在展开期就知道参数的数量。它还可以和我们在 in(11.3 节) 中进的另类优化结合起来，后者甚可以避免求值些参数。例代码 13.2 中有两个版本的 most-of ，它在多数参数都为真的时候返回真： (most-of t t t nil)T和 in 样，宏版
4、本展开成的代码只求值它需要数量的参数。例如:(most-of (a) (b) (c)展开的等价代码：(let (count 0)(or (and (a) ( (incf count) 1)(and (b) ( (incf count) 1)(and (c) ( (incf count) 1)在最理想的情况下，只对刚过半的参数求值。例代码 13.3 使编译期知道的参数(defun nthmost (n lst)(nth n (sort (copy-list lst) #)(defmacro nthmost (n lst)(if (and (integerp n) ()(defun gen-sta
5、rt (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 (
6、 ,var ,(car vars)(setq ,(mapcan #list(reverse vars)(cdr (reverse vars),(car vars) ,var),else)如果仅仅知道宏的部分参数值，也样有可能把计算作转移到编译期进。图 13.3就给出了这样的个宏。函数 nthmost 接受个数 n 以及个数列，并返回数列中第 n 的数；和其他序列函数样，它是从零开始索引的： (nthmost 2 (2 6 1 5 3 4)4函数版本写得常简单。它对列表排序，然后对排序的结果调 nth 。由于 sort 是破坏性的，nthmost 在排序之前先复制列表。这样实现，使得 nthmo
7、st 在两影响效率：它构造新的点对，且对整个参数列表排序，尽管我们只关前 个。如果我们在编译期知道 n 的值，就可以从另个度分析这个问题了。例代码13.3 中的其余代码定义了个宏版本的 nthmost 。这个宏做的第件事是去检查它的第个参数。如果第个参数字上不是个数，它就被展开成和我们上看到的相同的代码。如果第个参数是个数的话，我们可以采另个办法。说，如果你想要找到个盘第三的那块饼，那么你可以依次查看每块饼同时保持总是拿着已知最的三块，这个办法达到的。当你检查完所有的饼之后，你最的那块饼就是你要找的了。如果 是个常数，并且这个数字远于饼的总数，那么和 先对它们的全部进排序 的法相，这种技术可以
8、让你更便地得到想找的那块饼。例代码 13.4 nthmost 的展开式(nthmost 2 nums)展开成：(let (#:g7 nums)(unless ( #: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)(
9、setq #:g3 #:g2 #:g2 #:g1 #:g1 #:g8)(if ( #:g8 #:g2)(setq #:g3 #:g2 #:g2 #:g8)(if ( #:g8 #:g3)(setq #:g3 #:g8)nil)#:g3)这是种当在编译期已知时采取的策略。在它的展开式，宏创建了 个变量，然后调 nthmost-gen 来成那些求值成查看每块饼的代码。 例代码 13.4 给出了个例的宏展开。除了不能作为 apply 的参数传递以外，宏 nthmost 在为上和原来的函数样。这使宏的理由完全是出于效率：宏版本不在运期构造新点对，并且如果是个的常数，那么较的次数可以更少。难道为了写出效
10、的程序，就必须兴师动众，编这么长的宏么？对于本例来说，答案可能是否定的。这之所以给出两个版本的 nthmost ，主要的原因是想举个例，它揭了个普遍的原则：当某些参数在编译期已知时，你可以宏来成更效的代码。是否利这种可能性取决于你想获得多少好处，以及你可以另外付出多少努来编写个效的宏版本。由于 nthmost 的宏版本既长又繁，它可能只有在极端场合才值得去写。尽管如此，就算你宁愿不利它，编译期已知的信息总还是个值得考虑的因素。13.2 举例：贝塞尔曲线就像 with- 宏(第 11.2 节)，于编译期计算的宏更像是为特定应写的，不是为通的设计的实具。通的实具在编译期能了解多少信息？它的参数个数
11、，可能还有某些参数的值。但如果我们想要利其他的约束条件，这些条件也许就只能是程序才懂得使的信息了。本节将作为个实例，展宏是如何加速贝塞尔曲线的成的。如果对曲线的操作是交互式的话，那么它们的成速度必须得常快才。可以看出，如果曲线的分段数是已知的，那么多数计算就可以在编译期完成。把曲线成器写成个宏，我们就可以将预先算好的值嵌到代码中。这应该把它们保存在数组，这种更常规的优化式甚还要快。条贝塞尔曲线由四个点确定 两个端点和两个控制点。在两维平上，这些点定义了曲线上所有点的 和 坐标的参数程。如果两个端点是 (x0, y0) 和 (x3, y3)，以及两个控制点 (x1, y1) 和 (x2, y2)
12、，那么曲线上点的程就是：如果我们 u 在 0 和 1 之间的 n 个值来求值这个程，我们就得到曲线上的 n 个点。举个例，如果我们想把曲线画成 20 条线段，那么我们将 u = .05, .1,., .95 来求值程。对于u 在 0 或 1 上的求值是不需要的，因为如果 u = 0 它们将成第个端点 (x0, y0)，当 u = 1 时它们将成第个端点 。有个显易见的优化法是令 n 为定值，并提前计算 n 的指数，然后将它们存在个 (n - 1) x 3 的数组。通过把曲线成器定义成个宏，我们甚可以做得更好。如果 n 在展开时已知，程序可以简单地展开成 n 条画线指令。那些预先计算好的 n 的
13、指数，可以直接作为字上的值插到宏展开式，不必再保存在数组了。例代码 13.5 中有个实现了这策略的曲线成宏。它抛弃了即画线的策略，是将成的点保存在数组。当交互式地移动条曲线时，每个实例必须画两次：次显它，还有次是在画下个实例之前清除它。在两次画线之间，这些点必须保存在某个地。当 n = 20 时，genbez 展开成 21 个 setf。由于 的指数直接出现在代码，我们省下了在运期查找它们的开销，以及在启动时计算它们的开销。和 u 的指数样，数组的索引以常量的形式出现在展开式中，所以对那些 (setf aref) 的边界检查也可以在编译期完成。13.3 应后的章节将会提到其它些宏，它们也使了编
14、译期的已知信息。其中个很好的例是 if-match (第 18.4 节)。在这个例，模式匹配器会较两个序列，序列中可能含有变量，在较的过程中，模式匹配器会分析是否存在某种给这些变量赋值的式，可以让两个序列相等。if-match的设计显：如果序列中的个在编译期已知，并且只有这个序列含有变量，那么匹配可以做得更效。个办法是在运期较两个序列，并构造列表来保存这个过程中建的变量绑定，不过我们可以改成宏，让宏成的代码严格按照已知的序列来对照较，同时可以在真正的 Lisp 变量保存绑定。第 19-24 章描述的嵌式语，也在很程度上利了这些可在编译期获得的信息。由于嵌式语就是编译器，利这些信息是其唯然的作式
15、。这是个普遍规律：越是精设计的宏，它对其参数的约束也就越多，并且你利这些约束来产效的代码的机会也就越好。例代码 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 (* (- ,
