Продолжение с разделителями

В языках программирования продолжение с разделителями , составное продолжение или частичное продолжение — это «фрагмент» продолжения кадра , который был преобразован в функцию . В отличие от обычных продолжений, продолжения с разделителями возвращают значение и, таким образом, могут быть повторно использованы и составлены . Управляющие разделители, основа продолжений с разделителями, были введены Матиасом Феллейзеном в 1988 году. ^[1] хотя ранние намеки на составные и ограниченные продолжения можно найти в Кэролайн Талкотт Стэнфордской диссертации , опубликованной в 1984 году, Felleisen et al. , ^[2] Диссертация Феллейзена 1987 года, ^[3] и алгоритмы функционального поиска с возвратом , например, для сопоставления с образцом , для синтаксического анализа , на языке программирования Algebraic Logic Functional и в функциональных реализациях Пролога . где продолжение неудачи часто остается неявным, а причина успеха продолжения заключается в том, что оно компонуемо.

История

Продолжения с разделителями были впервые представлены Феллейзеном в 1988 году. ^[1] с оператором по имени ${\mathcal {F}}$ , впервые представленный в техническом отчете в 1987 году, ^[2] вместе с быстрой конструкцией $\#$ . Оператор был разработан как обобщение операторов управления, описанных в литературе, например: call/cc из Scheme , ISWIM J - оператор , Джон К. Рейнольдс . escape оператор и другие. Впоследствии сообществом исследователей языков программирования было изобретено множество конкурирующих операторов управления с разделителями, таких как prompt и control, ^[4] shift и reset, ^[5]^[6]cupto, ^[7] fcontrolи другие.

Примеры

В исследовательской литературе были предложены различные операторы для продолжений с разделителями. ^[8]

Одно независимое предложение ^[5] основан на стиле передачи продолжения (CPS), т. е. не на кадрах продолжения, и предлагает два оператора управления: shift и reset, которые порождают статические, а не динамические продолжения с разделителями. ^[9] reset оператор устанавливает предел продолжения, в то время как оператор shift оператор захватывает или конкретизирует текущее продолжение до самого внутреннего включающего reset. Например, рассмотрим следующий фрагмент в Scheme :

(* 2 (reset (+ 1 (shift k (k 5)))))

The reset ограничивает продолжение, которое shift захваты (по названию k в этом примере). Когда этот фрагмент выполняется, использование shift свяжет k к продолжению (+ 1 []) где [] представляет часть вычислений, которая должна быть заполнена значением. Это продолжение напрямую соответствует коду, окружающему shift вплоть до reset. Поскольку тело сдвига (т.е. (k 5)) немедленно вызывает продолжение, этот код эквивалентен следующему:

(* 2 (+ 1 5))

В общем, эти операторы могут кодировать более интересное поведение, например, возвращая захваченное продолжение. k как значение или вызов k несколько раз. shift оператор передает захваченное продолжение k к коду в его теле, который может либо вызвать его, создать его в результате или полностью игнорировать. Каким бы ни был результат, shift производит предоставлено сокровеннейшим reset, отбрасывая продолжение между reset и shift. Однако если продолжение вызывается, оно фактически переустанавливает продолжение после возврата в исходное состояние. reset. Когда все вычисления внутри reset завершено, результат возвращается продолжением с разделителями. ^[10] Например, в этом коде схемы :

 (reset (* 2 (shift k CODE)))

в любое время CODE вызывает (k N), (* 2 N) оценивается и возвращается.

Это эквивалентно следующему:

  (let ((k (lambda (x) (* 2 x)))) CODE)

Более того, как только все вычисления внутри shift завершается, продолжение отбрасывается и выполнение возобновляется снаружи reset. Поэтому,

 (reset (* 2 (shift k (k (k 4)))))

вызывает (k 4) сначала (который возвращает 8), а затем (k 8) (который возвращает 16). В этот момент shift выражение прекратилось, а остальная часть reset выражение отбрасывается. Таким образом, окончательный результат — 16.

