Скрипт вычисляет значения функции Аккермана, используя кэширование. Кэш вначале инициализируется, а потом происходит выполнение (ниже код).
Скрипт:

;; кэш для функции Аккермана
(defvar *akk-cache* nil)
;; счетчик рекурсивных вызовов (должен быть обнулен перед вызовом функции akk или akk-cache)
(defvar *akk-recursive-calls-counter* 0)
(defun print-akk-cache ()
(print *akk-cache*))
(defun print-akk-calls-counter ()
(format t "~a~%" *akk-recursive-calls-counter*))
;; эта функция инициализирует кэш указанным размером
(defun init-akk-cache (m n)
(setf *akk-cache* nil)
(setf *akk-cache* (make-list m))
(let ((cache-row (make-list n :initial-element 0)))
(dotimes (i m)
(setf (nth i *akk-cache*) (copy-list cache-row))))
(return-from init-akk-cache t))
;; установка значения в кэше
(defun set-akk-cache-value (m n value)
(setf (nth n (nth m *akk-cache*)) value)
(return-from set-akk-cache-value t))
;; получение значения из кэша               
(defun get-akk-cache-value (m n)
(if (or (> m (length *akk-cache*)) (> n (length (nth 0 *akk-cache*))))
(format t "FUCK!~%"))
(let ((result (nth n (nth m *akk-cache*))))
(return-from get-akk-cache-value result)))
;; функция Аккермана без использования кэширования
(defun akk (m n)
(incf *akk-recursive-calls-counter*)
(cond ((= m 0) (+ n 1))
   ((= n 0) (akk (- m 1) 1))
   (t (akk (- m 1) (akk m (- n 1))))))
;; функция Аккермана с использованием кэширования
(defun akk-cache (m n)
(incf *akk-recursive-calls-counter*)
(if (/= (get-akk-cache-value m n) 0)
(return-from akk-cache (get-akk-cache-value m n))
(let ((value (cond ((= m 0) (+ n 1))
          ((= n 0) (akk-cache (- m 1) 1))
          (t (akk-cache (- m 1) (akk-cache m (- n 1)))))))
   (set-akk-cache-value m n value)
   (return-from akk-cache value))))
;;
(defun akk-with-calls-counting ()
(loop for m from 0 to 3 do
(loop for n from 0 to 14 do
    (setf *akk-recursive-calls-counter* 0)
    (format t "(~2a ~2a) ~12a [~a]~%" m n (akk m n) *akk-recursive-calls-counter*))))
(defun akk-cache-with-calls-counting ()
(loop for m from 0 to 3 do
(loop for n from 0 to 14 do
    (setf *akk-recursive-calls-counter* 0)
    (format t "(~2a ~2a) ~12a [~a]~%" m n (akk-cache m n) *akk-recursive-calls-counter*))))

Я работаю в Emacs/Inferior Lisp, поэтому привожу коды для запуска:

(init-akk-cache 10 1000000)
(akk-cache-with-calls-counting)

Я дошел до (3 14), дальше у меня шло переполнение стека (я 4 * не считал). Если возможно, посчитайте, пожалуйста, например, не от 0 до 3 и от 0 до 14, как сейчас, а от 0 до 5 и от 0 до 20, например. Если будет переполнение стека, то нужно увеличить размер кэша, например, на 10х10000000 и так далее.
Мой компьютер не позволяет мне такое сделать, буду очень благодарен, если поможете.
Также, если предложите улучшения в коде, с удовольствием выслушаю.

Хм, чем ты это так отформатировал? ;)
;; кэш для функции Аккермана
(defvar *akk-cache* nil)
;; счетчик рекурсивных вызовов (должен быть обнулен перед вызовом функции akk или akk-cache)
(defvar *akk-recursive-calls-counter* 0)
(defun print-akk-cache ()
  (print *akk-cache*))
(defun print-akk-calls-counter ()
  (format t "~a~%" *akk-recursive-calls-counter*))
