Блог

Мой вопрос касается аргументов функций в сочетании с продолжениями. В частности, какое поведение требуется и что разрешено.

Предположим, у вас есть вызов функции (f arg1 arg2 arg3) . Я понимаю, что реализация совместимой схемы позволяет оценивать аргументы arg1 arg2 , и arg3 в любом порядке. Все в порядке. Но теперь предположим, что, скажем, arg2 это создает продолжение. Как правило, некоторые другие аргументы могут быть оценены до arg2 оценки, а некоторые могут быть оценены после arg2 оценки.

Предположим, что реализация схемы, которую мы используем, arg1 была оценена ранее arg2 . Далее предположим, что f это изменяет его локальную копию первого аргумента. Позже, когда будет вызвано продолжение, созданное во время оценки arg2 , arg3 оно будет оценено снова и f будет вызвано.

Вопрос заключается в следующем: когда f вызывается второй раз через продолжение, какое значение должен/может иметь его первый аргумент? Должно ли это быть то же значение, которое arg1 было оценено? Или это может быть измененное значение из предыдущего вызова f ? (Опять же, в этом примере предполагается , что arg1 это оценивается раньше arg2 , но та же проблема применима к различным порядкам оценки аргументов. Т. Е. , если arg3 оценивается раньше arg2 , то вопрос относится arg3 к.)

Я пробовал это в нескольких реализациях схем, и получил разные результаты. Я принял во внимание различные порядки оценки аргументов (это легко отследить, если регистрировать выражения аргументов при их оценке). Игнорируя это различие, одна реализация всегда использовала исходные значения аргументов, а другая иногда использовала исходные значения аргументов, а иногда использовала измененные значения аргументов, в зависимости от того, был ли f встроенный лямбда-код против глобальная функция. По-видимому, разница обусловлена тем, копируются ли фактические аргументы в локальные переменные функции или они используются на месте.

