Стиль передачи продолжения делает вещи рекурсивными?

Question

Больно спрашивать это здесь.Это действительно так.Каждый раз, когда я напрасно ищу ответы на свои проблемы, я вижу это.Дразнить меня Переполнение стека .

В любом случае, какое-то адское влияние заставило меня попытаться разгадать Ханойские башни.Мое первое решение было неполным, поскольку оно приводило к ошибке памяти , если запускался с большим количеством дисков:

(define hanoi
  (lambda (n from to other)
    (cond ((< n 0)
       (error `(Error! Number of disks ,n cannot be less than 0!)))
      ((= n 0)
       '())
      (else
       (append (hanoi (- n 1)
              from
              other
              to)
           `((,from ,to))
           (hanoi (- n 1)
              other
              to
              from))))))

Я где-то читал, что стиль передачи с продолжением решит проблему.Однако это тоже не помогло :

(define hanoi_cps
  (lambda (n from to other c)
    (cond ((< n 0)
       (error `(Error! Number of disks ,n cannot be less than 0!)))
      ((= n 0)
       (c '()))
      (else
       (hanoi_cps (- n 1)
              from
              other
              to
              (lambda (x)
            ((lambda (w)
               (w `((,from ,to))))
             (lambda (y)
               (hanoi_cps (- n 1)
                      other
                      to
                      from
                      (lambda (z)
                    (c (append x y z))))))))))))

Answer 1

В стиле передачи продолжения, вместо того, чтобы расширять пространство стека рекурсивными вызовами, вы создаете рекурсивно определенные лямбда-выражения в среде, в которой выполняются ваши продолжения ... другими словами, память используется где-то вдоль линия. Например, с помощью простого факториального алгоритма вы обычно пишете что-то вроде:

(define (factorial x)
    (cond ((eq? x 0) 1))
          ((eq? x 1) 1))
          (else (* x (factorial (- x 1))))))

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

(define (factorial x cont)
    (cond ((eq? x 0) (cont 1))
          ((eq? x 1) (cont 1))
          (else (factorial (- x 1) (lambda (y) (cont (* x y)))))))

То, что раньше занимало место в стеке, теперь используется средой анонимной лямбды. Окружение лямбды в этом случае заполняется значениями, необходимыми для разрешения значений x и cont при каждом рекурсивном вызове factorial. Поскольку cont сам по себе является лямбда-выражением со средой, вы можете видеть, как в конечном итоге будет потребляться память, поскольку каждое лямбда-продолжение должно будет хранить в своей среде лямбда-выражения из предыдущего вызова факториала ... это создает рекурсивно определенную лямбду - продолжение, в котором есть среда, представляющая собой рекурсивный список всех продолжений, которые были получены при рекурсивных вызовах factorial.

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

Answer 2

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