Рекурсия по списку s-выражений в Clojure
Чтобы установить контекст, я нахожусь в процессе изучения Clojure и разработки Lisp в более общем плане. На моем пути к Лиспу я в настоящее время прорабатываю серию "Little", чтобы укрепить основы функционального программирования и рекурсивного решения. В "Маленьком интриганке" я проработал многие из упражнений, однако, я изо всех сил пытаюсь преобразовать некоторые из них в 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? из-за отсутствия TCO у JVM? Если последнее, вообще говоря, каков должен быть общий шаблон для программ Clojure, который должен повторяться в списке S-выражений? Что бы это ни стоило, я видел метод multi / w/lazy-seq (см. Стр. 151 из Halloway's Programming Clojure) для "Заменить рекурсию на лень" - но я не уверен, как применить этот шаблон к этому примеру, в котором я не пытаюсь построить список, но вычислить одно целое значение.
Заранее спасибо за любые рекомендации по этому вопросу.
2 ответа
Во-первых, я должен посоветовать вам не беспокоиться о сложностях реализации, таких как переполнение стека, когда вы пробуетесь через 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.StackruError (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.StackruError (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
Прыжки на батуте, конечно, крутая техника, но обязательным условием для прыжка на батуте является то, что она должна содержать только хвостовые вызовы; CPS - настоящая звезда здесь. Он позволяет вам определить свой алгоритм с ясностью естественной рекурсии и с помощью преобразований, сохраняющих корректность, эффективно выразить его на любом хосте, который имеет один цикл и кучу.
Вы не можете сделать это с фиксированным объемом памяти. Вы можете использовать стек или кучу; это решение, которое вы принимаете. Если бы я писал это в 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)))