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

---

Введение и постановка задачи

Если вы ни разу не слышали слово “мемоизация”, то проще всего будет уяснить суть этого понятия на следующем распространенном примере.

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

 После чего переработать функцию таким образом:

-         Для “частых” аргументов функция “достает” заранее вычисленные значения из хранилища;

-         Для других аргументов значения честно вычисляются функцией.

Совершенно очевидно, что такое преобразование увеличит общую скорость вычислений. Причем прирост скорости будет особенно заметен, когда:

-         Область определения функции достаточно узка;

-         Вычисления каждого значения из области определения достаточно затратны.

Приведенный пример, однако, не слишком впечатляет, поскольку требует переработки кода. Так вот: мемоизация – это преобразование функции (не затрагивающее ее код), дающее новую функцию, которая:

-         Содержит внутреннее хранилище данных ;

-         Получив очередной аргумент/аргументы, проверяет, не вычислялась ли уже функция для этого аргумента/аргументов;

-         Если функция уже вычислялась, результат извлекается из хранилища и возвращается;

-         Если функция для этого аргумента/аргументов еще не вычислялась, то выполняется вычисление, результат с соответствующим ключом запоминается в хранилище и возвращается как результат.

Идея, как видите, проста. А ее исполнение сильно зависит от языка программирования. И особенно легко реализуется эта идея в интерпретируемом языке, поддерживающим лямбда-функции. Такими языками являются, например, Питон и Лисп.

Как следует из названия заметки, все наши действия мы будем выполнять в Лиспе. (А в Питоне все уже “сделано до нас”). Я использую HomeLisp, но желающие, надеюсь, смогут перенести эти идеи в любую версию Лиспа без особого труда.

Давайте рассмотрим пример, ставший классическим – “лобовое” вычисление чисел Фибоначчи, последовательности, имеющей вид:

 F₀=1, F₁=1, F_n=F_n-1+F_n-2

 Код функции, вычисляющей число Фибоначчи с номером n пишется сразу:

(defun fib (n)
    (if (<= n 1) 1 (+ (fib (- n 1)) (fib (- n 2)))))

Функция столь же проста, сколь и неэффективна. Если, к примеру, запустить ее с параметром n=20, то возникнет заметная “пауза”. Почему? Ответ на этот вопрос легко получить, если запросить статистику выполнения отдельных функций Лиспа при вычислении. В HomeLisp для этого служит встроенная функция stat. При вычислении двадцатого числа Фибоначчи статистика вызовов получается такой:

Для того, чтобы вычислить 20-е число Фибоначчи, потребовалось более двадцати тысяч рекурсивных вызовов нашей fib (не считая такого же количества вычитаний и сравнений)!

В чем же причина?

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

Известен способ, позволяющий резко ускорить этот код – отказаться от параллельной рекурсии и использовать накопительные параметры (или вообще отказаться от рекурсии и решить задачу чисто итеративно)

(defun fib (n &optional (c 1) (p 0))  ;; рекурсия
   (if (zerop n) c (fib (- n 1) (+ c p) c)))

(defun fib (n) ;; итерация
  (let ((c 1)
           (p 0)
           (tmp 0))
    (dotimes (i n c)
      (setq tmp (+ c p) p c c tmp))))

Оба эти способа хороши всем, кроме одного – они нарушают “прозрачность” кода. Прямое рекурсивное вычисление легко сопоставляется с математической постановкой задачи. А ускоренные программы требуют анализа – связь этих программ с математической постановкой задачи отнюдь не очевидна. И это – большой недостаток. Ведь программы “читают” не только компиляторы, но и программисты. Прозрачность и понятность кода – ценнейшее качество.

Теперь мы можем сформулировать задачу. Имеется функция (пока – одного аргумента), нам необходимо построить новую функцию, которая будет “содержать старую функцию внутри”. Эта новая функция должна выполнять следующее:

-         Получив значение аргумента, проверить не вычислялась ли функция с этим аргументом ранее. Если вычислялась, достать из внутреннего хранилища значение функции и вернуть его.

