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

Question

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

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

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

Answer 1

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

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

Answer 2

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

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

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

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

Answer 3

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