从机器语言到高级语言的原理

一、前言
每个编程语言都存在变量类型和类型之间的转换问题,一般很多书籍都提供了类型之间怎样进行转换的知识,但是很少介绍这些类型转换的背后原理。有人会问,我只要知道怎样进行转换这些类型就可以了,有必要了解这些知识么?我的觉得还是很有必要了解,只有了解了这些类型转换的原理,我们在编程时才能避免一些坑。例如:



float sum_element(float a[], unsigned length){
int i;
float result = 0;
for(i = 0; i <= length -1; i++){
result += a[i];
}
return result;
}
以上代码看着好像是没问题,但是隐藏着一个很大的bug,这个问题就是因为类型转换导致的。在这里我们先买个关子,具体会出现什么问题?为什么会出现这个问题?我们先介绍本文主要内容后再回答这些问题。



二、整数的表示形式
首先介绍计算机中的整型是如何表示的,了解整数在计算机中的表示才能知道整数的转化原理。整数在计算的表示方式有:补码、反码还有原码。目前大部分计算机都采用补码来表示整数。整数分为有符号和无符号,这两种方式在计算机里的表示不同。



1.无符号整数
这种形式不包含负数,只表示0和正整数。采用补码表示时,其实就是将数字转化为对应的二进制表示。
例如:12345对应的补码表示是:00 00 30 39(16进制)。
无符号的补码编码形式:
\(B2U_w(x) = \sum_{i=0}^{w-2}x_{i}2^{i}\)



如果要将二进制转换为10进制数,就按照上面的式子计算。
例如$B2U_4([0001]) = 02^3+02^2 + 02^1 + 12^0$



2.有符号表示
补码使用最高位表示符号,1表示整数,0表示负数。因此正负数各占一半,因为0是非负数(正整数),因此负数的范围会比正整数的范围大。例如c语言中int的取值范围是$-2^7$ ~$2^7-1$。
有符号的补码编码形式如下:
\(B2T_w(x) = -x_{w-1}2^{w-1}+\sum_{i=0}^{w-2}x_{i}2^{i}\)



同样二进制数转换为10进制数则采用以上公式计算。
在c语言标准中并没有要求用补码形式来表示有符号的整数,但几乎所有的机器都这么做了。而java的标准非常明确要求使用补码表示。




  1. 有符号和无符号整数之间的转换内幕
    在C语言中处理同样字长的有符号数和无符号数字之间相互转化的规则是:保持位值不变,只是改变了解释这些位的方式,因此可能得到不同的数值。例如:



short int sv = -12345;
unsigned short uv = (unsigned short) sv;
show_short(sv); //显示二进制
show_unshort(uv); //显示二进制
其输出结果如下:



[zjl@ ~/workplace/]$ ./show_bytes
cf c7
cf c7
从结果可以看出sv 和uv表示的二进制是一样的,但是具体的值会发生变化。
C语言中有符号数字与无符号数值进行计算时,首先将有符号数值转化为无符号数值,然后运算。这种方式对于标准的运算方式来说并无差异,但是如果是逻辑关系运算符时,就会出现问题。



例如:



-1 < 0
-1 < 0u
以上两个例子中输出的结果并不是都为真。 -1 < 0 因为两个都是有符号数据,直接比较。而-1 < 0u, 因为后面的值是无符号类型,因此将1转换为无符号类型。此刻1变为了2147483647U, 故出现了-1 > 0U的现象。java中不存在无符号整型类型,因此也不存在以上问题。




  1. 短字长类型与长字长类型之间的转换
    1)短类型转化为长类型
    对于无符号的转化为一个更大的数据类型,只要简单的在原来二进制值前添加0则可,这种运算叫做零扩散。
    例如:



unsigned short int v = 1; //二进制为 00 01
unsigned int iv = vl; //二进制变为 00 00 00 01
对于有符号数值,将一补码转换为一个更大数值类型可以执行符号拓展,在补码之前补充最高位值得副本,即将$[x_{w-1},x_{w-2},…,x_0]$转换为$[x_{w-1},x_{w-1},…,x_{w-1},x_{w-2},…,x_0]$.
例如:



