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

Question

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

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

Answer 1

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

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

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

Answer 2

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

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

Answer 3

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

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

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

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

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

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

Answer 4

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

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

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

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

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

Answer 5

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

Answer 6

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

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

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

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

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

Answer 7

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

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

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

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

Answer 8

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

Answer 9

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

Answer 10

Вы, вероятно, знакомы с идеей "передачи управления", которая - в таких языках, как C - проявляется в таких утверждениях, как break, continue, return а также goto, или - на языках, поддерживающих исключения - try а также catch заявления.

Вы можете себе представить, что break а также continue может быть реализовано с использованием goto (т.е. для каждого фрагмента кода, который использует break или continue, вы можете легко написать эквивалентный код, который использует goto с правильно размещенными этикетками).

Итак, пока давайте сосредоточимся на goto, который, как вы должны знать по своему опыту работы со сборкой, является самой простой операцией передачи управления (вы можете себе представить, что преобразовать return использовать goto - но мы перейдем к этому).

Итак, предположим, что у вас есть программа (скажем, на C), которая выглядит так:

instruction1;
instruction2;
...
instructionN;

где instructionK может быть либо присвоением, либо вызовом функции, либо оператором if (condition) goto some_label.

Вы можете добавить к каждой строке уникальный ярлык для goto:

line1: instruction1;
line2: instruction2;
...
lineN: instructionN;

В языках, поддерживающих первоклассные продолжения, есть специальная функция call/cc, который работает так: предположим, что instructionK имеет форму

...
lineK: call/cc(function(continuation) { ... })
lineK+1: instructionK+1;
...

Я использовал здесь обозначение JavaScript для анонимных функций, потому что C не поддерживает анонимные функции. Вы можете видеть, что функция имеет один аргумент, который я назвалcontinuation.

Тело функции выполняется немедленно, когда call/cc вызывается, и значение continuation аргументом будет адрес lineK+1(грубо говоря). Или, другими словами, текущее продолжение вlineK это lineK+1 - вот как вы могли подумать об этом.

Однако типичный интерфейс заключается в том, что это не просто адрес: continuation Аргумент - это процедура, которая при вызове выполняет переход к lineK+1. Вот какcall/cc позволяет реализовать return заявление.

Итак, вы могли подумать о call/cc как своего рода gotoна стероидах. Дело в том, что можно не только позвонитьcontinuation аргумент, но вы также можете сохранить его в переменных или других структурах данных.

Самое интересное использование call/ccчто я видел, это реализация оценщика Amb из книги Дораи Ситарам Teach Yourself Scheme in Fixnum Days (вы можете сравнить ее с версией из Structure and Interpretation of Computer Programs, которая не используетcall/cc).

Однажды я также реализовал свой собственный механизм управления ресурсами с использованием продолжений, как описано здесь.

Но кроме этого, первоклассные продолжения подвергались критике, и я бы не рекомендовал использовать их в производственном коде (они очень похожи на механизм setjmp/longjmp, доступный в C, что я бы тоже не одобрил. Но если вы... Я хотел бы увидеть пример использования, вот как вы могли бы использовать его для реализации многозадачности в 100 строках кода).

Answer 11

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

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