在Haskell中使用多态记录的意外缓存行为

Question

我在Haskell中使用多态记录遇到了一些意外的行为,当我希望它们被缓存时,某些值不会被缓存.

这是一个最小的例子:

{-# LANGUAGE RankNTypes #-}
import Debug.Trace

-- Prints out two "hello"s
data Translation = Trans { m :: forall a . Floating a => a }

g :: Floating a => a -> a
g x = x + 1

f :: Floating a => a -> a
f x = trace "hello" $ x - 2.0

-- Only one "hello"
-- data Translation = Trans { m :: Float }
--
-- f :: Float -> Float
-- f x = trace "hello" $ x - 2.0

main :: IO ()
main = do
    let trans = Trans { m = f 1.5 }
    putStrLn $ show $ m trans
    putStrLn $ show $ m trans

在这个例子中,我想如果值f 1.5被计算并存储在字段中m,则在下次访问时,它将不再被计算.但是,它似乎会在每次访问记录字段时重新计算,如"hello"打印两次这一事实所示.

另一方面,如果我们从字段中删除多态,则按预期缓存该值,并且"hello"仅打印一次.

我怀疑这是由于类型类(被视为记录)的交互阻止了记忆.但是,我不完全理解为什么.

我意识到,与-O2编译使问题消失,然而,在一个更大的系统,其中与-02编译似乎没有任何效果出现这种情况,所以我想了解这个问题的根本原因,所以我可以解决大型系统中的性能问题.

Answer 1

拿着我的啤酒瓶子(来源于某笑话.

{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE ConstraintKinds #-}
import Debug.Trace

data Dict c where Dict :: c => Dict c

-- An isomorphism between explicit dictionary-passing style (Dict c -> a)
-- and typeclass constraints (c => a) exists:
from :: (c => a) -> (Dict c -> a)
from v Dict = v

to :: (Dict c -> a) -> (c => a)
to f = f Dict

data Translation = Trans { m :: forall a . Floating a => a }

f1, f2 :: Dict (Floating a) -> a -> a
f1 = trace "hello" $ \Dict x -> x - 2.0
f2 = \Dict -> trace "hello" $ \x -> x - 2.0

main = do
    let trans1 = Trans { m = to (flip f1 1.5) }
        trans2 = Trans { m = to (flip f2 1.5) }
    putStrLn "trans1"
    print (m trans1)
    print (m trans1)
    putStrLn "trans2"
    print (m trans2)
    print (m trans2)

花一点时间来预测在运行之前输出的内容.然后去问你的GHC她是否同意你的猜测.

像泥一样清楚？

您需要在此处绘制的基本区别就在于这个显着简化的示例:

> g = trace "a" $ \() -> trace "b" ()
> g ()
a
b
()
> g ()
b
()

有一个单独的概念来缓存一个函数并缓存它的输出.简单地说,后者在GHC中从未完成(尽管下面讨论了优化版本的内容).前者可能听起来很愚蠢,但实际上并不像你想象的那么愚蠢; 你可以想象编写一个函数,比如说,id如果collat​​z猜想是真的,那么not.在这种情况下,完全有意义的是只测试一次collat​​z猜想,然后缓存我们是否应该表现为id或not之后永远.

一旦你理解了这个基本事实,你必须相信的下一个飞跃是在GHC中,类型类约束被编译为函数.(该函数的参数是类型类字典,告诉每个类型类'方法的行为.)GHC本身管理构造和传递这些字典,在大多数情况下,它对用户是非常透明的.

但是这种编译策略的结果是:多态但类型类约束类型是一个函数,即使它似乎没有函数箭头.那是,

f 1.5 :: Floating a => a

看起来像一个普通的旧价值; 但实际上它是一个函数,它接受Floating a字典并产生类型的值a.因此,每次应用此函数时,计算该值的任何计算a都将重新重新计算(读取:在特定的单态类型中使用),因为,毕竟,所选择的精确值主要取决于类型类方法的行为方式.

这只留下了为什么优化会在您的情况下改变一切的问题.在那里,我相信所发生的事情被称为"专业化",其中编译器将尝试注意多态事物何时被用于静态已知的单态类型并对其进行绑定.它是这样的:

-- starting point
main = do
    let trans = \dict -> trace "hello" $ minus dict (fromRational dict (3%2)) (fromRational dict (2%1))
    print (trans dictForDouble)
    print (trans dictForDouble)

-- specialization
main = do
    let trans = \dict -> trace "hello" $ minus dict (fromRational dict (3%2)) (fromRational dict (2%1))
    let transForDouble = trans dictForDouble
    print transForDouble
    print transForDouble

-- inlining
main = do
    let transForDouble = trace "hello" $ minus dictForDouble (fromRational dict (3%2)) (fromRational dictForDouble (2%1))
    print transForDouble
    print transForDouble

在最后一个中,功能消失了; 它"似乎"GHC缓存了trans应用于字典时的输出dictForDouble.(如果你使用优化进行编译,-ddump-simpl你会看到它进一步发展,进行常量传播以将minus ...内容转化为正确D# -0.5##.哇!)