Unique Objects

Unique Objects

by: Bartosz Milewski

以前发过一篇通过基于拥有关系的类型系统实现唯一性的博客文章C++ unique_ptr not being unique 。但我只是看到了冰山一角。

多线程编程是推动唯一性探索的主要动力。唯一对象是自由的，特别是在一个时间点只能被一个线程所访问。因为这样的原因，它们不需要加锁。它们也可以不通过深度复制 在线程间安全的传输。也就是说，他们是完美的高效的消息传递工具，但是。。。

你如何产生和修改一个带内部指针的唯一对象？一个经典的例子是双向连表。考虑如下的java代码：

1. public  class  Node {
2.     public  Node _next;
3.     public  Node _prev;
4. }
5. public  class  LinkedList {
6.     private  Node _head;
7.     public  void  insert(Node n) {
8.         n._next = _head;
9.         if  (_head != null )
10.             _head._prev = n;
11.         _head = n;
12.     }
13. }

假设你有 一个空连表的实例，现在你想插入一个节点而不破坏它的唯一性。

第一个危 险是你插入的节点因为有外部别名而不唯一，它是共享的。在节点被吸收后：

1. _head = n;

_head 将被指向一个别名污染的对象。列表捕获这样的一个对象后会打断唯一性。

解决的方 案是被插入的节点也必须是唯一的，并且它的拥有关系要从调用者转换到insert方法。（无论如何，在插入处理期间，节点失去了它的唯一性，因为在列表内 部潜在的存在两个别名：_head和_head._prev。对象们在列表内部不是必须得唯一，他们需要交叉连接。）

第二个危 险是插入方法可能泄露别名。棘手的部分是当我们让外部节点存储我们内部_head的引用时：

1. n._next = _head

我们知道 在这里是安全的因为开始节点的唯一性，它将被吸收进列表，所以这个别名将成为内部别名。但我们如何让编译器确信这段代码是安全的并拒绝不安全的代码？这就 需要类型系统来帮忙了。

Types for Uniqueness

有一些方 法可以让类型系统达成唯一性。根据我的知识，最实用而广乏的一个方式是Haller和Odersky在《Capabilities for External Uniqueness》这篇论文里提出的。我将在这篇文章里讨论这些。

论文作者 们不仅提出了理论，也实现了作为Scala延伸的系统原形。因为很多人对Scala不熟悉，我讲把他们的例子转化为伪java代码，希望没有漏掉太多东 西。

-Objects that are @unique

Scala 和java都支持用Annotation扩展类型系统。唯一性引进了3个Annotation: @unique, @transient 和 @exposed；还有两个额外的关键词，expose 和 localize。

您对 @unique对象的第一个大致估算是作为一个防泄露版的C++ unique_ptr，这样的对象被跟踪守护限制成只能有一个引用，别名是不允许的。这个对象的内部资源也不允许被外部引用，对象内部也不允许引用任何外 部对象。非常重要的一点是，@unique对象可以自由的引用其他@unique对象。这样一个交叉连接的乱麻被叫做族。

考虑这样 一个例子，一个非空的由交叉连接集合组成的@unique连表。非常容易由编译器保证没有@unique列表的外部别名产生。棘手的部分是如何不打断它的 唯一性而允许操作它。

连表和它的节点如何由族分离

看看插入 的定义，不带额外的注解时我们调用带一个节点的连表是在几个外部别名间共享的。在节点被包裹进连表后，别名仍然指向列表内部就打断了它的唯一性。因为这样 的原因。有唯一性领悟的编译器将标志这样一个不带注解的@unique列表插入动作为错误。那么我们如何注解这样的插入而让其保护唯一性呢？

Exposing 和 Localizing。

这是修改 版的插入定义：

1. public  void  insert(@unique  Node n) @transient  {
2.     expose (this ) { list =>
3.         var node = localize (n, list);
4.         node._next = list._head;
5.         if  (list._head != null )
6.             list._head._prev = node;
7.         list._head = node;
8.     }
9. }

别担心太 烦琐，这里大部分增加的代码可以被编译器推断出来，我这里写这么明确是为了加深理解。让我们深入细节。。

