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

Самый яркий пример совместного использования в функциональном программировании — это Clean, основанный на переписывании графов. Там вычисление относится к DAG, поэтому мы можем рассматривать выражение (sin x) * (sin x) как

    (*)
  /     \
sin x   sin x

Системы перезаписи графов имеют явное понятие совместного использования, поэтому мы могли бы выразить это вычисление как

   (*)
   / \
   \ /
  sin x

указывая узел умножения на тот же узел, тем самым разделяя вычисление sin x. Системы перезаписи терминов не имеют столь явного понятия разделения, но оптимизация по-прежнему актуальна. В GHC иногда можно выразить совместное использование с локальными переменными, например. переписывание

f x = (sin x) * (sin x)

в

f x = sinx * sinx
  where sinx = sin x

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

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

(string-append (read-line)
               (read-line))

а также

(let ((s (read-line)))
  (string-append s s))

Первый дважды выполняет действие ввода-вывода, запрашивая у пользователя две строки и добавляя их; второй «разделяет» действие ввода-вывода, выполняя его один раз и добавляя к себе. В общем, совместное использование чистых вычислений сокращает время выполнения без изменения результата программы, в то время как совместное использование побочного значения (которое может меняться со временем или взаимодействовать с пользователем) изменяет результат. Чтобы компилятор автоматически разделял вычисления, он должен знать, что они чистые, и, таким образом, сокращение числа вычислений не имеет значения. Clean делает это с уникальными типами; действие ввода-вывода имеет атрибут типа UNQ, который сообщает компилятору, что его нельзя использовать совместно. Haskell делает то же самое несколько иначе с монадой IO.

Совместное использование — это своего рода равенство: равенство указателей. В области ценностей Haskell (семантическая интерпретация) нет такой вещи, как совместное использование. Значения могут быть равны, только если они имеют экземпляры Eq, и тогда "равенство" определяется как бинарное отношение (==).

Таким образом, совместное использование избегает семантической интерпретации, ссылаясь на это лежащее в основе равенство указателей, которое существует благодаря реализации, а не семантике. Хотя иногда это полезный побочный эффект. К сожалению, поскольку язык Haskell определяется его семантической интерпретацией, использование совместного использования является неопределенным поведением. Он привязан к конкретной реализации. Несколько библиотек используют совместное использование и, таким образом, их поведение связано с GHC.

Однако есть один встроенный механизм обмена. Об этом свидетельствует StableName интерфейс. Мы генерируем объекты StableName a, используя makeStableName :: a -> IO (StableName a), и имеем instance Eq (StableName a) — таким образом, StableName вводит своего рода равенство для любого типа.

StableName равенство — это почти равенство указателей. Чтобы процитировать документацию Хэддока

Если sn1 :: StableName и sn2 :: StableName и sn1 == sn2, то sn1 и sn2 были созданы вызовами makeStableName для одного и того же объекта.

Обратите внимание, что это всего лишь оператор if, а не если и только если. Тот факт, что две вещи могут быть «эквивалентны указателям», но все же иногда иметь разные стабильные имена, является (а) вынужденным из-за гибкости, которую Haskell оставляет сборщику мусора, и (б) лазейкой, которая позволяет StableNames существовать в любой реализации Haskell, даже если нет такая вещь, как «равенство указателя» в реализации вообще.

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

Ваш пример не является примером совместного использования - он просто умножает значение на себя (а затем отбрасывает исходное значение).

Совместное использование — это случай, когда некоторая часть структуры данных встречается дважды в более крупной структуре данных или в разных структурах данных. Например:

p  = (1, 2)
pp = (p, p)  -- p is shared between the first and second component of pp

xs = [1, 2, 3]
ys = 0::1::xs
zs = 5::xs  -- ys and zs share the same tail

В памяти такое совместное использование приведет к структуре DAG.