Почему чисто функциональные языки не используют подсчет ссылок?

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

Я понимаю, что подсчет ссылок во многих случаях медленнее, чем GC, но, по крайней мере, он сокращает время паузы. Было бы неплохо иметь возможность использовать подсчет ссылок в случаях, когда время паузы плохое.

Ответ 1

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

class Node { 
  public readonly Node other;
  public Node() { 
    other = new Node(this);
  }
  public Node(Node node) {
    other = node;
  }
}

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

Изменить ephemient

В ответ на комментарий... это тривиально в Haskell

data Node a = Node { other :: Node a }
recursiveNode = Node { other = recursiveNode }

и едва ли больше усилий в SML.

datatype 'a node = NODE of unit -> 'a node
val recursiveNode : unit node =
    let fun mkRecursiveNode () = NODE mkRecursiveNode
    in mkRecursiveNode () end

Не требуется мутация.

Ответ 2

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

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

Подсчет ссылок имеет тенденцию делать действительно хорошо в таких ситуациях:

Почти вся память кучи используется для хранения живых объектов.
Назначение и назначение указателя нечасты относительно других операций.
Ссылки могут управляться на другом процессоре или компьютере.

Чтобы понять, как работают лучшие высокопроизводительные системы подсчета количества ссылок, просмотрите работу David Bacon и Эрез Петранк.

Ответ 3

Есть несколько вещей, я думаю.

Есть циклы: "let rec" на многих языках позволяет создавать "круговые" структуры. Кроме того, неизменность обычно не подразумевает никаких циклов, но это нарушает правило.
Недостатки ссылок в списках неверны: я не знаю, что коллекция с подсчетом ссылок работает хорошо, например. длинные структуры с односвязным списком, которые вы часто находите в FP (например, медленный, необходимо обеспечить хвостовое рекурсивное,...)
Другие стратегии имеют преимущества. Как вы намекаете, другие стратегии GC по-прежнему обычно лучше подходят для локализации памяти.

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

Ответ 4

Am прав?

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

let rec xs = 0::ys and ys = 1::xs

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

Если да, то почему они этого не делают?

Некоторые языки запрещают циклы и используют подсчет ссылок. Примеры Erlang и Mathematica.

Например, в Mathematica, когда вы ссылаетесь на значение, вы делаете глубокую копию, так что мутация оригинала не мутирует копию:

In[1] := xs = {1, 2, 3}
Out[1] = {1, 2, 3}

In[2] := ys = xs
Out[2] = {1, 2, 3}

In[3] := xs[[1]] = 5
Out[3] = 5

In[4] := xs
Out[4] = {5, 2, 3}

In[5] := ys
Out[5] = {1, 2, 3}

Ответ 5

Рассмотрим эту аллегорию, рассказанную David Moon, изобретатель Lisp Machine:

Однажды студент пришел на Луну и сказал: "Я понимаю, как сделать лучшего сборщика мусора. Мы должны держать подсчет ссылок указателей на каждую минус."

Луна терпеливо рассказала студенту следующую историю:

"Однажды студент пришел на Луну и сказал:" Я понимаю, как сделать лучшего сборщика мусора...

Ответ 6

Ссылочный счетчик MUCH медленнее, чем GC, потому что он не подходит для CPU. И GC большую часть времени может ждать простоя, а также GC может быть одновременно (в другом потоке). Так что проблема - GC наименее злая, и многие попытки показали это.