short sx = -12345; // cf c7
int x = sx; // ff ff c7 值为:53191
如果是负数,前面补充1,根据补码编码计算公式,最后得到的值不变。举个例子:比如将3位数变为4位数,位向量[101]的值为-4 + 1 = 3。对它进行符号拓展,得到位向量为[1101], 表示的值为-8 + 4 + 1 = -3。(具体证明公式感兴趣的可以参考《深入理解计算机系统》P49)同样如果是整数,补充0,最后的结果也是不变。



2) 长类型转化为短类型
长类型转换为短类型则采用截断方式,即根据短类型长度从长类型中截取最低位部分。$[x_{w-1},x_{w-2},…,x_0]$转为为k位的数字类型,变为$[x_{k-1},x_{k-2},…,x_0]$
例如:



int i = -12345; // ff ff cf c7
short i = (short) i; // 值为-12345, 补码:cf c7
三.揭开谜底
知道了c语言的转换原理以后,我们再回头看看文章开头提出的问题。



float sum_element(float a[], unsigned int length){
int i;
float result = 0;
for(i = 0; i <= length -1; i++){
result += a[i];
}
return result;
}
当length = 0 作为输入时,这段代码存在两个问题:



如果a数组长度有限,则出现数组下标越界问题。
length 是一个unsigned类型,即无符号类型。此刻length -1 的值会变为UMax, 所以此刻会进入到循环中。因为最大值为UMax,则for循环会不断迭代。如果数组长度有限就会出现数组下标越界问题。
如果a数组长度非常大,则出现系统异常。
因为length是无符号数字,而int是符号数字,length的取值范围比i大。因此当i达到int类型的最大值时还是小于length-1。i 会继续加1,最大值加1后就变为了负数最小值-214783648。此刻访问未知地址,可能会导致系统异常。

计算机语言是人与计算机进行交流的工具,是用来书写计算机程序的工具。



可以通俗地理解为,你用用特定的语言与特定的对象(特定操作系统与CPU的计算机)沟通,关键是需要有个翻译,这个翻译就是编译器或解释器,同样的语言,针对不同的对象(特定的CPU和操作系统)需要有不同的编译器或解释器。所以说编程语言是“设计”出来的,设计只需要思考和写文档,而该语言的编译器或解释器才是“开发”出来的。



(编译原理讲到了“自举编译器”。大意就是先用底层语言(应该是汇编)写一个能运行,但效率极低的C语言编译器(底层语言不好优化),有了C语言的编译器以后,就可以用C语言好好写一个编译器了,用之前那个运行没问题,但效率低得编译器编译一下,就得到了可以使用的编译器了。)



编译器也是程序,所以也需要用编程语言来编写,很多编程语言是用别的更基础的语言开发的,其中用最多的就是C语言。C语言编译器很多,大部分都是用别的C语言编译器编译出来的,而最早的C语言编译器是用汇编语言写出来的,最早的汇编语言编译器是通过“编译器自举”开发出来的。



从最基本的角度看,一种编程语言就是把一组特定的词汇,按照一组特定的语法规则组合到一起,形成计算机可以通过某种方式“理解”的东西,可以让计算机据此执行特定的动作。



首先要决定你想设计的语言应该解决什么问题。面对不同的领域、不同的需求、不同的抽象层级、不同的思考范式,也就产生了各有特长的编程语言。专注于高效、便捷地解决某特定范畴之内问题的语言,叫做领域专用语言(Domain Specific Language,DSL),而可以跨越若干领域解决问题的语言,叫做泛用语言(General-Purpose Language,GPL)。常见的 DSL 比如 MATLAB、SQL 等等;常见的 GPL 如汇编、C、Python。当然,两类语言之间的分界并不是很明显,有些语言一开始是作为 DSL 设计的,后来渐渐朝着 GPL 的方向发展,比如 PHP 和 JavaScript;反过来也有大量基于 GPL 开发而来的 DSL。



先看看这件事情的最底层。所谓“计算机执行动作”,其实只是“把一个二进制数字传入 CPU,然后等待什么事情发生”的形而上描述。二进制计算机所能理解的唯一东西就是二进制数字,称为“机器码”。比如:



