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

Question

Я пытаюсь понять концепцию продолжений и нашел несколько небольших примеров обучения, подобных этой из Википедия статья:

(define the-continuation #f)

(define (test)
  (let ((i 0))
    ; call/cc calls its first function argument, passing 
    ; a continuation variable representing this point in
    ; the program as the argument to that function. 
    ;
    ; In this case, the function argument assigns that
    ; continuation to the variable the-continuation. 
    ;
    (call/cc (lambda (k) (set! the-continuation k)))
    ;
    ; The next time the-continuation is called, we start here.
    (set! i (+ i 1))
    i))

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

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

Ваше здоровье!

Answer 1

В 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)

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

Таким образом, в основном используется 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))))

Answer 2

Приморский:

• домашняя страница
• Википедия Пейдж

Answer 3

@Pat

Приморский

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

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 ]

Так мило!

Answer 4

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

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

Answer 5

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

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

Answer 6

Я пришел в реализацию 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!

Answer 7

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

Answer 8

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

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

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

Answer 9

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

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

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

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

Answer 10

Как насчет 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, нет Оптимизация хвостового вызова, Таким образом, стек будет расти с каждым вызовом в продолжение, и вы в конечном итоге вернете поток управления в браузер. Тем не менее, я думаю, что это хорошая абстракция.

Answer 11

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

Answer 12

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