почему запоминание не является языковой особенностью?

Question

Мне было интересно ... почему запоминание изначально не предоставляется как языковая функция ни на одном из известных мне языков?

Редактировать : чтобы уточнить, я имею в виду, что язык предоставляет ключевое слово для указания данной функции как запоминаемой, а не то, что каждая функция автоматически запоминается «по умолчанию», если не указано иное. Например, fortran предоставляет ключевое слово PURE, чтобы указать конкретную функцию как таковую. Я предполагаю, что компилятор может воспользоваться этой информацией для запоминания вызова, но я игнорирую, что произойдет, если вы объявите PURE функцию с побочными эффектами.

Answer 1

То, что ВЫ хотите от создания памятки, может отличаться от того, что предоставляет опция памятки компилятора.

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

Возможно, вы знаете, что имеет смысл запоминать только последние 2 или 3 значения, потому что вы никогда не будете использовать значения старше этого. (Последовательность Фибоначчи приходит на ум.)

Вы можете генерировать МНОЖЕСТВО значений в одних прогонах и только несколько в других.

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

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

Компилятор запоминания должен либо предоставить запоминание «один размер подходит всем», либо предоставить множество возможных альтернатив и параметров для управления альтернативами. В какой-то момент всем становится проще потребовать от пользователя предоставить свои собственные заметки.

Answer 2

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

Answer 3

В Haskell запоминание является автоматическим для (чистых) функций, которые вы определили без аргументов. И пример Фибоначчи в этой вики - действительно самый простой наглядный пример, о котором я мог бы подумать.

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

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

Answer 4

Clojure имеет функцию памятки (http://richhickey.github.com/clojure/clojure.core-api.html#clojure.core/memoize):

memoize
function

Usage: (memoize f)

Returns a memoized version of a referentially transparent function. The
memoized version of the function keeps a cache of the mapping from arguments
to results and, when calls with the same arguments are repeated often, has
higher performance at the expense of higher memory use.

Answer 5

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

Answer 6

A) Memoization меняет пространство на время. Я полагаю, что это может оказаться довольно несвязанным свойством, в том смысле, что объем данных, которые должны хранить программы или библиотеки, может очень быстро потреблять большие объемы памяти.

Для нескольких языков запоминание легко реализовать и легко настроить в соответствии с заданными требованиями.

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

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

Answer 7

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

1. Компилятор должен идентифицировать допустимые функции для запоминания (например, они являются прозрачными по ссылкам).
2. Среда выполнения должна быть в состоянии разумно выбирать кандидатов для запоминания, не снижая общую производительность.

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

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

Answer 8

Я действительно думаю, что такой вариант должен быть.

В задачах обработки данных есть неизменные входные данные (например, как временные ряды, где в течение заданного времени, как только значение известно, оно никогда не может измениться). Учитывая сегодняшнюю доступность ОЗУ, если результат функции зависит только от таких неизменяемых данных, рационально запоминать их, а не перечитывать каждый раз, когда это необходимо. В настоящее время я должен (в Scala и C #) вручную ввести таблицу хранения в памяти и написать 3 функции вместо одной - одну для чтения значения из файла / db / ws, одну для сохранения в таблицу в памяти, одну для переноса их и читать из памяти, если доступно, или вызывать функцию raw, если нет. Я думаю, что это может и должно быть реализовано как ключевое слово и сделано за кулисами.

Answer 9

Обратный вопрос. Почему это должно? Как кто-то сказал, его можно поместить в библиотеку, поэтому нет необходимости добавлять синтаксис в язык, его можно использовать только в чистых функциях, которые трудно идентифицировать автоматически (если вы не заставляете программиста аннотировать их). Также очень сложно определить, будет ли запоминание ускорять процесс или нет. Я не думаю, что это желательная функция для языка программирования.

Answer 10

Ваш вопрос также оставляет открытым решение вашего изучения большего количества языков. Я думаю, что Lisp поддерживает запоминание, и я знаю, что Mathematica поддерживает.