В Clojure возможно ли комбинировать оптимизацию memoization и tail call?

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

[EDIT: этот вопрос был переписан с использованием 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) не сохраняется в кеше memoized функции, потому что точка рекурсии recur является анонимной функцией, которая не memoized.

Следовательно, если после вызова gcd(9,6), мы вызываем gcd(6,3), мы не будем использовать мемуаз.

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

Нижняя линия

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

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

Примечания

Ответы

Ответ 1

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

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

который затем может получить что-то из memoize:

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

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

Ответ 2

(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#]
                                           [email protected])))
                                state#))]
         (let [state# (swap! cache# update-cache!# args#)]
           (-> state# (get args#) deref))))))

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

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

Ответ 3

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

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

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

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

Ответ 4

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

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

Ответ 5

Это факториальная функция, реализованная с анонимной рекурсией с хвост и memoization промежуточных результатов. Мемонирование интегрировано с функцией и ссылкой на общий буфер (реализованный с использованием 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"