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

#haskell #functional-programming #memoization

#haskell #функциональное программирование #запоминание

Вопрос:

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

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

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

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

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

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

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

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

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

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

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

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

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

2. Как это бывает, есть недавнее сообщение в блоге именно на эту тему: augustss.blogspot.com/2011/04 /…

3. @Don: Это именно то, что я уже сказал в своем вопросе.

4. @MatrixFrog: Похоже, что на самом деле это не решает проблемы, которые я описал в своем вопросе, т. Е. в основном ограничение памяти и ее решение / реализация.

5. Похоже, что проблема, которая вас действительно интересует, — это сборка мусора.

Ответ №1:

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

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

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

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

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

1. Интересна ссылка на алгоритмы замены страниц. Многие из них действительно могут быть применены для запоминания. При этом запоминание все еще немного более особенное.

Ответ №2:

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

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

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

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

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

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

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

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

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

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

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

2. Приведенный вами пример LRU C интересен. Это, наконец, реальное решение — первое решение, которое я прочитал здесь, в этой теме. Это не оптимально, хотя из-за упорядоченной карты — hashmap подошел бы здесь намного лучше. И тогда вы в конечном итоге точно уже получаете мое собственное решение (см. Мою последнюю ссылку в моем вопросе). Итак, я все еще пропускаю некоторые альтернативные / лучшие решения, которые также затрагивают некоторые другие вопросы (например, динамическое изменение предела и т.д.).

3. Кстати., «хорошая автоматическая запоминание сложна», почему это? Это означает, что люди пробовали это, и это не сработало хорошо. Я не видел таких тестов. Можете ли вы сослаться на какой-либо?

4. @Paul Johnson: Побочный эффект в том смысле, что вы обновляете память и добавляете элементы в таблицу запоминания. Это также может повлиять на вашу программу, возможно, ваша программа прерывается, потому что она занимает много памяти из-за запоминания.

5. @Albert, вам нужно многое учесть, когда вы хотите выполнить автоматическое запоминание. Какие функции вы разрешаете сохранять в памяти? Вы запоминаете параметры, которые являются функциями? Если вы хотите сохранить в памяти только с помощью Haskell, вам нужно либо использовать fib-подобный (безопасный) шаблон, либо, для более сложных типов, использовать хэш-карты. Но тогда вы не сможете выполнить контурную привязку к оценке thunk в Haskell, и вам нужно будет управлять картой самостоятельно. Насколько я могу видеть сейчас, для этого требуется либо перевести все в состояние Monad, либо использовать unsafeperform .

Ответ №3:

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

 x = somethingVeryLong

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

 y = f x
z = g x

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

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

Ответ №4:

В качестве примера реализации автоматического запоминания вы можете взглянуть на Factor programming language и его словарь для запоминания. Например, простой генератор чисел Фибоначчи:

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

может быть сохранено путем замены «:» word на «MEMO:»

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

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

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

Ответ №5:

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

Ответ №6:

В Maple вы можете использовать опцию remember

 F := proc(n) option remember;
    if n<2 then n else F(n-1) F(n-2)
    end if
end proc;