вызов-с-текущим-продолжением
Оператор потока управления в функциональном программировании

В языке программирования Scheme процедура call-with-current-continuation , сокращенно call/cc , используется как оператор потока управления . Она была принята несколькими другими языками программирования.

Принимая функцию fв качестве единственного аргумента, (call/cc f)внутри выражения применяется к текущему продолжению выражения. Например, ((call/cc f) e2)эквивалентно применению fк текущему продолжению выражения. Текущее продолжение задается путем замены (call/cc f)переменной, cсвязанной лямбда-абстракцией, поэтому текущее продолжение — (lambda (c) (c e2)). Применение к ней функции fдает конечный результат (f (lambda (c) (c e2))).

В качестве дополнительного примера, в выражении (e1 (call/cc f))продолжение для подвыражения (call/cc f)— (lambda (c) (e1 c)), поэтому все выражение эквивалентно (f (lambda (c) (e1 c))). Другими словами, оно делает «снимок» текущего контекста управления или состояния управления программы как объекта и применяется fк нему. Объект продолжения является первоклассным значением и представлен как функция, с применением функции в качестве его единственной операции. Когда объект продолжения применяется к аргументу, существующее продолжение устраняется, а примененное продолжение восстанавливается на его месте, так что поток программы продолжится с точки, в которой было захвачено продолжение, а аргумент продолжения затем становится «возвращаемым значением» вызова call/cc. Продолжения, созданные с помощью call/cc, могут вызываться более одного раза и даже из-за пределов динамической области приложения call/cc.

В информатике превращение такого типа неявного состояния программы в видимый объект называется овеществлением . ( Scheme не делает синтаксических различий между применением продолжений и функций.)

С помощью call/cc можно реализовать множество сложных операторов управления из других языков с помощью нескольких строк кода, например, оператор Маккарти для недетерминированного выбора , возврат в стиле Prolog , сопрограммы в стиле Simula 67 и их обобщения, генераторы в стиле Icon , а также движки и потоки или даже малоизвестный COMEFROM [ требуется ссылка ] .amb

Примеры

Как показано в следующем примере, call/cc можно использовать для эмуляции функции оператора return, известного из языков в стиле C , который отсутствует в Scheme :

( определить ( f вернуть ) ( вернуть 2 ) 3 )       ( ф ( лямбда ( х ) х )) => 3    ( вызов-с-текущим-продолжением f ) => 2

Вызов f с обычным аргументом функции сначала применяет эту функцию к значению 2, а затем возвращает 3. Однако, когда f передается в call/cc (как в последней строке примера), применение параметра (продолжения) к 2 заставляет выполнение программы перейти к точке, где был вызван call/cc, и заставляет call/cc вернуть значение 2. Затем оно выводится функцией display.

В следующем примере call/cc используется дважды: один раз для генерации продолжения «возврата», как в первом примере, и один раз для приостановки итерации по списку элементов:

;; [LISTOF X] -> ( -> X u 'you-fell-off-the-end) ( define ( generate-one-element-at-a-time lst ) ;; Обе внутренние функции являются замыканиями над lst    ;; Внутренняя переменная/Функция, которая передает текущий элемент в списке ;; в свой аргумент return (который является продолжением) или передает маркер конца списка ;; если больше не осталось элементов. На каждом шаге имя функции ;; привязывается к продолжению, которое указывает обратно в тело функции, ;; в то время как return привязывается к любому продолжению, указанному вызывающим. ( define ( control-state return ) ( for-each ( lambda ( element ) ( set! return ( call-with-current-continuation ( lambda ( resume-here ) ;; Захват текущего продолжения ( set! control-state resume-here ) ( return element ))))) ;; (return element) вычисляется как next return lst ) ( return 'you-fell-off-the-end )) ;; (-> X u 'you-fell-off-the-end) ;; Это фактический генератор, создающий один элемент из a-list за раз. ( определить ( генератор ) ( вызов-с-текущим-продолжением- состояние-управления ))                                  ;; Верните генератор генератору ) ( определить генерацию-цифры ( генерировать-один-элемент-за-раз ' ( 0 1 2 )))     ( сгенерировать-цифру ) ;; 0 ( сгенерировать-цифру ) ;; 1 ( сгенерировать-цифру ) ;; 2 ( сгенерировать-цифру ) ;; ты-упал-с-конца

Каждый раз, когда цикл собирается обработать очередной элемент из списка, функция захватывает текущее продолжение и присваивает его переменной 'control-state'. Эта переменная изначально является замыканием , которое итерирует по всем элементам списка. По мере выполнения вычислений она становится замыканием, которое итерирует по суффиксу данного списка. Хотя использование "call/cc" необязательно для линейной коллекции, такой как [LISTOF X], код обобщается на любую коллекцию, которую можно обойти.

Call-with-current-continuation может также выражать другие сложные примитивы. Например, следующий пример выполняет кооперативную многозадачность с использованием продолжений:

