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 进行编译会使问题消失，但是，这种行为发生在一个更大的系统中，其中使用 -O2 进行编译似乎没有任何效果，因此我想了解根源问题的原因，所以我可以解决更大系统中的性能问题。

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 中完成（尽管请参阅下面关于优化版本的讨论）。前者听起来很蠢，但实际上并没有你想象的那么蠢；您可以想象编写一个函数，如果 collatz 猜想为真，则为 id，否则为 not。在这种情况下，只测试 collatz 猜想一次，然后永远缓存我们应该表现得像 id 还是 not 是完全有意义的。

一旦你理解了这个基本事实，你必须相信的下一个飞跃是在 GHC 中，类型类约束被编译为函数。（函数的参数是类型类字典，告诉每个类型类方法的行为。）GHC 本身为您管理构建和传递这些字典，并且在大多数情况下它对用户来说是非常透明的。

但是这个编译策略的结果是这样的：多态但是类型类约束的类型是一个函数即使它看起来没有函数其中的箭头。也就是说，

f 1.5 :: Floating a => a

看起来像一个普通的旧值；但实际上它是一个函数，它采用 Floating a 字典并生成 a 类型的值。因此，每次应用此函数（阅读：用于特定单态类型）时，任何用于计算值 a 的计算都会重新 redone 因为，毕竟，精确选择的值主要取决于类型类的方法的行为方式。

这只留下了为什么优化会改变您的情况的问题。我相信发生的事情被称为 "specialization"，其中编译器将尝试注意何时在静态已知的单态类型上使用多态事物并为此进行绑定。它是这样的：

-- 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

在最后一个中，功能消失了；它是 "as if" GHC 在应用于字典 dictForDouble 时缓存了 trans 的输出。（如果你使用优化和 -ddump-simpl 进行编译，你会发现它走得更远，通过不断传播将 minus ... 变成 D# -0.5##。哇！）

Answer 2

{-# LANGUAGE RankNTypes #-}

import Debug.Trace

--Does not get cached
data Translation = Trans { m :: forall a. Floating a => a }

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

因为 a 是一个严格的类型变量，受上下文期望的类型约束 forall a. Floating a => a 您还必须缓存上下文

--Does get cached
data Translation' = Trans' { m' :: Float }

f' :: Float -> Float
f' x = trace "f'" $ x - 2.0

因为这是一个 Float 类型的值，所以它可以计算一次并在之后缓存。

main :: IO ()
main = do
    let
        trans = Trans { m = f 1.5 }
        trans' = Trans' { m' = f' 1.5}

    putStrLn $ show $ (m trans :: Double)
    putStrLn $ show $ (m trans :: Float)
    -- ^ you can evaluate it with 2 different contexts

    putStrLn $ show $ (m' trans' :: Float)
    putStrLn $ show $ (m' trans' :: Float)
    -- ^ context fixed

请注意，无论打开还是关闭编译器优化，前一个都不会被缓存。

当它们都是 Float 并且您打开优化时，问题就消失了。

如果您使用优化编译更大的系统并且它在某些指标上效率低下，我会怀疑问题出在其他地方。

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

Unexpected caching behavior using polymorphic records in Haskell

polymorphism

haskell

record