Scheme基于消息传递实现memoize记忆化函数运行异常问题求解

核心错误原因 #

• memoize 函数最终返回值是原函数 f，所有内部定义的逻辑完全没生效。你写的内部函数 dispatch 从头到尾没有被调用，传入的 message 参数根本没有触发对应的 cond 分支逻辑，不管你传什么参数，memoize 都会直接返回未改造的原函数，所以 set! 相当于没执行任何修改。
• k 是无参函数，执行之后才会返回带记忆化表的包装函数。就算你调用了 dispatch 拿到 k，如果不执行 k，最终拿到的也不是可直接调用的记忆化函数。
• 语法错误，(set! fib(memoize 'm fib)) 不符合 Scheme 的函数调用语法，memoize 调用前缺少空格，应该写为 (set! fib (memoize 'm fib))。

修复后的代码示例 #

(define (memoize message f)
  (define (dispatch msg)
    (cond 
     ((eq? msg 'm) (k)) ; 调用k拿到记忆化包装函数
     ((eq? msg 'um) 20)))

  (define (k) 
    (let ((table (make-table)))
      (lambda (x)
        (let ((previously-computed-result (lookup x table)))
          (or previously-computed-result
              (let ((result (f x)))
                (insert! x result table)
                result))))))
  (dispatch message)) ; 调用dispatch，按传入的message返回对应结果

(set! fib (memoize 'm fib))

补充说明 #

如果不需要消息分发的逻辑，可以直接简化 memoize 实现，省略 message 判断分支，直接返回带缓存的包装函数即可。

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