10110 000 01100001



这串数字,对于某颗 CPU 来说,就是“把 01100001 放到 000 号寄存器里”的指令,其中“10110”的部分,就是 CPU 能懂得的“放入”指令。这样的指还有许许多多,比如做加法、求逻辑“与”,跳转,加密等等,全都只是一些二进制数字而已。



对人类来说,这种纯数字的写法太难记忆,就把它转写成:



MOV AL, 97



其中 MOV 代表“10110”,AL 代表 000 号寄存器,97 则是二进制数 01100001 的十进制表示。其他的数字指令也一并用这种简记法来转写。使用这样的一种转写方法来写程序,就是汇编语言(当然,这是一种极度简化的说法)。汇编语言谈不上太多设计,其实几乎就是在直接告诉 CPU 应该做什么。把汇编语言转化为机器码的程序,称为“汇编器(Assembler)“。



汇编语言的优势是很低级,你能直接控制 CPU 的行为;汇编语言的缺点也是它太低级,你必须直接控制 CPU 的行为。看看“把 A 的值放进甲寄存器;B 的值放进乙寄存器;把乙寄存器的值放进 A;把甲寄存器的值放进 B。”这段汇编指令执行后是什么结果?运行一下之后会看到,A 和 B 的值互换了。那么,能不能直接写“交换变量 A 和 B 的值”,然后由计算机来分解为一串机器码的组合呢?



所谓的“高级”编程语言就是这样的原理。将高级编程语言翻译成机器码(或者其他更接近机器码的形式)的过程,也就是计算机“理解”语言的过程,叫做“编译”,而完成这一工作的程序,叫做“编译器(compiler)”或者“解释器(interpreter)”,两者的区别是,编译器一次性解析所有代码并转换成机器码(但通常不会运行),而解释器则每解析一小部分就运行一小部分。



接下来就要考虑两个问题:高级语言要让人写起来方便;也要让计算机易懂。因为人类是难搞的物种,所以前者通常是语言设计的重点。毕竟,只要懂些编程的基本知识,任何人都可以在三天时间里设计出一门计算机语言,并且让计算机读懂它(也就是写出编译器),但要让一种计算机语言写起来舒服、读起来易懂、管理起来方便,所需耗费的心力和时间则相去不可以道里计。探寻这一问题的种种思潮所引发的范式转换和生产力革命,是计算机历史的永恒主题之一。计算机语言越来越高级,使用起来越来越简单,实现却越来越复杂;许多编程观念比如面向对象(object orientation)、函数编程(functional programming)、事件驱动(event driven)之诞生、沉寂、重现、兴盛和定型,都经由编程语言有所体现。



当然这并不是说编译部分就不重要。可靠、高效、灵活的编译器是一切编程工作的基石。我们日常所用的编译器都是如此千锤百炼的东西,以至于你很少会意识到它们本身也是复杂的软件工程项目,也有可能出问题,也在不断地发展着。十年前和现在的编译器,从架构理念到实现都有不小的差别。好在这种差别算不上天翻地覆,计算机语言编译的大致过程一直都是如下几个步骤:



高级语言的源代码经过词法分析(lexical analysis)成为一堆符记(token);



符记经过句法分析(syntactic analysis)成为语法树(abstract syntax tree, AST);



语法树经过优化,比如去除冗余的部分,最后映射成为机器码(machine code);



第一步,词法分析,根据的是语言设计者所规定的词汇规则。比如 PHP 规定变量前头必须加个 $ 符号,就是这样的规则。通常通过正则表达式(regular expression)给出这些规则。根据规则来分析源代码的编译器组件叫做词法分析器(lexer)或者扫描器(scanner)。扫描器可以自己手写,也可以让叫做 scanner generator 的程序读取一个正则表达式,然后帮你生成一个 scanner。词法分析的目的是判断人类写下的每个词是不是合乎拼写规则,如果不符的话,显然也就无法编译了。



