В Clojure возможно ли совместить запоминание и оптимизацию хвостовых вызовов?

Question

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

[РЕДАКТИРОВАТЬ: этот вопрос был переписан с использованием gcd в качестве примера вместо factorial.]

Запомнившийся gcd (наибольший общий делитель) может быть реализован так:

(def gcd (memoize (fn [a b] 
   (if (zero? b) 
       a 
       (recur b (mod a b)))) 

В этой реализации промежуточные результаты не запоминаются для последующих вызовов. Например, для вычисления gcd(9,6), gcd(6,3) вызывается как промежуточный результат. Однако gcd(6,3) не сохраняется в кэше запомненной функции, поскольку точка рекурсии recur является анонимной функцией, которая не запоминается.

Поэтому, если после звонка gcd(9,6) мы позвоним gcd(6,3), мы не получим выгоду от напоминания.

Единственное решение, о котором я могу подумать, - это использовать обычную рекурсию (явно позвоните gcd вместо recur), но тогда мы не получим выгоду от оптимизации Tail Call.

Итог

Есть ли способ достичь обоих:

1. Оптимизация вызова на хвост
2. Запоминание промежуточных результатов для последующих вызовов

Примечания

1. Этот вопрос похож на Объедините памятку и хвостовую рекурсию . Но все ответы там связаны с F#. Здесь я ищу ответ в clojure.
2. Этот вопрос был оставлен читателю в качестве упражнения для Радость Clojure (глава 12.4). Вы можете обратиться к соответствующей странице книги на http://bit.ly/HkQrio.

Answer 1

в вашем случае трудно показать, что memoize делает что-то с факториалом, потому что промежуточные вызовы уникальны, поэтому я перепишу несколько надуманный пример, предполагая, что цель состоит в том, чтобы исследовать способы избежать потери стека:

(defn stack-popper [n i] 
    (if (< i n) (* i (stack-popper n (inc i))) 1)) 

, который затем может извлечь что-то из памятки:

(def stack-popper 
   (memoize (fn [n i] (if (< i n) (* i (stack-popper n (inc i))) 1))))

общие подходы к отказу от стека:

использовать хвостовые вызовы

(def stack-popper 
    (memoize (fn [n acc] (if (> n 1) (recur (dec n) (* acc (dec n))) acc))))

использование батуты

(def stack-popper 
    (memoize (fn [n acc] 
        (if (> n 1) #(stack-popper (dec n) (* acc (dec n))) acc))))
(trampoline (stack-popper 4 1))

используйте ленивую последовательность

(reduce * (range 1 4))

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

Answer 2

(def gcd 
  (let [cache (atom {})]
    (fn [a b]
      @(or (@cache [a b])
         (let [p (promise)]
           (deliver p
             (loop [a a b b]
               (if-let [p2 (@cache [a b])]
                 @p2
                 (do
                   (swap! cache assoc [a b] p)
                   (if (zero? b) 
                     a 
                     (recur b (mod a b))))))))))))

Есть некоторые проблемы параллелизма (двойная оценка, та же проблема, что и с memoize, но хуже из-за обещаний), которые могут быть исправлены с помощью совета @ kotarak.

Превращение приведенного выше кода вмакрос оставлен в качестве упражнения для читателя.(Примечание Фогуса звучало как-то ненормально.)

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

Answer 3

(defmacro memofn
  [name args & body]
  `(let [cache# (atom {})]
     (fn ~name [& args#]
       (let [update-cache!# (fn update-cache!# [state# args#]
                              (if-not (contains? state# args#)
                                (assoc state# args#
                                       (delay
                                         (let [~args args#]
                                           ~@body)))
                                state#))]
         (let [state# (swap! cache# update-cache!# args#)]
           (-> state# (get args#) deref))))))

Это позволит рекурсивно определить запомненную функцию, которая также кэширует промежуточные результаты. Использование:

(def fib (memofn fib [n]
           (case n
             1 1
             0 1
             (+ (fib (dec n)) (fib (- n 2))))))

Answer 4

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

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

Вместо передачи результатапредыдущих вычислений в качестве аргумента (аккумулятора) мы получаем из буфера.

(def !                                            ; global variable referring to a function
  (let [m (atom [1 1 2 6 24])]                    ; buffer of results
    (fn [n]                                       ; factorial function definition
      (let [m-count (count @m)]                   ; number of results in a buffer
        (if (< n m-count)                         ; do we have buffered result for n?
          (nth @m n)                              ; · yes: return it
          (loop [cur m-count]                     ; · no: compute it recursively
            (let [r (*' (nth @m (dec cur)) cur)]  ; new result
              (swap! m assoc cur r)               ; store the result
              (if (= n cur)                       ; termination condition:
                r                                 ; · base case
                (recur (inc cur))))))))))         ; · recursive case

(time (do (! 8000) nil))  ; => "Elapsed time: 154.280516 msecs"
(time (do (! 8001) nil))  ; => "Elapsed time: 0.100222 msecs"
(time (do (! 7999) nil))  ; => "Elapsed time: 0.090444 msecs"
(time (do (! 7999) nil))  ; => "Elapsed time: 0.055873 msecs"

Answer 5

Используя рекуррент Clojure, вы можете написать факториал, используя аккумулятор, у которого нет роста стека, и просто запомнить его:

(defn fact
  ([n]
     (fact n 1))
  ([n acc]
     (if (= 1 n)
       acc
       (recur (dec n)
              (* n acc)))))