小土刀

【计算机系统导论】2.3 信息表示

前面我们介绍了编码和编程语言,但编码只是一种方式,说到具体要被编码的东西,就是这一节要介绍的『信息』了,人们如何看待信息,计算机如何看待信息,在之上我们发展出了怎么样的技术,接下来我们将会一一探讨。


2.3.1 信息的基本单位

信息(英语:Information),是一个严谨的科学术语,其定义不统一,是由它的极端复杂性决定的,获取信息的主要方法为六何法。信息的表现形式数不胜数:声音、图片、温度、体积、颜色……信息的分类也不计其数:电子信息、财经信息、天气信息、生物信息……。
在热力学中,信息是指任何会影响系统的热力学状态的事件。

信息可以减少不确定性。事件的不确定性是以其发生概率来量测,发生概率越高,不确定性越低,事件的不确定性越高,越需要额外的信息减少其不确定性。位元是典型的信息单位,但也可以使用像纳特之类的单位,例如投掷一个公正的硬币,其信息为log2(2/1) = 1 bit,投掷两个公正的硬币,其信息为log2(4/1) = 2 bits。

在信息论中,熵是接收的每条消息中包含的信息的平均量,又被称为信息熵、信源熵、平均自信息量。这里,消息代表来自分布或数据流中的事件、样本或特征。(熵最好理解为不确定性的量度而不是确定性的量度,因为越随机的信源的熵越大。)来自信源的另一个特征是样本的概率分布。这里的想法是,比较不可能发生的事情,当它发生了,会提供更多的信息。由于一些其他的原因(下面会有解释),把信息(熵)定义为概率分布的对数的相反数是有道理的。事件的概率分布和每个事件的信息量构成了一个随机变量,这个随机变量的均值(即期望)就是这个分布产生的信息量的平均值(即熵)。熵的单位通常为比特,但也用Sh、nat、Hart计量,取决于定义用到对数的底。

采用概率分布的对数作为信息的量度的原因是其可加性。例如,投掷一次硬币提供了1 Sh的信息,而掷m次就为m位。更一般地,你需要用log2(n)位来表示一个可以取n个值的变量。

在1948年,克劳德·艾尔伍德·香农将热力学的熵,引入到信息论,因此它又被称为香农熵。

熵的概念最早起源于物理学,用于度量一个热力学系统的无序程度。在信息论里面,熵是对不确定性的测量。但是在信息世界,熵越高,则能传输越多的信息,熵越低,则意味着传输的信息越少。

英语文本数据流的熵比较低,因为英语很容易读懂,也就是说很容易被预测。即便我们不知道下一段英语文字是什么内容,但是我们能很容易地预测,比如,字母e总是比字母z多,或者 qu 字母组合的可能性总是超过q与任何其它字母的组合。如果未经压缩,一段英文文本的每个字母需要8个比特来编码,但是实际上英文文本的熵大概只有4.7比特。

如果压缩是无损的,即通过解压缩可以百分之百地恢复初始的消息内容,那么压缩后的消息携带的信息和未压缩的原始消息是一样的多。而压缩后的消息可以通过较少的比特传递,因此压缩消息的每个比特能携带更多的信息,也就是说压缩信息的熵更加高。熵更高意味着比较难于预测压缩消息携带的信息,原因在于压缩消息里面没有冗余,即每个比特的消息携带了一个比特的信息。香农的信息理论揭示了,任何无损压缩技术不可能让一比特的消息携带超过一比特的信息。消息的熵乘以消息的长度决定了消息可以携带多少信息。

香农的信息理论同时揭示了,任何无损压缩技术不可能缩短任何消息。根据鸽笼原理,如果有一些消息变短,则至少有一条消息变长。在实际使用中,由于我们通常只关注于压缩特定的某一类消息,所以这通常不是问题。例如英语文档和随机文字,数字照片和噪音,都是不同类型的。所以如果一个压缩算法会将某些不太可能出现的,或者非目标类型的消息变得更大,通常是无关紧要的。但是,在我们的日常使用中,如果去压缩已经压缩过的数据,仍会出现问题。例如,将一个已经是FLAC格式的音乐文件压缩为ZIP文件很难使它占用的空间变小。

