Как делают меня memoize рекурсивная функция в Lisp?

Вот функция memoize, которая снова переплетает функцию символа:

(defun memoize-function (function-name)
  (setf (symbol-function function-name)
    (let ((cache (make-hash-table :test #'equal)))
         #'(lambda (&rest args)
             (multiple-value-bind 
                 (result exists)
                (gethash args cache)
               (if exists
                   result
                   (setf (gethash args cache)
                         (apply fn args)))))))

Вы затем сделали бы что-то вроде этого:

(defun collatz-steps (n)
  (if (= 1 n) 0
      (if (evenp n) 
          (1+ (collatz-steps (/ n 2)))
          (1+ (collatz-steps (1+ (* 3 n)))))))

(memoize-function 'collatz-steps)

я оставлю его до Вас для создания unmemoize-функции.

что-то вроде этого:

(setf collatz-steps (memoize lambda (n)
  (if (= 1 n) 0
    (if (evenp n) 
        (1+ (collatz-steps (/ n 2)))
        (1+ (collatz-steps (1+ (* 3 n))))))))

IOW: Ваша исходная (немемоизованная) функция является анонимной, и Вы только даете имя результату memoizing она.

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

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

код huaiyuan показывает ключевой шаг:

(setf (fdefinition 'collatz-steps) (memoize #'collatz-steps))

Этот прием также работает в Perl. На языке как C, однако, мемоизованная версия функции должна быть кодирована отдельно.

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

Только что я записал немного memoization стандартной программы для Схемы, которая использовала цепочку закрытий для отслеживания мемоизованное состояние:

(define (memoize op)
  (letrec ((get (lambda (key) (list #f)))
           (set (lambda (key item)
                  (let ((old-get get))
                    (set! get (lambda (new-key)
                                (if (equal? key new-key) (cons #t item)
                                    (old-get new-key))))))))
    (lambda args
      (let ((ans (get args)))
        (if (car ans) (cdr ans)
            (let ((new-ans (apply op args)))
              (set args new-ans)
              new-ans))))))

Это должно использоваться как так:

(define fib (memoize (lambda (x)
                       (if (< x 2) x
                           (+ (fib (- x 1)) (fib (- x 2)))))))

я уверен, что это может быть портировано Вашему фавориту, лексически определил объем разновидности Lisp легко.

Обратите внимание на несколько моментов:

(defun foo (bar)
   ... (foo 3) ...)

Выше - функция, которая вызывает сама себя.

В Common Lisp компилятор файлов может предполагать, что FOO не изменяется. Он НЕ будет вызывать обновленный FOO позже. Если вы измените привязку функции FOO, то вызов исходной функции все равно перейдет к старой функции.

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

Вы можете обойти это, чтобы всегда проходить через символ, например: (funcall 'foo 3)

(DEFVAR ...) - это форма верхнего уровня. Не используйте его внутри функций. Если вы объявили переменную, установите ее позже с помощью SETQ или SETF.

Для вашей проблемы я бы просто использовал хеш-таблицу для хранения промежуточных результатов.

Я бы, наверное, сделал что-то вроде:

(let ((memo (make-hash-table :test #'equal)))
  (defun collatz-steps (n)
    (or (gethash n memo)
    (setf (gethash n memo)
          (cond ((= n 1) 0)
            ((oddp n) (1+ (collatz-steps (+ 1 n n n))))
            (t (1+ (collatz-steps (/ n 2)))))))))

Это не красиво и функционально, но, в таком случае, это не очень хлопотно и работает. Недостатком является то, что у вас нет удобной непамятованной версии для тестирования, а очистка кэша граничит с "очень сложно".

Эта функция - именно та, которую Питер Норвиг приводит в качестве примера функции, которая кажется хорошим кандидатом для мемоизации, но таковой не является.

См. рисунок 3 (функция 'Hailstone') его оригинальной статьи о мемоизации ("Using Automatic Memoization as a Software Engineering Tool in Real-World AI Systems").

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