Мемоизация
В вычислительной технике мемоизация или мемоизация — это метод оптимизации, используемый в первую очередь для ускорения компьютерных программ путем сохранения результатов дорогостоящих вызовов функций в чистые функции и возврата кэшированного результата, когда те же входные данные повторяются. Мемоизация также использовалась в других контекстах (и для целей, отличных от увеличения скорости), например, при простом взаимно-рекурсивном анализе спуска. [1] Это тип кэширования , отличающийся от других форм кэширования, таких как буферизация и замена страниц . В контексте некоторых языков логического программирования мемоизация также известна как таблица . [2]
Этимология
[ редактировать ]Термин мемоизация был придуман Дональдом Мичи в 1968 году. [3] и происходит от латинского слова memorandum («чтобы запомнить»), которое в американском английском обычно сокращается до memo , и, таким образом, означает «превращение [результатов] функции в нечто, что нужно запомнить». Хотя мемоизацию можно спутать с запоминанием (поскольку они являются этимологическими родственниками ), мемоизация имеет особое значение в вычислительной технике.
Обзор
[ редактировать ]Мемоизированная функция «запоминает» результаты, соответствующие некоторому набору конкретных входных данных. Последующие вызовы с запомненными входными данными возвращают запомненный результат, а не пересчитывают его, тем самым исключая основную стоимость вызова с заданными параметрами из всех, кроме первого вызова функции с этими параметрами. Набор запоминаемых ассоциаций может быть набором фиксированного размера, управляемым алгоритмом замены, или фиксированным набором, в зависимости от характера функции и ее использования. Функцию можно запомнить только в том случае, если она ссылочно прозрачна ; то есть только в том случае, если вызов функции имеет тот же эффект, что и замена этого вызова функции ее возвращаемым значением. (Однако существуют особые исключения из этого ограничения.) Несмотря на то, что мемоизация связана с таблицами поиска , поскольку мемоизация часто использует такие таблицы в своей реализации, мемоизация заполняет свой кэш результатов прозрачно на лету, по мере необходимости, а не заранее.
Мемоизированные функции оптимизированы по скорости в обмен на более активное использование компьютера памяти . Временная/пространственная «стоимость» алгоритмов имеет в вычислительной технике особое название: вычислительная сложность . Все функции имеют вычислительную сложность во времени (т.е. для их выполнения требуется время) и в пространстве .
Несмотря на то, что происходит компромисс между пространством и временем (т. е. используемое пространство - это выигрыш в скорости), это отличается от некоторых других оптимизаций, которые включают компромисс между временем и пространством, таких как уменьшение силы , тем, что мемоизация - это время выполнения, а не время компиляции. оптимизация. Более того, уменьшение силы потенциально заменяет дорогостоящую операцию, такую как умножение, на менее затратную операцию, такую как сложение, а результаты экономии могут сильно зависеть от машины (непереноситься между машинами), тогда как мемоизация является более машинонезависимым перекрестным процессом. -платформенная стратегия.
Рассмотрим следующую функцию псевдокода вычисления факториала n для :
function factorial (n is a non-negative integer)
if n is 0 then
return 1 [by the convention that 0! = 1]
else
return factorial(n – 1) times n [recursively invoke factorial
with the parameter 1 less than n]
end if
end function
Для любого целого числа n такого, что n ≥ 0, конечный результат функции factorial является инвариантным ; если вызывается как x = factorial(3), результат таков, что x будет всегда присвоено значение 6. Приведенная выше немемоизированная реализация, учитывая природу используемого рекурсивного алгоритма, потребует n + 1 вызовов factorial для получения результата, и каждый из этих вызовов, в свою очередь, имеет соответствующую стоимость в виде времени, которое требуется функции для возврата вычисленного значения. В зависимости от машины эта стоимость может составлять сумму:
- Стоимость настройки кадра функционального стека вызовов.
- Стоимость сравнения n с 0.
- Стоимость вычитания 1 из n .
- Стоимость настройки кадра стека рекурсивных вызовов. (Как указано выше.)
- Стоимость умножения результата рекурсивного вызова
factorialпо н . - Стоимость сохранения возвращаемого результата, чтобы его можно было использовать вызывающим контекстом.
В немемоизированной реализации каждый вызов верхнего уровня factorial включает совокупную стоимость шагов со 2 по 6, пропорциональную начальному значению n .
Мемоизированная версия factorial функция следующая:
function factorial (n is a non-negative integer)
if n is 0 then
return 1 [by the convention that 0! = 1]
else if n is in lookup-table then
return lookup-table-value-for-n
else
let x = factorial(n – 1) times n [recursively invoke factorial
with the parameter 1 less than n]
store x in lookup-table in the nth slot [remember the result of n! for later]
return x
end if
end function
В этом конкретном примере, если factorial сначала вызывается со значением 5, а затем вызывается позже с любым значением, меньшим или равным пяти, эти возвращаемые значения также будут запомнены, поскольку factorial будет вызываться рекурсивно со значениями 5, 4, 3, 2, 1 и 0, а возвращаемые значения для каждого из них будут сохранены. Если затем он вызывается с номером больше 5, например 7, будет выполнено только 2 рекурсивных вызова (7 и 6), а значение 5! будут сохранены с предыдущего вызова. Таким образом, мемоизация позволяет функции становиться более эффективной по времени, чем чаще она вызывается, что в конечном итоге приводит к общему ускорению.
Некоторые другие соображения
[ редактировать ]Функциональное программирование
[ редактировать ]![[икона]](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Wiki_letter_w_cropped.svg/20px-Wiki_letter_w_cropped.svg.png){kind=small} | Этот раздел нуждается в расширении . Вы можете помочь, добавив к нему . ( апрель 2014 г. ) |
Мемоизация широко используется в компиляторах функциональных языков программирования , которые часто используют стратегию оценки вызова по имени . Чтобы избежать накладных расходов при вычислении значений аргументов, компиляторы этих языков активно используют вспомогательные функции, называемые thunks , для вычисления значений аргументов и запоминают эти функции, чтобы избежать повторных вычислений.
Автоматическое запоминание
[ редактировать ]Хотя мемоизация может быть добавлена к функциям внутренне и явно программистом , почти так же, как и вышеприведенная мемоизированная версия factorial реализована, ссылочно прозрачные функции также могут автоматически запоминаться извне . [1] Методы, использованные Питером Норвигом, применяются не только в Common Lisp (языке, на котором в его статье продемонстрировано автоматическое запоминание), но и в различных других языках программирования . Применение автоматического запоминания также было официально изучено при изучении переписывания терминов. [4] и искусственный интеллект . [5]
В языках программирования, где функции являются объектами первого класса (например , Lua , Python или Perl [6] ), автоматическое запоминание может быть реализовано путем замены (во время выполнения) функции ее вычисленным значением после того, как значение было вычислено для заданного набора параметров. Функция, выполняющая такую замену значения на объект-функцию, может в общих чертах обертывать любую ссылочно прозрачную функцию. Рассмотрим следующий псевдокод (где предполагается, что функции являются значениями первого класса):
function memoized-call (F is a function object parameter)
if F has no attached array values then
allocate an associative array called values;
attach values to F;
end if;
if F.values[arguments] is empty then
F.values[arguments] = F(arguments);
end if;
return F.values[arguments];
end function
Чтобы вызвать автоматически сохраненную версию factorial используя описанную выше стратегию, вместо вызова factorial напрямую, код вызывает memoized-call(factorial(n)). Каждый такой вызов сначала проверяет, выделен ли массив-держатель для хранения результатов, и если нет, присоединяет этот массив. Если в позиции нет записи values[arguments] (где arguments используются как ключ ассоциативного массива), реальный вызов осуществляется factorial с предоставленными аргументами. Наконец, запись в массиве в ключевой позиции возвращается вызывающей стороне.
Вышеупомянутая стратегия требует явного переноса при каждом вызове функции, которую необходимо запомнить. В тех языках, которые допускают замыкания , мемоизация может осуществляться неявно через фабрику функторов , которая возвращает обернутый мемоизированный функциональный объект в шаблоне декоратора . В псевдокоде это можно выразить следующим образом:
function construct-memoized-functor (F is a function object parameter)
allocate a function object called memoized-version;
let memoized-version(arguments) be
if self has no attached array values then [self is a reference to this object]
allocate an associative array called values;
attach values to self;
end if;
if self.values[arguments] is empty then
self.values[arguments] = F(arguments);
end if;
return self.values[arguments];
end let;
return memoized-version;
end function
Вместо того, чтобы позвонить factorial, новый объект функции memfact создается следующим образом:
memfact = construct-memoized-functor(factorial)
В приведенном выше примере предполагается, что функция factorial уже было определено до вызова construct-memoized-functor сделано. Начиная с этого момента, memfact(n) факториал n вызывается всякий раз, когда требуется . В таких языках, как Lua, существуют более сложные методы, которые позволяют заменять функцию новой функцией с тем же именем, что позволяет:
factorial = construct-memoized-functor(factorial)
По сути, такие методы включают в себя присоединение исходного объекта функции к созданному функтору и перенаправление вызовов исходной функции, запоминаемой через псевдоним, когда требуется вызов фактической функции (во избежание бесконечной рекурсии ), как показано ниже:
function construct-memoized-functor (F is a function object parameter)
allocate a function object called memoized-version;
let memoized-version(arguments) be
if self has no attached array values then [self is a reference to this object]
allocate an associative array called values;
attach values to self;
allocate a new function object called alias;
attach alias to self; [for later ability to invoke F indirectly]
self.alias = F;
end if;
if self.values[arguments] is empty then
self.values[arguments] = self.alias(arguments); [not a direct call to F]
end if;
return self.values[arguments];
end let;
return memoized-version;
end function
(Примечание. Некоторые из показанных выше шагов могут неявно управляться языком реализации и приведены для иллюстрации.)
Парсеры
[ редактировать ]Когда нисходящий синтаксический анализатор пытается проанализировать неоднозначные входные данные относительно неоднозначной контекстно-свободной грамматики (CFG), ему может потребоваться экспоненциальное количество шагов (относительно длины входных данных), чтобы опробовать все альтернативы CFG. для создания всех возможных деревьев разбора. В конечном итоге это потребует экспоненциального объема памяти. Мемоизация была исследована как стратегия синтаксического анализа в 1991 году Питером Норвигом, который продемонстрировал, что алгоритм, аналогичный использованию динамического программирования и наборов состояний в алгоритме Эрли (1970), а также таблиц в алгоритме CYK Кока, Янгера и Касами, может генерироваться путем введения автоматического запоминания в простой с обратным отслеживанием анализатор рекурсивного спуска для решения проблемы экспоненциальной временной сложности. [1] Основная идея подхода Норвига заключается в том, что когда к входным данным применяется синтаксический анализатор, результат сохраняется в memotable для последующего повторного использования, если тот же синтаксический анализатор когда-либо повторно применяется к тем же входным данным.
Ричард Фрост и Барбара Шидловски также использовали мемоизацию для уменьшения экспоненциальной временной сложности синтаксических комбинаторов , описывая результат как запоминающий чисто функциональный языковой процессор с нисходящим обратным отслеживанием. [7] Фрост показал, что базовые мемоизированные комбинаторы парсеров можно использовать в качестве строительных блоков для создания сложных парсеров как исполняемых спецификаций CFG. [8] [9]
Мемоизация была снова исследована в контексте синтаксического анализа в 1995 году Марком Джонсоном и Йохеном Дёрре. [10] [11] В 2002 году он был достаточно глубоко исследован Брайаном Фордом в форме, названной разбором Packrat . [12]
В 2007 году Фрост, Хафиз и Каллаган [ нужна ссылка ] описал алгоритм нисходящего анализа, который использует мемоизацию для отказа от избыточных вычислений и обработки любой формы неоднозначной CFG за полиномиальное время ( Θ (n 4 ) для леворекурсивных грамматик и Θ(n 3 ) для нелеворекурсивных грамматик). Их алгоритм синтаксического анализа сверху вниз также требует полиномиального пространства для потенциально экспоненциальных неоднозначных деревьев синтаксического анализа посредством «компактного представления» и «группировки локальных неоднозначностей». Их компактное представление сравнимо с компактным представлением восходящего синтаксического анализа Томиты . [13] Их использование мемоизации не ограничивается только получением ранее вычисленных результатов, когда анализатор многократно применяется к одной и той же входной позиции (что важно для требования полиномиального времени); он специализируется на выполнении следующих дополнительных задач:
- Процесс мемоизации (который можно рассматривать как «обертку» для выполнения любого синтаксического анализатора) обеспечивает постоянно растущий прямой леворекурсивный анализ, налагая ограничения на глубину в отношении длины ввода и текущей позиции ввода.
- Процедура «поиска» в мемо-таблице алгоритма также определяет возможность повторного использования сохраненного результата путем сравнения вычислительного контекста сохраненного результата с текущим контекстом синтаксического анализатора. Это контекстное сравнение является ключом к использованию косвенной (или скрытой) левой рекурсии .
- При успешном поиске в memotable вместо возврата полного набора результатов процесс возвращает только ссылки на фактический результат и в конечном итоге ускоряет общие вычисления.
- Во время обновления таблицы памяти процесс запоминания группирует (потенциально экспоненциальные) неоднозначные результаты и обеспечивает требования к полиномиальному пространству.
Фрост, Хафиз и Каллаган также описали реализацию алгоритма в PADL'08. [ нужна ссылка ] как набор функций высшего порядка (называемых комбинаторами синтаксического анализатора ) в Haskell , что позволяет создавать непосредственно исполняемые спецификации CFG как языковых процессоров. Важность способности их полиномиального алгоритма справляться с «любой формой неоднозначных CFG» с нисходящим синтаксическим анализом жизненно важна для синтаксического и семантического анализа во время обработки естественного языка . На сайте X-SAIGA можно найти дополнительную информацию об алгоритме и деталях реализации.
Хотя Норвиг увеличил мощность анализатора за счет мемоизации, расширенный анализатор по-прежнему был таким же сложным по времени, как алгоритм Эрли, который демонстрирует случай использования мемоизации для чего-то другого, кроме оптимизации скорости. Джонсон и Дорре [11] продемонстрировать еще одно такое применение мемоизации, не связанное со скоростью: использование мемоизации для задержки разрешения лингвистических ограничений до момента синтаксического анализа, где накоплено достаточно информации для разрешения этих ограничений. Напротив, в применении мемоизации для оптимизации скорости Форд продемонстрировал, что мемоизация может гарантировать, что синтаксический анализ грамматик выражений может анализировать за линейное время даже те языки , которые приводят к наихудшему поведению с возвратом. [12]
Рассмотрим следующую грамматику :
S → (A c) | (B d) A → X (a|b) B → X b X → x [X]
(Примечание: в приведенном выше примере продукция S → (A c ) | (B d ) гласит: «An S — это либо A , за которым следует a c , либо B, за которым следует a d ». Продукция X → x [ X] гласит: « X — это x, за которым следует необязательный X ».)
Эта грамматика генерирует один из следующих трех вариантов строки : xac , xbc или xbd (где x здесь понимается как один или несколько ) x . Далее рассмотрим, как эта грамматика, используемая в качестве спецификации синтаксического анализа, может повлиять на Разбор строки xxxxxxbd сверху вниз и слева направо :
- Правило A распознает xxxxxb (сначала спускаясь в X для распознавания одного x и снова спускаясь в X до тех пор, пока все x не будут израсходованы, а затем распознавая b ), а затем возвращаясь в S и не распознавая c . Следующее предложение S затем спустится в B, который, в свою очередь, снова спустится в X и распознает x посредством множества рекурсивных вызовов X , а затем a b , вернется к S и, наконец, распознает a d .
Ключевое понятие здесь заложено во фразе спускается в X. снова Процесс просмотра вперед, неудачи, резервного копирования и повторной попытки следующей альтернативы известен в синтаксическом анализе как возврат назад, и именно возврат назад предоставляет возможности для запоминания при синтаксическом анализе. Рассмотрим функцию RuleAcceptsSomeInput(Rule, Position, Input), где параметры следующие:
Rule— имя рассматриваемого правила.Positionэто смещение, которое в данный момент рассматривается во входных данных.Inputявляется рассматриваемым входом.
Пусть возвращаемое значение функции RuleAcceptsSomeInput быть длиной ввода, принятого Ruleили 0, если это правило не принимает никаких входных данных по этому смещению в строке. В сценарии обратного отслеживания с такой мемоизацией процесс синтаксического анализа выглядит следующим образом:
- Когда правило A спускается в X со смещением 0, оно запоминает длину 5 относительно этой позиции и X. правила После неудачи в d , B затем, вместо того, чтобы снова спуститься в X , запрашивает позицию 0 по правилу X в механизме запоминания и возвращает длину 5, тем самым избавляя от необходимости снова спускаться в X , и продолжает как если бы он спускался в X столько же раз, сколько раньше.
В приведенном выше примере может произойти один или несколько спусков на X , что позволяет использовать такие строки, как xxxxxxxxxxxxxxxxbd . Фактически, может быть любое количество x перед b . В то время как вызов S должен рекурсивно спускаться в X столько раз, сколько имеется x , B вообще никогда не придется спускаться в X, поскольку возвращаемое значение RuleAcceptsSomeInput(X, 0, xxxxxxxxxxxxxxxxbd) будет 16 (в данном конкретном случае).
Те парсеры, которые используют синтаксические предикаты , также способны запоминать результаты анализа предикатов, тем самым сокращая такие конструкции, как:
S → (A)? A A → /* some rule */
к одному спуску в A .
Если синтаксический анализатор создает дерево синтаксического анализа во время синтаксического анализа, он должен запомнить не только длину входных данных, которая соответствует некоторому смещению заданному правилу, но также должен сохранить поддерево, сгенерированное этим правилом, с этим смещением в ввода, поскольку последующие вызовы правила синтаксическим анализатором фактически не будут спускаться и перестраивать это дерево. По той же причине мемоизированные алгоритмы синтаксического анализатора, которые генерируют вызовы внешнего кода (иногда называемые процедурой семантического действия ) при совпадении правила, должны использовать некоторую схему, гарантирующую вызов таких правил в предсказуемом порядке.
Поскольку для любого синтаксического анализатора с обратным отслеживанием или синтаксическими предикатами не каждая грамматика потребует обратного отслеживания или проверки предикатов, накладные расходы на сохранение результатов анализа каждого правила по каждому смещению во входных данных (и сохранение дерева синтаксического анализа, если процесс синтаксического анализа делает это неявно) могут фактически замедляет парсер. Этот эффект можно смягчить путем явного выбора тех правил, которые анализатор будет запоминать. [14]
См. также
[ редактировать ]- Приближенные вычисления - категория методов повышения эффективности.
- Теория сложности вычислений – дополнительная информация о сложности алгоритмов
- Строка директора – быстрый поиск свободных переменных в выражениях.
- Шаблон Flyweight объектного программирования — шаблон проектирования , который также использует своего рода мемоизацию.
- Hashlife — метод запоминания для ускорения вычислений клеточных автоматов.
- Ленивая оценка - разделяет некоторые концепции с мемоизацией.
- Материализованное представление – аналогичное кэширование в запросах к базе данных.
- Частичная оценка - родственный метод автоматической оптимизации программы.
Ссылки
[ редактировать ]- ^ Перейти обратно: а б с Норвиг, Питер (1991). «Методы автоматического запоминания с помощью приложений для контекстно-свободного анализа» . Компьютерная лингвистика . 17 (1): 91–98.
- ^ Уоррен, Дэвид С. (1 марта 1992 г.). «Мемориалы для логических программ» . Коммуникации АКМ . 35 (3): 93–111. дои : 10.1145/131295.131299 . ISSN 0001-0782 .
- ^ Мичи, Дональд (1968). « Функции Memo и машинное обучение» (PDF) . Природа . 218 (5136): 19–22. Бибкод : 1968Natur.218...19M . дои : 10.1038/218019a0 . S2CID 4265138 .
- ^ Хоффман, Бертольд (1992). «Переписывание терминов с обменом и мемоизацией». В Киршнере, Х.; Леви, Г. (ред.). Алгебраическое и логическое программирование: Третья международная конференция, материалы, Вольтерра, Италия, 2–4 сентября 1992 г. Конспекты лекций по информатике. Том. 632. Берлин: Шпрингер. стр. 128–142. дои : 10.1007/BFb0013824 . ISBN 978-3-540-55873-6 .
- ^ Мэйфилд, Джеймс; и др. (1995). «Использование автоматического запоминания как инструмента разработки программного обеспечения в реальных системах искусственного интеллекта» (PDF) . Материалы одиннадцатой конференции IEEE по искусственному интеллекту для приложений (CAIA '95) . стр. 87–93. дои : 10.1109/CAIA.1995.378786 . hdl : 11603/12722 . ISBN 0-8186-7070-3 . S2CID 8963326 .
- ^ «Бриколаж: Мемоизация» .
- ^ Фрост, Ричард; Шидловски, Барбара (1996). «Запоминание чисто функциональных языковых процессоров с нисходящим возвратом» . наук. Вычислить. Программа . 27 (3): 263–288. дои : 10.1016/0167-6423(96)00014-7 .
- ^ Фрост, Ричард (1994). «Использование мемоизации для достижения полиномиальной сложности чисто функциональных исполняемых спецификаций недетерминированных нисходящих парсеров». Уведомления SIGPLAN . 29 (4): 23–30. дои : 10.1145/181761.181764 . S2CID 10616505 .
- ^ Фрост, Ричард (2003). «Монадическая мемоизация к сокращению поиска, сохраняющему корректность». Канадская конференция по искусственному интеллекту 2003 г. Конспекты лекций по информатике. Том. 2671. стр. 66–80. дои : 10.1007/3-540-44886-1_8 . ISBN 978-3-540-40300-5 .
- ^ Джонсон, Марк (1995). «Мемоизация нисходящего синтаксического анализа». Компьютерная лингвистика . 21 (3): 405–417. arXiv : cmp-lg/9504016 . Бибкод : 1995cmp.lg....4016J .
- ^ Перейти обратно: а б Джонсон, Марк и Дорре, Йохен (1995). «Мемоизация сопрограммных ограничений». Материалы 33-го ежегодного собрания Ассоциации компьютерной лингвистики . Кембридж, Массачусетс. arXiv : cmp-lg/9504028 .
{{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка ) - ^ Перейти обратно: а б Форд, Брайан (2002). Анализ Packrat: практический алгоритм линейного времени с обратным отслеживанием (магистерская диссертация). Массачусетский технологический институт. hdl : 1721.1/87310 .
- ^ Томита, Масару (1985). Эффективный синтаксический анализ естественного языка . Бостон: Клювер. ISBN 0-89838-202-5 .
- ^ Ачар, Умут А.; и др. (2003). «Выборочная мемоизация». Материалы 30-го симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования, 15–17 января 2003 г. Том. 38. Новый Орлеан, Луизиана. стр. 14–25. arXiv : 1106.0447 . дои : 10.1145/640128.604133 .
{{cite book}}:|journal=игнорируется ( помощь ) CS1 maint: отсутствует местоположение издателя ( ссылка )
Внешние ссылки
[ редактировать ]
- Примеры мемоизации на различных языках программирования
- groovy.lang.Closure#memoize() — Memoize — это функция языка Apache Groovy 1.8.
- Memoize — Memoize — небольшая библиотека, написанная Тимом Брэдшоу, для выполнения мемоизации в Common Lisp .
- IncPy — специальный интерпретатор Python , выполняющий автоматическое запоминание (без обязательных пользовательских аннотаций).
- Макросы Дэйва Хермана для определения мемоизированных процедур в Racket .
- Memoize.pm – модуль Perl , реализующий мемоизированные функции.
- Мемоизация Java — пример использования динамических прокси-классов на языке Java для создания общего шаблона мемоизации.
- memoization.java — библиотека мемоизации Java.
- С++памятка [ постоянная мертвая ссылка ] – Фреймворк мемоизации C++ .
- C-Memo — универсальная библиотека мемоизации для C, реализованная с использованием макросов-оболочек функций препроцессора.
- Tek271 Memoizer – Java-мемоайзер с открытым исходным кодом, использующий аннотации и подключаемые реализации кэша.
- memoizable — драгоценный камень Ruby , реализующий мемоизированные методы.
- Мемоизация Python — Python . пример мемоизации
- Мемоизация OCaml — реализована как расширение синтаксиса Camlp4 .
- Мемоизация в Lua — два примера реализации общей функции мемоизации в Lua .
- Мемоизация в Mathematica — Мемоизация и ограниченная мемоизация в Mathematica .
- Мемоизация в Javascript — расширение прототипа функции в JavaScript (архивная версия http://talideon.com/weblog/2005/07/javascript-memoization.cfm ).
- Мемоизация в Javascript – Примеры мемоизации в Javascript с использованием собственного механизма кэширования и использования библиотеки YUI.
- X-SAIGA – исполняемые спецификации грамматик. Содержит публикации, связанные с алгоритмом синтаксического анализа сверху вниз, который поддерживает левую рекурсию и неоднозначность в полиномиальном времени и пространстве.
- Мемоизация в схеме — Scheme на веб-странице класса. пример мемоизации
- Мемоизация в комбинаторной логике — веб-сервис для сокращения комбинаторной логики при запоминании каждого шага в базе данных.
- MbCache — результаты метода кэширования в .NET .