Я несколько раз пытался понять концепцию продолжения и звоните/куб.см. Каждая попытка была неудачной. Может кто-нибудь, пожалуйста, объясните мне эти понятия, в идеале, более реалистичные примеры, чем в Википедии или в других сообщениях SO.
У меня есть опыт в веб-программировании и ООП. Я также понимаю 6502 сборку и имел небольшую рану с Эрланг. Тем не менее, я не могу обернуть голову вокруг вызова/cc.
Послушайте, я нашел это продолжение прохождения лучшего описания по этой теме.
Вот лишенная подробностей копия этой статьи:
Author: Marijn Haverbeke Date: July 24th 2007
Функция вызова схемы с текущим продолжением позволяет захватить вычисление, состояние стека вызовов, как это было, и возобновить то же самое состояние в более позднее время. Вдобавок к такому примитиву могут быть реализованы различные формы обработки исключений и трюки типа longjmp на языке C.
function traverseDocument(node, func) { func(node); var children = node.childNodes; for (var i = 0; i < children.length; i++) traverseDocument(children[i], func); } function capitaliseText(node) { if (node.nodeType == 3) // A text node node.nodeValue = node.nodeValue.toUpperCase(); } traverseDocument(document.body, capitaliseText);Это можно преобразовать следующим образом: мы добавляем дополнительный аргумент к каждой функции, который будет использоваться для передачи продолжения функции. Это продолжение представляет собой значение функции, представляющее действия, которые должны произойти после того, как функция "вернется". Стек (call) становится устаревшим в стиле передачи продолжения - когда функция вызывает другую функцию, это последнее, что она делает. Вместо того, чтобы ждать возврата вызываемой функции, он помещает любую работу, которую он хочет сделать впоследствии, в продолжение, которое он передает функции.
function traverseDocument(node, func, c) { var children = node.childNodes; function handleChildren(i, c) { if (i < children.length) traverseDocument(children[i], func, function(){handleChildren(i + 1, c);}); else c(); } return func(node, function(){handleChildren(0, c);}); } function capitaliseText(node, c) { if (node.nodeType == 3) node.nodeValue = node.nodeValue.toUpperCase(); c(); } traverseDocument(document.body, capitaliseText, function(){});Представьте, что у нас есть огромный документ, который нужно использовать. Простое его прохождение занимает пять секунд, а зависание браузера на пять секунд - довольно плохой стиль. Рассмотрим эту простую модификацию capitaliseText (не обращайте внимания на уродливый глобал):
var nodeCounter = 0; function capitaliseText(node, c) { if (node.nodeType == 3) node.nodeValue = node.nodeValue.toUpperCase(); nodeCounter++; if (nodeCounter % 20 == 0) setTimeout(c, 100); else c(); }Теперь, каждые двадцать узлов, вычисления прерываются на сто миллисекунд, чтобы дать интерфейсу браузера момент для ответа на пользовательский ввод. Очень примитивная форма потоков - вы даже можете запускать несколько вычислений одновременно, как это.
Более полезное применение этого связано с XMLHttpRequests или различными хакингами тегов IFRAME и SCRIPT, используемыми для их моделирования. Это всегда требует, чтобы один работал с каким-то механизмом обратного вызова для обработки данных, которые сервер отправляет обратно. В простых случаях подойдет тривиальная функция, или можно использовать несколько глобальных переменных для хранения состояния вычислений, которое должно быть возобновлено после возвращения данных. В сложных случаях, например, когда данные используются функцией, которая должна возвращать вызывающей стороне некоторое значение, продолжения значительно упрощают ситуацию. Вы просто регистрируете продолжение как обратный вызов, и ваши вычисления возобновляются после завершения запроса.
Чтобы сравнить его с C, текущее продолжение похоже на текущее состояние стека. Он имеет все функции, ожидающие завершения текущей функции, чтобы они могли возобновить выполнение. Переменная, записанная как текущее продолжение, используется как функция, за исключением того, что она принимает предоставленное значение и возвращает его в стек ожидания. Это поведение похоже на функцию C longjmp, где вы можете сразу вернуться к нижним частям стека.
(define x 0) ; dummy value - will be used to store continuation later
(+ 2 (call/cc (lambda (cc)
(set! x cc) ; set x to the continuation cc; namely, (+ 2 _)
3))) ; returns 5
(x 4) ; returns 6
Одно ключевое различие между стеком C и продолжением состоит в том, что продолжение можно использовать в любой точке программы, даже если состояние стека изменилось. Это означает, что вы можете по существу восстановить предыдущие версии стека и использовать их снова и снова, что приводит к некоторому уникальному потоку программы.
(* 123 (+ 345 (* 789 (x 5)))) ; returns 7
reason: it is because (x 5) replaces the existing continuation,
(* 123 (+ 345 (* 789 _))), with x, (+ 2 _), and returns
5 to x, creating (+ 2 5), or 7.
Возможность сохранять и восстанавливать состояние программы имеет много общего с многопоточным процессом. Фактически, вы можете реализовать свой собственный планировщик потоков, используя продолжение, поскольку я попытался проиллюстрировать здесь.
Тривиальный пример использования продолжения будет реализовывать поток (волокно, если хотите) менеджер на однопроцессорной машине. Планировщик периодически прерывал поток выполнения (или, в случае волокон, вызывался в разных стратегических точках кода), сохранял состояние продолжения (соответствующее текущему потоку), затем переключился на другое состояние продолжения (соответствующее другой поток, состояние которого было сохранено ранее.)
Ссылаясь на ваш фон сборки, , состояние продолжения будет записывать такие данные, как указатель, регистры и регистр стека (указатель), которые будут сохранены и восстановлены по желанию.
Другим способом использования продолжения будет подумать о замене вызовов метода несколькими поточно-подобными объектами, которые сосуществуют параллельно (либо запущены, либо приостановлены), передавая управление друг другу, используя контексты продолжения вместо классической парадигмы call. Они будут использовать глобальные (общие) данные вместо того, чтобы полагаться на параметры. Это в некоторой степени более гибко, чем call в том смысле, что стек не должен заканчиваться тогда вниз (calls вложенные), но управление может проходить произвольно.
Попытка визуализировать эту концепцию на языке C, представьте, что у вас есть один большой цикл с одним выражением switch(continuation_point) { case point1: ... }, где каждый case соответствует точке сохранения продолжения и где код внутри каждого case может изменить значение continuation_point и отказаться от управления с этим continuation_point на break ing из switch и включить следующую итерацию в цикле.
Каков контекст вашего вопроса? Какие конкретные сценарии вас интересуют? Любой конкретный язык программирования? Достаточно ли пример потока/волокна?
Представьте, что ваш сценарий - сцена видеоигры. Call/cc - это как бонусная стадия.
Как только вы прикоснетесь к нему, вы перейдете на бонусную стадию (то есть определение функции, переданной в качестве аргумента для вызова /cc [f в данном случае]).
Бонусные этапы отличаются от обычных этапов, потому что обычно они содержат элемент (то есть аргумент функции, передаваемой в call/cc), который, если вы прикоснетесь к нему, потеряет и перенесется обратно на нормальный этап.
Поэтому не имеет значения, если их много args, когда вы достигнете одного из них, все кончено. Таким образом, наше выполнение достигает (arg 42) и возвращает его к сумме (+ 42 10).
Также есть некоторые замечания, на которые стоит обратить внимание:
(define f (lambda (k) (+ k 42)), потому что вы не можете sum a
функция.(define f (lambda (k) (f 42 10)))
потому что продолжение ожидает только один аргумент.touching никакого выхода, в этом случае функция работает как
любая обычная функция (например, (define f (lambda (k) 42) завершается и
возвращает 42).То, что помогло мне, - это идея, что на традиционном языке с вызовами функций вы неявно передаете продолжение при каждом вызове функции.
Перед тем, как перейти к функциональному коду, вы сохраняете какое-то состояние в стеке (т.е. вы нажимаете свой адрес возврата, а стек уже содержит ваших локальных жителей). Это по существу продолжение. Когда функция завершена, она должна определить, куда отправить поток выполнения. Он использует продолжение, хранящееся в стеке, выписывая обратный адрес и прыгая на него.
Другие языки обобщают эту идею продолжений, позволяя явно указывать, где продолжить выполнение кода, а не неявно продолжать с того места, где был вызван вызов функции.
EDIT на основе комментария:
Продолжение - это полное состояние выполнения. В любой момент исполнения вы можете разделить программу на две части (во времени, а не на пробел) - то, что было выполнено до этой точки, и все, что будет работать отсюда. "Текущее продолжение" - это "все, что будет работать отсюда" (вы можете думать о нем как о функции, которая будет делать все остальное в вашей программе). Таким образом, функция, которую вы передаете в call/cc, получает прошлое, которое было текущим при вызове call/cc. Функция может использовать продолжение, чтобы вернуть выполнение в оператор call/cc (скорее всего, он продолжит продолжение вокруг чего-то другого, потому что, если он использовал его напрямую, он мог бы сделать простой возврат вместо этого).
Когда я пытался понять call/cc, я обнаружил, что эта страница call-with-current-continuation-for-C-programmers была полезной.
Лучшее объяснение, которое я видел в книге Пола Грэма, Вкл Lisp.
Существует несколько уровней понимания call/cc. Сначала вам нужно понять термины и механизм работы механизма. Затем понимание того, как и когда call/cc используется в "реальной жизни", требуется программирование.
Первый уровень может быть достигнут путем изучения CPS, но есть альтернативы.
Для второго уровня я рекомендую следующий классик Фридманом.
Даниэль П. Фридман. "Приложения континуумов: приглашенный учебник". 1988 Принципы языков программирования (POPL88). Январь 1988 года.
Взгляните на описание и реализацию вызова /cc для FScheme: http://blogs.msdn.com/b/ashleyf/archive/2010/02/11/turning-your-brain-inside-out-with-continuations.aspx
Модель, которую я использовал для понимания продолжений с императивной точки зрения, заключается в том, что она является копией стека вызовов в сочетании с указателем на следующую инструкцию.
Call/cc вызывает функцию (переданную как аргумент) с продолжением в качестве аргумента.