Подтвердить что ты не робот

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

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

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

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

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

Ура!

4b9b3361

ОТВЕТЫ

Ответ 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)))))))))

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

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

функция также даст "возвращаемое значение": '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))))

Ответ 3

@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 ]

Так приятно!

Ответ 4

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

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

Ответ 5

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

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

Ответ 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 angry.
amb if x*y != 8

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

И здесь реализация post:

# 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!

Ответ 7

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

Ответ 8

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

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

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

Ответ 9

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

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

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

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

Ответ 10

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

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

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

Ответ 11

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

Ответ 12

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