вызов с текущим продолжением
В 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 к этому.
Объект продолжения является значением первого класса и представлен как функция, применение функции единственной операцией которой является . Когда объект продолжения применяется к аргументу, существующее продолжение удаляется, а примененное продолжение восстанавливается на его месте, так что выполнение программы продолжается с той точки, в которой продолжение было захвачено, а аргумент продолжения затем становится «возвращаемое значение» вызова вызова/cc. Продолжения, созданные с помощью call/cc, могут вызываться более одного раза и даже из-за пределов динамического экстента приложения call/cc.
В информатике создание такого типа неявного состояния программы видимым как объект называется овеществлением . ( Схема не делает синтаксического различия между применением продолжений и функций.)
С помощью call/cc можно реализовать множество сложных операторов управления из других языков с помощью нескольких строк кода, например, McCarthy 's amb оператор для недетерминированного выбора , Prolog в стиле возврат , в стиле Simula 67 сопрограммы и их обобщения, Icon в стиле генераторы , или механизмы и потоки , или даже малоизвестный COMEFROM [ нужна ссылка ] .
Примеры
[ редактировать ]Как показано в следующем примере, call/cc можно использовать для эмуляции функции оператора return, известной из языков C , которая отсутствует в Scheme :
(define (f return)
(return 2)
3)
(f (lambda (x) x))
=> 3
(call-with-current-continuation f)
=> 2
Вызов f с аргументом обычной функции сначала применяет эту функцию к значению 2, а затем возвращает 3. Однако, когда f передается в call/cc (как в последней строке примера), применяется параметр (продолжение) к 2. заставляет выполнение программы перейти к точке вызова call/cc и заставляет call/cc возвращать значение 2. Затем оно выводится функцией отображения.
В следующем примере call/cc используется дважды: один раз для создания продолжения «возврата», как в первом примере, и один раз для приостановки итерации по списку элементов:
;; [LISTOF X] -> ( -> X u 'you-fell-off-the-end)
(define (generate-one-element-at-a-time lst)
;; Both internal functions are closures over lst
;; Internal variable/Function which passes the current element in a list
;; to its return argument (which is a continuation), or passes an end-of-list marker
;; if no more elements are left. On each step the function name is
;; rebound to a continuation which points back into the function body,
;; while return is rebound to whatever continuation the caller specifies.
(define (control-state return)
(for-each
(lambda (element)
(set! return (call-with-current-continuation
(lambda (resume-here)
;; Grab the current continuation
(set! control-state resume-here)
(return element))))) ;; (return element) evaluates to next return
lst)
(return 'you-fell-off-the-end))
;; (-> X u 'you-fell-off-the-end)
;; This is the actual generator, producing one item from a-list at a time.
(define (generator)
(call-with-current-continuation control-state))
;; Return the generator
generator)
(define generate-digit
(generate-one-element-at-a-time '(0 1 2)))
(generate-digit) ;; 0
(generate-digit) ;; 1
(generate-digit) ;; 2
(generate-digit) ;; you-fell-off-the-end
Каждый раз, когда цикл собирается обработать другой элемент из списка, функция захватывает текущее продолжение и присваивает его переменной control-state. Эта переменная изначально является замыканием , которое проходит по всем элементам списка. По мере выполнения вычислений оно становится замыканием, которое перебирает суффикс данного списка. Хотя использование «call/cc» не является необходимым для линейной коллекции, такой как [LISTOF X], код обобщается на любую коллекцию, которую можно просмотреть.
Вызов с текущим продолжением может также выражать другие сложные примитивы. Например, следующий пример выполняет совместную многозадачность с использованием продолжений:
;; Cooperative multitasking using call-with-current-continuation
;; in 25 lines of scheme
;; The list of threads waiting to run. This is a list of one
;; argument non-returning functions (continuations, mostly)
;; A continuation is a non-returning function, just like (exit),
;; in that it never gives up control to whatever called it.
(define ready-list '())
;; A non-returning function. If there is any other thread
;; waiting to be run, it causes the next thread to run if there
;; is any left to run, otherwise it calls the original exit
;; which exits the whole environment.
(define exit
;; The original exit which we override.
(let ((exit exit))
;; The overriding function.
(lambda ()
(if (not (null? ready-list))
;; There is another thread waiting to be run.
;; So we run it.
(let ((cont (car ready-list)))
(set! ready-list (cdr ready-list))
;; Since the ready-list is only non-returning
;; functions, this will not return.
(cont #f))
;; Nothing left to run.
;; The original (exit) is a non returning function,
;; so this is a non-returning function.
(exit)))))
;; Takes a one argument function with a given
;; argument and forks it off. The forked function's new
;; thread will exit if/when the function ever exits.
(define (fork fn arg)
(set! ready-list
(append ready-list
;; This function added to the
;; ready-list is non-returning,
;; since exit is non returning.
(list
(lambda (x)
(fn arg)
(exit))))))
;; Gives up control for the next thread waiting to be run.
;; Although it will eventually return, it gives up control
;; and will only regain it when the continuation is called.
(define (yield)
(call-with-current-continuation
;; Capture the continuation representing THIS call to yield
(lambda (cont)
;; Stick it on the ready list
(set! ready-list
(append ready-list
(list cont)))
;; Get the next thread, and start it running.
(let ((cont (car ready-list)))
(set! ready-list (cdr ready-list))
;; Run it.
(cont #f)))))
В 1999 году Дэвид Мадор (изобретатель языка программирования Unlambda ) случайно обнаружил 12-символьный термин Unlambda, использующий call/cc, который печатал все натуральные числа последовательно в унарном представлении: ``r`ci`.*`ci. [1] Эта программа и очевидная тайна, окружающая ее эффект, привлекли некоторое внимание и широко известны как головоломка Инь-Ян . [2] Перевод схемы, предоставленный Мадором, выглядит следующим образом:
(let* ((yin
((lambda (cc) (display #\@) cc) (call-with-current-continuation (lambda (c) c))))
(yang
((lambda (cc) (display #\*) cc) (call-with-current-continuation (lambda (c) c)))))
(yin yang))
Критика
[ редактировать ]Олег Киселев, автор реализации продолжения с разделителями для OCaml и разработчик интерфейса прикладного программирования (API) для манипулирования стеком с разделителями для реализации операторов управления, выступает за использование продолжений с разделителями вместо продолжений полного стека, которыми манипулирует вызов /cc: «Предложение call/cc в качестве основной функции управления, с точки зрения которой должны быть реализованы все остальные средства управления, оказывается плохой идеей. Производительность, утечки памяти и ресурсов, простота реализации, простота использования, простота рассуждения — все это аргументы против call/ куб.см.» [3]
Отношение к неконструктивной логике
[ редактировать ]Соответствие Карри-Ховарда между доказательствами и программами связывает call/cc с законом Пирса , который расширяет интуиционистскую логику до неконструктивной классической логики : ((α → β) → α) → α. Здесь ((α → β) → α) — тип функции f , которая может либо возвращать значение типа α напрямую, либо применять аргумент к продолжению типа (α → β). Поскольку существующий контекст удаляется при применении продолжения, тип β никогда не используется и может считаться ⊥, пустым типом.
Принцип устранения двойного отрицания ((α → ⊥) → ⊥) → α можно сравнить с вариантом call-cc, который ожидает, что его аргумент f всегда будет оценивать текущее продолжение, обычно не возвращая значение. Вложения классической логики в интуиционистскую логику связаны с переводом в стиле передачи продолжения . [4]
Языки, реализующие вызов/cc
[ редактировать ]См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Дэвид Мадор, «ошеломляющий звонок / копия»
- ^ Инь Ван, «Понимание загадки Инь-Ян»
- ^ «Аргумент против вызова/cc» .
- ^ Соренсен, Мортен Хейне; Уржичин, Павел (2007). «Классическая логика и операторы управления». Лекции по изоморфизму Карри-Говарда (1-е изд.). Бостон, Массачусетс: Эльзевир. ISBN 978-0444520777 .
- ^ «Подпись CONT» . Стандартный ML штата Нью-Джерси . Bell Labs, Lucent Technologies. 28 октября 1997 г. Проверено 15 мая 2019 г.
- ^ «Класс: Продолжение» . Ruby-doc.org . Неурогами, Джеймс Бритт . Проверено 15 мая 2019 г.
- ^ Ковальке, Оливер (2014). «Переключение контекста с помощью вызова/cc» . Boost.org . Проверено 15 мая 2019 г.
- ^ «R: Вызов с текущим продолжением» .
