haskell - Haskell 中的内存

Question

Context :

def fib(n):
    if n < 2: return 1
    return fib(n-1) + fib(n-2)

can be sped up by memoization:

fib_memo = {}
def fib(n):
    if n < 2: return 1
    if not fib_memo.has_key(n):
        fib_memo[n] = fib(n-1) + fib(n-2)
    return fib_memo[n]

This implementation technique of memoization is used widely in manyprogramming languages, but it can’t be applied directly to Haskellbecause Haskell is pure and we don’t want to introduce impurity justto memoize a function. Fortunately, it is possible to memoize afunction without side effects thanks to Haskell’s nature of lazyevaluation.

The following memoize function takes a function of type Int -> aand returns a memoized version of the same function. The trick is toturn a function into a value because, in Haskell, functions are notmemoized but values are.

问题:

1. 在函数式编程中函数和值不是一样的吗？
2. 缓存如何不被视为副作用(在纯函数的上下文中)

Answer 1

所有函数都是值，但并非所有值都是函数。

这实际上是关于操作语义的，在 Haskell 中有时很难谈论它，因为 Haskell 仅根据其指称语义定义——也就是说，< em>什么表达式计算出的值，而不是如何计算发生。这不是副作用，因为记忆化的“有状态”本质仍然隐藏在纯粹的抽象背后:虽然有一些内部状态(在程序的部分图形缩减中表示)，但您的程序无法观察以一种将其与非记忆化版本区分开来的方式。这里的一个微妙之处是这些记忆化策略实际上并不是记忆化所必需的——所有可以保证的是它们在一些未指定的有限时间后给出的结果。

Haskell 实现不需要内存任何东西——它可以使用纯粹的按名称调用，例如，它不内存值，而是重新计算一切。这是按名称调用的示例。

let f x = x * x in f (2 + 2)
= (2 + 2) * (2 + 2)
= 4 * (2 + 2)
= 4 * 4
= 16

这里 2 + 2 计算了两次。大多数 Haskell 实现(除了优化之外)都会创建一个 thunk 以便它最多被计算一次(这被称为 call-by-need)。但是，对其进行两次评估的按名称调用的 Haskell 实现在技术上是符合要求的。因为 Haskell 是纯的，所以计算结果不会有差异。但在现实世界中，这种策略最终过于昂贵而无法实用。

至于选择不内存功能的逻辑是一样的。编译器使用类似 optimal evaluation 的方式积极内存每个函数，这完全符合编译器的要求。 . Haskell 的纯度意味着如果选择这种评估策略，结果不会有差异。但同样，在实际应用中，像这样内存每个函数最终会占用大量内存，而且最佳评估器的开销太高，无法提供良好的实际性能。

Haskell 编译器也可以选择内存一些函数而不是其他函数以最大化性能。这太棒了——我的理解是，目前还不知道如何可靠地做到这一点。编译器很难提前判断哪些计算成本低，哪些计算成本高，哪些计算可能会被重用，哪些不会。

因此选择了一种平衡，在这种平衡中，其评估形式通常小于其 thunk 的值被内存；而函数，其内存形式通常大于它们的定义(因为它们需要一个完整的备忘录 table)，但不是。然后我们得到一些像文章中的技术，根据我们作为程序员的判断在这些表示之间来回切换。