Продолжение

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

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

История [ править ]

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

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

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

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

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

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

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

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

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

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

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

Использует [ править ]

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

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

Примеры [ править ]

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

 (  define   the-continuation   #f  ) 

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

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

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

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

Сопрограммы [ править ]

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

 ;;;   Наивная очередь для планирования потоков. 
   ;;;   Он содержит список продолжений, «ожидающих запуска». 

     (  define   *queue*   '  ()) 

    (  define   (  пустая очередь?  ) 
      (  null?   *queue*  )) 

    (  define   (  enqueue   x  ) 
      (  set!   *queue*   (  add   *queue*   (  list   x  )))) 

    (  define   (  удалить из очереди  ) 
      (  let   ((  x   (  car   *queue*  ))) 
        (  set!   *queue*   (  cdr   *queue*  )) 
        x  )) 

    ;;;   Это запускает новый поток (proc). 

     (  define   (  fork   proc  ) 
      (  call/cc 
       (  лямбда   (  k  ) 
         (  очередь   k  ) 
         (  proc  )))) 

    ;;;   Это передает процессор другому потоку, если он есть. 

     (  define   (  выход  ) 
      (  вызов/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]

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

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

Common Lisp : cl-cont . Также можно использовать пользовательские макросы
С# / ВБ.NET : async и await: «зарегистрируйте остальную часть метода как продолжение, а затем немедленно вернитесь к вызывающему объекту; задача вызовет продолжение после завершения». Асинхронное программирование для C#
Фактор : callcc0 и callcc1
Haskell продолжения : монада в Control.Monad.Cont
Haxe : haxe-продолжение
Иконка , Юникон : create, suspend, @ оператор: ковыражения
Java : Lightwolf Javaflow (требует манипуляций с байт-кодом во время выполнения или во время компиляции)
Котлин : Continuation
JavaScript Носорог : Continuation
Попугай : ContinuationЧВК; использует стиль передачи продолжения для всего потока управления
Perl : Coro и непрерывность
Пико : call(exp()) и continue(aContinuation, anyValue)
Python : PyPy _continuation.continulets
Ракетка : call-with-current-continuation (обычно сокращается до call/cc)
Рубин : callcc
Скала : scala.util.continuations обеспечивает shift/ reset
Схема : call-with-current-continuation (обычно сокращается до call/cc)
Болтовня : Continuation currentDo:; в большинстве современных сред Smalltalk продолжения могут быть реализованы без дополнительной поддержки VM.
Стандартный ML штата Нью-Джерси : SMLofNJ.Cont.callcc
Унлямбда : c, операция управления потоком для вызова с текущим продолжением

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

В веб-разработке [ править ]

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

Виды [ править ]

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

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

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

Недостатки [ править ]

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

Лингвистика [ править ]

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

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

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

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

См. также [ править ]

Звонок с текущим продолжением
Закрытие
РОДОМ ИЗ
Стиль продолжения прохождения
Поток управления
Сопрограмма
Продолжение с разделителями
Денотационная семантика
ИДТИ К
Стопка спагетти
Quajects — тип объекта, который позволяет устанавливать выбираемые продолжения (так называемые «выноски») для методов для каждого объекта посредством внедрения зависимостей .

Ссылки [ править ]

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

Дальнейшее чтение [ править ]

Питер Ландин . Обобщенный отчет о переходах и метках. Исследование системного программирования UNIVAC. Август 1965 г. Перепечатано в журнале Higher Order and Символические вычисления, 11(2):125-143, 1998 г., с предисловием Хайо Тилеке.
Дрю МакДермотт и Джерри Сассман . Справочное руководство Conniver, MIT AI Memo 259. Май 1972 г.
Дэниел Боброу : Модель структур управления для языков программирования искусственного интеллекта IJCAI 1973.
Карл Хьюитт , Питер Бишоп и Ричард Стайгер . Универсальный модульный формализм актеров для искусственного интеллекта IJCAI 1973.
Кристофер Стрейчи и Кристофер П. Уодсворт . Продолжение: Математическая семантика обработки полных прыжков. Техническая монография ПРГ-11. Вычислительная лаборатория Оксфордского университета. Январь 1974 г. Перепечатано в журнале Higher Order and Символические вычисления, 13(1/2):135–152, 2000 г., с предисловием Кристофера П. Уодсворта.
Джон К. Рейнольдс . Дефиниционные интерпретаторы для языков программирования высшего порядка. Материалы 25-й национальной конференции ACM, стр. 717–740, 1972. Перепечатано в журнале Higher-Order and Символические вычисления 11 (4): 363-397, 1998, с предисловием.
Джон К. Рейнольдс. О соотношении прямой и продолженной семантики. Материалы второго коллоквиума по автоматам, языкам и программированию. LNCS Том. 14, стр. 141–156, 1974.
Рейнольдс, Джон К. (1993). «Открытия продолжений» (PDF) . LISP и символьные вычисления . 6 (3/4): 233–248.
Джеральд Сассман и Гай Стил . СХЕМА: Интерпретатор расширенного лямбда-исчисления AI, Memo 349, Лаборатория искусственного интеллекта Массачусетского технологического института, Кембридж, Массачусетс, декабрь 1975 г. Перепечатано в журнале Higher-Order and Символические вычисления 11(4):405-439, 1998 г., с предисловием.
Роберт Хиеб , Р. Кент Дибвиг , Карл Брюггеман . Представление управления при наличии первоклассных продолжений. Материалы конференции ACM SIGPLAN '90 по проектированию и реализации языков программирования, стр. 66–77.
Уилл Клингер , Энн Хартаймер , Эрик Ост . Стратегии реализации для продолжения. Материалы конференции ACM 1988 года по LISP и функциональному программированию, стр. 124–131, 1988. Журнальная версия: Higher-Order and Символические вычисления, 12 (1): 7-45, 1999.
Кристиан Кеннек . Обратное обращение к инверсии управления, или Продолжение против странично-ориентированного программирования. Уведомления SIGPLAN 38 (2), стр. 57–64, 2003 г.

Внешние ссылки [ править ]

ACM SIGPLAN Семинар по продолжению 2011 года на ICFP .
Продолжение для скряг Сэма Руби
В книге «Teach Yourself Scheme in Fixnum Days» Дораи Ситарама есть хорошая глава, посвященная продолжению.
Продолжения и Stackless Python, Кристиан Тизмер
Онлайн-материалы четвертого семинара ACM SIGPLAN по продолжениям. Архивировано 2 декабря 2010 г. в Wayback Machine.
Онлайн-материалы Второго семинара ACM SIGPLAN по продолжению
Продолжение, функции и переходы. Архивировано 2 декабря 2010 г. на Wayback Machine.
http://okmij.org/ftp/continuations/ автор Олег Киселев
https://wiki.haskell.org/Continuations ^{[ постоянная мертвая ссылка ]}
Носорог с продолжениями
Продолжение на чистой Java из фреймворка веб-приложений RIFE
Продолжения отладки на чистой Java. Архивировано 16 мая 2021 г. на Wayback Machine из среды веб-приложений RIFE.
Сравнение генераторов, сопрограмм и продолжений, источник приведенного выше примера

[history_of_continuations-1] Перейти обратно: ^а ^б ^с ^д Рейнольдс 1993 г.

[2] С. Р. Рассел заметил, что eval может служить интерпретатором для LISP, быстро закодировал его вручную, и теперь у нас был язык программирования с интерпретатором. —Джон Маккарти, История LISP

[3] «Стив «Слизень» Рассел» . Компьютерная история .

[cont-sandwich-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 г.

[Queinnec-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 (семинар по продолжению, 2004 г.), или Чунг-чи Шань, « Лингвистические побочные эффекты». (в «Прямой композиционности», под ред. Криса Баркера и Полин Джейкобсон, стр. 132–163, Oxford University Press, 2007).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]