Все, что происходит за пределами reset выражение скрыто, т.е. не подвержено влиянию передачи управления. Например, это возвращает 17:

 (+ 1 (reset (* 2 (shift k (k (k 4))))))

Продолжения с разделителями были впервые независимо описаны Felleisen et al. ^[2] и Джонсон. ^[11] С тех пор они использовались во многих областях, особенно при определении новых операторов управления ; увидеть Кейннека ^[12] для опроса.

Давайте рассмотрим более сложный пример. Позволять null быть пустым списком:

 (reset
   (begin
     (shift k (cons 1 (k (void)))) ;; (1)
     null))

Контекст, захваченный shift является (begin [*] null), где [*] это дыра, где kпараметр будет введен. Первый звонок из k внутри shift оценивает этот контекст с помощью (void) = #<void> замена отверстия, поэтому значение (k (void)) является (begin #<void> null) = null. Тело shift, а именно (cons 1 null) = (1), становится общей стоимостью reset выражение как конечный результат.

Усложняя этот пример, добавьте строку:

 (reset
   (begin
     (shift k (cons 1 (k (void))))
     (shift k (cons 2 (k (void))))
     null))

Если мы закомментируем первый shift, мы уже знаем результат, это (2); поэтому мы также можем переписать выражение следующим образом:

 (reset
   (begin
     (shift k (cons 1 (k (void))))
     (list 2)))

Это довольно знакомо и может быть переписано как (cons 1 (list 2)), то есть, (list 1 2).

Мы можем определить yield используя этот трюк:

(define (yield x) (shift k (cons x (k (void)))))

и использовать его при построении списков:

 (reset (begin
          (yield 1)
          (yield 2)
          (yield 3)
          null))    ;; (list 1 2 3)

Если мы заменим cons с stream-consмы можем создавать ленивые потоки:

  (define (stream-yield x) (shift k (stream-cons x (k (void)))))

  (define lazy-example
    (reset (begin
            (stream-yield 1)
            (stream-yield 2)
            (stream-yield 3)
            stream-null)))

Мы можем обобщить это и преобразовать списки в поток одним махом:

 (define (list->stream xs)
   (reset (begin
            (for-each stream-yield xs)
            stream-null)))

