共享在函数式编程语言的实现中引用了什么

Question

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

let x = sin x in x * x

还有哪些其他功能有助于共享,以及它们如何与实际执行IO的需求相互作用？

Answer 1

共享是一种平等:指针平等.在Haskell的价值土地(语义解释)中,没有共享这样的东西.如果它们具有实例,Eq则值只能相等,然后将"相等"定义为二元关系(==).

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

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

StableName平等几乎是指针平等.引用Haddock文档

如果sn1 :: StableName和sn2 :: StableName和sn1 == sn2,然后sn1和sn2通过调用创建makeStableName同一个对象.

请注意,这只是一个if语句,而不是if和only if.事实上,两个东西可以是"指针等价",但仍然有不同的稳定名称有时是(a)强迫Haskell留给GC的灵活性和(b)允许StableNames存在于任何Haskell实现中的漏洞,即使没有诸如"指针平等"之类的东西在实现中.

这些StableName仍然没有语义含义,但是因为它们是在IOmonad中引入的"OK".相反,它们可能被认为是在任何类型上实现可能的最小(最具体)等式关系的(具有讽刺意味的)不稳定子集.

Answer 2

函数式编程中最明显的共享示例来自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的做法有所不同.