熵的计算

如果有一枚理想的硬币,其出现正面和反面的机会相等,则抛硬币事件的熵等于其能够达到的最大值。我们无法知道下一个硬币抛掷的结果是什么,因此每一次抛硬币都是不可预测的。因此,使用一枚正常硬币进行若干次抛掷,这个事件的熵是一比特,因为结果不外乎两个——正面或者反面,可以表示为0, 1编码,而且两个结果彼此之间相互独立。若进行n次独立实验,则熵为n,因为可以用长度为n的比特流表示。但是如果一枚硬币的两面完全相同,那个这个系列抛硬币事件的熵等于零,因为结果能被准确预测。现实世界里,我们收集到的数据的熵介于上面两种情况之间。

TODO 补充例子

因此熵实际是对随机变量的比特量和顺次发生概率相乘再总和的数学期望。

熵的特性

因为和热力学中描述热力学熵的玻尔兹曼公式本质相同(仅仅单位不同,一纳特的信息量即相当于k焦耳每开尔文的热力学熵),所以也称为“熵”。

如果两个系统具有同样大的消息量,如一篇用不同文字写的同一文章,由于汉字的信息量较大,中文文章应用的汉字就比英文文章使用的字母要少。所以汉字印刷的文章要比其他应用总体数量少的字母印刷的文章要短。即使一个汉字占用两个字母的空间,汉字印刷的文章也要比英文字母印刷的用纸少。

物理学家和化学家对一个系统自发地从初始状态向前演进过程中,遵循热力学第二定律而发生的熵的变化更感兴趣。在传统热力学中,熵被定义为对系统的宏观测定,并没有涉及概率分布,而概率分布是信息熵的核心定义。

根据Jaynes(1957)的观点,热力学熵可以被视为香农信息理论的一个应用:热力学熵被定义为与要进一步确定系统的微观状态所需要的更多香农信息的量成比例。比如,系统温度的上升提高了系统的热力学熵,这增加了系统可能存在的微观状态的数量,也意味着需要更多的信息来描述对系统的完整状态。

Maxwell在以他的名字命名的思想实验中认为,如果存在一个小妖精知道每个分子的状态信息(热,或者冷),就能够降低系统的热力学熵。Landauer和他的同事则反驳说,让小妖精行使职责本身——即便只是了解和储存每个分子最初的香农信息——就会给系统带来热力学熵的增加,因此总的来说,系统的熵的总量没有减少。这就解决了Maxwell思想实验引发的悖论。Landauer法则能够解释现代计算机在处理大量信息时,必须解决散热问题。

2.3.2 比特的由来

比特(英语:Bit),亦称二进制位,指二进制中的一位,是信息的最小单位。Bit是Binary digit(二进制数位)的缩写,由数学家John Wilder Tukey提出(可能是1946年提出,但有资料称1943年就提出了)。这个术语第一次被正式使用,是在香农著名的论文《通信的数学理论》(A Mathematical Theory of Communication)第1页中。

假设一事件以A或B的方式发生,且A、B发生的概率相等,都为0.5,则一个二进位可用来代表A或B之一。例如:

  • 二进位可以用来表示一个简单的正负
  • 有两种状态的开关(如电灯开关)
  • 晶体管的通断
  • 某根导线上电压的有无
  • 一个抽像的逻辑上的是否

按照热力学与信息论的关系,信息量和热力学熵可以换算。

位模式并没有内在的含义,它们可能表示有符号整数、无符号整数、浮点数和指令等。具体代表什么意思要看指令对该字的哪些位进行操作。计算机数和真实世界里的数的主要不同是计算机数的大小是有限制的,因此限制了其精度;计算的数字有可能太大或太小而无法在一个字中表示。程序员必须记住这些限制并相应地编程。

2.3.3 数据类型

通过比特的各种长度和组合以及人们赋予的意义,产生了不同数据类型:

在程式设计的类型系统中,数据类型(Data type)是用来约束数据的解释。在编程语言中,常见的数据类型包括原始类型(如:整数、浮点数或字元)、多元组、记录单元、代数数据类型、抽象数据类型、参考类型、类以及函式类型。数据类型描述了数值的表示法、解释和结构,并以算法操作,或是物件在内存中的储存区,或者其它储存装置。

