共计 2125 个字符,预计需要花费 6 分钟才能阅读完成。
什么是计数循环
计数循环就是从一个数字 $i$ 开始始终遍历到另一个数字 $j$ 为止的循环过程。例如,上面的 Python 代码就会遍历从 0 到 9 这 10 个整数并一一打印它们
for i in range(10):
print(i)
如果是在 C 语言中实现同样的性能,代码会更显著一些
#include <stdio.h>
int main(int argc, char *argv[])
{for (int i = 0; i < 10; i++) {printf("%d\n", i);
}
return 0;
}
在 C 语言的例子中,显式地指定了计数器变量 i
从 0 开始并且在等于 10 的时候完结循环,比之 Python 版本更有循环的滋味。
拆开循环计数的语法糖
应用 C 语言的 while
语句同样能够实现计数循环,示例代码如下
#include <stdio.h>
int main(int argc, char *argv[])
{
int i = 0;
while (i < 10) {printf("%d\n", i);
i++;
}
return 0;
}
如果将 while
也视为 if
和goto
的语法糖的话,能够进一步将计数循环写成更原始的模式
#include <stdio.h>
int main(int argc, char *argv[])
{
int i = 0;
label0:
if (i >= 10) {goto label1;}
printf("%d\n", i);
i++;
goto label0;
label1:
return 0;
}
Common Lisp 中的 go 与续延
在 Common Lisp 中也有与 C 语言的 goto
个性相近的 special form,那就是 tagbody
和go
。应用它们能够将 C 代码直白地翻译为对应的 Common Lisp 版本
(let ((i 0))
(tagbody
label0
(when (>= i 10)
(go label1))
(format t "~D~%" i)
(incf i)
(go label0)
label1))
聪慧的你肯定曾经发现了,此处的第二个符号 label1
其实是丝毫不必要的,只有写成上面的模式即可
(let ((i 0))
(tagbody
label0
(when (< i 10)
(format t "~D~%" i)
(incf i)
(go label0))))
这个模式不仅仅是更简略了,而且它暴露出了一个事实:label0
所示意的,其实就是在将变量 i
绑定为 0之后 要执行的代码的地位。换句话说,它标识了一个续延(continuation)。
用 call/cc 从新实现计数循环
如果你用的语言中反对 first-class 的续延,那么便能够用来实现计数循环,例如 233-lisp。在 233-lisp 中,提供了非凡操作符 call/cc
来捕获以后续延对象,这个名字借鉴自 Scheme。借助这个操作符,即使没有 tagbody
和go
,也能够实现计数循环。
在下面的代码中,call/cc
捕捉到的续延就是“赋值给局部变量 i
”。在将这个续延k
保留到变量 next
之后,用 0 初始化变量 i
。之后只有i
还小于 10,就将它打印到规范输入,并启动保留在了变量 next
中的续延,回到给变量 i
赋值的中央。此时传递给续延的参数为 (+ i 1)
,就实现了变量i
的自增操作。当 (< i 10)
不再成立时,也就不会启动续延“回到过来”了,至此,过程完结。
在 233-lisp 中,将 dotimes
作为一个内置的宏用 call/cc
实现了一遍,参见这里,其代码如下
(defun expand-dotimes-to-call/cc (expr)
"将 DOTIMES 语句 EXPR 编译为等价的 CALL/CC 语句。"
(assert (eq (first expr) 'dotimes))
(destructuring-bind ((var count-form) &rest statements)
(rest expr)
(let ((a (gensym))
(count-form-result (gensym))
(next (gensym)))
`(let ((,count-form-result ,count-form)) ; 因为目前 LET 只反对一个绑定,因而这里要写多个 LET。(let ((,next 0)) ; 因为 233-lisp 中尚未反对 NIL,因而这里填个 0。(let ((,var (call/cc (k)
(progn
(setf ,next k)
0)))) ; 计数循环从 0 开始。(if (< ,var ,count-form-result)
(progn
,@statements
(,next (+ ,var 1)))
0))))))) ; 因为目前没有 NIL,因而返回一个数字 0 来代替。
变量 count-form-result
和next
别离示意在宏开展后的代码中的计数下限和被捕获的续延。之所以让它们以 (gensym)
的形式来命名,是为了防止屡次求值 count-form
表达式,以及防止存储续延的变量名恰好出其不意地与 statements
中的变量名抵触了,这也算是编写 Common Lisp 的宏时的最佳实际了。
后记
间接用 call/cc
来一个个实现 Common Lisp 中的各种控制流还是太繁琐了,更好的计划是用 call/cc
先实现 tagbody
和go
,而后再用后两者持续实现 do
,最初用do
别离实现 dolist
和dotimes
。当然了,这些都是后话了。
浏览原文