Какова продолжительность жизни памяти в функциональном языке, например Haskell?
В чистом функциональном языке с ленивой семантикой (например, Haskell) результаты вычислений запоминаются так, что дальнейшие оценки функции с одними и теми же входами не пересчитывают значение, а получают его непосредственно из кеша запоминаемых значений.
Мне интересно, возвращаются ли эти memoised значения в какой-то момент времени?
- Если это так, это означает, что memoized значения должны быть пересчитаны позже, и преимущества memoization не так выходят из IMHO.
- Если нет, то хорошо, это умно для кэширования всего... но означает ли это, что программа - если она будет работать в течение достаточно длительного периода времени - будет
всегда потребляют все больше и больше памяти?
Представьте себе программу, выполняющую интенсивный численный анализ: например, чтобы найти корни списка из сотни тысяч математических функций, используя алгоритм дихотомии.
Каждый раз, когда программа оценивает математическую функцию с конкретным реальным числом, результат будет запомнен. Но есть только очень небольшая вероятность
что во время алгоритма будет отображаться точно такой же Действительный номер, что приведет к утечке памяти (или, по крайней мере, к действительно плохому использованию).
Моя идея состоит в том, что, возможно, memoized значения просто "привязаны" к чему-то в программе (например, к текущему продолжению, стеку вызовов и т.д.), но я не смог найти что-то практическое по этому вопросу.
Я признаю, что я не смотрел глубоко на реализацию компилятора Haskell (ленивый?), но, пожалуйста, может кто-нибудь объяснить мне, как это работает на практике?
EDIT: Хорошо, я понимаю свою ошибку из первых ответов: Чистая семантика подразумевает ссылочную прозрачность, которая, в свою очередь, не подразумевает автоматическую Memoization, а просто гарантирует, что с ней не будет никаких проблем.
Я думаю, что несколько статей в Интернете вводят в заблуждение об этом, потому что с точки зрения начинающих кажется, что свойство ссылочной прозрачности настолько классно, что позволяет неявное воспоминание.
Ответы
Ответ 1
Haskell автоматически не запоминает вызовы функций, потому что это быстро потребляет тонны памяти. Если вы сами выполняете запись, вы можете выбрать, в какой области функция запоминается. Например, допустим, что функция фибоначчи определяется следующим образом:
fib n = fibs !! n
where fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
Здесь memoization выполняется только при одном вызове fib
, тогда как если вы оставите fibs
на верхнем уровне
fib n = fibs !! n
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
то сохраненный список сохраняется до тех пор, пока сборщик мусора не сможет определить, что больше нет пути к fibs
из любой части вашей программы.
Ответ 2
Моя идея заключается в том, что, возможно, memoized значения просто "привязаны" к чему-то в программе (например, к текущему продолжению, стеку вызовов и т.д.), но я не смог найти что-то практическое по этому вопросу.
Это правильно. В частности, когда вы видите что-то вроде:
fun x y = let
a = .....
b = ....
c = ....
in ....
или эквивалентное предложение where, значения a, b и c не могут быть вычислены до фактического использования (или они могут быть вычислены сразу же, потому что анализатор строгости может предположить, что значения будут оцениваться позже в любом случае). Но когда эти значения зависят от текущих параметров функции (здесь x и y), время выполнения, скорее всего, не будет запоминать каждую комбинацию x и y и результирующие a, b и c.
Заметим также, что на чистом языке также хорошо не помнить значения вообще - это практически практично, поскольку память дешевле процессорного времени.
Итак, ответ на ваш вопрос: в Haskell нет такой вещи, как время жизни промежуточных результатов. Все, что можно сказать, это то, что оцененное значение будет там, когда это необходимо.