线性哈斯克尔中纯粹的目的地传递风格

我今天的目标是让你们相信，事实上，传递目的地的风格是整洁的。而这种线性类型使目的地传递变得纯粹起作用。但首先，我必须回答一个问题。

如果你曾经用C、C++或Fortran编程，你肯定会遇到这种编程风格，这种风格有时被称为目标传递风格。这是一种编写实践，例如，将数组生成函数作为额外参数接受空数组并填充它。例如，考虑C strcpy函数：

它将源中的字符串复制到数组目标(完成后还返回目标)。

然而，在函数式编程语言编译文献中，“目的地传递风格”这个名称似乎更常见。C程序员似乎没有给它起个名字。所以很可能你从未遇到过它。

事实上，为什么要关心目的地传递呢？它确实让您提出了一个新问题：“分配数组是谁的责任？”如果我要用Haskell编写数组副本，它的类型为。

而且也没有办法避免CopyArray本身分配一个数组。这个问题根本不存在。使用strcpy，我可以选择分配一个数组，然后立即将其传递给strcpy，或者将数组的分配分配给其他人。

但是，一旦我可以问这个问题，我能用它做什么呢？我可以作曲！假设我们有一个将数组一分为二的函数。

CopyArray2：：Array a->；Array a CopyArray2 a=case SplitArray a of(al，Ar)->；Copy Array al<；>；Copy Array ar

当问题不存在时，无论发生什么情况，每次对CopyArray的调用都必须分配一个数组，然后将该数组复制到一个新的数组中。这意味着我们正在制作原始数组的多余副本，但却立即将其丢弃。这是相当浪费的。

通常情况下，你确实可以依靠数组融合来避免过于恶劣的行为。数组融合，例如在优秀的向量库中实现，将消除大量的中间分配。

然而，聚变是不可靠的。有时，简单的重构会使函数的大小超出GHC愿意内联的范围，并且会破坏整个融合管道。大多数情况下，这是可以的，但当您依赖于融合发生时，情况就不同了。如果您需要GHC在没有分配的情况下生成代码，为什么不直接编写您想要的程序，而不是尝试诱使编译器为您消除分配。

这一直是线性类型项目开发中的指导原则：编译器优化是很棒的，因为您不需要考虑很多事情；直到您这样做了，您才发现自己在事后猜测优化器。当这种情况发生时，我们希望线性类型使您能够编写您想要的代码，而不牺牲Haskell的类型安全性。

此外，在一篇关于F̃的文章中，作者发现，在数组融合优化的基础上使用目标传递可以显著提高性能。F Language是一种受限的基于数组的函数式语言，可以编译成非常高效的代码。不过，他们只在优化器中使用目的地传递，而不是将其作为一种语言功能。

最后，核聚变并不总是有效的。假设我重写了CopyArray2函数，以使用线程来更好地利用我的多核体系结构。

CopyArray3：：Array a->；IO(数组a)CopArray3=case plitArray a of(al，ar)->；do(bl，br)<；-并发(求值$CopyArray al)(求值$CopyArray ar)返回$bl；lt；>；br。

这超出了融合框架的优化能力。或者，我可能想要将数组复制到内存映射缓冲区中。关键是：融合会给你带来很多好处，但不是一切。

在Haskell中，对目的地传递方式进行编码的最明显的方法是将我们所有的计算都移到ST，这样CopyArray将是。

但这与函数式程序员编写程序的方式不太一致。它确实取消了所有上述限制，代价是到处添加状态，这是函数式编程通常避免的整个错误诱导面。

这是一个巨大的代价，这就是为什么矢量库不是这样的结构。它确实具有可变数组，但非常推荐使用不可变的耳光。

这就是线性类型有用的地方。的确，让我们退一步问一问：是什么让目的地从一开始就不纯洁？

如果我读出一个单元格，然后写到它，然后再读一遍：第二次我会看到不同的结果。

如果我向同一单元写入两次，则需要对写入进行排序，否则结果将是不确定的。

读取尚未初始化的单元格是不确定的(尽管在大多数情况下，我们可以通过将每个单元格初始化为UNDEFINED来挽救这种情况)。

