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

Чтение о FRP (функциональное реактивное программирование) Я поражен тем, насколько интуитивно понятен и логичен он по сравнению со стандартным императивным подходом; одна вещь, однако, озадачивает меня.. Как компьютер не исчерпывает память?

Из того, что я собрал из [здесь], заключается в том, что в FRP полная история (прошлое, настоящее и будущее) изменения стоимости - это первый класс, Это понятие сразу же вызывает у меня тревогу, говоря, что она очень быстро съедает вашу память, если она используется в среде, где прошлое значения не сразу очищается от памяти.

Чтение о [Fran], я заметил несколько примеров, имеющих рекурсивно определенные функции без условия завершения. Если функция никогда не заканчивается и не возвращает свое значение функции, вызывающей ее, как это когда-либо будет сделано? Или, если на то пошло, как это не взорвать стек через некоторое время? Даже ленивый язык, такой как Haskell, в какой-то момент столкнется с переполнением стека.

Объяснение этих вещей было бы очень полезно, поскольку это полностью меня озадачило.

Ответ 1

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

Вот почему этот классический пример Фибоначчи работает в постоянном пространстве: предыдущие записи в списке не нужны, как только будут рассчитаны следующие два, поэтому они собираются по ходу движения - если у вас нет других указателей на список.

fib n = fibs !! n
  where fibs = 0 : 1 : zipWith (+) fibs (drop 1 fibs)

Попробуйте запустить эту функцию для разных входов и посмотрите на использование памяти. (Запустите его с помощью +RTS -s.)

(Если вы хотите более подробное объяснение с диаграммами, посмотрите этот пост, который я написал.)

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

Точно такая же логика может быть использована для эффективного осуществления программ FRP.

Конечно, все не так просто. В примере fibs использование памяти будет идти вверх, если бы у нас был активный указатель на начало списка fibs. То же самое происходит с FRP, если у вас есть вычисление, которое зависит от слишком большого количества прошлых данных: оно называется течением времени.

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

Я никогда не пытался реализовать красивую систему FRP самостоятельно, поэтому я не могу объяснить проблемы более подробно. Если вас интересует более подробная информация по этой теме, отличным местом для просмотра является Conal Elliott blog - этот пост в качестве хорошей отправной точки. Вы также можете взглянуть на некоторые из написанных им работ, таких как "Push-Pull Functional Reactive Programming" , а также на другие статьи по этому вопросу, в том числе о Arrowized FRP например "Функциональное реактивное программирование, продолжение" (выбрано почти случайно).

сноски

¹ Это не действительно постоянное пространство, потому что промежуточные результаты становятся более крупными. Но он должен поддерживать постоянное количество ячеек списка в памяти.

Ответ 2

О времени утечки части вашего вопроса: это действительно одна из основных проблем при внедрении FRP. Тем не менее, исследователи и разработчики FRP нашли несколько способов избежать их.

Все зависит от конкретного API, который вы предлагаете для сигналов. Главный вопрос заключается в том, предоставите ли вы FRP более высокого порядка. Это часто принимает форму примитива "monadic join" для сигналов: способ преобразования сигнала сигналов в сигнал или, другими словами, API для создания сигнала, который динамически переключается между несколькими другими сигналами. Такой API очень мощный, но может ввести потенциал для утечек времени, то есть проблему, о которой вы спрашиваете: необходимость сохранить все сигналы предыдущих значений в памяти. Однако, как отмечает Хейнрих Аппельмус в комментарии к предыдущему ответу, есть способы решить эту проблему, ограничив API более высокого порядка определенными способами, используя систему типов или иначе. См. Этот комментарий для ссылок на дополнительные объяснения.

Многие библиотеки FRP просто не предлагают API более высокого порядка и, следовательно, (довольно легко) избегают проблем с утечками времени. Вы упомянули Элма, который в этом случае, как упоминалось здесь в разделе "Сигналы не являются монадами в Вязе". Это связано с высокой выразительностью, потому что не предлагается мощный монадический API, но не все полагают, что вам нужна общая сила такого API в структуре/библиотеке FRP.

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