所有在电脑中,基于数字电子学的底层数据,都是以比特(0 或 1)表示。其中数据的最小的定址单位,称为字节(通常是八位元,以八个位元为一组)。机器码指令处理的单位,称作字长(至 2007 年止,一般为 32 或 64 位元)大部分对字长的指令解译,主要以二进制为主,如一个 32 位元的字长,可以表示从 0 至 $2^{32}-1$ 的无符号整数值,或者表示从 $-2^{31}$ 至 $2^{31}-1$ 的有符号整数值。由于有了二的补数,机器语言和机器大多不需要区分无符号和有符号数据类型。存在着特殊的算术指令,对字长中的位元使用不同的解释,以此作为浮点数。

每一个数据类型都有一个数值上的最大和最小值,称作数值范围。了解数值的范围是很重要的,尤其是当使用较小的类型时,你就只能储存范围之内的数值。试图储存一个超出其范围的数值,可能会导致编译或执行错误,或者不正确的计算结果(因为被截断)。

一个变量的范围,是基于用以保存数值的字节数目,而且整数数据类型通常能够储存 $2^n$ 数值(此处的 $n$ 是指比特)。对于其它的数据类型(例如,浮点数),其数值范围更为复杂,且几乎取决于所使用的储存方法。还有一些不用完全部的比特,例如,布尔只需一个比特,且表示一个二进制值(虽然在实践中,通常会用完剩余的 7 个比特)。某些编程语言也允许反向决定,程式设计者定义解决问题所需的范围和精度,然后由编译器自动选择合适的整数或浮点数。

2.3.4 类型系统

结合 Go 语言重写

在计算机科学中,类型系统用于定义如何将编程语言中的数值和表达式归类为许多不同的类型,如何操作这些类型,这些类型如何互相作用。类型可以确认一个值或者一组值具有特定的意义和目的(虽然某些类型,如抽象类型和函数类型,在程序运行中,可能不表示为值)。类型系统在各种语言之间有非常大的不同,也许,最主要的差异存在于编译时期的语法,以及运行时期的操作实现方式。

类型系统(type system)是一门编程语言最核心也是最基础的部分。无论该语言基于何种编程范式,都必须在开天辟地之初首先对类型系统作出明确的定义。这是因为,编程语言虽然五花八门,千奇百怪,但是归根结底,编程语言最终的目标,本质上无非是回答两个问题:

  • 如何表示信息;
  • 如何处理信息。

无论是面向过程的编程语言、面向对象的编程语言、函数式编程语言、并行编程语言或者其他任何千奇百怪的编程语言,其根本性的终极目标,就是回答以上两个问题。各种编程语言之所以差异颇大,其实就是对这两个问题给出的答案不同导致的。

在如何表示信息这一问题上,编程语言通常需要定义一些“基本存储单元”,作为整个语言世界的基本构成要素。这种思想很类似于我们对物理世界的认识——宇宙虽然鬼斧神工,丰富多彩,但是在微观上,整个世界仅仅是由少数寥寥几种基本粒子构成的(物理细节不必深究,这里只是打个比方)。但是奇怪的是,基本粒子就只有几种,为何却能构成地球、水、人、树、风这些看似截然不同的东西呢?答案在于,基本粒子虽然不多,但是自然界确立了一套简单而精妙的组合规则,使得基本粒子能够以许多种不同的方式组合在一起,由于组合方式的不同(结构差异),组合规模的不同(数量差异),导致了最终宏观表现的不同。

与现实物理世界类似,一门编程语言就确立了一个独特的“世界”,这个世界可能丰富多彩,千奇百怪。但是就如我们现实世界一样,繁杂的外表之下,骨子里都是由一些“基本粒子”,按照一定的组合方式构成的。那么究竟有哪些基本粒子,又允许进行何种组合,对编程语言所确立的世界最终的宏观结果影响非常巨大。甚至可以说是根本性的。

