银弹的数学解释

前几个礼拜找资料的时候,偶尔翻到了Library-Centric Software Design LCSD'05的几篇paper.
其中有一篇<Libraries and their Reuse:Entropy, Kolmogorov complexity,and Zipf’s Law>。非常有趣，从一个独特的视角来考量软件重用性.就此翻译出来,其中有若干删节,为了更显标题党，主标题也是我自己添加的。此帖更新速度为日更,已经大致译完不会太监.若心急的可以自己去看英文,相关联接上还有一个ppt slides可帮助理解。




银弹的数学解释    
库与重用性——熵,柯模哥罗夫复杂性与齐普夫定律

Todd L. Veldhuizen

开放系统实验室

印地安纳大学伯明顿分校.

摘要
本文从信息论,柯莫哥罗夫复杂性的角度来分析软件的重用性,探究通过重用软件库中的组件来”压缩”程序的能力。软件业的主流观点认为:如果我们能营造恰当的正确的环境——正确的工具,正确的抽象,足够的经济支持,以及”某种重用文化”——那么软件模块的重用程度是无可限量的，它势必会极大地提高软件的生产率和质量。而本文将会通过分析为我们描绘出另外一幅图景：软件重用适用范围取决于特定问题域(problem domain)的内在禀性。如果问题域本身存在重用阻抗,那么各种编码利器、优良的软件文化只能在边际上影响软件模块的重用率.本文定义一种在问题域上度量的程序的差异性的参数——熵 ,并由此推导出该参数在代码重用和组件伸缩尺度的上界值.对于”低熵”的问题域H接近于0,程序之间高度相似.这种问题域非常接近于组件式软件工程(Component based software Engineering CBSE)的梦想——通过组装大尺度的组件来进行编程.对于那些熵接近于1的问题域,程序需要编写大量的新代码,只能在适当的比例内采用可重用的小尺度组件.我们的模型得到了来自Unix平台的实验数据的初步支持.
综述
软件重用给予了我们一种希望:我们可以通过系统地重用设计良好的组件来编写软件。实践也的确证明了重用性可以提高生产力、降低软件缺陷 [3, 12, 15, 22, 23]. 不过软件重用的局限性在哪里?——大尺度的重用会让软件开发更容易吗?这个问题众说纷纭，但是我们可以将这些争论归为两种互相针对的假设.第一种是这个领域内的一个极端,我将之归为组件式软件工程的观点.(CBSE,Component-Based Software Engineering)

假设1(强重用).

这种观点认为大尺度的重用可以通过组装大颗粒的预制组件来使得超大规模的软件生产成为可能。编程的所有活动可以归结为从软件库中选择恰当的组件,然后把它们装配起来。
人们认为当问题域的工作量高度集中,目的极为类似, 比如,当许多人编写需求大同小异的软件时,强重用很有用.但问题在于，强重用是否能在跨学科跨组织的软件开发中普遍适用?这一点仍然是不确定的。比强重用更为谨慎的观点是弱重用.
假设2(弱重用)

这种观点认为,大尺度的重用的确会非常有效地降低软件实现的工作量,但是这种方法节省的只是那些大规模工程的某一个片段.对于那些非常规的工程来说,我们总要创造一定量的、无法在现有组件库中找到的新代码。
弱重用思想的一个典型的代表就是,Jeffrey Poulin[23]对设计良好的软件中的代码重用问题的看法：超过85%的代码应该从库中重用,另外15%的代码都是为特殊应用定制的代码几乎没有什么重用的潜力.这种百分比,在不同的领域中有着巨大的差异,不过弱重用思想为当今软件工程描绘了一个大致准确的图景。很多人试图去阐明为何强重用不具有普适性(cf.[9]).但是无论这两种观点之间有什么样的差异,软件重用领域中存在着一种普遍认同的观点: 如果我们能营造恰当的正确的环境——正确的工具,正确的抽象,足够的经济支持,以及塑造”某种重用文化”——那么软件模块的重用程度是无可限量的，它势必会极大地提高软件的生产率和质量。

一种相反的观点。