;; эта функция инициализирует кэш указанным размером
(defun init-akk-cache (m n)
  (setf *akk-cache* nil)
  (setf *akk-cache* (make-list m))
  (let ((cache-row (make-list n :initial-element 0)))
    (dotimes (i m)
      (setf (nth i *akk-cache*) (copy-list cache-row))))
  (return-from init-akk-cache t))
;; установка значения в кэше
(defun set-akk-cache-value (m n value)
  (setf (nth n (nth m *akk-cache*)) value)
  (return-from set-akk-cache-value t))
;; получение значения из кэша                
(defun get-akk-cache-value (m n)
  (if (or (> m (length *akk-cache*)) (> n (length (nth 0 *akk-cache*))))
      (format t "FUCK!~%"))
  (let ((result (nth n (nth m *akk-cache*))))
    (return-from get-akk-cache-value result)))
;; функция Аккермана без использования кэширования
(defun akk (m n)
  (incf *akk-recursive-calls-counter*)
  (cond ((= m 0) (+ n 1))
        ((= n 0) (akk (- m 1) 1))
        (t (akk (- m 1) (akk m (- n 1))))))
;; функция Аккермана с использованием кэширования
(defun akk-cache (m n)
  (incf *akk-recursive-calls-counter*)
  (if (/= (get-akk-cache-value m n) 0)
      (return-from akk-cache (get-akk-cache-value m n))
      (let ((value (cond ((= m 0) (+ n 1))
                         ((= n 0) (akk-cache (- m 1) 1))
                         (t (akk-cache (- m 1) (akk-cache m (- n 1)))))))
        (set-akk-cache-value m n value)
        (return-from akk-cache value))))
;;
(defun akk-with-calls-counting ()
  (loop for m from 0 to 3 do
       (loop for n from 0 to 14 do
            (setf *akk-recursive-calls-counter* 0)
            (format t "(~2a ~2a) ~12a [~a]~%" m n (akk m n) *akk-recursive-calls-counter*))))
(defun akk-cache-with-calls-counting ()
  (loop for m from 0 to 3 do
       (loop for n from 0 to 14 do
            (setf *akk-recursive-calls-counter* 0)
            (format t "(~2a ~2a) ~12a [~a]~%" m n (akk-cache m n) *akk-recursive-calls-counter*))))

Я заменил списки на массив и стало выполняться мгновенно.

Отформатировал в Emacs'е нормально, просто при копировании не обратил внимание, что отступы исказились :).
А правда, что clisp без компиляции рекурсию не раскрывает, что нужно скомпилить в байт-код, тогда переполнения или не будет, или будет позже?

Вычисление A(4, 2) переполнило двухгигабайтный стек. :)
return-from не нужны.

Исправил на массивы - и правда работает быстрее, спасибо.
У меня 2ГБ ram, однако не могу вычислить (3 15) (уже с массивами) - Control stack guard page temporarily disabled: proceed with caution - переполняется стек.
Не могу понять, почему (кэш 10х100000). Пробовал увеличить кэш - не помогает, что вполне логично.

Покажите пожалуйста Ваш измененный код.

Так кажется короче (блин, что-то не могу победить нормально форматирование)

2andy128k
У Вас вычисление (4 2) переполнило _2ГБ_ стек? Я сделал цикл 0-4 внешний и 0-14 внутренний, оборвалось как у Вас на (4 2), однако в System Monitor написано, что память sbcl занимает ~ 400 МБ, что никак не 2ГБ.
Вероятно, у Вас получилось то же.
Тогда вопрос: можно ли избежать переполнения стека? (компиляция в байткод не помогает)

> Тогда вопрос: можно ли избежать переполнения стека? (компиляция в байткод не помогает)
Компиляция тут не при чём, я запускаю под SBCL - получаю тоже самое. Надо избавляться от рекурсии.

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

