Scheme记忆化惰性求值实现中set?变量两次检测的原因求解

两次set?检查的作用 #

两次检查的核心是处理递归force同一份promise（或多线程并发force同一份promise）的场景，严格保证promise的语义：同一个promise无论被force多少次，永远返回首个计算完成的结果，不会出现结果不一致或重复覆盖的问题。

先回顾promise的核心逻辑 #

我们先看如果简化成只有一层set?检查，会有什么缺陷：

; 存在缺陷的简化实现（仅一层检查）
(lambda ()
  (unless set?
    (let ([x (p)])
      ; 缺少第二次set?检查，直接赋值
      (set! val x)
      (set! set? #t)))
  val)

这个版本在单次force、无递归的场景下可以正常工作，但一旦出现递归force就会违反语义要求。

递归force场景的执行流程分析 #

我们举一个会递归force自身的promise示例：

(define cnt 0)
(define p
  (delay (begin
           (set! cnt (+ cnt 1))
           ; 第一次执行时递归force自身
           (when (= cnt 1)
             (force p))
           cnt)))

我们逐步走Dybvig的两层检查版本的执行流程：

• 第一次调用(force p)，进入promise闭包：此时set? = #f，通过第一层unless set?检查，开始执行封装的thunk p。
• 执行thunk：cnt变为1，满足条件触发递归调用(force p)。
• 递归调用进入promise闭包：此时第一次调用还未完成，set?仍然是#f，再次通过第一层检查，第二次执行thunk p。
• 递归层thunk执行：cnt变为2，不满足when条件，返回结果2。此时触发第二层unless set?检查，set?还是#f，所以将val设为2，set?设为#t，递归调用返回2。
• 回到第一层thunk执行：thunk执行完毕，得到返回结果2。此时触发第二层unless set?检查，发现set?已经被递归调用设为#t，直接跳过赋值操作，返回已经存储的val=2。
• 最终(force p)返回2，符合promise的记忆语义。

为什么第二层检查不可缺少 #

如果没有第二层检查，当多个force调用（递归或并发场景）都通过了第一层的set?检查、同时在执行thunk时，后执行完的thunk会覆盖先执行完的thunk的结果，直接违反promise必须返回同一个值的要求。
比如多线程场景下，两个线程同时force同一个promise，都通过了第一层检查开始执行thunk，线程A先执行完得到结果10，设置val=10、set?=#t；线程B后执行完得到结果20，如果没有第二层检查，线程B会把val覆盖为20，导致同一个promise先后返回10和20，完全不符合惰性求值的记忆要求。

书中的解释对应的就是这个逻辑：执行thunk的过程中如果promise已经被其他递归调用完成了，就直接使用已有的结果，保证永远返回首个完成的计算值。

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