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

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

История

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

Примеры

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

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

( * 2 ( сброс ( + 1 ( сдвиг k ( k 5 )))))        

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

( * 2 ( + 1 5 ))    

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

 ( сброс ( * 2 ( сдвиг k КОД )))     

всякий раз, когда CODEвызывается (k N), (* 2 N)оценивается и возвращается.

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

 ( пусть (( k ( лямбда ( x ) ( * 2 x )))) КОД )       

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

 ( сброс ( * 2 ( сдвиг k ( k ( k 4 )))))       

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

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

 ( + 1 ( сброс ( * 2 ( сдвиг k ( k ( k 4 ))))))         

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

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

 ( сброс ( начало ( сдвиг k ( cons 1 ( k ( void )))) ;; (1) ноль ))         

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

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

 ( сброс ( начало ( сдвиг k ( cons 1 ( k ( void )))) ( сдвиг k ( cons 2 ( k ( void )))) null ))              

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

 ( сброс ( начало ( сдвиг k ( cons 1 ( k ( void ))) ( список 2 )))         

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

Мы можем определить yieldс помощью этого трюка:

(определить (доходность x) (сдвиг k (cons x (k (void)))))

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

 ( сброс ( начало ( выход 1 ) ( выход 2 ) ( выход 3 ) ноль )) ;; (список 1 2 3)         

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

 ( define ( stream-yield x ) ( shift k ( stream-cons x ( k ( void ))))))         ( определить ленивый-пример ( reset ( begin ( stream-yield 1 ) ( stream-yield 2 ) ( stream-yield 3 ) stream-null )))          

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

 ( определить ( список->поток xs ) ( сброс ( начало ( для каждого потока-доходность xs ) поток-нуль )))        

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

 ( define ( for-each->stream-maker for-each ) ( лямбда ( коллекция ) ( сброс ( начало ( for-each ( лямбда ( элемент ) ( сдвиг k ( элемент потока-cons ( k 'игнорируется )))) коллекция ) поток-ноль ))))                        

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

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

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

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

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

( определить test-curry ( лямбда ( кандидат ) ( и ( = ( кандидат + 0 ) ( + )) ( = (( кандидат + 1 ) 1 ) ( + 1 )) ( = ((( кандидат + 2 ) 1 ) 10 ) ( + 1 10 )) ( = (((( кандидат + 3 ) 1 ) 10 ) 100 ) ( + 1 10 100 ))) ( = ((((( кандидат + 4 ) 1 ) 10 ) 100 ) 1000 ) ( + 1 10 100 1000 ))))                                                 

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

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

( определите curry_a ( лямбда ( f n ) ( if ( < n 0 ) ( error 'curry_a "negative input: ~s" n ) ( letrec ([ визит ( лямбда ( i a ) ( if ( = i 0 ) ( применить f ( обратный a )) ( лямбда ( v ) ( посещение ( -i 1 ) ( cons v a ) ))))]) ( посещение n ' ())))))                                     

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

((( curry_a + 2 ) 1 ) 10 )    

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

((( посещение 2 ' ()) 1 ) 10 )    

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

((( лямбда ( v ) ( посещение 1 ( cons v ' ()))) 1 ) 10 )        

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

(( посещение 1 ( минусы 1 ' ())) 10 )     

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

(( лямбда ( v ) ( посещение 0 ( cons v ( cons 1 ' ())))) 10 )         

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

( посещение 0 ( минусы 10 ( минусы 1 ' ())))      

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

( применить + ( обратный ( cons 10 ( cons 1 ' ()))))       

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

( применить + ( минусы 1 ( минусы 10 ' ())))      

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

( + 1 10 )  

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

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

( define curry_c ( лямбда ( f n ) ( if ( < n 0 ) ( ошибка 'curry_c "отрицательный ввод: ~s" n ) ( letrec ([ посещение ( лямбда ( i c ) ( if ( = i 0 ) ( c ' ()) ( лямбда ( v ) ( посещение ( -i 1 ) ( лямбда ( vs ) ( c ( cons v vs )))))))))]) ( посещение n ( лямбда ( vs ) ( применить f vs ) )) ))))                                          

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

((( curry_c + 2 ) 1 ) 10 )    

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

((( посещение 2 ( лямбда ( vs ) ( применить + vs ))) 1 ) 10 )        

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

((( лямбда ( v ) ( посещение 1 ( лямбда ( vs ) (( лямбда ( vs ) ( применить + vs )) ( cons v vs ))))) 1 ) 10 )               

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

(( посещение 1 ( лямбда ( vs ) (( лямбда ( vs ) ( применить + vs )) ( минусы 1 vs )))) 10 )            

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

(( лямбда ( v ) ( посещение 0 ( лямбда ( vs ) (( лямбда ( vs ) (( лямбда ( vs ) ( применить + vs )) ( минусы 1 vs ))) ( минусы v vs ))))) 10 )                   

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

( посещение 0 ( лямбда ( vs ) (( лямбда ( vs ) (( лямбда ( vs ) ( применить + vs )) ( минусы 1 vs ))) ( минусы 10 vs ))))                

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

(( лямбда ( vs ) (( лямбда ( vs ) (( лямбда ( vs ) ( применить + vs )) ( cons 1 vs ))) ( cons 10 vs ))) ' ())               

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

(( лямбда ( vs ) (( лямбда ( vs ) ( применить + vs )) ( cons 1 vs ))) ( cons 10 ' ()))            

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

(( лямбда ( vs ) ( применить + vs )) ( cons 1 ( cons 10 ' ())))         

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

( применить + ( минусы 1 ( минусы 10 ' ())))      

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

( + 1 10 )  

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

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

( define curry_d ( лямбда ( f n ) ( if ( < n 0 ) ( ошибка 'curry_d "отрицательный ввод: ~s" n ) ( letrec ([ посещение ( лямбда ( i ) ( if ( = i 0 ) ' () ( cons ( shift k k ) ( посещение ( -i 1 ) ))))]) ( сброс ( применить f ( посещение n )))))))                                  

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

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

((( curry_d + 2 ) 1 ) 10 )    

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

((( сбросить ( применить + ( посетить 2 ))) 1 ) 10 )      

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

((( сброс ( применить + ( минусы ( сдвиг k k ) ( посещение 1 )))) 1 ) 10 )          

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

((( лямбда ( x ) ( сброс ( применить + ( минусы x ( посещение 1 ))))) 1 ) 10 )          

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

(( сброс ( применить + ( минусы 1 ( посещение 1 )))) 10 )       

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

(( сброс ( применить + ( минусы 1 ( минусы ( сдвиг k k ) ( посещение 0 ))))) 10 )           

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

(( лямбда ( x ) ( сброс ( применить + ( минусы 1 ( минусы x ( посещение 0 )))))) 10 )           

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

( сброс ( применить + ( минусы 1 ( минусы 10 ( посещение 0 )))))        

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

( сброс ( применить + ( минусы 1 ( минусы 10 ' ()))))       

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

( сброс ( + 1 10 ))   

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

( сброс 11 ) 

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

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

( define curry_cp ( лямбда ( f n ) ( if ( < n 0 ) ( ошибка 'curry_cp "отрицательный ввод: ~s" n ) ( letrec ([ посещение ( лямбда ( i ) ( if ( = i 0 ) ' () ( cons ( control k ( лямбда ( x ) ( подсказка ( k x )))) ( посещение ( - i 1 )))))]) ( подсказка ( применить f ( посещение n )))))))                                      

Рекомендации

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

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

• Учебник по составным продолжениям на SchemeWiki
• Ограниченные продолжения в операционных системах, Олег Киселев и Чун-чи Шань
• Собственные продолжения с разделителями в OCaml (байт-код и собственный код)
• Shift/Reset для самых маленьких (на русском языке)
• Несколько хороших статей о продолжениях с разделителями и первоклассных макросах