代码里， 传入insert的n被申明为@unique。这保证了它来自它的拥有族并且n是它的唯一引用。另外传@unique参数到一个方法是被这个方法消费了 的，调用者不再拥有自己对之的引用（编译器使之作废），这个例子可以证明：

1. @unique  LinkedList lst = new  @unique  LinkedList();
2. @unique  Node nd = new  @unique  Node();
3. lst.insert(nd);
4. nd._next; // error: nd has been consumed!

这个方法 自己被明确的注解为@transient，意味者这里的this对象是@unique，但没有被这个方法消费。一般来说，@transient注解可以加 在任何参数上，不只是this指针。你可能熟悉@transient的另外一个名字 -- borrowed 。

在插入方 法里，this参数是明确的被裸露了（实际上，因为这个方法是@transient，编译器隐式的裸露了this指针）

1. expose (this ) { list => ... }

expose 域里this裸露后的新名字是list.

一旦一个 族被暴露，它的组成部分可以被重连接。技巧是在重连接操作时不允许任何别名泄露。这里的一个难点是：为了保证不泄露，编译器把裸露对象标志为一个特殊类 型。它的原始类型被打上唯一标识符的标签。这个标识符是为单个裸露域创建的。这个裸露族的所有成员也被标记为上一些标签。编译器的类型检测每次都自动分配 保证双边都被标记的任务。

让 @unique节点进入族我还需要更多的原料，这通过使参数n localizing 到list族来实现。

1. var node = localize (n, list);

Exposed list and localized node

localize 语句做了两件事，它消费了n,并且返回一个带有第二个参数标记的引用。基于这样的出发点，所有暴露域里的节点带有同样的标记，这样的标记通过类型检测来指 派。

列表被暴露后：所有的引用被标记了。node被本地化 了（标记为和列表同样的标签）。现在可以不违背类型系统而重新连接它们了。

注意，在 我的伪java代码里，我没有特别申明本地化后返回的node类型。这是因为标记的类型是从来不会在编程中明确用到。这是编译器的操控的领域。

Functional Decomposition

最后的这 个例子是关于如何把那些裸露对象的代码整和进一个方法。一个切实可行的类型系统不能强迫约束代码的结构。很多编程语言的一个基本要求是可以功能分解 -- 把工作伪托给分离的子程序，这样就可以在上下文复用它们了。我们必须能够定义可以操作暴露/本地化了的对象的函数。

这是一个 来自Haller/Odersky的在暴露域里递归调用的例子。显然这是一个单向连接的方法。

1. void  append(@unique  SinglyLinkedList other) @transient
2. {
3.     expose(this ) { list =>
4.         if  (list._next == null )
5.             list._next = other; // localize and consume
6.         else
7.             list._next.append(other);
8.     }
9. }

在if语 句的第一个分支，@unique的other参数，被隐式的本地化和消费了。在第二个分支，它被递归的传给了append方法。请注意一个重要的细 节，list._next不是@unique的，它是裸露的。它的类型带有unique标记。append方法被注解为@transient，这导致 unique和exposed参数都安全的作为transient参数被接受了（包括隐式的this参数）。

因为这样 的规则，省略transient方法的裸露声明是安全的。append方法可以被简化为：

1. void  append(@unique  SinglyLinkedList other) @transient
2. {
3.     // 'this' is implicitly exposed
4.     if  (_next == null )
5.         _next = other; // localize and consume
6.     else
7.         _next.append(other);
8. }

当你在其 他方法里重用append方法时事情就变的有趣了，考虑下面的insert实现：

1. void  insert(@unique  SingleLinkedList other) @transient
2. {
3.     var locOther = localize(other, this );
4.     if  (other != null )
5.     {
6.         locOther.append(_next)
7.         _next = locOther;
8.    }
9. }

insert 方法是transient的， 它工作在一个unique或exposed的列表。接受一个唯一性的list，other被localize语句消费了，this引用隐式的和一些 locOther标签裸露了，所以最后的语句_next=locOther 带了类型检测。唯一的没有进行类型检测的是传给append的参数，它应该是唯一的，但在这里被一个裸露的参数替代了。

