Рекурсия над списком s-выражений в Clojure

Чтобы установить некоторый контекст, я в процессе обучения Clojure и Lisp развивается более широко. На моем пути к Lisp я в настоящее время работаю в серии "Маленькие", чтобы укрепить фундамент в функциональном программировании и рекурсивном решении. В "The Little Schemer", я работал над многими упражнениями, однако, я немного пытаюсь преобразовать некоторые из них в Clojure. В частности, я изо всех сил пытаюсь преобразовать их, чтобы использовать "recur", чтобы включить TCO. Например, здесь реализована реализация на основе Clojure функции "происходит" (от Little Schemer), которая подсчитывает количество вхождений атома, входящих в список S-выражений:

(defn atom? [l]
  (not (list? l)))

(defn occurs [a lst]
  (cond
   (empty? lst) 0
   (atom? (first lst))
    (cond
     (= a (first lst)) (inc (occurs a (rest lst)))
     true (occurs a (rest lst)))
   true (+ (occurs a (first lst))
           (occurs a (rest lst)))))

В принципе, (occurs 'abc '(abc (def abc) (abc (abc def) (def (((((abc))))))))) будет оцениваться до 5. Очевидная проблема заключается в том, что это определение потребляет стековые фреймы и выдувает стек, если слишком сильно указывается список S-выражений.

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

Здесь, как далеко я получу, если попытаюсь реорганизовать это, используя "recur" вместе с использованием параметра аккумулятора:

(defn recur-occurs [a lst]
  (letfn [(myoccurs [a lst count]
            (cond
             (empty? lst) 0
             (atom? (first lst))
             (cond
              (= a (first lst)) (recur a (rest lst) (inc count))
              true (recur a (rest lst) count))
             true (+ (recur a (first lst) count)
                     (recur a (rest lst) count))))]
    (myoccurs a lst 0)))

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