-         Если значение ранее не вычислялось, вычислить его (обратясь к “старой” функции), занести пару (аргумент, значение-функции) во внутреннее хранилище и вернуть вычисленное значение.

Первая реализация

Начнем реализацию с того, что выберем внутреннее хранилище. Проще всего для первых экспериментов выбрать ассоциативный список. Это классическая структура данных, широко используемая в Лиспе. Ассоциативный список состоит из пар “ключ-значение”. Для получения значения по ключу служит встроенная функция assoc. Она берет на вход список и ключ, а возвращает пару, соответствующую ключу (или nil, если ключ не найден). Извлечь значение из пары должен программист. Почему так неудобно? Разве не проще было бы сразу возвращать значение по ключу? Причина в том, что если возвращать "чистое значение", то невозможно будет отличить случай отсутствия значения (возврат Nil), от случая, когда Nil является легальным значением.

Теперь давайте возьмем нашу первую реализацию fib (основанную на математическом определении последовательности Фибоначчи) и доработаем ее в соответствии механизмом мемоизации. Сразу возникнет вопрос: где разместить ассоциативный список (в котором будут храниться результаты вычислений). В теле fib хранить этот список бессмысленно – все локальные переменные при каждом вызове функции создаются заново, а статических переменных в Лиспе нет. Как же быть?

На помощь придет замыкание - функция с зафиксированными на момент создания значениями ее свободных переменных. Свободная переменная – это переменная, входящая в тело функции, но не входящая в список параметров и не созданной внутри функции с помощью let/let*. Проще всего замыкание в HomeLisp создается заданием функции (с помощью defun) в области действия let-конструкции. Это выглядит так:

(let ((asso nil))
   (defun fib (n)
    (if (<= n 1) 1 (+ (fib (- n 1)) (fib (- n 2))))))

Получившаяся функция fib с виду совсем обычна: ее можно вызвать с одним аргументом и получить правильное значение:

(fib 5)
==> 8

Но есть и существенное отличие – теперь у функции имеется контекст (содержащий, естественно, переменную asso). В HomeLisp  этот контекст можно увидеть:

