Что такое call /cc?

Question

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

У меня есть опыт работы в веб-программировании и ООП.Я также разбираюсь в сборке 6502, и у меня были небольшие разногласия с Erlang.Тем не менее, я все еще не могу разобраться с 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) становится устаревшим в стиле передачи продолжения & # 8213; когда функция вызывает другую функцию, это последнее, что она делает. Вместо того, чтобы ждать возврата вызываемой функции, он помещает любую работу, которую он хочет сделать впоследствии, в продолжение, которое он передает функции.

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();
}

     

Теперь, каждые двадцать узлов вычисление прерывается на сто миллисекунд, чтобы дать интерфейсу браузера момент для ответа на ввод пользователя. Очень примитивная форма работы с потоками & # 8213; Вы можете даже запустить несколько вычислений одновременно, как это.

     

Более полезное применение этого связано с 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

Представьте, что ваш сценарий - это сцена для видеоигры.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).

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

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

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

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

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

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

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

Answer 3

Answer 4

Answer 5

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

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

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

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

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

Answer 6

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

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

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

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

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

Answer 7

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

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

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

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

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

Answer 8

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

Answer 9

Answer 10

Answer 11

Когда я пытался понять call / cc, я обнаружил, что это

Answer 12

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

Answer 13

Представьте, что ваш сценарий - это сцена для видеоигры.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 14

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

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

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

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

Answer 15

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

Answer 16

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

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