Ищем примеры "реального" использования продолжений

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

Некоторые веб-серверы и веб-фреймворки используют продолжения для хранения информации о сеансе. Объект продолжения создается для каждого сеанса и затем используется каждым запросом внутри сеанса.

Здесь есть статья об этом подходе.

Приморский:

• домашняя страница
• страница википедии

@Pat

Seaside

Да, Приморский - отличный пример. Я быстро просмотрел его код и обнаружил, что это сообщение иллюстрирует передачу управления между компонентами, по-видимому, с сохранением состояния через Интернет.

WAComponent >> call: aComponent
    "Pass control from the receiver to aComponent. The receiver will be
    temporarily replaced with aComponent. Code can return from here later
    on by sending #answer: to aComponent."

    ^ AnswerContinuation currentDo: [ :cc |
        self show: aComponent onAnswer: cc.
        WARenderNotification raiseSignal ]

Так мило!

В Algo & Data II мы использовали их все время для «выхода» или «возврата» из (длинной) функции.

например, алгоритм BFS для обхода деревьев был реализован следующим образом:

(define (BFS graph root-discovered node-discovered edge-discovered edge-bumped . nodes)
  (define visited (make-vector (graph.order graph) #f))
  (define q (queue.new))
  (define exit ())
  (define (BFS-tree node)
    (if (node-discovered node)
      (exit node))
    (graph.map-edges
     graph
     node
     (lambda (node2)
       (cond ((not (vector-ref visited node2))
              (when (edge-discovered node node2)
                (vector-set! visited node2 #t)
                (queue.enqueue! q node2)))
             (else
              (edge-bumped node node2)))))
    (if (not (queue.empty? q))
      (BFS-tree (queue.serve! q))))

  (call-with-current-continuation
   (lambda (my-future)
     (set! exit my-future)
     (cond ((null? nodes)
            (graph.map-nodes
             graph
             (lambda (node)
               (when (not (vector-ref visited node))
                 (vector-set! visited node #t)
                 (root-discovered node)
                 (BFS-tree node)))))
           (else
            (let loop-nodes
              ((node-list (car nodes)))
              (vector-set! visited (car node-list) #t)
              (root-discovered (car node-list))
              (BFS-tree (car node-list))
              (if (not (null? (cdr node-list)))
                (loop-nodes (cdr node-list)))))))))

Как видите, алгоритм завершится, когда функция обнаружения узла вернет true:

    (if (node-discovered node)
      (exit node))

функция также выдаст «возвращаемое значение»: 'узел'

почему функция завершается из-за этого утверждения:

(call-with-current-continuation
       (lambda (my-future)
         (set! exit my-future)

когда мы используем exit, он вернется в состояние до выполнения, опустошая стек вызовов и возвращая значение, которое вы ему дали.

Итак, в основном call-cc используется (здесь) для выхода из рекурсивной функции, вместо того, чтобы ждать, пока вся рекурсия завершится сама по себе (что может быть довольно дорого при выполнении большого количества вычислительной работы)

другой меньший пример, делающий то же самое с call-cc:

(define (connected? g node1 node2)
  (define visited (make-vector (graph.order g) #f))
  (define return ())
  (define (connected-rec x y)
    (if (eq? x y)
      (return #t))
    (vector-set! visited x #t)
    (graph.map-edges g
                     x
                     (lambda (t)
                       (if (not (vector-ref visited t))
                         (connected-rec t y)))))
  (call-with-current-continuation
   (lambda (future)
     (set! return future)
     (connected-rec node1 node2)
     (return #f))))

Я наткнулся на реализацию оператора amb в эта почта из http://www.randomhacks.net, используя продолжения.

Вот что делает оператор amb:

# amb will (appear to) choose values
# for x and y that prevent future
# trouble.
x = amb 1, 2, 3
y = amb 4, 5, 6

# Ooops! If x*y isn't 8, amb would
# get angry.  You wouldn't like
# amb when it's angry.
amb if x*y != 8

# Sure enough, x is 2 and y is 4.
puts x, y 

А вот реализация поста:

# A list of places we can "rewind" to
# if we encounter amb with no
# arguments.
$backtrack_points = []

# Rewind to our most recent backtrack
# point.
def backtrack
  if $backtrack_points.empty?
    raise "Can't backtrack"
  else
    $backtrack_points.pop.call
  end
end

# Recursive implementation of the
# amb operator.
def amb *choices
  # Fail if we have no arguments.
  backtrack if choices.empty?
  callcc {|cc|
    # cc contains the "current
    # continuation".  When called,
    # it will make the program
    # rewind to the end of this block.
    $backtrack_points.push cc

    # Return our first argument.
    return choices[0]
  }

  # We only get here if we backtrack
  # using the stored value of cc,
  # above.  We call amb recursively
  # with the arguments we didn't use.
  amb *choices[1...choices.length]
end

# Backtracking beyond a call to cut
# is strictly forbidden.
def cut
  $backtrack_points = []
end

Мне нравится amb!

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

Если ваши продолжения сериализуемы, вы также можете сохранить их при сбое приложения, а затем повторно вызвать их, чтобы получить подробную информацию о значениях переменных, трассировках стека и т. д.

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

В этой модели вместо того, чтобы запускать новый (тяжелый) поток каждый раз, когда приходит запрос, вы просто начинаете некоторую работу в функции. Затем, когда вы будете готовы заблокировать ввод-вывод (т. Е. Чтение из базы данных), вы передаете продолжение в обработчик сетевого ответа. Когда ответ вернется, вы выполните продолжение. С помощью этой схемы вы можете обрабатывать множество запросов всего несколькими потоками.

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

Как насчет Google Mapplets API? Существует множество функций (все заканчиваются на Async), которым вы передаете обратный вызов. Функция API выполняет асинхронный запрос, получает его результат, а затем передает этот результат в ваш обратный вызов (как «следующее, что нужно сделать»). Для меня это очень похоже на стиль прохождения продолжения.

Этот пример показывает очень простой случай.

map.getZoomAsync(function(zoom) {
    alert("Current zoom level is " + zoom); // this is the continuation
});  
alert("This might happen before or after you see the zoom level message");

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

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

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

Оператор amb - хороший пример, позволяющий декларативное программирование, подобное прологу.

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

Используя оператор amb, я могу просто заполнить ограничения, которым должна удовлетворять мелодия, и позволить Scheme вычислить результат.

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