第二步,句法分析,根据的是语言设计者所规定的语法规则。关于形式语言的语法理论,涉及到语言学和数理逻辑,是一个复杂而艰深的领域,好在对于设计一门计算机语言来说,只需要知道,计算机语言的语法通常是上下文无关文法(context-free grammar)即可:生成一条计算机语句的规则与这一规则所处的环境无关。这样一来,解析一条编程语句的过程就是确定的无二的。根据规则来将上一步骤获得的词汇解析为特定的数据结构——比如语法树——的工具,叫做句法分析器(parser)。同样,句法分析器可以自己写,也可以用特定的方法(最常见的是巴克斯范式(BNF))给出下上下文无关文法的形式语言描述,然后用所谓 parser generator 来生成。可以说,语法树(或者类似的中间产物)代表了从编程语句中提炼出来的意义,这是整个编译过程的核心所在。



第三步,语法树或者其他的语义表示方法经由优化器(optimizer)的修剪,送入负责将特定结构转化为目标机器代码的程序生成可以运行的二进制程序。这一步必须考虑执行效率优化和目标架构的特点,与高级编程语言本身已经并无太大关联了。



至此便可以开始设计编程语言了。



简单来说,定义一门语言,有点像定义一个宇宙。一开始,宇宙空空如也。为了让这个宇宙能够开始运转,并衍生出超越我们想象的复杂世界,我们作为“造物主”,需要准备好两种东西:一是元素——就是提供一些基本的数据类型;二是规则——基本元素之间的运算法则。



以上两种东西合起来,就是这门语言的“类型系统”。数学一点而言,就是定义一个基本集合,并定义在这个集合之上的运算。



这看起来没什么了不起。常常被人们忽略,但事实上,我们复杂的世界本质上也不过是由一些简单的基本单元基于一些基本规则运动的结果。语言设计也遵循这一原则。



可以说,类型系统是一门语言的核心。因为一门编程语言,本质而言,主要做两件事情:一是描述信息;二是处理信息。



描述信息需要使用存储空间,而处理信息需要使用运算。问题是运算本身对存储空间会进行特别的解释和假设,这就导致了我们的存储空间尽管都是字节或之类的看起来别无二致的通用的空间,但从语言角度来看必须对这些空间进行特别的限定和理解,于是便产生了”类型“的概念。



例如C语言有double和long,本质而言两种类型都是使用字节进行存储。但由于运算时采取完全不同的解释(甚至会采用cpu内部不同的运算器件),因此有必要对他们进行区分。



除了基本的类型系统之外,语言还需要有一些流程控制机制。和代码组织机制。这些都需要设计。可以借鉴现有的编程语言,也可以创造独一无二的新方式。随你自由。



至于对象、变量什么的,其实之前设计类型系统的时候就已经涵盖了。函数之类的在类型系统中也会涉及,同时也会影响代码组织机制等等。



大家知道世界上最早的编程语言是什么吗?一般认为是1954年开始开发的FORTRAN语言。



然后,仔细想想看,到底什么才是编程语言?如果将对机器的控制也看成是编写“程序”的话,那么编程的起源便可以追溯到杰卡德织机上面所使用的打孔纸带。



1801年,正值工业期间,杰卡德织机的发明使得提花编织的图案可以通过“程序”来自动完成。从前在各个家庭中出现了自动纺织机,用于家庭作坊式的自动纺织生产,而杰卡德织机则相当于是这些家庭纺织机的放大版。我想那些自动纺织机应该也可以通过类似打孔纸带的东西来输入图案,当然,最近的年轻人恐怕没有亲眼见过纺织机吧。



这种用打孔机来控制机器的想法,对各个领域都产生了影响。例如在英国从事通用计算机研发的查尔斯·巴贝奇,就在自制的“分析机”上用打孔纸带来控制程序,遗憾的是,由于资金和其他一些问题,巴贝奇在生前未能将他的分析机制造出来。



不过,分析机的设计已经完成,用于分析机的程序也作为文档保留了下来。协助开发这些程序的,是英国诗人拜伦之女爱达·洛夫莱斯,据说她和巴贝奇是师兄妹关系。如果不算分析机的设计者巴贝——那么世界上第一位程序员实际上是一位女性。为了纪念她,还有一种编程语言是以她的名字Ada命名。



