Что такое Call / CC? - PullRequest
       124

Что такое Call / CC?

44 голосов
/ 05 марта 2009

Я несколько раз пытался понять концепцию продолжений и call / cc . Каждая попытка была неудачной. Может кто-нибудь объяснить мне эти концепции, в идеале с более реалистичными примерами, чем в Википедии или в других сообщениях SO.

У меня есть опыт работы в веб-программировании и ООП. Я также понимаю сборку 6502 и имел незначительный рандеву с Эрлангом. Тем не менее, я не могу обернуть голову в call / cc.

Ответы [ 10 ]

22 голосов
/ 05 марта 2009

Чтобы сравнить его с 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.

Возможность сохранения и восстановления состояния программы имеет много общего с многопоточностью. Фактически, вы можете реализовать свой собственный планировщик потоков, используя продолжения, как я пытался проиллюстрировать здесь .

13 голосов
/ 05 марта 2009

Смотри, я нашел это Стиль прохождения продолжения лучшее описание по этой теме.

Вот копия подробностей этой статьи:

Автор: Марин Хавербеке Дата: 24 июля 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, используемыми для их моделирования. Это всегда требует, чтобы один работал с каким-то механизмом обратного вызова для обработки данных, которые сервер отправляет обратно. В простых случаях подойдет тривиальная функция, или можно использовать несколько глобальных переменных для хранения состояния вычислений, которое должно быть возобновлено после возвращения данных. В сложных случаях, например, когда данные используются функцией, которая должна возвращать вызывающей стороне некоторое значение, продолжения значительно упрощают ситуацию. Вы просто регистрируете продолжение как обратный вызов, и после завершения запроса ваши вычисления возобновляются.

8 голосов
/ 05 марта 2009

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

Ссылаясь на фон вашей сборки, состояние продолжения будет захватывать такие детали, как указатель инструкции, регистры и контекст стека (указатель) , которые будут сохраняться и восстанавливаться по желанию.

Другим способом использования продолжения было бы подумать о замене вызовов методов несколькими нитевидными объектами , которые сосуществуют параллельно (либо запущены, либо приостановлены), передавая управление друг другу, используя контексты продолжения вместо «классическая» парадигма call. Они будут работать с глобальными (общими) данными вместо того, чтобы полагаться на параметры. Это в некоторой степени более гибко, чем call, в том смысле, что стек не нужно свернуть, а затем уменьшить (calls вложено ), но управление может проходить произвольно.

Попытка визуализировать эту концепцию на языке, подобном C, представьте, что у вас есть один большой цикл с одним оператором switch(continuation_point) { case point1: ... }, где каждый case соответствует точке продолжения-сохранения и где код внутри каждого case можно изменить значение continuation_point и отказаться от управления этим continuation_point путем break от switch и включения следующей итерации в цикле.

Каков контекст вашего вопроса? Какие конкретные сценарии вас интересуют? Какой-то конкретный язык программирования? Достаточно ли приведенного выше примера нитки / волокна?

5 голосов
/ 05 марта 2009

Мне помогло то, что в традиционном языке с вызовами функций вы неявно пропускаете продолжение каждый раз, когда выполняете вызов функции.

Перед переходом к коду функции вы сохраняете некоторое состояние в стеке (то есть вы нажимаете свой обратный адрес, и в стеке уже содержатся ваши локальные данные). Это по сути продолжение. Когда функция завершена, она должна определить, куда отправить поток выполнения. Он использует продолжение, хранящееся в стеке, получая адрес возврата и переходя к нему.

Другие языки обобщают эту идею продолжения, позволяя вам явно указывать, где продолжить выполнение кода, а не неявно продолжать с того места, где был выполнен вызов функции.

РЕДАКТИРОВАТЬ на основе комментария:

Продолжение - состояние полного выполнения. В любой момент выполнения вы можете разделить программу на две части (по времени, а не по пространству) - то, что было запущено до этого момента, и все, что будет происходить отсюда. «Текущее продолжение» - это «все, что будет запускаться отсюда» (вы можете думать о нем как о функции, которая сделает все, что сделала бы остальная часть вашей программы). Таким образом, функция, которую вы предоставляете call/cc, получает продолжение, которое было текущим при вызове call/cc. Функция может использовать продолжение, чтобы вернуть выполнение в оператор call/cc (более вероятно, что оно передаст продолжение чему-то другому, потому что, если оно использовало его напрямую, оно могло бы вместо этого сделать простой возврат).

4 голосов
/ 03 июня 2009

Когда я пытался понять call / cc, я обнаружил, что эта страница call-with-current-продолжения-для-C-программистов была полезна.

3 голосов
/ 02 октября 2017

Представьте, что ваш сценарий - сцена видеоигры. Call / cc - это как бонусная стадия.

parellel between bonus stage and call/cc

Как только вы прикоснетесь к нему, вы перейдете на стадию бонуса (т. Е. Определение функции, переданной в качестве аргумента для вызова / cc [f в данном случае]).

Бонусные этапы отличаются от обычных этапов , потому что обычно они имеют элемент (т. Е. Аргумент функции, передаваемой в call / cc), который при касании его теряется транспортируется обратно к нормальной стадии.

parellel between exit bonus stage and call/cc function args

Так что не имеет значения, если их много args, когда вы достигнете одного из них, все кончено. Таким образом, наше исполнение достигает (arg 42) и возвращает его к сумме (+ 42 10).

Также есть некоторые замечания, на которые стоит обратить внимание:

  • Не все функции могут быть использованы с call / cc. Так как он ожидает продолжение (это функция), вы не можете иметь f, как это: (define f (lambda (k) (+ k 42)), потому что вы не можете sum a функция.
  • Также вы не можете иметь (define f (lambda (k) (f 42 10))) потому что продолжение ожидает только один аргумент.
  • Вы можете закончить без touching никакого выхода, в этом случае функция работает как любая обычная функция (например, (define f (lambda (k) 42) заканчивается и возвращает 42).
3 голосов
/ 05 марта 2009

Лучшее объяснение, которое я видел, в книге Пола Грэма На Лиспе .

2 голосов
/ 23 сентября 2011

Модель, которую я использовал для понимания продолжений с императивной точки зрения, состоит в том, что это копия стека вызовов в сочетании с указателем на следующую инструкцию.

Call / cc вызывает функцию (переданную в качестве аргумента) с продолжением в качестве аргумента.

2 голосов
/ 23 апреля 2011

Взгляните на описание и реализацию call / cc для FScheme: http://blogs.msdn.com/b/ashleyf/archive/2010/02/11/turning-your-brain-inside-out-with-continuations.aspx

2 голосов
/ 09 марта 2009

Есть несколько уровней понимания вызова / куб. Для начала вам необходимо понять термины и то, как работает механизм. Затем понимание того, как и когда call / cc используется в «реальной жизни» необходимо программирование.

Первый уровень можно достичь, изучая CPS, но есть альтернативы.

Для второго уровня я рекомендую следующую классику Фридмана.

Даниэль П. Фридман. «Приложения продолжений: приглашенный учебник». 1988 Основы языков программирования (POPL88). Январь 1988 года.

...