使用 call/cc 实现计数循环

意识上传
• 阅读 941

什么是计数循环

计数循环就是从一个数字$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也视为ifgoto的语法糖的话,可以进一步将计数循环写成更原始的形式

#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,那就是tagbodygo。使用它们可以将 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。借助这个操作符,即便没有tagbodygo,也可以实现计数循环。

使用 call/cc 实现计数循环

在上面的代码中,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-resultnext分别表示在宏展开后的代码中的计数上限和被捕捉的续延。之所以让它们以(gensym)的方式来命名,是为了避免多次求值count-form表达式,以及避免存储续延的变量名恰好出乎意料地与statements中的变量名冲突了,这也算是编写 Common Lisp 的宏时的最佳实践了。

后记

直接用call/cc来一个个实现 Common Lisp 中的各种控制流还是太繁琐了,更好的方案是用call/cc先实现tagbodygo,然后再用后两者继续实现do,最后用do分别实现dolistdotimes。当然了,这些都是后话了。

阅读原文

点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
美凌格栋栋酱 美凌格栋栋酱
6个月前
Oracle 分组与拼接字符串同时使用
SELECTT.,ROWNUMIDFROM(SELECTT.EMPLID,T.NAME,T.BU,T.REALDEPART,T.FORMATDATE,SUM(T.S0)S0,MAX(UPDATETIME)CREATETIME,LISTAGG(TOCHAR(
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
Easter79 Easter79
3年前
typeScript数据类型
//布尔类型letisDone:booleanfalse;//数字类型所有数字都是浮点数numberletdecLiteral:number6;lethexLiteral:number0xf00d;letbinaryLiteral:number0b101
Peter20 Peter20
4年前
mysql中like用法
like的通配符有两种%(百分号):代表零个、一个或者多个字符。\(下划线):代表一个数字或者字符。1\.name以"李"开头wherenamelike'李%'2\.name中包含"云",“云”可以在任何位置wherenamelike'%云%'3\.第二个和第三个字符是0的值wheresalarylike'\00%'4\
Wesley13 Wesley13
3年前
FLV文件格式
1.        FLV文件对齐方式FLV文件以大端对齐方式存放多字节整型。如存放数字无符号16位的数字300(0x012C),那么在FLV文件中存放的顺序是:|0x01|0x2C|。如果是无符号32位数字300(0x0000012C),那么在FLV文件中的存放顺序是:|0x00|0x00|0x00|0x01|0x2C。2.  
Wesley13 Wesley13
3年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Wesley13 Wesley13
3年前
PHP创建多级树型结构
<!lang:php<?php$areaarray(array('id'1,'pid'0,'name''中国'),array('id'5,'pid'0,'name''美国'),array('id'2,'pid'1,'name''吉林'),array('id'4,'pid'2,'n
Wesley13 Wesley13
3年前
Java日期时间API系列36
  十二时辰,古代劳动人民把一昼夜划分成十二个时段,每一个时段叫一个时辰。二十四小时和十二时辰对照表:时辰时间24时制子时深夜11:00凌晨01:0023:0001:00丑时上午01:00上午03:0001:0003:00寅时上午03:00上午0
Python进阶者 Python进阶者
1年前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这