乍听之下,不无道理;仔细揣摩,胡说八道

0%

模拟小于运算符的短路特性

忆往昔峥嵘岁月稠在Python的语言标准的Comparisions章节中提到

Also unlike C, expressions like a < b < c have the interpretation that is conventional in mathematics

也就是说,在C语言中要写成a < b && b < c的表达式,在Python中可以写成a < b < c。并且,标准中还提到

Comparisons can be chained arbitrarily, e.g., x < y <= z is equivalent to x < y and y <= z, except that y is evaluated only once (but in both cases z is not evaluated at all when x < y is found to be false).

一般将这种性质成为短路。因此,像2 < 1 < (1 / 0)这样的表达式在Python中不会引发异常,而是返回False

Python的小于号能拥有短路特性,是因为它并非一个普通函数,而是有语言层面加持的操作符。而在Common Lisp(下称CL)中,小于号仅仅是一个普通函数,就像Haskell中的小于号也是一个函数一般。不同的是,CL的小于号能接受多于两个的参数

1
(< 1 2 3 -1) ; 结果为NIL

但它并没有短路特性

1
(< 1 2 3 -1 (/ 1 0)) ; 引发名为DIVISION-BY-ZERO的错误

要想模拟出具有短路特性的小于号,必须借助于宏的力量。

想生成什么样的代码

要想写出一个宏,必须先设想出它的语法,以及它会展开成什么样的代码。姑且为这个宏起名为less-than,它的语法应当为

1
2
3
(defmacro less-than (form &rest more-forms)
; TBC
)

至于它的展开结果可以有多种选择。例如,可以(less-than 2 1 (/ 1 0))展开为自身具有短路特性的and形式

1
(and (< 2 1) (< 1 (/ 1 0)))

但就像在C语言中用宏朴素地实现计算二者最大值的MAX宏一样,上面的展开方式在一些情况下会招致重复求值

1
(less-than 1 (progn (print 'hello) 2) 3)

因此,起码要展开为andlet的搭配

1
2
3
4
5
(let ((g917 1)
(g918 (progn (print 'hello) 2)))
(and (< g917 g918)
(let ((g919 3))
(< g918 g919))))

要想展开为这种结构,可以如这般实现less-than

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
(defmacro less-than (form &rest more-forms)
(labels ((aux (lhs forms)
"LHS表示紧接着下一次要比较的、小于号的左操作数。"
(unless forms
(return-from aux))
(let* ((rhs (gensym))
(rv (aux rhs (rest forms))))
(if rv
`(let ((,rhs ,(first forms)))
(and (< ,lhs ,rhs)
,rv))
`(< ,lhs ,(first forms))))))
(cond ((null more-forms)
`(< ,form))
(t
(let ((lhs (gensym)))
`(let ((,lhs ,form))
,(aux lhs more-forms)))))))

用上面的输入验证一下是否会导致重复求值

1
2
3
4
5
CL-USER> (macroexpand-1 '(less-than 1 (progn (print 'hello) 2) 3))
(LET ((#:G942 1))
(LET ((#:G943 (PROGN (PRINT 'HELLO) 2)))
(AND (< #:G942 #:G943) (< #:G943 3))))
T

优化一下

显然less-than可以优化,只需要简单地运用递归的技巧即可

1
2
3
4
5
6
7
8
9
10
(defmacro less-than (form &rest more-forms)
(cond ((<= (length more-forms) 1)
`(< ,form ,@more-forms))
(t
(let ((lhs (gensym))
(rhs (gensym)))
`(let ((,lhs ,form)
(,rhs ,(first more-forms)))
(and (< ,lhs ,rhs)
(less-than ,rhs ,@(rest more-forms))))))))

展开后的代码简短得多

1
2
3
4
CL-USER> (macroexpand-1 '(less-than 1 (progn (print 'hello) 2) 3))
(LET ((#:G955 1) (#:G956 (PROGN (PRINT 'HELLO) 2)))
(AND (< #:G955 #:G956) (LESS-THAN #:G956 3)))
T
Liutos wechat
欢迎您扫一扫上面的微信公众号,订阅我的博客!
你的一点心意,我的十分动力。