> Если я правильно понимаю, уйти от рекурсии в данной случае невозможно, так как функция аккремана на этом и построена.
От рекурсии всегда можно уйти ;)

А как в данном случае?

> А как в данном случае?
Ну, не так просто, как обычно :) Надо подумать... А что, очень надо?

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

Я последовательно увеличивал стек дошёл до 2ГБ. Дальше не стал.
Запускал так:
sbcl --control-stack-size 2048

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

Ну, если сможешь понять, то вот:
(defvar *akk-cache* nil)
(defun akk (x y)
  (let ((*akk-cache* (or *akk-cache*
                         (make-hash-table :test 'equal)))
        (stack `((,x ,y))))
    (labels ((akk-cache (m n)
               (gethash `(,m ,n) *akk-cache*))
             (new-value (value)
               (setf (gethash (car stack) *akk-cache*)
                     value)
               (cond
                 ((not stack) t)
                 ((not (second stack))
                  (pop stack))
                 ((second (second stack))
                  (pop stack))
                 (t (let ((m (first (car stack)))
                          (n (second (car stack)))
                          (i (first (second stack))))
                      (pop stack)
                      (pop stack)
                      (push (list i (gethash `(,m ,n) *akk-cache*))
                            stack))))))
      (loop
         while stack
         do (let ((m (first (car stack)))
                  (n (second (car stack))))
              (if (akk-cache m n)
                  (pop stack)
                  (cond ((= m 0)
                         (new-value (1+ n)))
                        ((and (= n 0)
                              (akk-cache (1- m) 1))
                         (new-value (akk-cache (1- m) 1)))
                        ((= n 0)
                         (push (list (1- m) 1)
                               stack))
                        ((and (akk-cache m (1- n))
                              (akk-cache (1- m)
                                         (akk-cache m (1- n))))
                         (new-value (akk-cache (1- m)
                                                  (akk-cache m (1- n)))))
                        ((akk-cache m (1- n))
                         (push (list (1- m)
                                     (akk-cache m (1- n)))
                               stack))
                        (t (push (list (1- m))
                                 stack)
                           (push (list m (1- n))
                                 stack))))))
      (akk-cache x y))))

А уВас этот код нормально выполняется/компилируется?

> А у Вас этот код нормально выполняется/компилируется?
Конечно, что не так?

Так это та же самая рекурсия. Только и того, что один стек заменён на другой.

На вычислении (akk 4 2) съело 3.5 гига памяти и было убито ядром.

> Так это та же самая рекурсия. Только и того, что один стек заменён на другой.
Это не рекурсия. Никакой рекурсии. Ну а куда же здесь без стэка? Можно, конечно, время от времени оставлять кэш, но сбрасывать стэк и начинать всё с начала, там можно будет больше посчитать, но будет дольше.

Еще можно так (на просторах интернета есть объяснение этому; см. ту же английскую википедию про эту функцию, а не русскую википедию про нее):
http://paste.lisp.org/display/96207   (не знаю как тут код вставлять).
Взято из вот тут http://www.ymeme.com/ackermann-function-lisp.html
p.s. как я понял, функция Аккермана интересна как раз в виде рекурсии, так как на ней проверяют насколько "смекалистый" компилятор по отошению к оптимизации рекурсий.

> как я понял, функция Аккермана интересна как раз в виде рекурсии, так как на ней проверяют насколько "смекалистый"> компилятор по отошению к оптимизации рекурсий.
Чего-то я плохо понял, о какой "смекалистости" идёт речь. Скорей уж, о накладных расходах на рекурсию...

О "смекалистости" читать тут http://en.wikipedia.org/wiki/Ackermann_function#Use_as_benchmark

Я здесь попробывал реализовать запись/чтение кэша в файл, у меня записывает около 21 МБ и выдает ошибку.
И, кстати, почему массивы работают быстрее, чем списки?

> И, кстати, почему массивы работают быстрее, чем списки?
rtfm! Вопрос исчерпан, нашел ответ в интернете.