Летрек и реентерабельные продолжения

Question

Мне сказали, что следующее выражение предназначено для оценки 0, но многие реализации Схемы оценивают его как 1:

(let ((cont #f))
  (letrec ((x (call-with-current-continuation (lambda (c) (set! cont c) 0)))
           (y (call-with-current-continuation (lambda (c) (set! cont c) 0))))
    (if cont
        (let ((c cont))
          (set! cont #f)
          (set! x 1)
          (set! y 1)
          (c 0))
        (+ x y))))

Я должен признать, что не могу сказать, с чего начать. Я понимаю основы продолжений и call/cc, но могу ли я получить подробное объяснение этого выражения?

Answer 1

Это интересный фрагмент. Я столкнулся с этим вопросом, потому что я искал обсуждения точных различий между letrec а также letrec* и как они различались между различными версиями отчетов Схемы и различными реализациями Схемы. Экспериментируя с этим фрагментом, я провел некоторые исследования и сообщу результаты здесь.

Если вы мысленно рассмотрите выполнение этого фрагмента, вам следует обратить внимание на два вопроса:

Q1. В каком порядке находятся пункты инициализации для x а также y оценивать?

Q2. Все ли пункты инициализации оцениваются в первую очередь, и их результаты кэшируются, а затем все присвоения x а также y выполнено потом? Или некоторые из назначений были сделаны до того, как были оценены некоторые из пунктов инициализации?

За letrec Отчеты Схемы говорят, что ответ на Q1 является "неопределенным". Большинство реализаций фактически оценивают предложения в порядке слева направо; но вы не должны полагаться на это поведение.

Схемы R6RS и R7RS вводят новую обязательную конструкцию letrec* это определяет порядок оценки слева направо. Это также отличается в некоторых других отношениях от letrec, как мы увидим ниже.

Возвращаясь к letrec Отчеты Схемы, относящиеся, по крайней мере, к R5RS , указывают на то, что ответом на вопрос Q2 является "оценить все пункты инициализации перед выполнением любого из назначений". Я говорю "кажется, что уточнить", потому что язык не так явно говорит о том, что это необходимо, как это может быть. На самом деле, многие реализации Scheme не соответствуют этому требованию. И это то, что отвечает за разницу между "предполагаемым" и "наблюдаемым" поведением в отношении вашего фрагмента.

Давайте пройдемся по вашему фрагменту, помня Q2. Сначала мы отложим два "местоположения" (ссылочные ячейки) для x а также y быть привязанным к. Затем мы оцениваем одно из условий инициализации. Допустим, это пункт для x хотя, как я уже сказал, с letrec это может быть либо один. Мы сохраняем продолжение этой оценки в cont, Результат этой оценки равен 0. Теперь, в зависимости от ответа на вопрос Q2, мы либо присваиваем этот результат немедленно x или мы кешируем это, чтобы сделать назначение позже. Далее мы оцениваем другое предложение инициализации. Мы сохраняем его продолжение в cont перезаписывая предыдущий. Результат этой оценки равен 0. Теперь все пункты инициализации были оценены. В зависимости от ответа на вопрос 2, мы могли бы в этот момент присвоить кэшированный результат 0 x ; или назначение x возможно, уже произошло. В любом случае, назначение y происходит сейчас.

Затем мы начинаем оценивать основную часть (letrec (...) ...) выражение (впервые). Продолжение хранится в cont поэтому мы извлекаем его в c затем очистите cont а также set! каждый из x а также y 1. Затем мы вызываем полученное продолжение со значением 0. Это возвращает нас к последнему предложению инициализации, которое мы предположили как y "S. Аргумент, который мы приводим к продолжению, затем используется вместо (call-with-current-continuation (lambda (c) (set! cont c) 0)) и будет назначен y, В зависимости от ответа на Q2, присвоение 0 для x может или не может иметь место (снова) в этот момент.

Затем мы начинаем оценивать основную часть (letrec (...) ...) выражение (во второй раз). Сейчас cont это #f, поэтому мы получаем (+ x y), Который будет либо (+ 1 0) или же (+ 0 0) в зависимости от того, был ли 0 переназначен x когда мы вызвали сохраненное продолжение.

Вы можете отследить это поведение, украсив свой фрагмент некоторыми display звонки, например так:

(let ((cont #f))
 (letrec ((x (begin (display (list 'xinit x y cont)) (call-with-current-continuation (lambda (c) (set! cont c) 0))))
          (y (begin (display (list 'yinit x y cont)) (call-with-current-continuation (lambda (c) (set! cont c) 0)))))
  (display (list 'body x y cont))
  (if cont
   (let ((c cont))
    (set! cont #f)
    (set! x 1)
    (set! y 1)
    (c 'new))
   (cons x y))))

Я тоже заменил (+ x y) с (cons x y) и вызвал продолжение с аргументом 'new вместо 0,

Я запустил этот фрагмент в Racket 5.2, используя несколько разных "языковых режимов", а также в Chicken 4.7. Вот результаты. Обе реализации оценивали x пункт инициализации первым и y пункт второй, хотя, как я уже сказал, это поведение не определено.

Ракетка с #lang r5rs а также #lang r6rs соответствует спецификации для Q2, и поэтому мы получаем "предполагаемый" результат переназначения 0 к другой переменной, когда вызывается продолжение. (При экспериментировании с r6rs мне нужно было обернуть окончательный результат в display чтобы увидеть, что это будет.)

Вот вывод трассировки:

(xinit #<undefined> #<undefined> #f)
(yinit #<undefined> #<undefined> #<continuation>)
(body 0 0 #<continuation>)
(body 0 new #f)
(0 . new)

Ракетка с #lang racket и Цыпленок не соответствует этому. Вместо этого после оценки каждого предложения инициализации оно присваивается соответствующей переменной. Таким образом, когда вызывается продолжение, оно заканчивается тем, что присваивает значение окончательному значению.

Вот вывод трассировки с некоторыми добавленными комментариями:

(xinit #<undefined> #<undefined> #f)
(yinit 0 #<undefined> #<continuation>) ; note that x has already been assigned
(body 0 0 #<continuation>)
(body 1 new #f) ; so now x is not re-assigned
(1 . new)

Теперь о том, что действительно требуют отчеты Схемы. Вот соответствующий раздел от R5RS:

Синтаксис библиотеки: (letrec )

Синтаксис: должен иметь форму (( )...), а должен быть последовательностью из одного или нескольких выражений. Ошибка <переменная> появляться более одного раза в списке связанных переменных.

Семантика: связаны с новыми местоположениями, содержащими неопределенные значения, оцениваются в результирующей среде (в некотором неопределенном порядке), каждая присваивается результату соответствующего , вычисляется в результирующей среде, и возвращается значение (значения) последнего выражения в . Каждая привязка имеет полное выражение letrec в качестве своей области, что позволяет определять взаимно рекурсивные процедуры.

(letrec ((even?
          (lambda (n)
            (if (zero? n)
                #t
                (odd? (- n 1)))))
         (odd?
          (lambda (n)
            (if (zero? n)
                #f
                (even? (- n 1))))))
  (even? 88))   
===>  #t

Одно ограничение на letrec очень важно: должна быть возможность оценивать каждый без присваивания или ссылки на значение любого . Если это ограничение нарушено, то это ошибка. Ограничение необходимо, потому что Scheme передает аргументы по значению, а не по имени. В наиболее распространенных случаях использования letrec все являются лямбда-выражениями, и ограничение выполняется автоматически.

Первое предложение разделов "Семантика" звучит так, как будто требуется, чтобы все назначения выполнялись после того, как все предложения инициализации были оценены; хотя, как я сказал ранее, это не так явно, как могло бы быть.

В R6RS и R7RS единственными существенными изменениями в этой части спецификации является добавление требования, которое:

продолжение каждого не должно вызываться более одного раза.

R6RS и R7RS также добавляют еще одну обязательную конструкцию, хотя: letrec*, Это отличается от letrec двумя способами. Во-первых, он определяет порядок оценки слева направо. Соответственно, указанное выше "ограничение" может быть несколько ослаблено. Теперь можно ссылаться на значения переменных, которым уже присвоены их начальные значения:

Должна быть предусмотрена возможность оценки каждого без присваивания или ссылки на значение соответствующего или любой из привязок, следующих за ним в .

Второе отличие заключается в нашем Q2. С letrec* спецификация теперь требует, чтобы назначения выполнялись после оценки каждого предложения инициализации. Вот первый параграф "Семантики" из R7RS (черновик 6):

Семантика: связаны с новыми местоположениями, каждая назначается в порядке слева направо результату оценки соответствующего , оценивается в результирующей среде, и значения последнего выражения в возвращаются. Несмотря на слева-направо оценку и порядок присваивания, каждая привязка имеет полное выражение letrec* в качестве своей области, что позволяет определять взаимно рекурсивные процедуры.

Так что курица и ракетка с помощью #lang racket --- и многие другие реализации --- кажется, на самом деле для реализации их letrec как letrec* s.

Answer 2

Причина того, что это оценивается в 1, из-за (set! x 1), Если вместо 1 вы установите x в 0, это приведет к нулю. Это потому, что переменная продолжения cont который хранит продолжение фактически хранит продолжение для y и не для x как это устанавливается на продолжение у после х.