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

Question

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

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

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

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

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

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

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

---

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

---

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

---

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

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

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

Answer 1

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

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

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

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

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

Answer 2

Похоже, что Haskell не выполняет автоматическое запоминание.Или я что-то не так понимаю?

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

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

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

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

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

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

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

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

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

Answer 3

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

x = somethingVeryLong

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

y = f x
z = g x

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

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

Answer 4

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

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

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

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

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

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

Answer 5

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