5

共享意味着如果要多次使用临时数据,则将其存储。也就是说,一个函数只计算一次它的参数。一个例子是:

let x = sin x in x * x

还有哪些其他功能有助于共享,它们将如何与实际程序执行 IO 的需求交互?

4

3 回答 3

7

共享是关于一种平等:指针平等。在 Haskell 的价值土地(语义解释)中,没有共享这样的东西。只有当它们具有的实例时,值才能相等Eq,然后“相等”被定义为二元关系(==)

因此,共享通过引用这个基于实现而不是语义而存在的底层指针相等来逃避语义解释。不过,这有时是一个有用的副作用。不幸的是,由于 Haskell 是由其语义解释定义的,因此使用共享是未定义的行为。它与特定的实现有关。一些图书馆使用共享,因此具有与 GHC 相关的行为。

不过,有一种内置的共享机制。这是由StableName接口公开的。我们使用并有一个生成StableName a对象——因此为任何类型引入了某种相等性。makeStableName :: a -> IO (StableName a)instance Eq (StableName a)StableName

StableName相等几乎是指针相等。引用 Haddock 文档

If sn1 :: StableNameand sn2 :: StableNameand sn1 == sn2then sn1and是通过对同一对象sn2的调用创建的。makeStableName

请注意,这只是一个if语句,而不是if 且仅当。两个东西可以是“指针等价的”但有时仍然具有不同的稳定名称的事实是(a)Haskell 留给 GC 的灵活性和(b)允许StableNames 存在于任何 Haskell 实现中的漏洞,即使没有无论如何,在实现中诸如“指针相等”之类的东西。

这些StableNames 仍然没有语义,但是因为它们是在IO“OK”的 monad 中引入的。相反,可以说它们实现了任何类型上可能的最小(最具体)等式关系的(具有讽刺意味的)不稳定子集。

于 2013-05-08T03:07:33.120 回答
5

函数式编程中共享最明显的例子来自于基于图重写的 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))

第一个执行两次 IO 动作,向用户请求两行并附加它们;第二个“共享” IO 操作,执行一次并将其附加到自身。一般来说,共享一个纯计算可以在不改变程序结果的情况下减少执行时间,而共享一个副作用值(一个可能随时间变化或与用户交互的值)会改变结果。为了让编译器自动共享计算,它需要知道它们是纯的,因此减少计算次数并不重要。Clean 使用唯一性类型进行此操作;一个 IO 动作具有类型属性 UNQ,它告诉编译器它不应该被共享。Haskell 对 IO monad 的处理方式略有不同。

于 2013-05-08T15:54:32.467 回答
1

您的示例不是共享示例-它只是将一个值与自身相乘(然后将原始值丢弃)。

共享是数据结构的某些部分在更大的数据结构或不同的数据结构中出现两次的情况。例如:

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 结构。

于 2013-05-08T16:34:34.547 回答