有一定编程经验的程序员,往往对类型系统不太关心。他们更感兴趣的是语言的其他特性,例如并行计算能力,编程风格,类库等等。这些特性当然非常重要,就生产环境的应用来说,语言特性甚至是处于次要地位的。类库被许多程序员认为比语言本身更重要。然而,坚实的应用是以对语言深刻的理解为基础的,花费一些时间对语言的本质进行研究,会对深入理解语言背后的设计考虑有很大的帮助。也能让我们避免陷入语言的陷阱,或者陷入与别人的口水战之中。

回到对类型系统的考虑,那么究竟什么是类型系统呢?

一门语言定义了一套基本类型的“集合”,这个集合就作为一个整体被称为类型系统。这一称谓中,涉及到两个关键词——“类型”和“系统”。

什么是“类型”?

计算机存储是以二进制方式进行的,并以连续的八个二进制位为一个基本单元——“字节”。从这一点来看,计算机存储是通用的,存储人类的文字或者存储图像、声音或其他别的媒介都没有内在的本质差异。但是奇怪的是,在编程语言概念上,却总是会引入一系列的大相径庭的“基本类型”。例如,int和double,一个存储整数,一个存储浮点数。如果我们考虑一下,就会发现其实int和double本身并没有什么差别,都只不过是若干个字节构成的存储单元而已。那么对他们进行区分意义何在?其实就“存储”概念而言,我们用二进制方式,以字节为单位来实现信息的存储,已经给出了信息表示的“终极答案”了。但是完成存储,只是整个计算机系统功能的一部分。如果仅仅是把信息存储,而不进行计算,那么计算机就不叫计算机,改叫存储机了。可见,问题的实质在于,我们要存储,更要计算。

int和double都是几个字节构成的,但是其运算规则截然不同,差异巨大。同样的,string和int或double也不相同。我们在string上进行拼接、删减、搜索、替换。但是在int上进行加减乘除。这些计算需求和内部实现上的差异,迫使我们的语言层次上进行明显的区分。

上面举的类型,都是来自C家族语言中的概念。但是我们也知道,在一些语言中,不需要我们对类型进行显式的说明。但是不说明不代表不存在。只不过一个是程序员显式声明,一个是编译器(或解释器)自主推导;一个是把责任推给程序员,一个是把责任推给编译器作者。类型系统总是内在的存在的。永远没有被去除。

什么是“系统”?

坦白讲,这是一个非常模糊的概念。我们会说操作系统、消化系统、生态系统……各种各样的系统,然而对于系统本身是什么,在不同的科学领域有截然不同的定义。通常我们所说的系统中,存在一些基本要素(软件模块、细胞、物种等等),然后存在一定的相互作用关系(函数调用、细胞连接、捕食与被捕食等等),在此基础上实现一定的功能(完成金融计算、排解人体毒素、完成有机物的自然循环等等)。那么我们就把这些基本元素,以及其构成方式,统称为一个系统。

之所以说“系统”是个模糊的概念,原因在于,这一概念本身并非原子概念,一个系统,也可能再分解为一系列的子系统,例如操作系统就可以分为输入输出子系统,绘图子系统等等,人体内的消化系统也能够分解为一系列的子系统。而子系统又可在更小的级别进行分解。系统的划分是相对的,系统的构成也是相对的,因此其本身常常是模糊的。

这么说来,如果要追究系统一词的内涵,会很困难。但是在我们讨论的编程语言这一领域内,当提到“类型系统”时,系统其实就是指:

  • 一组基本类型构成的“基本类型集合”;
  • “基本类型集合”上定义的一系列组合、运算、转换方法。

这两点合起来,就成为了我们的“类型系统”。只要做到这两点,就已经非常强大了。这其中,“基本类型集合”是一个非常小的有限集合,也就寥寥几个元素,而“组合、运算、转换”等规则,也是一个较小的有限集合。但是通过选择不同的元素进行组合,这两个有限的集合之上,却衍生出了一个无限集合——“类型空间”。

理解这一点非常关键。因为这恰好符合了我们对自然界构成的认识——有限的若干种基本粒子,有限的若干种基本规则,结果却是无限可能性的巨大世界。

