更新时间:2022-06-17 08:13:54
本节书摘来自华章计算机《从问题到程序:用Python学编程和计算》一书中的第1章,第1.1节,作者:裘宗燕 更多章节内容可以访问云栖社区“华章计算机”公众号查看。
我们已经生活在信息时代,环顾四周,信息技术的影响无处不在。由于信息科学技术的发展和应用,我们的世界的方方面面都与20年前大不相同了,例如:
为什么在这不长的几十年时间里,人类社会的方方面面会发生这么大变化?回答很简单:因为有了计算机,这种强大、灵活、威力无穷的通用信息处理工具(它从根本上有别于人类发明的其他工具),改变了人类社会的每个方面。
那么,计算机的威力从哪里来?为什么一台计算机(基于电子元器件组合起来的一套设备)能完成如此丰富多彩的不同工作?本章首先希望回答这个问题。
本章将帮助读者在比较直观的层面建立起对计算机、计算、程序、程序设计和编程语言的基本认识,然后简单介绍本书使用的编程语言——Python语言,最后介绍在学习实际编程中必然遇到的一些情况和问题。
人类发展的历史,也是积累知识的历史。今天的人们未必比古人更聪明,至少相差不会太多。但是,今天人们掌握的知识比古人多得多,而且一年多于一年,一代多于一代。正是由于这种知识积累,使今天人类的生活与古人大不相同了。
1.1.1 “是什么”和“怎样做”的知识
人类积累的知识,从某种角度看可分为两大类:
两个实例
在日常生活和学习中,到处都可以看到这两类不同知识,现举两例:
【例1.1 菜单和菜谱】以常见的菜肴——西红柿炒鸡蛋为例,在饭店菜单上可以看到对它的描述:通过自然语言写出,介绍其色香味方面的特点,可能再附以照片给人感官印象。这是有关该菜肴的一套说明性描述,说明了西红柿炒鸡蛋是什么。而翻开一本菜谱,其中有关同一菜肴的描述则完全不同。首先是一个配料表,说明制作这一菜肴需要准备哪些基本食材和配料,烹制前如何处理(准备工作)。而后是有关用火和烹制过程的详细说明,告诉人们应该怎样做,才能得到一盘合格的西红柿炒鸡蛋。
显然,上述两种说明都针对同一客体,即同一盘菜肴,但它们显然很不一样。前者传递的是有关“是什么”的知识,或称说明性的知识,而后者传递的是有关“怎样做”的知识(操作性的,或称为过程性的知识)。作为饭店顾客,查阅菜单弄清菜肴的特点,符合自己的需要,就可以选择它。而作为学做菜的人们则需要参考菜谱实际操作,才能做出合乎预期的菜肴。
【例1.2 最大公约数】最大公约数是基础数学中的一个基本概念,出现在小学数学课本里。作为数学概念,最大公约数有严格的数学定义:
定义:两个正整数x和y的最大公约数(常简写为GCD),就是能整除x并能整除y的正整数中最大的那个数(允许至多一个数为0是本定义的扩充)。
这个定义基于几个更基本的数学概念(正整数、整除、最大),严格定义了一个新概念:最大公约数。只要理解了这几个基本概念,就能理解这个新概念。显然这一定义传播的一些知识属于是什么的说明性知识。但是这个定义没有说明在遇到一对正整数时,如何把它们的最大公约数求出来。后一工作就要靠过程性的知识了。
求最大公约数的一种著名方法称为辗转相除法,又称为欧几里得方法。该方法说明了求两个正整数的最大公约数的一种计算过程,可严格描述如下:
这里的每一行描述一两个简单操作,做计算时只需一行行地往下做。最后两行有点特殊:第3行说明满足一定条件就得到了结果;第4行说明要转回前面继续。
如果给定一对正整数x和y,实施上面描述的计算过程,最后就能得到它们的最大公约数。进一步说,要执行这个计算过程,需要知道如何完成两个基本操作:求一个整数除以另一个整数的余数,判断一个整数是否为0。
过程性知识
说明性和过程性的知识都非常重要,前者是人们有关客观事物的朴素认识的深入、积累和总结,而后者则是人们对自己的各方面实践活动的总结。
本书主要关注后一类知识(过程性知识)。其表现形式可能是一段自然语言说明,也可能采用某些特殊的格式(例如上面有关求最大公约数的描述,或者菜谱里有关一个菜肴的描述)。但是,这类知识重要性,主要不在于其描述的形式,而在于它所描述的(操作、计算)过程可以实施,最终产生出所期望的结果或者效果。
历史上人们早已发明了许多有价值的计算过程,但实施却很困难,因为只能由人按照特定的方法一步步计算,需要大量人力,也极端费时。有很多著名的例子,例如,开普勒花了近10年时间计算太阳系的行星轨道;二战中美国陆军部为计算大炮的装药和弹道,雇佣了成百的美国妇女参与计算弹道手册等。
近几十年来,由于人类发明了计算机这种自动化的计算机器,过程性知识的重要性大大提升了。以计算机作为过程自动化的基础,社会生产生活的方方面面都已经发生了巨大变化,而且,这一变化趋势还在继续,没有看到丝毫减退的迹象。今天在几乎任何领域中,一旦人们弄清了一件事可以怎么做,就会考虑如何借助于计算机去完成它。
1.1.2 计算和程序
环顾四周,计算机已经是今天人类使用最广泛的一种机器了。它不但以独立可见的形式出现在家庭、办公室和许多其他地方,还被嵌入在几乎所有现代化的设备、仪器、家用器具中。为什么计算机这么有用?为什么计算机到处都能用?实际上,计算机就是一种能自动完成计算的机器,要理解计算机,就需要理解计算。人们从小学(或者学龄前)就开始接触计算,学习基本计算规则。那么计算是什么?
计算是一类按规则操作抽象符号(序列)的过程。例如,最基本的整数算术就是操作算术表达式(由10个数字符号和几个表示运算的符号构成的序列)。人们使用一组基本算术规则,从需要计算的符号序列出发,逐步变换,最后得到计算结果。人类社会发展(如计量、分配、度量等)产生了计算的需求,逐渐发明了与计算有关的各种记法和过程。在计算机出现前,计算由人(通过头脑和手等)实施,可能借助一些简单工具(手指、纸笔、算盘、计算尺)。越来越烦琐的计算,需要花费非常多的人力和物力,也限制了很多工程技术的发展。今天,计算机已经把人从包含大量细节的烦琐计算中解放出来了。
要理解计算机和计算,也必须理解程序的概念,理解计算、程序和计算机之间的关系。讨论程序和编程(程序设计)就是本书的主题。
程序与计算
“程序”一词来自生活,通常指为完成某项事务而确定的一套既定活动方式或者活动安排。在表述上,程序应看作是对一系列动作的进行过程的描述。日常生活中也可以找到许多“程序”实例。例如,下面序列描述了一个学生早晨起床后的活动:
这是一个直线型序列,包含一系列简单活动(步骤),是最简单的程序形式。如果按顺序实施序列中描述的动作,最后的效果就是完成了一项事务或者工作。
另一个复杂一些的过程是完成一门数学课程的作业,可以描述为:
显然,这个程序比前一个复杂些。最主要复杂性在于它不是一个平铺直叙的序列,其中有些步骤有条件,需要根据情况处理,还可能出现重复的动作或动作序列。
仔细探究这个实例,可以看到它还可能进一步细化,以便处理实际中可能遇到的各种复杂情况。例如步骤4.1,其中的审题、思考和查阅书籍又可能交替进行,可能出现多次反复。还可能遇到各种异常情况,例如作业本用完了、笔出了故障、电话铃突然响了,或者到了上课或吃饭时间等。由此可见,要把一个“程序”描述完全并不容易。
现实生活中有许多这样的程序性活动,典型的如一个会议的议程、一场演出的节目单、运动会的程序册。总而言之,对一项事务、活动等的进展过程的细节描述就是一个“程序”。一个程序的描述通常有开始与结束,动作者(人或机器)根据程序执行一系列动作,到达程序结束位置时,整个工作完成。在一个程序描述中,总有一批预先假定的“基本动作”。例如,上面有关作业的描述中把“查阅参考书”看作基本动作。但如果参考书在图书馆,那么这个动作就需要进一步分解。程序的精细化(精化,或称功能分解)也是在本书后面有关计算机程序设计的讨论中特别强调的最本质的东西。
在计算中做的都是程序性的工作,通过一系列较为简单的操作完成。以多位数加法为例,需要数字对位等准备,然后使用基本数字加法规则,从低位到高位逐位求和并处理进位,直至做完所有数位,最后收集结果。有关计算过程可以描述如下:
这里的基本执行方式是执行完一步后执行下一步,除非当前步骤中明确要求下一步做什么。有些步骤有条件,如果当前步骤的条件不成立,就直接转去执行下一步的操作。虽然多位数加法是人们最熟悉的计算,将其详细地严格写出还是有点烦琐。显然这里也有开始和结束,有特定的基本操作(一位十进制数的加法,判断一个数字是否0)。乘法的计算过程更复杂,其中需要做逐位的乘法、结果的对位和加法计算等。
日常生活中的程序可以看作计算机程序的直观对应物,在一些情况下也会明确写出实际文本,例如一次会议程序或演出节目单。但两者之间还是有巨大差异,主要在于后者的极端严格性。日常生活中程序性活动的描述可以含糊笼统,实际执行也可以有变化调整,不一定完全按程序走。而计算机程序的描述则要求绝对严格,计算机作为执行主体,对程序的执行一丝不苟,一步步按程序中的条目行事,丝毫没有商量的余地。
计算机和程序
为了研究计算的理论,数学家阿兰•图灵在1936年提出了一种计算模型,后来被人们称作图灵机。这是一种非常简单的抽象计算机器(可以看作一种数学模型),其中有一个控制部件,指挥一个读写头在一条记录数据的带子上读写数据。著名的图灵-丘奇论题说,对于任何可以通过计算解决的问题,都可以设计一台图灵机解决。人们用这个论题定义什么是计算。图灵还证明了计算的局限性,通过实例证明了不可计算问题的存在性。
图灵还有另一个特别重要的贡献:他在图灵机模型的基础上设计了一台称为通用图灵机的特殊图灵机,并证明了通用图灵机能模拟任何一台图灵机的工作过程,也就是说,能完成任何可能的计算工作。图灵的做法是把具体图灵机表达为通用图灵机可以处理的编码表示形式,实际上就是程序。因此,通用图灵机是一种可编程的通用机器,可以看作今天的通用电子计算机的理论模型,因此图灵被人们称为“计算机之父”。
有关图灵机(和图灵-丘奇论题)和通用图灵机的工作非常重要。前者告诉我们,如果需要考虑设计和制造完成计算的机器,只需要考虑计算能力“等价于”图灵机模型的机器就足够了。后者告诉我们,不需要考虑如何去设计能完成千奇百怪的具体计算的设备(例如加法机、乘法机、文字编辑机、超级玛丽游戏机等),只需要设计和制造出一种设备,其功能等价于通用图灵机,就能解决所有的计算问题了。
现实中的计算机是20世纪40年代人们发明的一种自动机器,基于电子技术,能完成各种计算工作。从20世纪30年代末开始,各国的研究者们开始基于电子技术开发出一些计算设备。早期的这类设备只能做一件专门计算工作,是功能固定的计算设备。例如1942年完成的ABC机器(Atanasoff-Berry Computer)专门求线性方程组的数值解,图灵领导开发的bombe(意为密码破解)机器专门破解德国Enigma密码机生成的密码。
1946年在美国宾州大学开始运行的ENIAC是第一台得到较多实际使用的可编程计算机,只需要给它换一个“程序”,它就能做另一种计算工作。但是,这台机器的程序由一些外部连线和开关设置组成,要想换一个程序,需要重新连接许多线路,改动很多开关。这件事通常需要许多人工作几天时间,非常麻烦。
著名数学家冯•诺依曼考察了ENIAC机器之后写出了一份报告,提出了采用程序存储方式的计算机的逻辑设计,为现代计算机的发展指明了正确方向。程序存储计算机的特点就是把需要执行的程序编码,像数据一样存入计算机的存储器,然后让计算机的执行部件自动提取程序的内容,执行相应操作。这样,一方面计算机能摆脱外部拖累,用自己的速度快速执行程序。另一方面,给计算机换一个程序,就像是给它输入一组数据一样,非常方便。具有这种结构的计算机被称为冯•诺依曼计算机。1948年英国曼切斯特大学研究者开发出Mark I计算机,通常被认为是第一台实际投入使用的程序存储计算机。
其实,所谓的冯•诺依曼计算机,也就是图灵理论中的通用图灵机的一种具体体现形式,是一台通用的计算设备。而完成具体计算的计算机程序,对应于图灵的通用图灵机理论中的具体图灵机的编码表示形式。也就是说,人们在设计和实现计算设备方面的多年实际探索,最终再次证明了图灵理论的重要意义。
计算机的基本原理
计算机能执行一组基本操作,每个操作完成一个简单动作,例如做一次整数运算、把一个数从这里搬到那里、比较两个数的大小等。计算机提供了一套指令,每种指令对应计算机的一个基本动作。最基本的计算机程序,就是一个这种指令的序列。
计算机的基本原理很简单,就是能自动地按照程序要求一步步工作。其工作方式如图1.1所示,这是一个循环,循环中不断地交替执行两个动作:第一个动作是取得程序里的一条指令,第二个动作是执行该指令要求的操作。完成一次基本循环后进入下一个循环,再次取得下一条应该执行的指令并执行它。周而复始,直至遇到一条明确要求它停止工作的指令。这个图表现了计算机运行的微观情况。
要指挥计算机工作,最基本的方式就是写出一个程序,把这个程序提供给计算机,命令计算机去执行它。此后计算机就会按照程序的描述,一丝不苟地执行其中的指令,直至整个程序执行结束。因此,从宏观上看到的计算机工作的情况如图1.2所示:获得一个程序,执行它,可能给出得到的结果;然后取得人们提供的下一个程序,执行并给出结果。同样是循环往复。人们常把计算机执行程序的过程简单说成是程序的执行过程。
00000001000000001000 -- 将单元1000的数据装入寄存器0
00000001000100001010 -- 将单元1010的数据装入寄存器1
00000101000000000001 -- 将寄存器1的数据乘到寄存器0原有数据上
00000001000100001100 -- 将单元1100的数据装入寄存器1
00000100000000000001 -- 将寄存器1的数据加到寄存器0原有数据上
00000010000000001110 -- 将寄存器0里的数据存入单元1110
这里描述的程序包含6条指令,要求计算机做的事情就是计算算术表达式a × b + c的值。为便于理解,这里用a、b、c代表计算机里的三个存储单元,它们的地址分别为1000、1010和1100。这个程序描述了完成这一计算,最后将结果存入单元1110的计算过程。上面提到的寄存器是一类存储数据的部件,计算机硬件可以直接操作其中数据,保存在其他地方(例如内存单元)的数据需要先装入寄存器,然后才能在计算中使用。
计算机诞生之初,人们只能用机器语言写程序。由上面的简单例子可见,对于人的使用而言,二进制编码形式的机器语言非常不方便:用它写程序非常困难,工作效率极低,写出的程序难以理解,正确性很难保证,发现程序有错也很难辨认和改正。
复杂的程序可能包含成百万、成千万条,甚至更多条指令,其中的执行流程错综复杂,理解一个二进制机器语言描述的复杂程序到底做了什么,很容易变成人力所不能及的事情。为了缓解这个问题,人们很快开发出符号形式的、相对更容易使用的汇编语言。用汇编语言写的程序需要通过专门软件(称为汇编系统)加工,翻译成机器语言后送给计算机执行。下面是用某种假想的汇编语言写的程序,它完成与上面程序同样的工作:
load 0 a -- 将单元a的数据装入寄存器0
load 1 b -- 将单元b的数据装入寄存器1
mult 0 1 -- 将寄存器1的数据乘到寄存器0原有数据上
load 1 c -- 将单元c的数据装入寄存器1
add 0 1 -- 将寄存器1的数据加到寄存器0原有数据上
save 0 d -- 将寄存器0里的数据存入单元d
汇编语言的每条指令对应一条机器语言指令,其中用助记的符号名表示操作和存储单元。这样,每条指令的意义都更容易理解和把握,理解整个程序也容易了许多。但是,汇编语言没有结构,一个程序是基本指令的一个长序列,是一盘散沙。用汇编语言编写复杂程序仍然很困难,难以理解,其中的错误也很难被定位和改正。
高级编程语言
1954年诞生了第一个高级程序语言Fortran,程序设计进入了一个新时代。Fortran采用完全符号化的描述形式,用类似数学表达式的形式描述数据和计算。语言中提供了有类型的变量,作为计算机存储单元的抽象。它还提供了一些高级流程控制机制,如循环和子程序等。这些高级机制使编程者摆脱了许多具体的计算机硬件细节,可以把复杂的程序分解为一些较小的较容易把握的部分,方便了复杂程序的书写。写出的程序更容易阅读,发现错误后也更容易辨认和改正。Fortran语言诞生后受到广泛欢迎。
从Fortran语言诞生至今,人们提出的语言已经有数千种,其中大部分是试验性语言,只有少数语言得到广泛使用。随着时代的发展,今天绝大部分程序都是用高级语言写的,人们也已习惯于用编程语言这一术语特指各种高级程序语言了。用高级语言描述前面的程序只需要一行。例如,下面是用本书中将要使用的Python语言写出的完成同样计算的程序:
d = a * b + c
这一行程序要求计算机算出 = 符号右边表达式的值,最后用d记录计算的结果。这种表示方式接近人们熟悉的数学形式,明显更容易阅读和理解。
与机器语言和汇编语言相比,高级语言的形式人更习惯,更容易使用,这也使更多的人愿意参与到程序设计活动中。用高级语言写程序,工作效率更高,使人能开发出更多应用系统,这些又反过来推动了计算机应用的发展,进而推动了计算机工业的大发展。可以说,高级编程语言的诞生和发展,对计算机领域的发展起到决定性作用。
当然,计算机也不能直接执行高级语言描述的程序。人们在设计好一个高级语言后,还需要开发一套实现该语言的软件,这种软件被称作高级语言系统,也常说成是这一高级语言的实现。在研究开发各种高级语言的过程中,人们深入研究了实现语言的技术。高级语言的基本实现方式有两种,分别称为编译和解释:
1)编译方式:首先针对要实现的语言开发出一个翻译软件,它能把用这个语言写的程序翻译成计算机机器语言的等价程序。我们在用这种高级语言写出一个程序P之后,先用上述翻译程序处理,得到与P对应的机器语言程序P'。在此之后,只要命令计算机执行程序P',计算机就能完成程序P要求的计算工作了。
2)解释方式:首先针对要实现的语言开发一个解释系统,该系统能读入用这种语言写的程序,直接按程序的要求指挥计算机完成相应的计算工作。要运行一个写好的程序,只要把它送给运行着上述解释系统的计算机,就可以完成程序要求的工作了。
有许多高级语言适合采用第一种方式实现,如Fortran、C语言等,也有许多语言适合采用第二种方式或某种混合方式。从表面看,本书中使用的Python是采用解释方式实现的语言,但其中还有些细节。后面会介绍Python语言实现的一些情况。
随着计算机科学技术的发展,人们不断开发出新的程序语言,老的语言也被逐渐淘汰,仍在用的老语言也在不断变化。以Fortran为例,它在过去60年中经历了多次大改版,其较新版本(如Fortran 90、95、2003和2008)与早期Fortran相比已经有很大不同。其他历史较长的语言也都如此。推动语言发展的因素很多。随着程序设计工作的长期实践,人们对程序设计应该怎样做、需要什么东西去描述程序等,不断产生新的认识,其中许多重要认识被凝结到新语言里。推动语言发展的另一原因是应用。新的应用领域常对描述工具提出新要求,这些认识和要求促使人们改造已有的语言,或者提出新语言。
目前世界上使用较广的语言有C、Java、C++、Python等,这些语言通常被看作常规语言,因为它们有许多常见的共同特征。还有一些语言比较特殊,在形式和编程方式等方面与常规语言差异很大,它们互相之间也常常大相径庭。这些非常规的语言各具特点,有些语言有自己的应用领域,甚至有特殊的使用人群。这一类语言包括Lisp、Smalltalk、Prolog、ML等。虽然不如常规语言使用广泛,但这些语言也非常重要,它们都曾在程序语言或计算机的发展历史上起过(有些仍然起着)极其重要的作用。
上面说的都是通用编程语言,其设计目标具有一般性,希望能用于解决范围广泛的计算问题。除此之外,现在还发展出许多专用的编程语言,或者比较偏向于应用于某些问题的编程语言。常见的如Maple和Mathematica用于做符号计算和数学问题的计算,SAS和R等用于做与统计有关的计算,MATLAB等用于做矩阵计算和工程计算。还有许多专用于很窄的特殊问题的语言,例如专用于控制某种数控机床,专用于某类机器人的动作设计,专用于特殊的编织机器的花纹设计等。这些语言各有特点,但从程序性的角度看,它们也继承了通用语言的一些基本概念和特征。
如前所说,高级语言的发展推动了计算机应用和整个计算机领域的发展,计算机硬件和计算机应用的发展反过来又推动了高级语言的发展和变化。早期人们对高级语言还有些顾虑,主要是认为用它们编写的程序的执行效率不如直接用汇编语言编写的程序。经过多年的研究和开发,语言实现技术的发展已经基本消除了这方面的问题。今天绝大部分程序都是用高级语言开发的,只有极少量的程序或程序部分是用汇编语言开发的。因此,今天人们在谈论编程语言时,默认地就是指高级编程语言,本书后面也这样做。
编程语言的要素
编程语言是人设计的一类语言,设计目标就是用于写程序。一个完整的程序描述了一个计算过程,就像一个剧本描述一出话剧或一部电影的表演过程。计算机执行程序,与演员们执行剧本也有类似之处。当然,在这里完全没有临场发挥,因此简单得多。
上面的讨论实际上也揭示了程序的两方面特征:一方面,一个程序是一段文本描述,完全是静态的,就像一篇论文、一本小说,可以阅读和理解,甚至可以修改重构。但另一方面,一个程序又蕴涵着一个执行过程、一段计算,这是一种动态的活动。这是程序的两面性,编程的目标是实现其蕴涵的动态过程,但却要用一段静态文本去描述它。学习编程的一个重要方面,就是去理解这种静态描述与动态过程的关系。
程序语言的一边关联着编写程序的人们,另一边关联着执行程序的计算机,因此其形式必须满足这两个关联方的需要:为了使计算机能够处理和执行,编程语言必须有严格定义的形式。另一方面,由于程序需要人来写,所以编程语言应该具有人比较容易使用和理解的形式,便于人阅读、理解、参考,需要易读、易理解、易学习、易使用。各种成功的高级语言,其设计都是在这两种需要之间取得了较好的折中。
语言学的研究者们提出了语言的三个要素:语法、语义和语用。这种提法原本是针对人们在日常生活中使用的“自然语言”。作为一类人造语言,编程语言在语法和语义方面的情况比各种自然语言(如汉语、英语)更清晰准确:
本书将采用Python语言作为讨论计算与编程的工作语言。由于上面这些情况,在后面章节中介绍Python语言的一种结构时,通常也包括几部分内容:(尽可能严格地)说明这种结构的语法形式,其结构和各个组成部分;(直接并可能通过示例)解释这种结构产生的计算过程(操作的过程);通过一些例子说明这种结构可以(或者应该)如何使用。在介绍过一种结构之后,随后的实例中可能经常使用它们。讨论中还会经常出现不同结构的相互关系和对比,通过实例说明如何结合使用多种不同的结构。