在被称为世界上第一台计算机的ENIAC(1946年)中,程序不是用打孔纸带,而是通过接电线的方式来输入,让人总觉得这是一种退步。



不过,无论是打孔纸带,还是接电线,都不太可能实现太复杂的程序,真正的程序恐怕还要等到存储程序式计算机出现以后。一般认为,世界上第一台存储程序式电子计算机,是1949年出现的EDSAC。



到了这个时候,所谓的“机器语言”就算正式问世了。当时的计算机程序都是用机器语言来缩写的。那个时候不要说是编译器,连汇编器都没有发明出来呢,因此使用机器语言也就是理所当然的事情了。



说到底,机器语言就是一连串数字,将计算的步骤从指令表中查出对应的机器语言编码,再人工写成数列,这个工作可不容易。或者说,以前的人虽然没有意识到,但从我们现代人的角度来看,这种辛苦简直是难以置信。比如说,把引导程序的机器语言数列整个背下来,每次启动的时候手动输入进去;将机器语言指令表全部背下来,不用在纸上打草稿就能直接输入机器语言指令并正确运行--“古代”的程序员们留下了无数的光辉事迹(或者是传说),那时候的人们真是太伟大了。



然而有一天,有一个人忽然想到,查表这种工作本来应该是计算机最擅长的,那到让计算机自己做不做好了吗?于是,人们用更加容易记忆的指令(助记符)来代替数值,并开发了一种能够自动生成机器语言的程序,这就是汇编器。



汇编器是用来解释“汇编语言”的程序,汇编语言中所使用的助记符,和计算机指令是一一对应的关系。早期的计算机主要还是用于数值计算,因此数学才是主宰。在数学的世界里,数百年传承下来的“语言”就是算式,因此用接近算式的形式来编写计算机指令就显得相当方便。随后,FORTRAN于1954年问世了。FORTRAN这个名字的意思是:算式翻译器(FORmula TRANslator).



也就是说,编程语言是由编程者根据自己的需要发明出来的。早期的计算机,由于性能不足、运算成本高,因此编写和维护都被看成是非人的工作,而编程语言正是其开发摆脱非人性的象征。



其实,由助记符自动生成机器语言的汇编器,以及由人类较易懂的算式语句生成机器语言的编译器,当时都被认为是革新性的技术,被称为“自动编程”。此外,编译器开发技术的研究甚至被视为人工智能研究的一部分。



未来的编程语言可能不会像过去的语言那样,让语言本身单独存在,而是和编辑器、调试器、性能分析器等一切工具相互配合,以达到提高整体生产效率的目的。



计算机语言的发展过程



按照计算机语言的发展阶段,可以分为机器语言、汇编语言和高级语言三类。



7解释型、编译型、混合型语言比较



8常用语言的应用领域



9 为什么这么多的语言?



语言设计人员设计的语言是为了解决特定的问题的目的而设计的(以用其编写的程序应用于特定领域)



语言设计人员设计的语言在以下方面有侧重点的取舍:编程简单、程序易读、执行效率高;



10 结构程序设计与面向对象程序设计



传统的结构程序设计采取的方式是先考虑求解问题的算法,然后再寻找合适的数据结构。即传统的结构程序是:程序=算法+数据结构。



面向对象的软件开发思想认为程序是由对象组成的,而所有的这些程序代码又都是是放在类中的。



传统的过程化程序设计,必须从顶部的main函数开始编写程序。在设计面向对象的系统时没有所谓的顶部。而是从设计类开始,然后再往每个类中添加方法。



C语言是支持结构程序设计的语言,而C++既支持结构程序设计,同时也支持面向对象程序设计。



11 一个成功的编程语言必须满足4个准则



需要建立一个明显的社区。只有让采用者安心,他才会去使用此技术;



需要具备可移植性,如Java虚拟机已经提高了后继语言的门槛;



需要提供经济上的动机,生产力、无线运算、数据搜索;



它需要展示技术优点;



如Java是一个很棒的静态面向对象语言,具有可移植性及大量的API、产品、开放源码项目,也是一个设计良好的语言和虚拟机


Category lang