在实现函数式编程语言时，共享是指什么 [英] What does sharing refer to in the implementation of a functional programming language
问题描述
共享表示临时数据将在多次使用时存储。也就是说，一个函数只能评估一次它的参数。一个例子是：
let x = sin x in x * x
还有哪些其他功能可以共享 ，它们如何与实际程序执行IO的需求进行交互？ b $ b
函数式编程中最清晰的共享示例来自Clean，它基于图形重写。在那里，一个计算指的是一个DAG，所以我们可以把表达式看作是（sin x）*（sin x）作为
（*）
/ \
sin x sin x
图表重写系统有一个明确的共享概念，所以我们可以将计算表达为 $ b
（*）
/ \
\ /
sin x
将乘法节点指向同一节点，从而共享 sin x 的计算。术语重写系统没有如此明确的共享概念，但优化仍然相关。在GHC中，人们有时可以用局部变量表达共享，例如，重写
fx =（sin x）*（sin x）
转换为
fx = sinx * sinx
where sinx = sin x
但是由于这两者在语义上是等价的，因此编译器可以自由地实现相同方式，有无共享。根据我的理解，GHC通常会保留与局部变量一起引入的共享，有时会引入它（在第一个中增加共享），但是没有在术语重写系统中正式表达共享，这两种行为都依赖于实现（请参阅tel的评论和回答）。
共享触控IO，因为无法共享副作用值。如果我们考虑一种不纯的语言，那么
（string-append（read-line）
（ ）
和
<$ p $（$ s $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $'
第一个执行两次IO操作，向用户请求两行并追加它们;第二个共享IO操作，执行一次并将其附加到自身。通常，共享一个纯粹的计算可以在不改变程序结果的情况下减少执行时间，同时共享一个副作用值（可能随时间变化或者与用户交互）会改变结果。为了编译器自动共享计算，它需要知道它们是纯的，因此减少评估数量并不重要。 Clean用独特的类型来做这件事;一个IO动作具有类型属性UNQ，它告诉编译器它不应该被共享。 Haskell和IO monad的做法有些不同。
Sharing means that temporary data is stored if it is going to be used multiple times. That is, a function evaluates it's arguments only once. An example would be:
let x = sin x in x * x
What other features contribute to sharing and how would they interact with the need for practical programs to perform IO?
The clearest example of sharing in functional programming comes from Clean, which is based on graph rewriting. There, a computation refers to a DAG, so we can view the expression (sin x) * (sin x) as
(*)
/ \
sin x sin x
Graph rewriting systems have an explicit notion of sharing, so we could express that computation as
(*)
/ \
\ /
sin x
pointing the multiplication node to the same node, thereby sharing the computation of sin x. Term rewriting systems do not have so explicit a notion of sharing, but the optimization is still relevant. In GHC, one can sometimes express sharing with local variables, e.g. rewriting
f x = (sin x) * (sin x)
into
f x = sinx * sinx
where sinx = sin x
But since the two are semantically equivalent, the compiler is free to implement both the same way, with or without sharing. By my understanding, the GHC will generally preserve sharing introduced with local variables and sometimes introduce it (adding sharing to the first), but with no formal expression of sharing in term rewriting systems either behaviour is implementation dependent (see tel's comment and answer).
Sharing touches IO because side-effecting values cannot be shared. If we consider an impure language, there is a difference between
(string-append (read-line)
(read-line))
and
(let ((s (read-line)))
(string-append s s))
The first executes the IO action twice, requesting two lines from the user and appending them; the second "shares" the IO action, executing it once and appending it to itself. In general, sharing a pure computation reduces execution time without changing the result of the program, while sharing a side-effecting value (one that may change over time, or interacts with the user) changes the result. For the compiler to automatically share computations, it needs to know that they are pure, and thus that reducing the number of evaluations does not matter. Clean does this with uniqueness types; an IO action has the type attribute UNQ, which tells the compiler that it should not be shared. Haskell does the same somewhat differently with the IO monad.
这篇关于在实现函数式编程语言时，共享是指什么的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