;; Кооперативная многозадачность с использованием вызова-с-текущим-продолжением ;; в 25 строках схемы;; Список потоков, ожидающих запуска. Это список из одного ;; аргумента невозвращающих функций (в основном продолжений) ;; Продолжение — это невозвращающая функция, как и (exit), ;; в том смысле, что оно никогда не передает управление тому, кто его вызвал.( определить готовый список ' ())  ;; Невозвращаемая функция. Если есть какой-либо другой поток , ;; ожидающий запуска, он запускает следующий поток, если ;; осталось что-то для запуска, в противном случае он вызывает исходный выход , ;; который завершает всю среду. ( define exit ;; Исходный выход, который мы переопределяем. ( let (( exit exit )) ;; Переопределяющая функция. ( lambda () ( if ( not ( null? ready-list )) ;; Есть другой поток, ожидающий запуска. ;; Поэтому мы запускаем его. ( let (( cont ( car ready-list ))) ( set! ready-list ( cdr ready-list )) ;; Поскольку ready-list содержит только невозвращаемые ;; функции, этот не вернет ничего. ( cont #f )) ;; Нечего больше запускать. ;; Исходный (exit) — это невозвращаемая функция, ;; поэтому это невозвращаемая функция. ( exit )))))                              ;; Принимает функцию с одним аргументом с заданным ;; аргументом и разветвляет ее. Новый поток разветвленной функции ;; завершит работу, если/когда функция когда-либо завершится. ( define ( fork fn arg ) ( set! ready-list ( append ready-list ;; Эта функция, добавленная в ;; ready-list, не возвращается, ;; поскольку exit не возвращается. ( list ( lambda ( x ) ( fn arg ) ( exit ))))))            ;; Отдает управление следующему потоку, ожидающему запуска. ;; Хотя он в конечном итоге вернется, он отдает управление ;; и вернет его себе только при вызове продолжения. ( define ( yield ) ( call-with-current-continuation ;; Захватывает продолжение, представляющее ЭТОТ вызов yield ( lambda ( cont ) ;; Вставляет его в готовый список ( set! ready-list ( append ready-list ( list cont ))) ;; Получает следующий поток и запускает его выполнение. ( let (( cont ( car ready-list ))) ( set! ready-list ( cdr ready-list )) ;; Запускает его. ( cont #f )))))

В 1999 году Дэвид Мадор (изобретатель языка программирования Unlambda ) случайно обнаружил 12-символьный термин Unlambda, использующий call/cc, который печатал все натуральные числа последовательно в унарном представлении: ``r`ci`.*`ci. [1] Эта программа и очевидная таинственность, окружающая ее эффект, привлекли некоторое внимание и широко известны как головоломка инь-ян . [2] Перевод на Scheme, предоставленный Мадором, выглядит следующим образом:

( let* (( инь (( лямбда ( cc ) ( display # \ @ ) cc ) ( call-with-current-continuation ( lambda ( c ) c )))) ( ян (( лямбда ( cc ) ( display # \ * ) cc ) ( call-with-current-continuation ( lambda ( c ) c ))))) ( инь янь ))

Критика

Олег Киселев, автор реализации продолжения с разделителями для OCaml и разработчик интерфейса прикладного программирования (API) для манипуляции стеком с разделителями для реализации операторов управления, выступает за использование продолжений с разделителями вместо продолжений полного стека, которыми манипулирует call/cc: «Предложение call/cc в качестве основной функции управления, в терминах которой должны быть реализованы все остальные средства управления, оказывается плохой идеей. Производительность, утечки памяти и ресурсов, простота реализации, простота использования, простота рассуждений — все это говорит против call/cc». [3]

Отношение к неконструктивной логике

Соответствие Карри–Ховарда между доказательствами и программами связывает call/cc с законом Пирса , который расширяет интуиционистскую логику до неконструктивной классической логики : ((α → β) → α) → α. Здесь ((α → β) → α) — это тип функции f , которая может либо возвращать значение типа α напрямую, либо применять аргумент к продолжению типа (α → β). Поскольку существующий контекст удаляется при применении продолжения, тип β никогда не используется и может быть принят за ⊥, пустой тип.

Принцип устранения двойного отрицания ((α → ⊥) → ⊥) → α сравним с вариантом call-cc, который ожидает, что его аргумент f всегда будет оценивать текущее продолжение без обычного возврата значения. Вложения классической логики в интуиционистскую логику связаны с переводом стиля передачи продолжения . [4]

Языки, реализующие call/cc

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

Ссылки

  1. ^ Дэвид Мадор, «звонок/копия — ошеломляющий вызов»
  2. ^ Инь Ван, «Понимание загадки Инь-Ян»
  3. ^ «Аргумент против call/cc».
  4. ^ Sørensen, Morten Heine; Urzyczyn, Paweł (2007). "Классическая логика и операторы управления". Лекции по изоморфизму Карри-Ховарда (1-е изд.). Бостон, Массачусетс: Elsevier. ISBN 978-0444520777.
  5. ^ "Подпись CONT". Стандартный ML Нью-Джерси . Bell Labs, Lucent Technologies. 1997-10-28 . Получено 2019-05-15 .
  6. ^ "Класс: Продолжение". Ruby-doc.org . Neurogami, Джеймс Бритт . Получено 15.05.2019 .
  7. ^ Ковальке, Оливер (2014). «Переключение контекста с помощью вызова/cc». Boost.org . Получено 15.05.2019 .
  8. ^ "R: Вызов с текущим продолжением".
  • Краткое введение в вызов с текущим продолжением
  • Определение вызова с текущим продолжением в спецификации Scheme
  • Юмористическое объяснение вызова с текущим продолжением от Роба Уорнока в comp.lang.lisp Usenet
  • Кооперативная многозадачность в Scheme с использованием Call-CC
Взято с "https://en.wikipedia.org/w/index.php?title=Вызов-с-продолжением-текущего-состояния&oldid=1110924162"