完全符合R7RS-small标准的程序中所有letrec都可替换为letrec*吗？

结论 #

存在完全符合R7RS-small标准、无实现依赖/未定义行为的程序，将其中的letrec替换为letrec*会改变程序行为，因此不是所有场景下都可以直接替换。

两者的核心规则差异 #

R7RS-small标准中，二者的绑定初始化逻辑有明确区别：

• letrec所有绑定的初始化表达式求值顺序未指定，实现可以按任意顺序执行这些表达式，所有表达式都在包含全部letrec绑定的环境中求值
• letrec*所有绑定的初始化表达式严格按从左到右的顺序求值，每个表达式的求值环境中已经包含了所有左侧已完成初始化的绑定

合法的差异示例 #

示例1：初始化带可观测副作用

(letrec ((a (display "第一个绑定初始化"))
         (b (display "第二个绑定初始化")))
  (newline))

上述代码完全符合R7RS标准，无未定义行为，最终输出的两个字符串顺序是不确定的，不同实现可能输出第一个绑定初始化第二个绑定初始化，也可能反过来。如果把letrec替换为letrec*，输出顺序会固定为从左到右，行为发生明确变化。

示例2：初始化包含控制流跳转

(call/cc (lambda (return)
  (letrec ((x (return 100))
           (y (return 200)))
    #f)))

该代码的返回值是不确定的，可能为100也可能为200，取决于实现先求值哪个初始化表达式。如果替换为letrec*，则一定会先求值x的初始化表达式，直接返回100，返回值固定，行为发生变化。

补充说明 #

只有当letrec的所有初始化表达式同时满足两个条件：1、无任何可观测的副作用；2、求值结果与执行顺序无关时，替换为letrec*才不会改变程序行为。只要不满足上述条件，替换就可能引发行为差异。

内容的提问来源于stack exchange，提问作者Flux