本文所阐述的观点认为，软件重用适用范围取决于特定问题域(problem domain)的内在禀性。如果问题域本身存在重用阻抗,那么各种编码利器、优良的软件文化只能在边际上影响软件模块的重用率。我们为问题域赋予一个熵参数H(entropy parameter)  ，用它来度量问题域本身的多样性.当H为1时,软件是极度多样化的,期望从中获得重用性是几乎不可能的;实际上,我们可以看到对于大型工程来说我们直接从库中引用组件的比例趋向于0.对于那些H<1的问题域,软件在某种程度上具有一定的同质性，随着H的减小重用的可能性就逐渐增大。我们所构建的这个理论认为,对于一个应用来说,从库中可以获得重用的代码比例最多只有1-H,剩下的代码是为特殊应用编写的定制代码.当H趋向于0,我们就逐渐趋向于理想中强重用的形态——“通过组装大尺度的组件来编程”。重用的可能性的严格的受限于参数H，它是某个问题域的内在禀性。

我们构建这个理论时,将重用性看作是利用库来压缩或者归并软件的能力。“压缩后程序”这样的术语可能贯穿全文。所谓的压缩后程序是指采用库来编写的程序,“未压缩程序”是指那些没有引用过任何库组件的版本。对此我们将引入信息论(information theory)和柯莫哥罗夫复杂性(Kolmogorove complexity).在描述后文所涉及的可压缩性时,这两者之间有一些细微的差别.信息论主要侧重于分析出现频率的模式并且给出他们的最短表述——比如英语里我们用”car”来替代”automobile carriage“。而柯莫哥罗夫复杂性则着重于描述我们针对某一个特定的程序,如何找到一个具有相同行为最短表述的能力,而不考虑这个程序应该是什么。我们假定读者对信息论有一定的基础知识(相关资料可以在[7,Ch2]或[19]中找到)。对于柯莫哥罗夫复杂性,我们会在第三节回顾一下基本定理.

库组件与素数。

整数可以分解为若干素数的乘积;软件可以看作是一系列组件的拼装.库组件事软件的素数.如果否认他们之间的这些高度相似性,是一件极为短视的做法:

。素数有无穷多个；而在5.2.1中我们会证明对于某个特定的问题域需要无穷多个组件来把程序降低到指定的尺寸(由此可见库编写者不愁没工作)

。第n个素数是整数   的因子。而本文将指出第n个最为频繁使用的库组件的理想重用率为

  (Section 4.2)

。厄多斯-卡茨定理(Erdos-Kac theorem) 指出一个整数的因子数目趋向于一个正态分布.我们测量实验数据暗示存在一个极为类似的定理(图4),该定理应该是可被证明的。

。素数定理指出第n个素数长度是bit.我们认为理想化的库配置是,第n个最频繁使用的组件尺寸应该在 与 之间

图1:从若干个Unix平台上收集的共享对象的数据。它显示了库组件的引用次数.很显然引用次数与齐普夫频率定律的  结果(带点对角斜线)极为吻合。在第六节中我们会具体的解释这一数据。

重用和齐普夫定律。我们知道硬件指令频率遵从一个经典的曲线，该曲线是George K.Zipf是在研究自然语言中的单词使用频率时所提出的[16,18,27].齐普夫指出,如果在一个自然语言中根据使用频率来排序的话,第n个单词的频率是 .齐普夫经验曲线在许多场合都会遇到.证据显示编程语言的结构也遵从齐普夫定律[5,17].那么将其扩展到库组件上也是很自然的。我们的结果支持这个结论.图1展示了三个Unix平台上的共享对象中子过程的使用次数,显然它是类齐普夫的 曲线。这个结果会在第6节有详细的描述.这个曲线的出现不是偶然的.在4.2节中我们会看到它是程序员们试图通过库重用来尽可能地编写简短代码的直接结果.同时它也使得重用率趋向于”最大熵”，也即齐普夫定律曲线。

2 库重用建模
在本节中我们旨在抽象出一个软件重用的模型,使得的它能在特定的问题域中反映出软件重用的本质特性.最基本的场景是这样的,我们把所能收集到的所有可能的库看成是一个库,它含有大量的软件组件.这些组件可能是子过程,框架,设计模式,泛型,组件生成器，或者其它我们可能发明的抽象工具.这些抽象工具的具体特性我们并不关心。从库中使用一个组件，我们可以达到缩减程序尺寸的效果,可能最终我们会以此为目标来实现软件。程序尺寸可以作为一个粗糙的下界,但是可能存在一个模糊两者的巨大的误差。
2.1问题域中的程序分布
我们假定我们可以将程序员在某个问题域上的程序模型化为一个关于程序集的概率分布。我们可以把这个概率分布定义在”未压缩”程序集上,也就是那些没有使用任何库的组件的程序.我们将这些未压缩得程序视为程序员着手实现的出发点.我们可以将编译过的程序集模型化为一个二进制字符串集{0,1}。我们采用  来表示其中某一个字符串的w的长度.有限长的程序的数目可能是无限可数的(countably infinite)，因此我们会马上面对一个定义概率分布的问题。在这种概率分布中单个程序的概率可能是无穷多个。严格的来说我们应该采用测度论来描述它比如Loeb测度, 测度论允许我们讨论独立的程序集上的概率。但是这种方法会增加我们讨论的复杂性，因此我们采取一种更为人接受的方法,这种类似的方法在文献[4,6,25]有所提及.

