三年前，一篇博客文章在 Haskell 中引入了目标传递风格（DPS）编程，重点关注数组处理，得益于线性 Haskell，其 API 变得安全。今天，将介绍一种略有不同的 API 以 DPS 方式操作任意数据类型，并展示其在程序某些部分的有用性。

本文主要基于最近在 JFLA 2024 发表的论文Destination-passing style programming: a Haskell implementation，假设对线性 Haskell有基本了解且在 Haskell 中有中级流利度。

尾模构造

Haskell 默认是惰性语言，但实际上许多算法在严格设置下更有效。这是 Haskell 扩展对选择性严格性支持的原因之一，例如通过严格字段注释。
非尾递归函数如map在惰性设置中效率尚可，但在严格数据结构上，非尾递归会消耗栈空间，这就是为什么在像 OCaml 这样的严格语言中，尾递归实现的追求比在 Haskell 中更重要。
如果任何函数都可以通过 CPS 转换为尾递归，这种转换会以堆空间换取栈空间（用于分配构建的延续），在性能方面通常不是优势。实际上，我们希望专注于不依赖延续的尾递归实现，但不幸的是，一些函数在纯函数设置中没有。
例如，一些函数几乎是尾递归的，即递归调用是返回值中的倒数第二个计算，最后一个只是构造函数应用。map就是这种情况：

map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x : xs) = (f x) : map f xs

有人可能认为map的尾递归版本可以使用累加器来存储结果列表，然后在末尾反转它，但这会引入一个额外的线性操作（反转累加器），而在朴素版本中不存在。
实际上，Bour 等人在 2021 年发现，每当一个函数具有这种特定形状——在递归调用上只有构造函数应用——称为尾递归模构造，这个函数可以很容易且自动地转换为等价的目标传递风格（DPS）尾递归函数。
在 OCaml 中，这种转换完全在编译器中进行。而在本文中，将展示如何在 Haskell 的用户空间中通过线性类型实现，从而使 API 安全。
对于map，以下是转换为 DPS Haskell 的代码，稍后会详细介绍：

mapDPS :: (a -> b) -> [a] -> Dest [b] %1 -> ()
mapDPS f [] d = fill @'[] d
mapDPS f (x : xs) = let!(dh :: Dest b, dt :: Dest [b]) = fill @'(:) d
                     in fillLeaf (f x) dh `lseq` mapDPS f xs dt

什么是目标传递风格编程？

目标传递风格（DPS）是一种编程习惯，其中函数不返回结果，而是将结果直接写入作为参数接收的内存位置。这给函数的调用者更多的内存控制权，而不是完全由被调用者控制。在非垃圾回收语言中，或用于数组处理（如上述博客文章），它允许一次分配一大块内存，然后让程序的每个部分负责填充这块内存的一小部分（由一个华丽的指针表示，即目标），从而得到几乎无分配的代码。在早期的命令式语言如 C 中，这实际上很常见：memcpy和strcpy都接收一个目标作为参数。
在函数式、不可变、基于垃圾回收的语言中，我们不能通过规避堆对象的分配来获得无分配的代码。相反，我们获得了一个有趣的特性：能够以与常规基于构造函数的方法相反的顺序构建函数结构。这与安全地创建和操作不完整数据结构（包含未指定的字段，即漏洞）的能力密切相关。这正是本文将重点关注的。

你说的不完整结构？

不完整结构可以看作是构造函数对象的树，类似于常规数据结构。然而，构造函数的一些字段可能未指定，在结构中留下漏洞。
拥有不完整结构与在Maybe a类型表示的结构中拥有可选字段非常不同。对于所谓的不完整结构，我们不是通过叶子本身的不同类型来表示值的缺失（或漏洞的存在），而是只要至少在某个地方存在一个漏洞，就禁止对整个结构进行任何读取。这样，字段的值可以（实际上必须）在稍后更新，而无需再次分配整个结构。
要更新不完整结构中尚未填充的字段，我们使用目标。目标是指向不完整结构中漏洞的唯一指针，一旦漏洞被填充，该指针就不再可用。这些指针与结构一起携带，直到它们被消耗。因此，目标也是一种知道结构是否有任何剩余漏洞的方式。当一个不完整结构不再有任何伴随的目标时，就可以安全地读取它。
在这一点上，不完整结构可能被视为 Haskell 的克星，因为如果处理不当，它们会带来一种形式的可变性和一系列内存错误。然而，通过适当的线性API，这是本文的真正创新之处，它们既强大又安全。特别是，对目标的线性约束保证：