所有这些行为在纯代码中都是被禁止的。但是，如果我们能确保每个细胞在被读取之前只被写入一次，我们就可以避免所有被禁止的行为。啊哈！只有一次，这是线性类型擅长的事情！好的，那么让我们再来一次：

这意味着CopyArray是一个纯函数，它只使用其目的地(全部)一次。我们只需要确保只有一个指向目标数组的唯一指针，这是我们使用Alloc函数实现的：

为线性函数的作用域分配目的地。在函数结束时，我们知道目的地已被填满，因此我们得到一个数组。顺便说一句，从这个目的地传递版本的CopyArray中，很容易检索到直接样式变体：

复制数组：：数组a->数组a复制数组a=分配(长度a)(\d->；复制数组a d)。

相反的，正如我在这篇文章中一直在争论的那样，很大程度上是不正确的。所以目的地传递函数是更基本的。

然后，这只是一个遵循类型的问题(奇怪的&；\case结构是由于GHC中线性类型的当前实现的限制，请看这里)。

CopyArray2：：Array a->；dArray a⊸()CopyArray2 a d=case拆分数组a，共(al，ar)->；拆分数组d；\case(dl，dr)->；Copy阵列dl`lseq‘Copy阵列ar DR。

哇！没有多余的分配。这不是因为优化器，而是因为我的程序的语义：它不会在任何地方分配数组。

您可以在LINEAR-BASE的Data.Array.Destination模块中找到更完整的目标数组接口。

线性类型的一个特点是，它们通常允许将本质上看起来不纯净的对象公开为纯接口。但我想说的是，在目的地的情况下，我们实际上做了更多的事情：我们改进了界面，而不是不纯的界面。这并不是因为纯接口比纯接口更好(尽管这是一个合理的立场)，而是因为线性目标接口更忠实地表示了目标的含义。

不再混淆什么是输入，什么是输出：输入是数组，输出是DArray。目的地只用于输出，不能用作数据的临时存储。这些类型确保它们已完全填满，并且在目标作为数组读回时，我们不会意外覆盖输出。

如果你想更深入地了解这一特定品牌的大麻，让我给你留下几条评论，你可以把它们作为关闭这篇博客的帖子，或者打开新的途径。

Alloc函数将使用目的地的函数作为参数，而不是直接返回目的地。这种风格在线性Haskell中很常见，作为一种强制唯一性的手段。这有时被视为线性哈斯克尔设计的局限。然而，在这种特殊情况下，该函数对于界定目的地的范围是必要的。事实上，Alalc函数实际上与F̃文章中的函数相同，在该文章中没有任何线性类型。

仿射类型(仿射参数最多使用一次，而不是线性参数恰好使用一次)有时比线性类型更可取。例如，仿射类型似乎更好地表示流计算。但在目的地的情况下，我们确实需要线性类型：从分配的目的地返回部分填充的目的地没有多大意义。

当使用线性类型来建立数组函数的纯接口时，实际上是为了提高效率而改变数组(就像在这个线性基数的模中)，我们失去了用可变数组的别名来换取纯洁性的能力。有时这是一个完全可以接受的折衷方案，但有些算法依赖于共享变异来提高效率，这在线性纯可变数组中是无法实现的。我们没有对目的地进行这样的取舍：线性目的地是纯输出，可以说是目的地传递风格的一个比可变数组更忠实的接口。

您有没有注意到，在目标传递的复制Array2中，直接样式实现中的Call到数组连接被替换为对SplitDArray的调用？如果你有，你有没有注意到这两个函数之间的对称性？

取消复制(<；>；)：：(数组a，数组a)->；数组拆分DArray：：Darray a⊸(数据数组a，数据数组a)

这不是巧合。目的地和建设者之间存在一种二元性。当写入除数组类型以外的其他类型的目标时，也会发生这种二元性。我在2017年哈斯克尔交易所(Haskell Exchange 2017)上谈到了这种现象。

如果我定义类型PushArraya=DArray a⊸()，则复制数组的类型。

我们可以给PushArray一个(受限的)数组接口，那么我们甚至不需要放弃直接样式来从目的地获益。这是线性基座中数据、阵列、偏振框架的一部分。

在之前的一篇博文中，我曾写过线性类型如何使直接操作压缩数据表示成为可能。事实上，博客帖子中所需类型是目的地的一种形式。