令  表示编译后长度至多为n bits的的程序集合。我们引入一族条件分布  它的定义域由长度为  bits的程序所组成子集,值域则是对应程序子集在整个集合中出现的概率即  ，且满足 以及  。  给出了在某个特定的问题域上实现未压缩程序的概率,  代码长度至多为  bits。要使得这一族分布之间可以互相定义,我们可以定义 

 例如我们可以在长度为 分布上加上一个条件概率来的得到长度为 的概率分布.我们不能假定这样的分布可以被有效地描述出来。

下面的章节里我们会经常用到一个假定 的期望.例如，若是一个将程序集映射到实数集的函数,那么如果下列极限存在的话，期望E与该极限等价 

2.2 熵参数H
问题域的一个关键特性是程序员编写的程序具有相似性.我们不会认为某一问题域中的程序分布会均匀分布在所有可能出现的功能上,与此相反我们认为分布会集中于那些解决特定类型的问题特别是与问题域有关的问题。我们通过引入一个参数H将这种直觉经验形式化。我们通过这个参数来度量在某个问题域上概率分布偏离均匀分布的程度。如果我们程序
假定程序的满足静态随机过程,那么H的行为与信息论中的熵极为相似。当H=1时程序分布为均匀分布,表示软件呈现极端的多样性，重用的机会非常小.对于H<1情况则有一定的重用潜力.实际上只要我们加简单地思考一下,就会发现可以从库中重用的程序比例最多只有1-H。
我们通过标准方法来定义分布  的熵(参见[7,19]):

 
 
它表示了在特定问题域上要表示长度  的程序,其比特数的期望值。不过我们真正感兴趣的是  的极限行为，因为它和随机过程的熵率非常类似.广义上来讲这个极限可能不存在——它非常可能是发散的——因此我们寻求一个较弱的结果，选择了limsup即极限的近似上界.

定义1(熵参数) 将问题域的熵参数定义为当  时的最大值:

 
作为这个定义的一个结果,当  时我们几乎可以保证  。

除了在某些试验性的场景之外，我们不能期望从这个定义中直接计算出H值,不过我们通过经验作出估计还是有可能的.我们引入H参数主要是做为一种理论工具来对那些具有大量相似特性的问题域  或者发散特性的问题域  进行建模型.H的主要用途有如下几点。

断言2.1 在一个熵参数为H的问题域内,通过库组件重用的代码期望比例最多只有1-H

这个结论来自于信息论中的无噪声编码定理(Noiseless Coding Theorem 即香农定理[1,$25]).
它表明对于带有熵H的随机数据进行编码,至少需要(平均来说)需要H比特。假定一个未压缩程序的大小为  ,如果我们定义H使得我们几乎总是能够保证  ，那么我们可以将这个程序压缩到一个期望长度，根据无噪声编码定理最好的结果为  。因此通过使用库来节省的代码长度最多只有(1-H)S.因此我们立刻可以看出来那些随意开出的可重用药方诸如:”高效的团队可以从库组件中重用70%的代码”都是不切实际的。重用的目标必须与问题域的熵值H挂钩。

图(2)描绘本文所考虑的场景:程序员首先去实现一个不使用任何库的长度为s的无压缩程序，从中取得针对问题域的程序分布. 然后使用库来实现它以便高效的压缩程序.压缩后的期望长度至少为Hs 比特。这个库有一批组件组成,每一个组件带有一个引用他们时使用的标记或者码字(codeword)。我们总是将程序进行编译,因此不用关心高度压缩的源代码是什么样子。


 

图2:基本场景:程序员在一个问题域中着手实现一个程序，其长度在不使用库编译后为s。通过使用库组建,他们能够将编后的代码尺寸降低到一个期望长度 
bits。
 