1. 当一个结构不再有伴随的目标时，它是一个完整的结构（即没有剩余的漏洞）；
2. 一旦一个漏洞被一个值填充，该值就不能再更改（即漏洞是一次性写入的）。

不完整结构的实现

如前所述，引入了不透明的data Incomplete a b来表示不完整对象。a部分是正在构建的可能包含漏洞的结构，b部分携带指向这些漏洞的目标。目标在底层是原始指针，放在一个漂亮的盒子里：data Dest a表示指向类型a的漏洞的指针。
我们可以对Incomplete a b做什么？只要b侧仍然包含目标（因为它们表示a侧存在漏洞），我们就不能读取a侧的结构（尚未）。b侧必须被线性消耗才能使结构可读。我们可以通过线性延续b %1 -> c来访问不完整对象的目标，这通过一个（线性）Functor实例暴露：

instance Control.Functor (Incomplete a) where
  fmap :: (b %1 -> c) %1 -> Incomplete a b %1 -> Incomplete a c
  (<&>) :: Incomplete a b %1 -> (b %1 -> c) %1 -> Incomplete a c  -- flipped arguments

这个Functor实例允许我们通过类型为b %1 -> c的线性延续访问不完整对象的目标。
让我们回顾一下之前的例子。mapDPS的签名为(a -> b) -> [a] -> Dest [b] %1 -> ()。这意味着mapDPS f list实际上是类型为Dest [b] %1 -> ()的线性延续。
换句话说，给定一个具有类型[b]漏洞的不完整结构i :: Incomplete u (Dest [b])，我们可以使用i <&> mapDPS f list将f映射到list的结果写入这个漏洞。得到的结构将具有类型Incomplete u ()（不再有目标），并且可以在稍后读取。
这里我们可以看到 DPS 的本质：函数的责任减少了，因为它们不能选择将结果写入何处；相反，输出位置现在作为显式参数传递给函数。此外，在mapDPS等函数内部，我们实际上别无选择，只能忘记我们正在构建的全局结构——它变得隐式——而只关注目标的处理。Functor实例就是将位置分配给mapDPS等数据生产者以写入其输出的粘合剂。

操作目标

让我们仔细看看mapDPS的实现：

mapDPS f [] d = fill @'[] d
mapDPS f (x : xs) = let!(dh :: Dest b, dt :: Dest [b]) = fill @'(:) d
                     in fillLeaf (f x) dh `lseq` mapDPS f xs dt

在基本情况下，输入列表中没有元素了，但我们仍然收到一个需要线性处理的目标d :: Dest [b]。这里唯一有意义的操作是将空列表写入由d表示的漏洞，这就是fill @'[] d所做的。
递归情况更有趣：

1. 应该在列表中添加一个cons单元，携带值f x :: b；
2. 我们需要以某种方式创建另一个类型为Dest [b]的目标，以传递给递归调用。
   所有这些都通过两步完成，使用fill @'(:)和fillLeaf。
   首先使用fill @'(:) d在链表末尾添加一个新的空心cons单元(:) _h _t :: [b]，也就是说，一个具有未指定字段（头_h和尾_t都是漏洞）的cons单元。在底层，它分配新的空心cons单元，将其地址写入目标d :: Dest [b]，并返回一个指向漏洞_h的目标dh :: Dest b和一个指向漏洞_t的目标dt :: Dest [b]。这给出了签名fill @'(:) :: Dest [b] %1 -> (Dest b, Dest [b])。
   然后，使用fillLeaf将dh :: Dest b（表示新添加的cons单元的“值部分”）填充为f x :: b的结果。fillLeaf :: a -> Dest a %1 -> ()实际上非常简单。它接受一个值、一个目标，并将值地址写入由目标表示的漏洞。在这个过程中，目标被线性消耗。
   完成此操作后，只剩下一个未消耗的目标：dt :: Dest [b]。这正是将传递给递归调用的目标！它对应于链表的新“末尾”。
   在这里我们可以直接看到fill @'(:)如何通过在末尾添加一个新的“插槽”来扩展（不完整）列表；而cons (:)通常用于从前面扩展一个正常的链表。这就是我在引言中所说的以相反的顺序构建函数结构的含义。
   实际上，我刚刚介绍的内容不限于列表。只要它实现了Generic，就可以用于构建任何类型的结构。这基本上是fill的唯一约束；它可以用于各种构造函数。例如，我们可以以类似的方式构建一个二叉树，从根开始，以自顶向下的方式逐步扩展它，使用fill @'Leaf和fill @'Node（假设data Tree a = Leaf | Node a (Tree a) (Tree a) deriving Generic）。

