代码之家 › 专栏 › 技术社区 › kye

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

record polymorphism haskell

kye · 技术社区 · 5 年前

我在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进行编译似乎没有任何效果,因此我想了解问题的根本原因,这样我就可以解决更大系统中的性能问题。

2 回复 | 直到 5 年前

Daniel Wagner 5 年前

拿着我的啤酒。

{-# 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 如果collatz猜想是真的并且 not 否则。在这种情况下,只测试一次collatz猜想,然后缓存我们是否应该 身份证件 或 不 以后永远。

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

但这种编译策略的结果是: 多态的 但是typeclass约束的类型是一个函数 即使里面没有功能箭头 . 也就是说,

f 1.5 :: Floating a => a

看起来像是一个普通的旧值;但实际上它是一个功能这需要一个 Floating a 字典并生成类型的值 a . 所以任何涉及到计算值的计算 一 是重做每次应用此函数时都要重新刷新(阅读:在特定的单态类型中使用),因为毕竟,所选的精确值关键取决于typeclass的方法的行为方式。

这只留下了一个问题,为什么优化会改变您的情况。在这里,我相信所发生的事情被称为“专门化”,在这种专门化中,编译器将尝试注意到多态性的东西何时被用于静态的已知单态类型,并为此进行绑定。就像这样:

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

在最后一个例子中,函数ness消失了;它“好像”ghc缓存了 trans 当应用到字典时 dictForDouble . (如果使用优化和 -ddump-simpl 你会看到它走得更远,不断地传播,把 minus ... 填塞 D# -0.5## . 唷!

steve 5 年前

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

注意,无论编译器优化是打开还是关闭,前者都不会被缓存。

当他们都是 浮标 打开优化,问题就消失了。

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