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

Question

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

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

Answer 1

Посмотрите, я нашел это лучшее описание на эту тему.

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

Автор: Marijn Haverbeke Дата: 24 июля 2007

Схема Позвони-с-тока продолжения функции позволяет захватить вычисления, состояние стека вызовов как бы и возобновить это же состояние позднее. В дополнение к такому примитиву могут быть реализованы различные формы обработки исключений и трюки типа «С».

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

Представьте, что у нас есть документ huuuuge, который можно использовать. Простое перемещение за один раз занимает пять секунд, а замораживание браузера в течение пяти секунд - довольно плохой стиль. Рассмотрим эту простую модификацию 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

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

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

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

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

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

Answer 3

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

Answer 4

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

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

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

EDIT на основе комментариев:

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

Answer 5

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

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

Answer 6

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

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

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

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

Answer 7

Когда я пытался понять, звоните/cc, я нашел эту страницу call-with-current-continuation-for-C-programmers полезной.

Answer 8

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

Answer 9

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

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

Answer 10

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

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

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

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

Также есть некоторые замечания Заслуживает внимания:

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