Вот версия, в которой используется глобальная функция:

 (define (bar x cc y)
    (set! x (* x 2))
    (set! y (* y 3))
    (format #t "~a ~an" x y)
    cc)

(define (foo a b)
    (let* ((first #t)
           (cb (bar
                (  a 10)
                (call/cc (lambda (x) x))
                (  b 100))))
        (if first
            (begin
                (set! first #f)
                cb)
            (cb '()))))

(define cc (foo 1 2))
(call/cc cc)
(call/cc cc)
 

The above version uses the original argument values when calling
the function bar in both of the Scheme implementations that I tested.
The function bar sees 11 for the first argument and 102 for the
third argument each time it is called. The output is:

 22 306
22 306
22 306
 

Now, here is a version that replaces the global function with an inline
lambda:

 (define (foo a b)
    (let* ((first #t)
           (cb ((lambda (x cc y)
                    (set! x (* x 2))
                    (set! y (* y 3))
                    (format #t "~a ~an" x y)
                    cc)
                (  a 10)
                (call/cc (lambda (x) x))
                (  b 100))))
        (if first
            (begin
                (set! first #f)
                cb)
            (cb '()))))

(define cc (foo 1 2))
(call/cc cc)
(call/cc cc)
 

In one of the Scheme implementations I tested (BiwaScheme), this
behaves the same as the previous version. I.e., the called function
always sees the original argument values.

В другой реализации схемы (Gosh/Gauche) это поведение отличается от предыдущей версии. В этом случае вызываемая функция использует измененное значение первого аргумента. Другими словами, он обрабатывает встроенный лямбда-код по-другому, используя тот факт, что он может видеть определение функции, и, по-видимому, использует более прямой механизм передачи аргументов, который позволяет избежать необходимости их копирования. Поскольку он не копирует аргументы, те, которые были оценены до точки продолжения, сохраняют свои измененные значения. Лямбда видит 11 и 102 для первого и третьего аргументов в первый раз, затем он видит 22 и 102 во второй раз, 44 и 102 в третий раз. Таким образом, продолжение собирает измененные значения аргументов. На выходе получается:

 22 306
44 306
88 306
 

Итак, опять же, мой вопрос заключается в следующем: разрешено ли оба поведения
стандартом схемы (R6RS и/или R7RS)? Или Схема на самом деле требует
, чтобы исходные значения аргументов использовались при
вызове продолжения?

Обновление: Я первоначально сообщил, что реализация схемы Гоша дала три разных набора значений, показанных выше. Это было правдой, но только для определенных версий Гоша. Версия, которую я первоначально тестировал, была Gauche 0.9.3.3, в которой показаны три разных набора значений. Позже я нашел сайт, на котором есть три разные версии Gauche. Самый старый, Gauche 0.9.4, также показывает три различных набора значений. Но две более новые версии, Gauche 0.9.5 и Gauche 0.9.8, показывают повторяющиеся значения:

 22 306
22 306
22 306
 

Это довольно убедительно доказывает, что это считалось ошибкой, которая
с тех пор была исправлена (как и все говорили).

Продолжение буквально создаст копию стека в момент вызова call/cc, копию, которая также называется a control-point . Продолжение также хранит внутри него копию текущей динамической среды (точнее, пространства состояний из модуля dynamic-wind) и копию локального состояния потока.

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

Стек начинается с верхнего уровня (на самом деле есть другие пакеты, которые представляют собой продолжение процедур завершения работы, но они затрагиваются только после завершения кода), они не запоминаются при вызове call/cc. Итак, если в файле/repl вы дали 2 выражения, такие как

 (  (f 1) 2)
(display "ok")
 

каждое из этих выражений будет иметь свой собственный пакет, поэтому сохранение продолжения внутри f не приведет к переоценке display .

Я думаю, этого должно быть достаточно, чтобы проанализировать вашу проблему. Аргументы оцениваются в неопределенном порядке.

Редактировать:

Что касается ответа foo , то, конечно, он неправильный 22 306 44 306 88 306 , но он правильный 22 306 22 306 22 306 .

Я никогда не использовал ни одну из этих 2 реализаций. Это ошибка в реализации, которая не привязывается x после каждого вызова (лямбда (x cc y)…), так как захват продолжения выполняется вне лямбда().

Ошибка реализации кажется очевидной, она заключается в их генерации Scode-они остаются x в стеке, несмотря на то, что set! x он присутствовал, что должно быть показателем для выделения x в виде коробки в куче.

Хотя порядок оценки не определен в отчете, он не определен в коде CPS реализации. Например.

(f ( x 4) (call/cc cont-fun)) , где x-свободная переменная, становится либо:

 (call/ccamp; 
 cont-funamp;
 (lambda (v2)
   ( amp; x 
       4
       (lambda (v1)
         (famp; v1 v2 haltamp;))))
 

Или:

 ( amp; x 
    4
    (lambda (v1)
      (call/ccamp; 
       cont-funamp;
       (lambda (v2)
         (famp; v1 v2 haltamp;)))))
 

Так что если продолжение функция cont-funamp; мутирует, x это скажется на результате в версию, которая вычисляет аргументы слева направо, начиная с добавлением делается в продолжении, но во втором варианте мутации x не влияют на дополнение, поскольку значение уже вычислено в переданное значение v2 и в случае продолжения попадает в плен и повторите это значение никогда не будет пересчитано. В первой версии, хотя вы всегда вычисляете v1 , поэтому здесь изменение свободной переменной x повлияет на результат.

Если вы, как разработчик, хотите избежать этого, вы let* , черт возьми,:

 (let* ((a2 (call/cc cont-fun))
       (a1 (  x 4)))
  (f a1 a2))
 

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

Теперь я избегал использовать ваши мутирующие примеры, но на самом деле это просто перенаправление привязок. Вы слишком усложнили bar , так как set! это не имеет никакого длительного эффекта. Это всегда то же самое, что:

 (define (bar x cc y)
  (format #t "~a ~an" (* x 2) (* y 3))
  cc)
 

Продолжение застало в:

 (bar (  a 10)
     (call/cc (lambda (x) x))
     (  b 100))
 

Независимо от того, в каком порядке мы знаем, что вызов bar является окончательным продолжением после вычисления всех 3 выражений, а затем выполните тело let* первого и 2 последовательных раза.

Ваша вторая версия ничего не меняет, так как функция не зависит от свободных переменных. То, как последовательный вызов продолжения дал вам 44 и 88, безусловно, является неудачной оптимизацией компилятора. Он не должен этого делать. Я бы сообщил об этом как об ошибке.