stringtranslate.com

Продолжение

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

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

История

Самое раннее описание продолжений было сделано Адрианом ван Вейнгаарденом в сентябре 1964 года. Вейнгаарден выступил на рабочей конференции ИФИП по языкам формального описания языка, проходившей в Баден-бай-Вене, Австрия. В рамках формулировки препроцессора Algol 60 он призвал к преобразованию правильных процедур в стиль передачи продолжения , [1] хотя он не использовал это название, и его намерением было упростить программу и, таким образом, сделать ее результат более удобным. прозрачный.

Кристофер Стрейчи , Кристофер П. Уодсворт и Джон К. Рейнольдс выдвинули термин « продолжение» на видное место в своей работе в области денотационной семантики , которая широко использует продолжения, позволяющие анализировать последовательные программы с точки зрения семантики функционального программирования . [1]

Стив Рассел [2] изобрел продолжение в своей второй реализации Lisp для IBM 704 , хотя и не дал ему названия. [3]

Рейнольдс (1993) дает полную историю открытия продолжений.

Первоклассные продолжения

Первоклассные продолжения — это способность языка полностью контролировать порядок выполнения инструкций. Их можно использовать для перехода к функции, вызвавшей вызов текущей функции, или к функции, которая ранее завершилась. Первоклассное продолжение можно рассматривать как сохранение состояния выполнения программы. Важно отметить, что настоящие первоклассные продолжения не сохраняют данные программы – в отличие от образа процесса – только контекст выполнения. Это иллюстрируется описанием «сэндвича продолжения»:

Допустим, вы сидите на кухне перед холодильником и думаете о сэндвиче. Вы тут же берете продолжение и кладете его в карман. Затем вы достаете из холодильника немного индейки и хлеба и делаете себе бутерброд, который сейчас лежит на прилавке. Вы вызываете продолжение в кармане и снова оказываетесь перед холодильником, думая о сэндвиче. Но, к счастью, на прилавке лежит сэндвич, а все материалы, из которых он был приготовлен, исчезли. Итак, вы едите это. :-) [4]

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

Scheme была первой полноценной производственной системой, обеспечивающей сначала «catch» [1] , а затем call/cc . Брюс Дуба представил call/cc в SML .

Продолжения также используются в моделях вычислений, включая денотационную семантику , модель актера , исчисление процессов и лямбда-исчисление . Эти модели полагаются на то, что программисты или инженеры-семантики пишут математические функции в так называемом стиле передачи продолжения . Это означает, что каждая функция использует функцию, которая представляет остальную часть вычислений относительно вызова этой функции. Чтобы вернуть значение, функция вызывает эту «функцию продолжения» с возвращаемым значением; чтобы прервать вычисление, он возвращает значение.

Функциональные программисты, которые пишут свои программы в стиле передачи продолжения, получают выразительную возможность манипулировать потоком управления произвольными способами. Цена состоит в том, что им приходится вручную поддерживать инварианты управления и продолжений, что может быть очень сложной задачей (но см. «стиль передачи продолжения» ниже).

Использование

Продолжения упрощают и уточняют реализацию нескольких распространенных шаблонов проектирования , включая сопрограммы / зеленые потоки и обработку исключений , предоставляя базовый низкоуровневый примитив, который объединяет эти, казалось бы, не связанные между собой шаблоны. Продолжения могут обеспечить элегантные решения некоторых сложных проблем высокого уровня, таких как программирование веб-сервера, поддерживающего несколько страниц, доступ к которым осуществляется с помощью кнопок «Вперед» и «Назад» и по ссылкам. Веб-фреймворк Smalltalk Seaside эффективно использует продолжения, позволяя программировать веб-сервер в процедурном стиле, переключая продолжения при переключении страниц .

Существуют и более сложные конструкции, для которых «продолжение дает элегантное описание» [1] . Например, в C longjmp можно использовать для перехода от середины одной функции к другой, при условии, что вторая функция находится глубже в стеке (если она ожидает возврата от первой функции, возможно, среди других). Другие более сложные примеры включают сопрограммы в Simula 67 , Lua и Perl ; тасклеты в Stackless Python ; генераторы в Icon и Python ; продолжения в Scala (начиная с версии 2.8); волокна в Ruby (начиная с версии 1.9.1); механизм возврата в Прологе ; монады в функциональном программировании ; и нити .

Примеры

