关于applicative-orderimperativey-combinator?

显示全部楼层 · 2021-1-29 05:08:21

标题里写不下了，想问的问题1是:为什么applicative-orderimperativey-combinator不能应用于＂含状态＂的函数?这个问题来源于theseasonedschemer一书125页关于((Ybiz)5)和((Y!biz)5)的两个问题.书中给出的Y的定义是:(defineY(lambda(le)((lambda(f)(ff))(lambda(f)(le(lambda(x)((ff)x)))))))Y!是:(defineY-bang1(lambda(f)(let((h(lambda(x)'())))(set!h(f(lambda(x)(hx))))h)))biz是:(definebiz(let((x0))(lambda(f)(set!x(add1x))(lambda(a)(if(=ax)0(fa))))))后面附的pastebin链接里有代码.试验的结果是(Ybiz)work,(Y!biz)死循环.不明白为什么(Y!biz)死循环?代码链接和拍的书在附件中:https://pastebin.com/kmSQWaXy顺便请教:问题2:如何调试scheme的代码?我看了一下　https://www.cs.indiana.edu/chezscheme/debug/　和https://www.scheme.com/csug8/debug.html#./debug:h0　感觉还是不明白怎么能像gdb调binary一样单步运行(似乎trace/在崩掉的地方查看functionframe/backtrace/continuation/查看object都还可以).问题3:有什么进阶的lisp/scheme/ml/lamndacalculus的书推荐吗?

千问 · 2021-1-29 05:08:21

（昨晚刚看完那一章，过来回答一下第1个问题……）
lijinpei (jp) 在 ta 的帖子中提到：标题里写不下了，想问的问题1是:为什么applicative-orderimperativey-combinator不能应用于＂含状态＂的函数?
问题不在于函数“含状态”，而在于biz这个高阶函数里set!的位置：(definebiz(let((x0))(lambda(f)(set!x(+1x))(lambda(a)(if(=ax)0(fa))))))用letrec之类宏来定义递归函数时，外面的那一层(lambda(f)...)是宏生成的，程序员根本不可能在中间这个特殊位置放一个set!，这在TSS书中同一页也有暗示。
先看Y!，我觉得它其实更容易理解：(defineY!(lambda(g)(let((f(lambda(a)'())))(set!h(g(lambda(a)(fa))))h)))求值(Y!biz)时，Y!中的局部变量f被set!为(g(lambda(a)(ha)))；后者在求值时先将xset!为1，然后得到值(lambda(a)(if(=ax)0(fa)))，所以f也就被绑定到这一函数，其中不再涉及set!，因此死循环。
再看Y：(defineY(lambda(g)((lambda(h)(hh))(lambda(x)(g(lambda(a)((xx)a)))))))(Y!biz)先被展开为((lambda(x)(g(lambda(a)((xx)a))))(lambda(x)(g(lambda(a)((xx)a)))))然后被展开为(g(lambda(a)(((lambda(x)(g(lambda(a)((xx)a))))(lambda(x)(g(lambda(a)((xx)a)))))a)))因为lambda延时求值的效果，这里g的参数以f的身份被带入实际的biz函数后就暂停求值了，直到f被再次调用时才恢复求值：((lambda(x)(g(lambda(a)((xx)a))))(lambda(x)(g(lambda(a)((xx)a)))))然后(g(lambda(a)(((lambda(x)(g(lambda(a)((xx)a))))(lambda(x)(g(lambda(a)((xx)a)))))a)))如此便可循环往复；因为每次循环都涉及了完整的g函数，即除外层(let((x0)))之外的biz，因此(set!x(+1x))会生效，于是现世安稳，岁月静好。
最后补充一句，由上文可见原本的Y组合子在实际应用时每次递归都涉及多层函数展开，其中的性能开销可能是在如此讲究优雅的TSS中也说letrec由Y!实现的一个原因吧。不过我猜更重要的原因是实现互递归时，Y写起来相对Y!而言太复杂？

千问 · 2021-1-29 05:08:21

对于delapplicativeorder/delY!h=(Y-bang1biz)=(Y-bangbiz)=(bizh)=(lambda(a)(if(=ax)0(ha)))withfreevariablexofvalue1,也就是说,先求了一次h=(bizh)=某lambda,再求(某lambda0)对于delnormalorder/delY,求((Ybiz)0)先求(Ybiz),求值的过程中(set!x(+x1)),展开得到了某lambda:(lambda(a)(if(=ax)0(fa))),这里面f是某一大坨东西,不过lambda延迟求值先不用管.然后求(某lambda0)得到(f0)然后发现这时候得到的式子和((Ybiz)0)是一样的,只不过xinc了,从而循环中包含了incx.发明这俩东西的人真是个人才(不知道有没有什么编译技术能把用YC写的递归函数改成letrec递归函数.Casper (311.5:Esistvollbracht!) 在 ta 的帖子中提到：（昨晚刚看完那一章，过来回答一下第1个问题……）问题不在于函数“含状态”，而在于biz这个高阶函数里set!的位置：用letrec之类宏来定义递归函数时，外面的那一层(lambda(f)...)是宏生成的，……

千问 · 2021-1-29 05:08:21

lijinpei (jp) 在 ta 的帖子中提到：对于applicativeorder[...]对于normalorder[...]
这俩都是应用序的吧，TLS、TSS两书中明确指出了的。正是在应用序下，才须要用lambda来实现延时求值。（此外，正则序下的命令式编程似乎有点不好想象……）不管怎样，延时求值是解释这一现象的关键。

千问 · 2021-1-29 05:08:21

我删了我的回帖中的applicative/normalCasper (311.5:Esistvollbracht!) 在 ta 的帖子中提到：这俩都是应用序的吧，TLS、TSS两书中明确指出了的。正是在应用序下，才须要用lambda来实现惰性求值。（此外，正则序下的命令式编程似乎有点不好想象……）……

千问 · 2021-1-29 05:08:21

Casper (311.5:Esistvollbracht!) 在 ta 的帖子中提到：用letrec之类宏来定义递归函数时，外面的那一层(lambda(f)...)是宏生成的，程序员根本不可能在中间这个特殊位置放一个set!，这在TSS书中同一页也有暗示。
于是被自己打脸了：(let((x0))(letrec((f(begin(set!x(+1x))(lambda(a)(if(=ax)0(fa))))))(f2)))
最后补充一句，由上文可见原本的Y组合子在实际应用时每次递归都涉及多层函数展开，其中的性能开销可能是在如此讲究优雅的TSS中也说letrec由Y!实现的一个原因吧。不过我猜更重要的原因是实现互递归时，Y写起来相对Y!而言太复杂？
在试验上面的代码时查阅R*RS，才意识到其规定了letrec的初始化语句本来在定义时就得被求值，所以自然排除了使用Y的可能。当然，这也使上面这段代码死循环的原因一目了然。