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

Question

Я пытаюсь написать игрушечный интерпретатор схемы python, основанный на метакруговом оценщике в 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

В схеме/Ракетка, вы бы написать 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» также записывается в КПС. В Python вы можете использовать «лямбду», если позволяет Guido; В противном случае я считаю, что для этого можно определить внутреннюю функцию.