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

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

2 голосов
/ 15 февраля 2012

Я пытаюсь написать интерпретатор Scheme для 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?

1 Ответ

3 голосов
/ 15 февраля 2012

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

...