Как написать функции анализатора / оценки, такие как `eval-if`, в форме CPS?

Question

Я пытаюсь написать игрушечный интерпретатор Python Scheme, основанный на мета-циклическом оценщике в SICP. Поскольку 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)))

в питоне:

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

В схеме /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)))))

Обратите внимание, что это предполагает, что ваш eval также написан на CPS. В Python вы можете использовать "лямбду", если это позволяет Гвидо; в противном случае, я считаю, что вы можете определить внутреннюю функцию для этого.