这一简单优雅而惊人的世界构成观,贯穿了人类现实世界和计算机编程语言所定义的虚拟世界。或许语言的设计者也没有料想到,但是最终的结果确实是有限的设计导出了无限的可能性。

所以,当认识到这一点之后。就再也不会轻视类型系统,再也不会把类型系统看得简单,自以为十分了解了。而类型系统设计上的细微差异,最终也会导致截 然不同的类型空间,导致对信息表达方式的巨大差异。那么还有什么理由不认真的研究这一基本要素的呢?还有什么理由让我们逃开这一许多程序员认为“简单”的主题呢?

从类型理论角度出发创造的编程语言有两个特点:需要编译器,必须有系统设计,在系统设计确定好类型即可:Design the type system correctly, and the language will design itself.只要你正确设计系统,语言将会设计自己。

这也是大部分编程语言总是从“类”开始,任何一个对象或值都都属于一个特定的类型,这样才能回避罗素悖论。

可能有人对类型理论如何解决了罗素悖论不是非常清楚,这里打一个不是很恰当比喻解释一下:

包装盒问题,包装盒是一个集合,而产品也是一个集合概念。

我们买的产品都有包装盒,包装盒属于这个产品吗?

要看情况而定,有的属于有的不是,比如茶叶、月饼包装盒属于,而快递用的包装盒,包括超市的购物袋都不属于。

在精确形式逻辑语言中是不能看情况的,因为语言本身已经抽象离开了其指称的实物,是形而上的,那么如何在这个抽象层面保证确定性?

引入类型,如果包装盒属于产品这个集合类型,那么你买到这个产品这个集合时,就包括包装盒这个集合。否则如果包装盒不属于产品集合的类型,如是用于快递运输包装的。

所以,使用类型系统,我们必须首先有一个系统设计,这个设计实际是进行类型边界划分过程,我们通常用类图表达,四色原型和领域驱动都是帮助我们划分不同类型的方法。

物以类聚,类型理论解决了罗素悖论,挽救了数学,催生了计算机科学,奠定了西方科学文明的基石。

用DDD 行话说,物以类聚,就是物以类內聚,內聚是类型边界划分的核心。

类型理论明确规定任何实体必须有类型,这是面向对象OO基础。

面向函数语言则是从另外一个角度来思考问题:函数,函数学派典型代表是lambda calculi,导致了Lisp, ML, 和 Haskell 等语言,正如面向对象学派呼唤每个都是对象,他们认为everything is a function;每个都是函数。

侧重过程或侧重结果是计算机世界中两种不同的思维角度,就像有的人侧重过程,而有的人看重结果一样,这两样是无法取舍的,都是必须的,阴阳一体而已。

回到这个类型(Type)系统和函数系统lambda calculi,很显然,这两种视角也是一种侧重过程和侧重结果的思维,如果你看着结果数值,那么一定要给它类型;如果你看中计算过程函数,那么也一定要给他套上类型,否则全部都违反罗素悖论。

lambda calculi套上类型系统称为:Church’s Type Theory

有了以上宏观中立出发点,当我去理解Lambda Calculi时,就比较好理解,比如God Math/Bad Math这篇文章谈到,everything is a function; there are no values at all except for functions,一切都是函数,除了函数以外什么都没有,没有值(我前面提到侧重结果),在侧重函数的世界里,是排他的,否则它不能成为一个阴(或阳)。

在SICP这本书中,作者也写到过类似的观点,在第三章的末尾
We began this chapter with the goal of building computational models whose structure matches our
perception of the real world we are trying to model. We can model the world as a collection of separate, time-bound, interacting objects with state, or we can model the world as a single, timeless, stateless unity.

Each view has powerful advantages, but neither view alone is completely satisfactory. A grand unification has yet to emerge.

译文:本章开始时提出了一个目标,构造出一些计算模型,使其结构能够符合我们对于试图去模拟的真实世界的看法,我们可以将这个世界模拟为相互分离,受时间约束具有状态的相互交流的对象,或者模拟成单一的,无时间无状态的统一体,每种观点都有强有力的优势,但是就其自身而言,又没有一种方式能够完全令人满意,我们还在等待一个大一统计算理论的诞生

捧个钱场?

热评文章