这次没有 安全转化帮助了，所以如果我们想要重用append，就必须修改它的定义。首先，我们标记它的参数为@exposed。一个@exposed的参数被调用 者标记了。为了让append 工作，this必须被调用者标记为同样的标签。另外，在append里的_next=other语句，不需要类型检测。这是因为append方法也必须被 标记为@exposed （当这里有超过一个@exposed参数，他们全都要被标记为某个标签）

新版本的 append方法：

1. void  append(@exposed  SinglyLinkedList other) @exposed
2. {
3.     if  (_next == null )
4.         _next = other; // both exposed under the same tag
5.     else
6.         _next.append(other); // both exposed under the same tag
7. }

一些有趣 的事情发生在append方法里。当它的操作在exposed对象上时，它的调用者负责裸露和本地化unique对象（这是我们在insert里做的事 情）。有趣的是，append也可以操作在非注解类型上了。比如append一个非唯一对象到一个非唯一对象将被类型检测。因为非注解类型就想当于带 nulltag的暴露类型， 他们来自一个自拥有的全局族。

这种注解 /非注解的多态意味者你不需要为唯一对象定义很多分离的类。Haller和Odersky的发现使几乎所有Scala集合库里的方法只加上 @exposed注解而不改变他们的实现就可以达成唯一性。这就是为何他们提议在完整的类上使用@exposed注解。

Conclusion

每次我读 Scala的论文都有深刻的印象。它使用的所有运行时相对于java拥有坚实的理论基础和丰富的实践经验。我喜欢Scala对并发性的关注以及强安全的灵 活消息传输。像函数式语言，Scala支持不变量消息，和唯一性注解，它也将支持安全的可变量消息。而这些都不需要同步（其他语言也有消息队列的实现方 式）或深度复制。

在 Scala的并发模型里有一个缺陷，它可能在线程间不带保护的共享对象。它取决于被声明为共享的同步方法的参数，就像在java里一样。这里没有大体上的 数据竞争自由保证。目前为止，只有拥有者类型系统能够提供这样的担保。如果Martin Odersky开始为Scala挽起袖子再做重大突破我是不会惊讶的。

在此非常 感谢Philip Haller为本文做的审阅工作和提供宝贵的评论。Philip告诉我一个新的原形在进行中了，它将为编程者和实现者简化类型系统特性。

评论

2 楼 sleets 2010-04-10  

d的介绍上说为了更简单的编程，所以从动态语言借鉴了很多语法。

你实际使用的时候会发现它的垃圾收集器非常影响性能，去抱怨的话他们会告诉你一个好程序员会尽量少分配内存，并且在程序启动的时候就分配所有使用的内存。

使用D虽然有很多优势，但实际要用D写出好程序需要程序员有丰富的编程经验和技巧，这和它的介绍多少有点冲突。`

到目前为至，D语言没有经过考验大量使用在生产环境的产品，很多项目作者都失去兴趣了， D在可用性上的缺憾是主要原因。

不精心优化，D的很多时候性能都没有Python等动态语言强。而优化需要很多额外的时间精力，优化时也会带来更多更难调试的bug。

如果你不在乎性能，只想写一个特性丰富的产品。D仍然不是一个很好的选择，你需要去把很多库封装给D用，这需要你至少有C语言的经验。当然转换工作不需要多少技巧和经验。但在只想简单编程的人来说，是一个门槛。


D2想降低多线程编程的门槛，如果不能用D2轻松便捷的写出高效安全的程序。它的目标就没有达成。以现在状况来看，仍然有很远很远的路要走。

1 楼 hqs7636 2010-04-09  

好文！没人顶啊

这里好像有说到多核多线程下的新的内存管理模式：
http://www.ece.ncsu.edu/arpers/Papers/MMT_IPDPS10.pdf

https://buildsecurityin.us-cert.gov/bsi/articles/knowledge/coding/306-BSI.html

在ng上帖了一下，没人搭理，哈哈