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

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


trampolines scheme sicp continuation-passing
person PJ.Hades    schedule 15.02.2012    source источник

Ответы (1)


arrow_upward
3
arrow_downward

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

person John Clements    schedule 15.02.2012
comment
Спасибо :) Я подписался на эту статью для реализации планировщика батута pogo_stick. У меня возникают трудности с написанием этих функций на Python, поскольку он будет включать множество внутренних функций. Дело обстоит хуже, если подумать об отделении анализатора от eval. Чтобы оценить (set! var expr), нужно сначала проанализировать expr, а затем выполнить, оба из двух шагов будут включены в pogo_stick планировщик. Может, стоит подумать о других способах оптимизации хвостового вызова? Извините, это немного расплывчато. - person PJ.Hades; 15.02.2012
comment
Ага. Вы следуете плану, аналогичному тому, что я сделал с моей реализацией PyScheme (hkn. eecs.berkeley.edu/~dyoo/python/pyscheme) Удачной реализации! - person dyoo; 15.02.2012
comment
@dyoo, я читал ваш код PyScheme, он мне очень помогает, когда я запутался :). - person PJ.Hades; 16.02.2012