scheme - 如何以 CPS 形式编写分析器/评估器函数，如 `eval-if`？

Question

我正在尝试基于 SICP 中的元循环评估器编写一个玩具 python Scheme 解释器。由于python只支持有限深度的调用栈，我不得不消除尾调用。我阅读了蹦床并用它实现了解析器。

但我不知道如何以连续传递风格编写分析器/评估器函数以将它们与蹦床一起使用。例如，eval-if功能:

(define (eval-if expr env)
    (if (is-true? (eval (if-predicate expr) env))
        (eval (if-consequent expr) env)
        (eval (if-alternate expr) env)))

在 python 中:

def eval_if(expr, env):
    if is_true(eval(if_predicate(expr), env)):
        return eval(if_consequent(expr), env)
    else:
        return eval(if_alternate(expr), env)

当我想检查谓词是否为真时，我不得不调用新一轮的 eval在上面。我应该如何以 CPS 形式编写这种递归调用？

Answer 1

在 scheme/Racket 中，您可以将此函数的 CPSed 形式编写为:

;; evaluate an 'if':
(define (eval-if expr env k)
  (eval (if-predicate expr) env
        (lambda (testval)
          (if (is-true? testval)
              (eval (if-consequent expr) env k)
              (eval (if-alternate expr) env k)))))

请注意，这假设您的“评估”也是用 CPS 编写的。在 Python 中，如果 Guido 允许，您大概可以使用“lambda”；否则，我相信您可以为此定义一个内部函数。