(context 'fib)
==> ((ASSO NIL))

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

(let ((asso nil))
  (defun fib (n) 
      (let ((tmp (assoc n asso)))
          (if tmp (cdr tmp)
              (let ((r (if (<= n 1) 1 (+ (fib (- n 1)) (fib (- n 2))))))
                     (push (cons n r) asso) r)))))  

Что внутри? Когда fib получит управление (с конкретным значением n), первым делом выполняется попытка "достать" из ассоциативного списка значение fib(n), используя n как ключ.

Если попытка успешна, то переменная tmp получит значение соответствующей пары. Остается вернуть результат, взяв cdr этой пары.

Если же ключа n в ассоциативном списке нет, то смело вычисляем нужное значение (да-да, с той самой параллельной рекурсией) и присваиваем результат переменной r. Добавляем пару (n . r) в ассоциативный список (это делает push) и возвращаем r. Всё!

Функцию fib можно проверить "в деле":

(fib 10)
==> 89

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

(context 'fib)
==> ((ASSO ((10 . 89) (9 . 55) (8 . 34) (7 . 21) (6 . 13) (5 . 8) (4 . 5) (3 . 3)
            (2 . 2) (0 . 1) (1 . 1))))

Что же, для мемоизации функции нужно всякий раз вручную подобным образом перерабатывать ее код? Конечно, нет. Мы сейчас создадим макро "memoize", которое будет "брать" обычную функцию и автоматически строить нужное замыкание под прежним именем.

Макро – это очень хитрая функция Лиспа. Ее вычисление имеет две особенности:

-         ядро Лиспа не вычисляет значения аргументов macro;

-         макро вычисляется в два этапа: на первом этапе строится форма, которая вычисляется на втором этапе (в текущем окружении переменных).

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

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

Прежде, чем браться за макро, следует сказать пару слов об одной возможности HomeLisp. Имеется встроенная функция getd, которая обеспечивает доступ к телу любой функции, написанной на Лиспе. Как это работает – показано ниже:

(defun fib (n)
   (if (<= n 2) 1 (+ (fib (- n 1)) (fib (- n 2)))))

(getd 'fib)
==> (EXPR (N) (IF (<= N 2) 1 (+ (FIB (- N 1)) (FIB (- N 2)))))

Как можно убедиться, мы получаем доступ к телу fib и к списку параметров. Теперь начнем конструировать макро. Делать это мы будем постепенно.

(defmacro memoize (f)
  (let ((body (cdr (getd f)))
           (parm (cadr (getd f)))) ...

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

(defmacro memoize (f)
  (let ((body (cdr (getd f)))
(parm (cadr (getd f))))
      `(let ((asso nil)) ...

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

Для тех, кто не знаком с обратной блокировкой, следует сказать несколько слов. Обычный апостроф блокирует вычисление всех символов выражения, а обратный – только тех, перед которыми не стоит запятая. Вот пример:

(let ((a 111))
  `(a ,a))

==> (A 111)

Видим, что первый символ A остался без изменения, а второй (перед которым стоит запятая) заменен своим значением.

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

(let ((a '(1 1 1)))
  `(a ,a))

==> (A (1 1 1))

Все вполне логично: символ заменился значением. Но иногда бывает нужно, чтобы символы списка “встали на базовый уровень” (т.е. иногда нужно “убрать” мешающие скобки). Для этого перед нужным символом следует поставить пару “,@”:

(let ((a '(1 1 1)))
  `(a ,@a))

==> (A 1 1 1)

Теперь вернемся в наше макро. Дальше должна размещаться конструкция defun:

(defmacro memoize (f)
  (let ((body (cdr (getd f)))
        (parm (cadr (getd f))))
   `(let ((asso nil))
    (defun ,f ,parm
        (let ((tmp (assoc ,@parm asso)))
            (if tmp (cdr tmp)
                (let ((r ((lambda ,@body) ,@parm)))
                  (push (cons ,@parm r) asso) r)))))))

Рассмотрим более подробно то, что “происходит” внутри. Для нашей функции fib, значением переменной body будет список:

((N) (IF (<= N 2) 1 (+ (FIB (- N 1)) (FIB (- N 2))))) 

Значением переменной parm будет список (N), а значением переменной f будет имя нашей функции – fib. А теперь аккуратно подставим значения этих переменных в тело `let. Получим:

`(let ((asso nil))
    (defun fib (N)
         (let ((tmp (assoc N asso)))
              (if tmp (cdr tmp)
                 (let ((r ((lambda (N) (if (<= N 2) 1 (+ (FIB (- N 1)) (FIB (- N 2))))) N)))
                        (push (cons N r) asso) r )))))

Мы присваиваем локальной переменной r значение очередного числа Фибоначчи, затем заносим соответствующую пару в локальный ассоциативный список замыкания и возвращаем значение r как результат.

Прежде чем двигаться дальше, следует обратить внимание на два тонких момента.

Для внутреннего вызова “начинки” мемоизируемой функции мы использовали лямбда-выражение. Его формальный параметр – символ N. И этот же символ является и фактическим параметром. Подобная ситуация может вызвать замешательство, но она вполне корректна – значение фактического параметра будет присвоено при вызове нашей будущей функции fib. Если замешательство не прошло, взгляните на пример ниже:

(let ((x 4))
   ((lambda (x) (* x x)) x))

==> 16

Второй тонкий момент связан с самим макро. Создавая макро нужно быть предельно осторожным при выборе имен для рабочих переменных. Если второй этап вычисления макро порождает какой-то вычислительный процесс в исходном окружения, и какое-либо внутреннее имя совпадает с именем переменной из окружения, то может произойти т.н. “захват переменной” – крайне неприятный эффект (подробности – в знаменитой книге П.Грэма “ANSI Common Lisp”). К счастью, в нашем случае таких “опасных переменных”, кажется, нет.

Итак, макро мемоизации готово. Убедимся, что макро работает не только для функции fib. Создадим функцию, которая вычисляет члены последовательности, в которой очередной равен сумме трех предыдущих:

(defun g (n) 
   (if (< n 2) 1 (+ (g (- n 1)) (g (- n 2)) (g (- n 3)))))

Проверим ее работоспособность:

(g 6)
==> 31

(g 10)
==> 355

Функция работает. Попробуем применить к ней наше макро:

(memoize g)
==> G

(g 10)
==> 355

(context 'g)
==> ((ASSO ((10 . 355) (9 . 193) (8 . 105) (7 . 57) (6 . 31) (5 . 17) (4 . 9) (3 . 5) (2 . 3) (-1 . 1) (0 . 1) (1 . 1))))

А если переменных несколько

На этом можно было бы остановиться. Но у нашего макро есть один серьезный недостаток: легко убедиться, что макро не будет работать с функцией нескольких переменных. Как решить эту проблему? В чем разница между одной или более переменными в списке параметров? Пусть вместо одного параметра будет список. Список вполне может быть ключом ассоциативного списка. Чуть подправим наше макро:

(defmacro memoize (f)
  (let ((body (cdr (getd f)))
        (parm (cadr (getd f))))
   `(let ((asso nil))
     (defun ,f ,parm
          (let ((tmp (assoc (list ,@parm) asso)))
              (if tmp (cdr tmp)
                  (let ((r ((lambda ,@body) ,@parm)))
                       (push (cons (list ,@parm) r) asso) r)))))))

Что сделано? В двух местах (там, где идет обращение к ассоциативному списку)  фактические параметры “заключены в скобки”. Конструкция (list ,@parm) может показаться странной: сначала мы (с помощью @) удаляем скобки, а затем тут же добавляем… Не проще ли просто написать  ,parm? Не проще! Если бы мы попробовали это сделать, то у нас получилось бы (для мемоизируемой функции двух переменных x и y):

(let ((tmp (assoc (x y) asso))) …

При вызове мемоизированной функции с параметрами, к примеру, x=5, y=6 этот фрагмент породит ошибку “отсутствие функции 5”.

Проверим работоспособность макро  на достаточно “дикой” функции:

(defun g (x y)
  (cond ((or (<= x 0) (<= y 0)) 1)
              (t (+ (g (- x 1) y) (g x (- y 1)) (g (- x 2) (- y 2))))))

По той же причине, что и наша первая fib, эта функция будет вычисляться очень долго. Но код работоспособен:

(g 6 7)
==> 5139

Мемоизируем функцию g и повторяем вычисления:

(memoize g)
==> G

(g 6 7)
==> 5139

На моем компьютере мемоизированная функция для аргументов 6 и 7 вычисляется за время, сопоставимое, со временем работы исходного варианта функции. Понятно, что после первого вычисления, последующие будут “выполняться” мгновенно, но все же обидно – прироста производительности почти нет…

Причина – в ассоциативном списке. Поиск в ассоциативном списке выполняется за время O(n). Пришло время отказаться от ассоциативного списка и использовать вместо него хэш-таблицу. Поиск в хэш-таблице осуществляется быстрее, чем в ассоциативном списке. Посмотрим, даст ли замена ассоциативного списка на хэш-таблицу прирост производительности.

Хэш вместо ассоциативного списка

В HomeLisp имеется встроенная хэш-таблица (основанная на известном майкрософтовском dictionary). Для работы с хэш-таблицей ее нужно предварительно создать (вызвав hashCreate). Затем можно заносить и извлекать данные, а также проверять наличие данных с заданным ключом. Подробнее - здесь.

Функции hashCreate нужно дать на вход “чистый” атом. После успешного завершения список свойств этого атома модифицируется и атом станет “идентификатором” хэш-таблицы. Идентификаторы хэш-таблиц глобальны. Для нас это очень важно – если при мемоизации функции будет создаваться новая хэш-таблица, нужно обеспечить уникальность ее идентификатора. Проще всего сделать это можно с помощью стандартной функции gensym (создающей при каждом вызове уникальный атом).

Переработанное макро может иметь вид:

(defmacro memoize (f)
  (let ((h    (gensym 'hash))
        (body (cdr (getd f)))
        (parm (cadr (getd f))))
   `(let ((!hash (quote ,h)))
        (hashCreate (quote ,h))
        (defun ,f ,parm
	   (if (hashKeyExist (quote ,h) (output (list ,@parm))) 
	        (car (hashGet (quote ,h) (output (list ,@parm))))
              (let ((r ((lambda ,@body) ,@parm)))
		    (hashPut (quote ,h) (output (list ,@parm)) r) r)))))) 

Новое макро в целом повторяет старое. Только обращения к ассоцитивному списку замены обращением к хэш-таблице. Переменная h на первом этапе раскрытия макро получит уникальное значение (что-то вроде hash3). Мы запоминаем это значение (оно может пригодиться), а дальше выполняем те же построения, что и для версии с ассоциативным списком. В качестве ключа мы используем список параметров, преобразованный в строку (это делает функция output). Все остальное – то же самое, что и в версии с ассоциативным списком.

Проверяем работоспособность и убеждаемся, что скорость работы мемоизированной функции выше в несколько раз (на моей машине – в 3-4 раза).

Мы можем поинтересоваться контекстом нашей функции. Но результатов вычислений мы уже не увидим – они скрыты в хэш-таблице. Единственное, что можно увидеть – это идентификатор этой таблицы:

(context 'g)
==> ((!HASH HASH5))

А теперь можно и “полюбоваться” на результаты предыдущих вычислений (с помощью встроенной функции hashMap):

(hashMap 'hash5 (lambda (k v) (printline (list k v))) )

("(0 7)" 1)
("(0 6)" 1)
… … …
("(6 5)" 1241)
("(6 6)" 2643)
("(6 7)" 5139)

Комментарии здесь, я полагаю, излишни.

Последний "бантик"

Нам осталось совсем немного – хотелось бы иметь возможность восстановить исходную функцию. Сейчас мы напишем макро unmemoize, которое восстановит исходный вид мемоизированной функции.

Для этого следует в контексте хранить какой-либо ключ, который будет признаком того, что замыкание есть результат мемоизирования. Это сделать совсем легко:

(defmacro memoize (f)
  (let ((h    (gensym 'hash))
        (body (cdr (getd f)))
        (parm (cadr (getd f))))
   `(let ((!memoize (quote ,f))
          (body (quote ,body))
          (!hash (quote ,h)))
        (hashCreate (quote ,h))
        (defun ,f ,parm
	      (if (hashKeyExist (quote ,h) (output (list ,@parm))) 
		      (car (hashGet (quote ,h) (output (list ,@parm))))
              (let ((r ((lambda ,@body) ,@parm)))
				    (hashPut (quote ,h) (output (list ,@parm)) r) r))))))

Кроме ключа мы сохранили и исходное тело функции. Сейчас это нам понадобится. Пишем макро unmemoize:

(defmacro unmemoize (f)
  (if (null (assoc '!memoize (context f))) (raiseerror "Функция не была мемоизирована!")
      (let* ((context (context f))
             (body    (cadr (assoc 'body context))))
	             (hashDestroy (cadr (assoc '!hash context)))  
               `(defun ,f ,@body))))

Разберем этот код. На первом этапе раскрытия макро происходит обращение к контексту f. Если в контексте найден ключ !memoize (а контекст замыкания есть не что иное, как ассоциативный список), то мы на правильном пути. Если же ключ не найден (или контекст вообще пуст), то возбуждаем состояние ошибки.

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

Итак, мы реализовали вполне работоспособный вариант мемоизации, причем весьма простыми средствами.

 Спасибо, что дочитали до конца!

Недавно мне попалась интересная статья  Автор размышляет на тему “Почему невозможно создать идеальный язык программирования”. Приводит множество резонных соображений. Но в конце проговаривается о том, что идеальный язык давно создан и, как вы думаете, он называется?