Схема - переход на стиль продолжения-передачи

Я вроде как понимаю, как преобразовать элементарные функции, такие как арифметика, в стиль передачи продолжения в Scheme. Но что, если функция включает рекурсию? Например,

(define funname 
     (lambda (arg0 arg1)
                (and (some procedure)
                      (funname (- arg0 1) arg1))))

Пожалуйста, дайте мне совет. Заранее спасибо.


continuations scheme
person CosmicRabbitMediaInc    schedule 10.11.2011    source источник

Ответы (3)


arrow_upward
1
arrow_downward 

(define (func x y k)
  (some-procedure
   (lambda (ret)
     (if ret
         (- x 1
            (lambda (ret)
              (func ret y k)))
         (k #f))))

Вам не хватает базового случая, поэтому единственным явным вызовом продолжения является (k #f). Если у вас есть базовый вариант, вы также передадите возвращаемое значение базового варианта в продолжение. Например:

(define (func x y k)
  (zero? x
         (lambda (ret)
           (if ret
               (k y)
               (some-procedure
                (lambda (ret)
                  (if ret
                      (- x 1
                         (lambda (ret)
                           (func ret y k)))
                      (k #f))))))))
person Chris Jester-Young    schedule 10.11.2011

arrow_upward
4
arrow_downward

Одним из мест, где есть хорошее объяснение продолжений и CPS, является книга Кришнамурти PLAI. Соответствующая часть (VII) не зависит от других частей книги, так что вы можете сразу перейти к ней. В частности, есть расширенный пример преобразования кода в CPS вручную и работы с рекурсивными функциями (первая часть главы 17).

Кроме того, я написал расширенную версию этого текста для своего класса, в которой есть больше примеров и многое другое. подробности по этому вопросу - вы тоже можете найти это полезным. В дополнение к тексту PLAI я расскажу о некоторых распространенных случаях использования продолжений, таких как реализация генераторов, неоднозначный оператор и многое другое. (Но обратите внимание, что PLAI продолжает обсуждение стратегий реализации, которые не рассматриваются в моем тексте.)

person Eli Barzilay    schedule 10.11.2011

arrow_upward
1
arrow_downward

Это частично дублирует ответ Криса Джестера-Янга, но я надеюсь, что смогу объяснить это лучше :-).

В CPS разница, которую вы ищете, заключается между этими двумя вещами (примерно):

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

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

person Luis Casillas    schedule 12.12.2011