В более сложном примере ниже продолжение можно безопасно обернуть в тело лямбды и использовать как таковое:

 (define (for-each->stream-maker for-each) 
   (lambda (collection) 
     (reset (begin 
              (for-each (lambda (element) 
                          (shift k 
                            (stream-cons element (k 'ignored)))) 
                        collection) 
              stream-null))))

Часть между reset и shift включает в себя такие функции управления, как lambda и for-each; это невозможно перефразировать с помощью лямбда-выражений ^{[ почему? ]}.

Продолжения с разделителями также полезны в лингвистике : см. в разделе «Продолжения в лингвистике» подробности .

Проработанная иллюстрация `(shift k k)` идиома: обобщенная функция карри

Обобщенной функции карри присваивается некаррированная функция f и его арность (скажем, 3), и он возвращает значение (lambda (v1) (lambda (v2) (lambda (v3) (f v1 v2 v3)))). Этот пример принадлежит Оливье Данви и был разработан в середине 1980-х годов. ^[13]

Вот функция модульного теста, иллюстрирующая, что должна делать обобщенная функция карри:

(define test-curry
  (lambda (candidate)
    (and (= (candidate + 0)
            (+))
         (= ((candidate + 1) 1)
            (+ 1))
         (= (((candidate + 2) 1) 10)
            (+ 1 10))
         (= ((((candidate + 3) 1) 10) 100)
            (+ 1 10 100)))
         (= (((((candidate + 4) 1) 10) 100) 1000)
            (+ 1 10 100 1000))))

Эти модульные тесты проверяют, является ли каррирование вариативной функции + в n-арную каррированную функцию и применение результата к n аргументам дает тот же результат, что и применение + к этим n аргументам для n = 0, 1, 2, 3 и 4.

Следующая рекурсивная функция основана на аккумуляторе и в конечном итоге инвертирует аккумулятор перед применением заданной некаррированной функции. В каждом случае индукционного шага функция (lambda (v) ...) явно применяется к аргументу в каррированном приложении:

(define curry_a
  (lambda (f n)
    (if (< n 0)
        (error 'curry_a "negative input: ~s" n)
        (letrec ([visit (lambda (i a)
                          (if (= i 0)
                              (apply f (reverse a))
                              (lambda (v)
                                (visit (- i 1) (cons v a)))))])
          (visit n '())))))

Например, оценивая

(((curry_a + 2) 1) 10)

сводится к оценке

(((visit 2 '()) 1) 10)

что сводится к оценке

(((lambda (v) (visit 1 (cons v '()))) 1) 10)

который бета-сводится к оценке

((visit 1 (cons 1 '())) 10)

что сводится к оценке

((lambda (v) (visit 0 (cons v (cons 1 '())))) 10)

который бета-сводится к оценке

(visit 0 (cons 10 (cons 1 '())))

что сводится к оценке

(apply + (reverse (cons 10 (cons 1 '()))))

что сводится к оценке

(apply + (cons 1 (cons 10 '())))

что эквивалентно

(+ 1 10)

который дельта-редуцирует к результату, 11.

Следующая рекурсивная функция основана на продолжении и не требует обращения списка. Аналогично, на каждом этапе индукции функция (lambda (v) ...) явно применяется к аргументу в каррированном приложении:

(define curry_c
  (lambda (f n)
    (if (< n 0)
        (error 'curry_c "negative input: ~s" n)
        (letrec ([visit (lambda (i c)
                          (if (= i 0)
                              (c '())
                              (lambda (v)
                                (visit (- i 1) (lambda (vs)
                                                 (c (cons v vs)))))))])
          (visit n (lambda (vs)
                     (apply f vs)))))))

Итак, оценивая

(((curry_c + 2) 1) 10)

сводится к оценке

(((visit 2 (lambda (vs) (apply + vs))) 1) 10)

что сводится к оценке

(((lambda (v) (visit 1 (lambda (vs) ((lambda (vs) (apply + vs)) (cons v vs))))) 1) 10)

который бета-сводится к оценке

((visit 1 (lambda (vs) ((lambda (vs) (apply + vs)) (cons 1 vs)))) 10)

что сводится к оценке

((lambda (v) (visit 0 (lambda (vs) ((lambda (vs) ((lambda (vs) (apply + vs)) (cons 1 vs))) (cons v vs))))) 10)

который бета-сводится к оценке

(visit 0 (lambda (vs) ((lambda (vs) ((lambda (vs) (apply + vs)) (cons 1 vs))) (cons 10 vs))))

что сводится к оценке

((lambda (vs) ((lambda (vs) ((lambda (vs) (apply + vs)) (cons 1 vs))) (cons 10 vs))) '())

который бета-сводится к оценке

((lambda (vs) ((lambda (vs) (apply + vs)) (cons 1 vs))) (cons 10 '()))

который бета-сводится к оценке

((lambda (vs) (apply + vs)) (cons 1 (cons 10 '())))

который бета-сводится к оценке

(apply + (cons 1 (cons 10 '())))

что эквивалентно

(+ 1 10)

который дельта-редуцирует к результату, 11.

Следующая рекурсивная функция, curry_d, является прямым аналогом curry_c и включает в себя (shift k k) идиома, используя реализацию сдвига и сброса Анджея Филинского в терминах глобальной изменяемой ячейки и call/cc. ^[14] В каждом экземпляре шага индукции абстракция продолжения неявно применяется к аргументу в каррированном приложении:

(define curry_d
  (lambda (f n)
    (if (< n 0)
        (error 'curry_d "negative input: ~s" n)
        (letrec ([visit (lambda (i)
                          (if (= i 0)
                              '()
                              (cons (shift k k)
                                    (visit (- i 1)))))])
          (reset (apply f (visit n)))))))

Суть дела заключается в наблюдательной эквивалентности между (reset (... (shift k k) ...)) и (lambda (x) (reset (... x ...))) где x свежий, а многоточия представляют собой чистый контекст, т.е. тот, у кого нет управляющих эффектов.

Итак, оценивая

(((curry_d + 2) 1) 10)

сводится к оценке

(((reset (apply + (visit 2))) 1) 10)

что сводится к оценке

(((reset (apply + (cons (shift k k) (visit 1)))) 1) 10)

что по наблюдениям эквивалентно

(((lambda (x) (reset (apply + (cons x (visit 1))))) 1) 10)

который бета-сводится к оценке

((reset (apply + (cons 1 (visit 1)))) 10)

что сводится к оценке

((reset (apply + (cons 1 (cons (shift k k) (visit 0))))) 10)

что по наблюдениям эквивалентно

((lambda (x) (reset (apply + (cons 1 (cons x (visit 0)))))) 10)

который бета-сводится к оценке

(reset (apply + (cons 1 (cons 10 (visit 0)))))

что сводится к оценке

(reset (apply + (cons 1 (cons 10 '()))))

что эквивалентно

(reset (+ 1 10))

которая дельта-сводится к оценке

(reset 11)

что дает результат, 11.

Определение curry_d также иллюстрирует статические продолжения с разделителями. Этот статический экстент необходимо явно закодировать, если кто-то хочет использовать control и prompt: ^[15]

(define curry_cp
  (lambda (f n)
    (if (< n 0)
        (error 'curry_cp "negative input: ~s" n)
        (letrec ([visit (lambda (i)
                          (if (= i 0)
                              '()
                              (cons (control k (lambda (x) (prompt (k x))))
                                    (visit (- i 1)))))])
          (prompt (apply f (visit n)))))))

Ссылки

^ Перейти обратно: ^а ^б Феллейзен, Матиас (1988). «Теория и практика первоклассных подсказок». Принципы языков программирования . стр. 180–190. дои : 10.1145/73560.73576 . ISBN 0-89791-252-7 . S2CID 16705769 .
^ Перейти обратно: ^а ^б ^с Феллейзен, Матиас; Фридман, Дэниел П.; Дуба, Брюс; Маррилл, Джон (февраль 1987 г.). За пределами продолжений (PDF) (Технический отчет). Факультет компьютерных наук Университета Индианы . 216.
^ Феллейзен, Матиас (1987). Исчисления преобразования Lambda-v-CS: синтаксическая теория управления и состояния в императивных языках программирования высшего порядка (PDF) (Диссертация).
^ Ситарам, Дораи; Феллейзен, Матиас (1990). «Разграничители элементов управления и их иерархии» (PDF) . LISP и символьные вычисления . 3 : 67–99. дои : 10.1007/BF01806126 . S2CID 31430221 .
^ Перейти обратно: ^а ^б Дэнви, Оливье; Филинский, Анджей (1990). «Абстрагирующий контроль». LISP и функциональное программирование . стр. 151–160. дои : 10.1145/91556.91622 . ISBN 0-89791-368-Х . S2CID 6426191 .
^ Дэнви, Оливье (2006). Аналитический подход к программам как объектам данных (Диссертация). дои : 10.7146/аул.214.152 .
^ Реми, Дидье; Гюнтер, Карл; Рике, Джон Г. (1995). «Обобщение исключений и контроля в ML-подобных языках». Язык функционального программирования и архитектура компьютера .
^ См., например, операторов, предлагаемых racket/control ракеток Библиотека [1] ; следующие примеры могут работать в Racket, используя (require racket/control)
^ Бернацкий, Дариуш; Дэнви , Оливье; Шан, Чунг-чи (2006). «О статических и динамических размерах ограниченных продолжений» . Наука компьютерного программирования . 60 (3): 274–297.
^ Гасбихлер, Мартин; Спербер, Майкл (2002). Международная конференция по функциональному программированию . CiteSeerX 10.1.1.11.3425 .
^ Джонсон, Грегори Ф. (июнь 1987 г.). «GL: денотационный испытательный стенд с продолжениями и частичными продолжениями». Учеб. Симпозиум SIGPLAN '87 по устным переводчикам и методам перевода . стр. 218–225.
^ Кейннек, Кристиан (апрель 1994 г.). «Библиотека операторов управления высокого уровня». Lisp Pointers, ACM SIGPLAN Special Interest Publ. На Лиспе . 6 . Политехническая школа и INRIA -Рокенкур: 11–26. CiteSeerX 10.1.1.29.4790 .
^ https://delimited-continuation.github.io/a-generalized-curry-procedure.scm
^ Филинский, Анджей (1994). «Представление монад». Принципы языков программирования . стр. 446–457. дои : 10.1145/174675.178047 .
^ https://delimited-continuation.github.io/a-generalized-curry-procedure.rkt

Внешние ссылки

[felleisen88-1] Перейти обратно: ^а ^б Феллейзен, Матиас (1988). «Теория и практика первоклассных подсказок». Принципы языков программирования . стр. 180–190. дои : 10.1145/73560.73576 . ISBN 0-89791-252-7 . S2CID 16705769 .

[felleisen_87_tr-2] Перейти обратно: ^а ^б ^с Феллейзен, Матиас; Фридман, Дэниел П.; Дуба, Брюс; Маррилл, Джон (февраль 1987 г.). За пределами продолжений (PDF) (Технический отчет). Факультет компьютерных наук Университета Индианы . 216.

[felleisen-thesis-3] Феллейзен, Матиас (1987). Исчисления преобразования Lambda-v-CS: синтаксическая теория управления и состояния в императивных языках программирования высшего порядка (PDF) (Диссертация).

[4] Ситарам, Дораи; Феллейзен, Матиас (1990). «Разграничители элементов управления и их иерархии» (PDF) . LISP и символьные вычисления . 3 : 67–99. дои : 10.1007/BF01806126 . S2CID 31430221 .

[danvy90-5] Перейти обратно: ^а ^б Дэнви, Оливье; Филинский, Анджей (1990). «Абстрагирующий контроль». LISP и функциональное программирование . стр. 151–160. дои : 10.1145/91556.91622 . ISBN 0-89791-368-Х . S2CID 6426191 .

[danvy06-6] Дэнви, Оливье (2006). Аналитический подход к программам как объектам данных (Диссертация). дои : 10.7146/аул.214.152 .

[gunter95-7] Реми, Дидье; Гюнтер, Карл; Рике, Джон Г. (1995). «Обобщение исключений и контроля в ML-подобных языках». Язык функционального программирования и архитектура компьютера .

[Ref_-8] См., например, операторов, предлагаемых racket/control ракеток Библиотека [1] ; следующие примеры могут работать в Racket, используя (require racket/control)

[biernacki_et_al_scp-06-9] Бернацкий, Дариуш; Дэнви , Оливье; Шан, Чунг-чи (2006). «О статических и динамических размерах ограниченных продолжений» . Наука компьютерного программирования . 60 (3): 274–297.

[final-shift-10] Гасбихлер, Мартин; Спербер, Майкл (2002). Международная конференция по функциональному программированию . CiteSeerX 10.1.1.11.3425 .

[johnson_87_siit-11] Джонсон, Грегори Ф. (июнь 1987 г.). «GL: денотационный испытательный стенд с продолжениями и частичными продолжениями». Учеб. Симпозиум SIGPLAN '87 по устным переводчикам и методам перевода . стр. 218–225.

[queinnec_survey-12] Кейннек, Кристиан (апрель 1994 г.). «Библиотека операторов управления высокого уровня». Lisp Pointers, ACM SIGPLAN Special Interest Publ. На Лиспе . 6 . Политехническая школа и INRIA -Рокенкур: 11–26. CiteSeerX 10.1.1.29.4790 .

[13] ttps://delimited-continuation.github.io/a-generalized-curry-procedure.scm

[filinski94-14] Филинский, Анджей (1994). «Представление монад». Принципы языков программирования . стр. 446–457. дои : 10.1145/174675.178047 .

[15] ttps://delimited-continuation.github.io/a-generalized-curry-procedure.rkt

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

История

Примеры

Проработанная иллюстрация (shift k k) идиома: обобщенная функция карри

Ссылки

Внешние ссылки

Проработанная иллюстрация `(shift k k)` идиома: обобщенная функция карри