2.2.1 基元(motifs)与渐进等分性(AEP)
我们可能会问这样的问题,当H<1时程序集中是否一定存在共同的模式(pattern)或者基元(motifs)，使得我们可以将它们抽象到类库里通过重用的方式来压缩程序呢?如果我们愿意假定某一问题域上的程序行为类似于一个稳态遍历信号源的话,那么Shannon-McMillan-Breiman定理(Asymptotic equipartition property 或者称AEP)[7,15.7] 可以保证当H<1时,程序中的一定存在具有相同模式可剥离的有限子序列,我们的确可以达到最优的程序压缩效果。实践证明显示，对于更为复杂的软件组件，稳态遍历信号源的假定似乎太强了。当H<1时在要软件中出现基元可能需要一个更弱的遍历特性.这种特性会是什么目前还尚未明了;在剩余的章节中我们也不会假定渐进等分性AEP的存在。

                                                                 2.3 库的熵最大化
一个真正的计算机程序员都是懒惰,没耐心，狂妄自大的.懒惰驱使着他们努力工作去避免为在未来重复的自己工作——Larry Wall
程序员，正如我们见到的，是懒惰的——他们通过编写库来捕捉普遍发生模式抽象让他们不需要一遍一遍地重复编写相同代码。这种驱使程序员们去开发库的社会活动有着一些有趣的理论效应.我们可以将程序员开发领域专用库的活动看成是在一个问题域上不断地压缩程序的过程。如果存在一个通用的模式，那么最终肯定会有人识别出它将它们加入一个库.当代码中缺乏共同模式时也就意味着代码的具有极高的熵，为此我们提出了下面几条原则。
原则1(熵最大化).程序员开发领域专用库的行为实际上是将问题域中的频繁重复代码的出现次数最小化.也就意味着使用库的编写的代码在编译后具有最大的熵.
我们在第6节中展示了这个原则的一个旁证:从经验上来看，库组件的重用率接近于一个熵最大的格局。
在实践中程序员必须在程序的简洁性与可读性之间艰难的取舍；文献[11]中就有一段关于这个问题的精辟探讨。不过,我们持续寻求简洁性与提取公共模式的驱动力来自于软件库开发的内在压力:熵本质上是通讯效率的一种度量，程序员在维持代码可读性的同时尽力使得熵最大化。
                                                                 2.4 柏拉图库
在软件库发展的早期，一个软件库最多也就是几百个子过程。而今日对于计算机来说为了重用存储几百万个子过程是非常普通的事情。让我们假设随着历史向前发展，当我们发现有用的算法和抽象时，我们会不断地向我们的软件库内加入组件。我们当前的软件库可以被看作是某一个我们正在不断逼近的无穷(但是可数)组件库的缩减版本。正如厄多斯那本数学的上帝之书一样，某一个问题域上库的上限可以看成是某个无穷无尽的柏拉图库,我们现在发现的仅仅是这个库的某一个更大的片断而已。如果我们有可能接触到这个组建库，那么我们就可以用一种非常高效的方法来编写程序.我们把柏拉图库当做一个策略——一个虚构故事—来说明有限的库是如何有效。
我们需要小心地对待无穷对象.我们即不应该假定存在最优的无穷库，也不应该假定这种无穷库具有有限的表述或者是计算可枚举的。我们仅仅假设随着时间的流逝,柏拉图库的某些片断应该会出现在我们的软件库中。
                                                                 2.5 重用率的存在性
度量可重用性可以有许多方式。我们这里主要关注一个组件的重用率(reuse rate).重用率记为，它表示在一个已压缩程序中第n个库组件应用的预期率。
的单位是编译后代码每Bit中的引用数。在下文中，我们假定在一个问题域中平均重用率是存在的。
假设1. 令 为一个长度 已压缩程序中第n个库组件的引用总数。
我们假设


 
其中o(s)表示一个比s小的渐进误差项。
很不幸的是,我们没有什么好的方法可以从某个问题域上的未压缩程序的随机分布  计算出压缩后的组件重用率。这与2.2节中提到的遍历过程问题极为相关。我们通过假定平均利用率的存在来暂且回避这一问题。这不是一个严格的假定。许多恰当的随机过程模型都可以推导出假设1，比如将组件抽象为更新随机过程(renewal process 参看[26,$3])
2.6库组件的顺序性
为了方便起见,我们应该将库组件按照问题域中的期望重用率，由高到低排列。


 
这么做有两个原因。首先这样排列比较整齐，当我们将 和n对应起来就会看到一个单调函数而不是随机噪声。我们在  上推导出的渐进极限并不依赖于这种顺序。第二，为了推导出更好的程序压缩方式，我们需要用一个最短的 identifier 去描述使用的最频繁的组件。如果我们将柏拉图库按照使用频率来排序的，那么这个结果也是很自然的。