functional-programming - 解码散列约束数据的技术选择

Question

似乎有相当多的民间传说知识在有限的圈子里流传，关于哈希consing 与数据的编码-解码相结合的陷阱。我正在寻找对这些花絮的可引用引用。

例如，有人曾经指给我图书馆 aterm并提到作者已经清楚地考虑了这一点，并且磁盘上的表示是自下而上的(节点的子节点在数据流中位于节点本身之前)。当您需要重新共享每个节点(内存中可能存在相同的节点)时，这确实是正确的处理方式。这种重新共享的过程需要自下而上进行，因此解码本身也可能是这样，这样就可以在一次传递中完成所有操作。

我正在描述在我们自己的背景下遇到的困难，以及我们找到的解决方案。我将不胜感激任何对上述民俗知识的引用。之前显然有人遇到过这个问题(aterm库只是一个例子)。但我没有找到任何书面形式。即使是我掌握的关于 aterm 的一小部分信息也是听说的。我并不担心它不可靠(你不能编造这个)，但是“个人交流”和“看看它在源代码中是如何完成的”在引用中被认为是糟糕的形式。

我有足够的关于 hash-consing 的引用。我只对干扰编程其他方面的引用感兴趣，例如编码或分发。

Answer 1

好吧，这没什么用，但是 Andrew Kennedy 写了一个函数珍珠，简称为 Pickling Combinator，它出现在 Journal of Functional Programming, (2004), 14:6:727-739 中。对结构共享及其在泡菜中的处理方式进行了广泛的讨论，但没有直接讨论此问题如何与语言实现中的哈希约束相关。但是这篇文章确实讨论了内存和泡菜中的结构共享，所以我希望它总比没有好。

Martin Elsman 于 2005 年在 Trends in Functional Programming 上发表了一篇后续论文；标题是 Type-specialized serialization with sharing。这篇文章主要处理 unpickler(反序列化器)的 hash-consing，而不是实现中的 hash-consing，但它可能还是值得的。

JFP 论文是专有的，但似乎有 preprint on Andrew's web page .
Elsman 的论文似乎可以通过 Google Scholar 获得，网址为 http://tinyurl.com/yd5tw2b .

(在前世，我参与了一个创建人们可以阅读和编辑的 ASCII 泡菜的项目。我愚蠢地未能发布它，但我保留了兴趣。)