повторное использование/memoization глобальных полиморфных значений (класса) в Haskell

Question

Я обеспокоен тем, когда и когда значение класса «глобальное» является общим/memoized, особенно через границы модулей. Я прочитал this и this, но они, похоже, не отражают мою ситуацию, и я вижу некоторое другое поведение от того, что можно было бы ожидать от ответов.

Рассмотрим класс, который выставляет значение, которое может быть дорогим, чтобы вычислить:

{-# LANGUAGE FlexibleInstances, UndecidableInstances #-} 

module A 

import Debug.Trace 

class Costly a where 
    costly :: a 

instance Num i => Costly i where 
    -- an expensive (but non-recursive) computation 
    costly = trace "costly!" $ (repeat 1) !! 10000000 

foo :: Int 
foo = costly + 1 

costlyInt :: Int 
costlyInt = costly 

И отдельный модуль:

module B 
import A 

bar :: Int 
bar = costly + 2 

main = do 
    print foo 
    print bar 
    print costlyInt 
    print costlyInt 

Запуск main дает две отдельные оценки costly (как указано след): один для foo, и один для bar. Я знаю, что costlyInt просто возвращает (оценивается) costly от foo, потому что если я удалю print foo от main, то первый costlyInt станет дорогостоящим. (. Я могу также привести к costlyInt чтобы выполнить раздельную оценку независимо от того, что, обобщая тип foo к Num a => a)

Я думаю, я знаю, почему такое поведение бывает: экземпляр Costly фактически является функция, которая принимает Num словарь и создает словарь Costly. Поэтому при компиляции bar и разрешении ссылки на costly, ghc генерирует новый словарь Costly, который имеет в нем дорогой кусок. Вопрос 1: Правильно ли я об этом?

Есть несколько способов, чтобы вызвать только один оценку из costly, в том числе:

• Положите все в одном модуле.
• Удалите ограничение экземпляра Num i и просто укажите экземпляр Costly Int.

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

Есть также изменения, которые не сократить число оценок, таких как:

• Использование INLINE, INLINABLE или NOINLINE на costly определения в экземпляре. (Я не ожидал, что это сработает, но эй, стоит сделать снимок.)
• Использование прагмы SPECIALIZE instance Costly Int в определении экземпляра.

Последнее удивительно для меня - я ожидал, что это, по существу эквивалентен второй пункт выше, что сделал работы. То есть, я думал, что это сгенерирует специальный словарь Costly Int, который будет делиться всеми foo, bar и costlyInt. Мой вопрос 2: что мне здесь не хватает?

Мой последний вопрос: существует ли относительно простой и надежный способ получить то, что я хочу, т. Е. Все ссылки на costly конкретного конкретного типа, разделяемого между модулями? Из того, что я видел до сих пор, я подозреваю, что ответ отрицательный, но я все еще надеюсь.

Answer 1

Управление совместным использованием является сложным в GHC. Существует множество оптимизаций, которые GHC делает, что может повлиять на совместное использование (например, вложение, перемещение вещей и т. Д.).

В этом случае, чтобы ответить на вопрос, почему Прагма специализироваться не достичь желаемого эффекта, давайте посмотрим на ядро ​​модуля B, в частности, из bar функции:

Rec { 
bar_xs 
bar_xs = : x1_r3lO bar_xs 
end Rec } 

bar1 = $w!! bar_xs 10000000 
--  ^^^ this repeats the computation. bar_xs is just repeat 1 

bar = 
    case trace $fCostlyi2 bar1 of _ { I# x_aDm -> I# (+# x_aDm 2) } 
    --   ^^^ this is just the "costly!" string 

Это Ждут» работайте так, как мы хотели. Вместо повторного использования costly GHC решил просто встроить функцию costly.

Таким образом, мы должны не допустить, чтобы GHC был сложным, или вычисление будет дублировано. Как мы это делаем? Вы можете подумать, добавив {-# NOINLINE costly #-} прагму будут достаточно, но, к сожалению, специализация без встраивания, кажется, не работает вместе хорошо:

A.hs:13:3: Warning: 
    Ignoring useless SPECIALISE pragma for NOINLINE function: ‘$ccostly’ 

Но есть хитрость, чтобы убедить GHC делать то, что мы хотим: мы можем написать costly следующим образом:

instance Num i => Costly i where 
    -- an expensive (but non-recursive) computation 
    costly = memo where 
    memo :: i 
    memo = trace "costly!" $ (repeat 1) !! 10000000 
    {-# NOINLINE memo #-} 
    {-# SPECIALIZE instance Costly Int #-} 
-- (this might require -XScopedTypeVariables) 

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