Автоматическое запоминание в функциональных языках программирования

Я всегда думал, что Haskell сделает какое-то автоматическое интеллектуальное воспоминание. Например, наивная реализация Фибоначчи

fib 0 = 0
fib 1 = 1
fib n = fib (n-2) + fib (n-1)

Из-за этого

будет быстрым. Теперь я прочитал этот, и кажется, что я ошибся - Haskell, похоже, не делает автоматическую memoization. Или я понимаю что-то не так?

Существуют ли другие языки, которые выполняют автоматическую (т.е. неявную, а не явную) memoization?

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

Не могли бы вы ссылаться (или ссылаться) на некоторые общие реалии реального мира?

Спасибо, Альберт

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

Изменить: некоторые собственные мысли с примерной реализацией (с лимитом) можно найти здесь.

Изменить: я не пытаюсь решить конкретную проблему в конкретном приложении. Я ищу общие решения для memoization, которые могут быть применены глобально ко всем функциям (чисто функциональной) программы (поэтому алгоритмы, которые не реализуют ограничение памяти, не являются решением). Конечно, там (возможно) нет оптимального/лучшего решения. Но это делает мой вопрос не менее интересным.

Чтобы попробовать такое решение, я подумал о том, чтобы добавить его в Haskell в качестве оптимизации. Мне действительно интересно, насколько хорошо это будет.

И интересно, кто-то уже это сделал.

Ответ 1

Haskell, похоже, не делает автоматическую memoization. Или я понимаю что-то не так?

Нет, Хаскелл этого не делает. Однако общие выражения вычисляются только один раз. В примере, данном Paul Johnson x, хранится в куче как thunk. Оба y и z могут ссылаться на x, поскольку x находится в области видимости, и они ссылаются на одно и то же местоположение. Как только x должен быть оценен, он будет оцениваться только один раз, и только результат оценки будет сохранен. Таким образом, это не действительно memoisation, но это результат реализации.

Существуют ли другие языки, которые выполняют автоматическую (т.е. неявную, а не явную) memoization?

Я видел, как декоратор @memoized входит в некоторый исходный код python. Конечно, вы могли бы полностью создать для себя свой декоратор/реализацию. В комплекте с LRU и другими политиками, которые вы хотите использовать.

Каковы распространенные способы реализации memoization?

Нет реального метода common для реализации memoisation. Для fib-подобных шаблонов (только один аргумент, который представляет собой число) memoisation, как используется в примере с фиолетом, можно было разработать общее решение (hashmaps one), и оно будет работать, но оно также может быть субоптимальным для вашей конкретной проблемы.

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

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

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

Как только у вас есть основной механизм memoisation, вы можете настроить функции поиска и хранения для вашей таблицы memoising для реализации LRU или какого-то другого механизма, позволяющего уменьшить потребление памяти. Возможно, вы можете получить идею LRU от этого примера на С++.

Ответ 2

Я сказал в комментарии, что ваши требования звучат как сбор мусора. Я думал об этом, потому что вы заинтересованы в управлении ограниченным пулом памяти, продувая его время от времени, чтобы он не переходил.

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

Однако мемонирование не часто делается путем ограничения сохраненных результатов; требуемая мутация для вышеупомянутых алгоритмов, как правило, не-haskellish. Не позволяйте этому отговаривать вас. У вас есть интересные идеи, которые могут быть ценными дополнениями к исследованию возможностей memoization в Haskell, выполненных таким образом.

Иногда особая проблема memoization хорошо подходит для ограниченной памяти. Например, выравнивание двух последовательностей генов можно выполнить с помощью динамического программирования (см. Wikipedia Динамическое программирование # Последовательность выравнивания) с 2-мерной таблицей заметок. Но так как решение DP для данной ячейки зависит только от результатов предыдущей строки, вы можете начинать снизу и отбрасывать строки, которые находятся на расстоянии более 1 от текущей строки. Числа Фибоначчи одинаковы: вам нужны только предыдущие два числа в последовательности, чтобы вычислить следующий. Вы можете отказаться от чего-либо ранее, если все, что вас интересует, это n ^th.

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

Ответ 3

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

x = somethingVeryLong

и где-то еще в той же области, что у вас есть

y = f x
z = g x

то x будет вычисляться только один раз.

Этот пакет показывает, как сохраненные значения могут быть сохранены с использованием различных ключей и справочных таблиц. Меморандум обычно используется в одном вызове более крупной функции, так что сохраненные значения не зависнут вечно (что, как вы говорите, будет проблемой). Если вы хотите, чтобы memoiser также забывал старые значения с помощью LRU или чего-то другого, я думаю, вам, вероятно, нужно поместить его в монаду штата или что-то еще; вы не можете заставить Haskell вести себя так, используя обычный подход к воспоминаниям.

Ответ 4

Например, при реализации автоматической memoization вы можете посмотреть язык программирования факторов и его Словарь "Воспоминания" . Например, простой генератор чисел Фибоначчи:

: fib ( n -- n )
    dup 1 > [
        [ 1 - fib ]
        [ 2 - fib ]
        bi +
    ] when ;

может быть замечено заменой слова ":" на "MEMO:"

MEMO: fib ( n -- n )
    dup 1 > [
        [ 1 - fib ]
        [ 2 - fib ]
        bi +
    ] when ;

В этом случае входные данные и соответствующие выходы будут прозрачно сохранены в словаре в памяти.

Синтаксис языка факторов может сбивать с толку:). Я рекомендую вам смотреть видео-презентацию из Google Tech Talks о Factor, чтобы понять, как можно реализовать мемонирование таким образом.

Ответ 5

Нет ответа, но эта страница: http://www.haskell.org/haskellwiki/Memoization предлагает идеи о Memoization в Haskell, а также показывает реализацию на основе списка Последовательность Фибоначчи, которая может представлять интерес.