Блог

Я не уверен, что понимаю разницу между парами операторов продолжения с разделителями prompt/control и reset/shift . Я понимаю некоторые основные примеры использования, но в этих примерах их поведение одинаковое.

Я нашел этот пример в «О динамической протяженности разделенных продолжений«, Дариуша Бирнакки и Оливье Данви:

 reset
  (fn () => shift (fn k => 10   (k 100))
            shift (fn k’ => 1))

prompt 
  (fn () => control (fn k => 10   (k 100))
            control (fn k’ => 1))
  

который я перевел в Scheme и успешно запустил с ожидаемыми результатами в Racket с использованием racket/control библиотеки:

 (reset  (  (shift   k  (  10 (k 100)))
           (shift   kk 1))) 
   ;; ==> 11

(prompt (  (control k  (  10 (k 100)))
           (control kk 1))) 
   ;; ==> 1
  

Их объяснение заключается в том, что,

В первом случае, когда k применяется, выражение shift (fn kk => 1) вычисляется в контексте, который может быть представлен функционально как fn v => 100 v и в мета-контексте, который может быть представлен как (fn v => 10 v) :: nil ; этот контекст захватывается и отбрасывается, а промежуточный ответ является 1 ; этот промежуточный ответ подключается к верхнему контексту из мета-контекста, т. е. fn v => 10 v Применяется к 1 ; следующим промежуточным ответом является 11 ; и это окончательный ответ, поскольку мета-контекст пуст.

Во втором случае, когда k применяется, элемент управления выражением (fn kk => 1) вычисляется в контексте, который является результатом составления fn v => 10 v и fn v => 100 v (и, следовательно, может быть представлен функционально как fn v => 10 (100 v) ), и в мета-контексте, который является пустым; этот контекст фиксируется и отбрасывается, и промежуточный ответ является 1 ; и это окончательный ответпоскольку мета-контекст пуст.

Меня смутила идея «мета-контекста», которую они определяют как

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

Я не понял идею «всех оставшихся вычислений» здесь, я не уверен, почему это было бы (fn v => 10 v) :: nil в первом примере (почему именно этот фрагмент кода?)

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

редактировать: я также вижу, что порядок выражений с двумя shift окружениями имеет значение: если я поменяю их местами, то результат будет 1 для обоих control и reset .

Сначала давайте вспомним правила сокращения обоих prompt/control и reset/shift .

 (prompt val) => val
(prompt E[control k expr]) => (prompt ((λk. expr) (λv. E[v])))
; E is free from prompt
  

 (reset val) => val
(reset E[shift k expr]) => (reset ((λk. expr) (λv. (reset E[v]))))
; E is free from reset
  

Мы видим, что reset и prompt они одинаковы. Однако второе правило немного отличается. reset/shift Пара вводит сброс, вокруг E[v] которого ограничивается область того, что может быть захвачено shift внутренним E[v]

Давайте теперь уменьшим оба выражения шаг за шагом.

Первый, shift/reduce :

 (reset (  (shift k (  10 (k 100))) (shift kk 1)))
=> (reset ((λk. (  10 (k 100))) (λv. (reset (  v (shift kk 1))))))
; Here, E[v] = (  v (shift kk 1))
=> (reset ((λk. (  10 (k 100))) (λv. (reset ((λkk. 1) (λw. (  v w)))))))
; Here, E'[w] = (  v w)
; Because of the reset, `E'[w]` catches only `(  v w)`
; which gets discarded right away.
=> (reset ((λk. (  10 (k 100))) (λv. (reset 1))))
=> (reset ((λk. (  10 (k 100))) (λv. 1)))
=> (reset (  10 ((λv. 1) 100)))
=> (reset (  10 1))
=> (reset 11)
=> 11
  

Во-вторых, prompt/control :

 (prompt  (  (control k (  10 (k 100))) (control kk 1)))
=> (prompt ((λk. (  10 (k 100))) (λv. (  v (control kk 1)))))
; Here, E[v] = (  v (control kk 1))
=> (prompt ((λkk. 1) (λw. ((λk. (  10 (k 100))) (λv. (  v w))))))
; Here, E'[w] = ((λk. (  10 (k 100))) (λv. (  v w)))
; Because there is no `prompt` the scope of `E'[w]` is much larger and
; everything in it get discarded right away
=> (prompt 1)
=> 1
  

В заключение, разница есть, только если есть по крайней мере 2 control / shift operators и shift уменьшает объем того, что может быть захвачено контекстом E' .