Язык программирования Scheme включает оператор управления call-with-current-continuation (сокращенно: call/cc), с помощью которого программа Scheme может манипулировать потоком управления:

 ( определить продолжение #f )   ( define ( test ) ( let (( i 0 )) ; call/cc вызывает свой первый аргумент функции, передавая ; переменную продолжения, представляющую эту точку в ; программу в качестве аргумента этой функции. ; ; В этом случае функция Аргумент присваивает это ; продолжение переменной the-continuation. ; ( call/cc ( лямбда ( k ) ( set! the-continuation k ))) ; ; В следующий раз, когда будет вызвана функция-continuation, мы начнем здесь. ( set! я ( + я 1 )) я ))

Используя вышеизложенное, следующий блок кода определяет функцию test, которая the-continuationсама устанавливает свое будущее состояние выполнения:

 > ( тест ) 1 > ( -продолжение ) 2 > ( -продолжение ) 3 > ; сохраняет текущее продолжение (которое далее выведет 4) подальше > ( defineother -continuation the-continuation ) > ( test ) ; сбрасывает-продолжение 1 > ( продолжение ) 2 > ( другое-продолжение ) ; использует ранее сохраненное продолжение 4

Более подробное введение в этот механизм см. в разделе call-with-current-continuation .

Сопрограммы

В этом примере показано возможное использование продолжений для реализации сопрограмм в виде отдельных потоков. [5]

 ;;; Наивная очередь для планирования потоков. ;;; Он содержит список продолжений, «ожидающих запуска».  ( определить *очередь* ' ())   ( define ( пустая очередь? ) ( null? *queue* )    ( определить ( поставить в очередь x ) ( установить! *очередь* ( добавить *очередь* ( список x ))))         ( определить ( удалить из очереди ) ( let (( x ( car *queue* ))) ( set! *queue* ( cdr *queue* )) x ))           ;;; Это запускает новый поток (proc). ( define ( fork proc ) ( call/cc ( лямбда ( k ) ( очередь k ) ( proc ))))         ;;; Это передает процессор другому потоку, если он есть. ( определить ( выход ) ( вызов/cc ( лямбда ( k ) ( постановка в очередь k ) (( удаление из очереди )))))        ;;; Это завершает текущий поток или всю программу ;;; если других тем не осталось.  ( определить ( выход из потока ) ( если ( пустая очередь? ) ( выход ) (( удалить из очереди ))))

Определенные выше функции позволяют определять и выполнять потоки посредством совместной многозадачности , то есть потоков, которые передают управление следующему в очереди:

 ;;; Тело типичного потока Scheme, выполняющего следующие действия: ( define ( do-stuff-n-print str ) ( лямбда () ( let цикл (( n 0 )) ( format #t "~A ~A \n " str n ) ( выход ) ( цикл ( + n 1 ) ))))                   ;;; Создайте два потока и запустите их работу. ( fork ( do-stuff-n-print "This is AAA" )) ( fork ( do-stuff-n-print "Hello from BBB" )) ( thread-exit )

Предыдущий код выдаст следующий результат:

Это ААА 0 Привет от БББ 0 Это ААА 1 Привет от БББ 1 Это ААА 2 Привет от БББ 2 ...

Выполнение

Программа должна выделить место в памяти для переменных, которые используют ее функции. Большинство языков программирования используют стек вызовов для хранения необходимых переменных, поскольку он позволяет быстро и просто выделять и автоматически освобождать память. Другие языки программирования используют для этого кучу , что обеспечивает гибкость при выделении и освобождении памяти за счет более высоких затрат. Обе эти реализации имеют преимущества и недостатки в контексте продолжений. [6]

Поддержка языков программирования

Многие языки программирования имеют первоклассные продолжения под разными именами; конкретно:

На любом языке, который поддерживает замыкания и правильные хвостовые вызовы , можно писать программы в стиле передачи продолжения и вручную реализовывать вызов /cc. (В стиле передачи продолжения call/cc становится простой функцией, которую можно написать с помощью лямбда .) Это особенно распространенная стратегия в Haskell , где легко создать « монаду передачи продолжения » (например, Contмонаду и ContTпреобразователь монад в mtlбиблиотеке). Поддержка правильных хвостовых вызовов необходима, поскольку в стиле передачи продолжения ни одна функция никогда не возвращает результат; все вызовы являются хвостовыми вызовами.

В веб-разработке

Одной из областей, в которой продолжения нашли практическое применение, является веб-программирование . [7] [8] Использование продолжений защищает программиста от отсутствия состояния протокола HTTP . В традиционной модели веб-программирования отсутствие состояния отражается на структуре программы, что приводит к коду, построенному на основе модели, которая очень плохо подходит для выражения вычислительных задач. Таким образом, продолжения позволяют использовать код, обладающий полезными свойствами, связанными с инверсией управления , избегая при этом связанных с ним проблем. «Обратное обращение к инверсии управления, или Продолжения против странично-ориентированного программирования» [9] — это статья, которая представляет собой хорошее введение в продолжения, применяемые в веб-программировании.

Виды

Поддержка продолжений широко варьируется. Язык программирования поддерживает повторно вызываемые продолжения, если продолжение можно вызывать повторно (даже после того, как оно уже вернулось). Повторно вызываемые продолжения были введены Питером Дж. Лэндином с использованием его оператора J (для перехода), который мог переносить поток управления обратно в середину вызова процедуры. Повторно вызываемые продолжения на языке Racket также называются «реентерабельными» . Однако такое использование термина «реентерабельный» можно легко спутать с его использованием при обсуждении многопоточности .

Более ограниченный вид — это escape-продолжение , которое можно использовать для перехода из текущего контекста в окружающий. Многие языки, которые явно не поддерживают продолжения, поддерживают обработку исключений , что эквивалентно escape-продолжениям и может использоваться для тех же целей. C setjmp/longjmpтакже эквивалентны: их можно использовать только для раскручивания стека. Escape-продолжения также можно использовать для устранения хвостовых вызовов .

Одним из обобщений продолжений являются продолжения с разделителями . Операторы продолжения, например, call/ccзахватывают все оставшиеся вычисления в заданной точке программы и не предоставляют возможности ограничить этот захват. Операторы продолжения с разделителями решают эту проблему, предоставляя два отдельных механизма управления: приглашение , ограничивающее операцию продолжения, и оператор повторения, такой как shiftили control. Таким образом, продолжения, записанные с помощью операторов-разделителей, представляют собой лишь часть контекста программы.

Недостатки

Продолжения являются функциональным выражением оператора GOTO , и здесь применяются те же предостережения. [10] Хотя они являются разумным вариантом в некоторых особых случаях, таких как веб-программирование, использование продолжений может привести к созданию кода, за которым будет трудно следить. Фактически, эзотерический язык программирования Unlambda включает вызов с текущим продолжением в качестве одной из своих функций исключительно потому, что выражения, связанные с ним, «как правило, безнадежно трудно отследить». [11] Внешние ссылки ниже иллюстрируют эту концепцию более подробно.

Лингвистика

В книге «Продолжения и природа количественной оценки» Крис Баркер представил «гипотезу продолжения», согласно которой

некоторые лингвистические выражения (в частности, QNP [квантификационные именные группы]) имеют денотаты, которые манипулируют своими собственными продолжениями. [12]

Баркер утверждал, что эту гипотезу можно использовать для объяснения таких явлений, как двойственность значений NP (например, тот факт, что QNP «каждый» ведет себя совсем иначе, чем неквантификационное существительное «Боб», внося свой вклад в смысл такого предложения, как «Алиса видит [Боба/всех]»), смещение области видимости (например, что «капля дождя упала на каждую машину» обычно интерпретируется как , а не как ) и двусмысленность области действия (что предложение типа «кто-то видел всех» может быть двусмысленным). между и ). Он также заметил, что эта идея является в некотором смысле естественным продолжением подхода Ричарда Монтегю в «Правильном подходе к количественной оценке в обычном английском языке» (PTQ), написав, что «оглядываясь назад, можно сказать, что ограниченная форма передачи продолжения является ясно различима в основе PTQ-трактовки NP как обобщенных кванторов Монтегю (1973).

Степень, в которой продолжения могут использоваться для объяснения других общих явлений естественного языка, является темой текущих исследований. [13]

Смотрите также

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

  1. ^ abcd Рейнольдс 1993
  2. ^ С. Р. Рассел заметил, что eval может служить интерпретатором для LISP, быстро закодировал его вручную, и теперь у нас был язык программирования с интерпретатором. —Джон Маккарти, История LISP
  3. ^ "Стив "Слизень" Рассел" . Компьютерная история .
  4. ↑ Палмер, Люк (29 июня 2004 г.). "undo()? (пример "сэндвича с продолжением")". perl.perl6.language (группа новостей) . Проверено 4 октября 2009 г.
  5. ^ Хейнс, Коннектикут, Фридман, Д. П. и Ванд, М. 1984. Продолжения и сопрограммы. В материалах симпозиума ACM 1984 г. по LISP и функциональному программированию (Остин, Техас, США, 6–08 августа 1984 г.). ЛФП '84. ACM, Нью-Йорк, штат Нью-Йорк, 293–298.
  6. ^ «Вызов с текущим продолжением для программистов на C» . Сообщество-Схема-Вики . 12 октября 2008 г.
  7. ^ «Список чтения по XML и веб-программированию». Архивировано из оригинала 14 июня 2010 г. Проверено 3 августа 2006 г.
  8. ^ «Веб-программирование с продолжениями» (PDF) . Архивировано из оригинала (PDF) 5 сентября 2012 г. Проверено 5 сентября 2012 г.
  9. ^ Christian.Queinnec (2003) Обратное обращение к инверсии управления или Продолжение против странично-ориентированного программирования
  10. ^ Куигли, Джон (сентябрь 2007 г.). «Продолжение вычислений» (PDF) . п. 38.
  11. ^ Мадор, Дэвид. «Язык программирования Unlambda». www.madore.org . Проверено 19 июня 2021 г.
  12. ^ Крис Баркер, Продолжения и природа количественной оценки, 2002 Семантика естественного языка 10: 211-242.
  13. ^ См., например, Криса Баркера, «Продолжение на естественном языке», архивировано 24 августа 2007 г. в Wayback Machine (Continuations Workshop, 2004 г.), или Чунг-чи Шан, «Лингвистические побочные эффекты» (в «Прямой композиционности», под ред. Криса Баркера и Полин Джейкобсон, стр. 132–163, Oxford University Press, 2007).

дальнейшее чтение

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