Существуют ли дополнительные методы для шаблона "аккумулятора" для достижения ваших рекурсивных вызовов, помещенных в позицию хвоста, которые я должен применять здесь, или это проблема просто более "фундаментальная" и что нет чистого Clojure на основе решения JVM отсутствия ТСО? Если последнее, вообще говоря, какова должна быть общая модель для программ Clojure для использования, которые должны повторяться в списке S-выражений? Для того, что это стоит, я видел метод multi method w/lazy-seq, используемый (ссылка на "Halloway" Programming Clojure "для справки), чтобы" заменить рекурсию на лень ", но я не уверен, как применять этот шаблон к этому примеру, в котором я не пытаюсь создать список, но для вычисления целочисленного значения.

Заранее благодарю вас за любые рекомендации по этому вопросу.

Ответ 1

Во-первых, я должен посоветовать вам не беспокоиться о реализации, как переполнение стека, когда вы прокладываете себе путь через The Little Schemer. Хорошо быть добросовестным в таких вопросах, как отсутствие оптимизации хвостовых звонков, когда вы программируете в гневе, но основной момент книги - научить вас думать рекурсивно. Преобразование примеров, в которых проходит процесс аккумулирования накопителей, безусловно, является хорошей практикой, но по сути это рекурсия в пользу итерации.

Однако, и я должен предисловие к этому с предупреждением спойлера, есть способ сохранить один и тот же рекурсивный алгоритм, не подвергаясь прихотям стека JVM. Мы можем использовать стиль продолжения, чтобы сделать наш собственный стек в виде дополнительного анонимного аргумента функции k:

(defn occurs-cps [a lst k]
  (cond
   (empty? lst) (k 0) 
   (atom? (first lst))
   (cond
    (= a (first lst)) (occurs-cps a (rest lst)
                                  (fn [v] (k (inc v))))
    :else (occurs-cps a (rest lst) k))
   :else (occurs-cps a (first lst)
                     (fn [fst]
                       (occurs-cps a (rest lst)
                                   (fn [rst] (k (+ fst rst))))))))

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

scratch.core=> (occurs-cps 'abc 
                           '(abc (def abc) (abc (abc def) (def (((((abc)))))))) 
                           (fn [v] v))
5

Я больше не буду вдаваться в подробности о том, как делать CPS, как для более поздней главы TLS. Тем не менее, я отмечу, что это, конечно, еще не работает полностью:

scratch.core=> (def ls (repeat 20000 'foo))          
#'scratch.core/ls
scratch.core=> (occurs-cps 'foo ls (fn [v] v))       
java.lang.StackOverflowError (NO_SOURCE_FILE:0)

CPS позволяет нам перемещать все наши нетривиальные вызовы построения стека в позицию хвоста, но в Clojure нам нужно сделать дополнительный шаг для их замены с помощью recur:

(defn occurs-cps-recur [a lst k]
  (cond
   (empty? lst) (k 0)
   (atom? (first lst))
   (cond
    (= a (first lst)) (recur a (rest lst)
                             (fn [v] (k (inc v))))
    :else (recur a (rest lst) k))
   :else (recur a (first lst)
                (fn [fst]
                  (recur a (rest lst) ;; Problem
                         (fn [rst] (k (+ fst rst))))))))

Увы, это не так: java.lang.IllegalArgumentException: Mismatched argument count to recur, expected: 1 args, got: 3 (core.clj:39). Самый последний recur фактически относится к fn прямо над ним, тот, который мы используем, чтобы представлять наши продолжения! Мы можем получить хорошее поведение большую часть времени, изменяя только recur на вызов occurs-cps-recur, но вложенные в патологию входы все равно переполняют стек:

scratch.core=> (occurs-cps-recur 'foo ls (fn [v] v))
20000
scratch.core=> (def nested (reduce (fn [onion _] (list onion)) 
                                   'foo (range 20000)))
#'scratch.core/nested
scratch.core=> (occurs-cps-recur 'foo nested (fn [v] v))
Java.lang.StackOverflowError (NO_SOURCE_FILE:0)

Вместо того, чтобы сделать вызов occurs-* и ожидая, что он вернет ответ, мы можем немедленно его вернуть. Когда мы вызываем этот thunk, он уходит и выполняет некоторую работу вплоть до рекурсивного вызова, который, в свою очередь, вернет еще один thunk. Это бамбуковый стиль, а функция, которая "отскакивает" от наших ударных, - trampoline. Возвращение thunk каждый раз, когда мы делаем рекурсивный вызов, ограничивает наш размер стека одним вызовом за раз, поэтому наш единственный предел - это куча:

(defn occurs-cps-tramp [a lst k]
  (fn [] 
    (cond
     (empty? lst) (k 0) 
     (atom? (first lst))
     (cond
      (= a (first lst)) (occurs-cps-tramp a (rest lst)
                                          (fn [v] (k (inc v))))
      :else (occurs-cps-tramp a (rest lst) k))
     :else (occurs-cps-tramp a (first lst)
                             (fn [fst]
                               (occurs-cps-tramp a (rest lst)
                                                 (fn [rst] (k (+ fst rst)))))))))

(declare done answer)

(defn my-trampoline [th]
  (if done
    answer
    (recur (th))))

(defn empty-k [v]
  (set! answer v)
  (set! done true))

(defn run []
  (binding [done false answer 'whocares]
    (my-trampoline (occurs-cps-tramp 'foo nested empty-k))))

;; scratch.core=> (run)                             
;; 1

Обратите внимание, что Clojure имеет встроенный trampoline (с некоторыми ограничениями на возвращаемый тип). Используя это вместо этого, нам не нужен специализированный empty-k:

scratch.core=> (trampoline (occurs-cps-tramp 'foo nested (fn [v] v)))
1

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

Ответ 2

Вы не можете сделать это с фиксированным объемом памяти. Вы можете использовать стек или кучу; что решение вы принимаете. Если бы я писал это в Clojure, я бы делал это с map и reduce, а не с ручной рекурсией:

(defn occurs [x coll]
  (if (coll? coll)
    (reduce + (map #(occurs x %) coll))
    (if (= x coll)
      1, 0)))

Обратите внимание, что более короткие решения существуют, если вы используете tree-seq или flatten, но в этот момент большая часть проблемы исчезла, поэтому не так много, чтобы учиться.

Изменить

Здесь версия, которая не использует какой-либо стек, вместо этого позволяя своей очереди становиться все больше и больше (используя кучу).

(defn heap-occurs [item coll]
  (loop [count 0, queue coll]
    (if-let [[x & xs] (seq queue)]
      (if (coll? x)
        (recur count (concat x xs))
        (recur (+ (if (= item x) 1, 0)
                  count)
               xs))
      count)))