创建和处理不完整结构

可以使用alloc :: Linearly %1 -> Incomplete a (Dest a)创建一个新的空Incomplete。这个函数用一个Linearly令牌（见下文）交换一个所选类型a的Incomplete。得到的Incomplete有一个指向其根类型为a的单个目标。换句话说，即使新结构的根在当前也是一个漏洞，稍后将使用fill或fillLeaf的第一次使用来指定它。
相反，一旦我们在b侧只有单位()的Incomplete，目标的缺失表明a侧的结构是完整的。因此，我们可以通过使用fromIncomplete :: Incomplete a () %1 -> Ur a从Incomplete包装中取出它，使其可读。
以非线性方式使用构建的结构是有效的（这就是为什么在fromIncomplete的返回位置将其包装在Ur中），因为它仅由非线性元素组成：fillLeaf在其第一个参数中是非线性的，并且结构的主干可以复制而不破坏线性。
这个 API 的最后一个缺失部分是linearly :: (Linearly %1 -> Ur b) %1 -> Ur b，其定义与之前关于线性范围的博客文章中的定义相同。linearly界定了一个可以使用线性对象的范围。只有非线性对象才能离开这个范围（因为像以前一样，返回类型受到Ur的限制），例如通过调用fromIncomplete完成的完整结构。
Linearly类型（linearly提供了一个实例）是一个线性令牌，可以复制它来生成任意数量的Incomplete，但每个Incomplete仍必须线性管理。
有了这些最后的要素，我们可以完成尾递归map的定义：

map :: (a -> b) -> [a] -> [b]
map f l =
  unur $ linearly $ \token ->
    fromIncomplete $ alloc token <$> \d ->
      mapDPS f l d

性能

API 背后的当前实现基于紧凑区域，因为它们使在内存上操作更容易，而不会与垃圾回收器产生太多冲突。然而，在某些上下文中，它们会导致额外的复制，这使得有时难以与优化的惰性 Haskell 代码竞争。
目前，对于大列表，mapDPS的实现在内存方面比优化的惰性实现更有效（对于较小的列表效率较低）。在相关论文的第 6 节中对不同用例进行基准测试时也获得了相同的结果。我期望未来一个不使用紧凑区域、直接在 GC 堆中进行的实现将具有更好的性能。
此外，这里详细介绍的 DPS 技术在严格语言中被证明非常有效。这项工作可能会启发除 Haskell 之外的其他语言的性能和表达性改进。

结论

本文介绍的 API 定义了一组工具，足以通过目标传递风格编程在 Haskell 中安全地创建和操作不完整数据结构。它比函数式编程语言中通常使用的基于构造函数的构建方法更通用，也比 OCaml 中 Tail Modulo Cons 引入的 DPS 工具更通用。它也是线性类型如何在 Haskell 中强制使用一次性内存模型的一个很好的例子。
完整的原型 API 可在此处获得。目前，它需要自定义 GHC 版本才能工作，但希望将来能够将 DPS 编程所需的少数原始操作合并到 GHC 中。
感谢 Arnaud Spiwack 对这项工作的所有方面提供的坚实支持和反馈。

1. OCaml 自版本 4.14.0以来就有对尾递归模构造的实验支持。↩