进阶程序设计

一个编程范式(programming paradigm)是一种编程风格——一种构造程序的方式,有它自己的思想和语言特性。本考纲里有四个编程范式。

"描述命令式(过程式)语言是什么意思"(两分)。 一种语言,其程序是按顺序执行并改变程序状态的一系列指令;程序员用过程、顺序、选择和迭代说明任务如何完成。 "描述声明式语言是什么意思":程序陈述事实和规则(已知什么、想要什么),由语言的推理引擎找出如何得到答案;程序员不*给出步骤的顺序。*

从代码样本识别范式(试卷 3 的常规题):LDD 200、ADD #5、STO 201 是低级(助记符、寄存器、内存地址);带过程和赋值的 FOR Count ← 1 TO 10 … NEXT Count 是命令式;CLASS Dog … PRIVATE Name : STRING … PUBLIC PROCEDURE NEW(…) 是面向对象;type(lion, wild). 和 dangerous(X) IF type(X, wild) 是声明式(逻辑)。在连线题中:低级配"与机器指令直接对应的助记符",命令式配"改变状态的一系列语句",OOP 配"把属性和方法结合起来的对象",声明式配"事实和规则,不给出执行顺序"。

Low-level programming

贴近硬件地用机器码(machine code)或汇编语言(assembly language)编程,那里每条指令映射到 CPU 运行的东西。它给出对寄存器(registers)和内存地址(memory addresses)的直接访问,用不同的寻址方式(addressing modes,立即、直接、间接、变址和相对)。它非常快而紧凑,但特定于架构、繁琐,且难以维护。这是低级(low-level)编程,用于设备驱动、固件和引导加载程序。

五种寻址方式。 大纲要求会写用每种寻址方式(addressing mode)的低级代码(指令集在主题 4)。装载指令的操作数可以有五种读法,考试给出内存内容并问累加器保存什么:

• 立即寻址(LDM #105):操作数就是值;ACC 变为 105。
• 直接寻址(LDD 105):操作数是值的地址;ACC 变为 105 的内容,这里是 27。
• 间接寻址(LDI 105):操作数是一个地址的地址;ACC 变为 27 的内容,这里是 91。用于指针和位置在运行时才确定的数据。
• 变址寻址(LDX 105):地址是操作数加变址寄存器 IX;IX = 2 时,ACC 变为 107 的内容。用于通过递增 IX 遍历数组。
• 相对寻址(JMR +65):目标是相对当前指令地址的偏移,这使代码可重定位。

例题。 内存:105 存 27,106 存 64,200 存 0。写代码把 105 和 106 的内容相加,结果存入 200 并输出。LDD 105(ACC = 27),ADD 106(ACC = 91),STO 200,OUT。若改为把 105 中的值加倍:LDD 105,ADD 105,STO 105。被要求追踪时,写出每行之后的寄存器内容。

Imperative (procedural) programming

在命令式编程(imperative programming)中,程序员写一个改变程序状态的命令序列——赋值、条件、循环、函数调用。变量(variables)容纳状态;语句改变它;代码被组织成过程和函数(也叫结构化编程)。这是主题 9 和 11 的风格(Python、C)。当算法有清晰的顺序步骤时很强。

Object-oriented programming (OOP)

在面向对象编程(object-oriented programming)中,程序从对象(objects)构建——把数据(属性(attributes))和操作(方法(methods))结合的单元。对象是类(classes)的实例(instances)。四大支柱:

• 封装(encapsulation)——一个对象的数据被隐藏在它的方法之后;外部代码只用公共方法,而不直接用数据。这保护对象并让它的内部改变而不弄坏调用者。例如,一个 BankAccount 隐藏它的 balance;你只通过 deposit() 和 withdraw() 改变它,它们能强制执行一条规则如"永不低于零"。
• 继承(inheritance)——一个子类(subclass)特化一个父类(superclass),继承它的属性和方法并添加或重写(overriding)它们。为"是一个"("一个 Manager 是一个 Employee")建模。
• 多态(polymorphism)——不同的对象对同一个方法调用做出不同的响应;调用者不必知道确切的类型。每个 Shape 有 Area(),而一个 Circle 和一个 Rectangle 各以它们自己的方式实现它。
• 抽象(abstraction)——显示一个简单的接口并隐藏实现。

其他术语:

• 一个构造函数(constructor)是一个在对象被创建时运行的特殊方法,用来设置它的属性。
• getter 和 setter 通过方法读写一个对象的属性(它的性质)。
• 聚合(aggregation)和包含(containment)从其他对象构建一个对象(一个"有一个"关系)。

OOP 用于大型系统、GUI、模拟和游戏。

按评分方式理解的 OOP

定义。 *类:*定义该类型对象的属性和方法的模板(蓝图)。*对象:*类的一个实例(instance),由类创建,有自己的属性值("一个对象的出现"是考试对实例的说法)。*属性:*属于类的一个数据项。*方法:*属于类、作用于其属性的过程或函数。*封装:*把属性和方法组合在一个类中并限制外部访问数据:属性是私有的,只能通过公有方法读取或改变。*继承:*子类获得父(超)类的属性和方法,并可以增加自己的或重写它们。多态:同名方法在不同类中行为不同;通常子类重新定义父类的一个方法,每个对象运行正确的版本。*包含:*一个类把另一个类的对象作为属性(汽车有发动机)。"指出限制外部访问数据的特性"是封装;"一个对象的出现的术语"是实例。

"概述类的结构"(三分):保存对象数据的属性,通常声明为私有;作用于这些属性的方法(过程和函数),通常是公有的;以及一个构造函数,在创建对象时运行以初始化属性。"给出 OOP 的三个好处":代码通过继承重用;数据由封装保护,只能被类自己的方法改变;大型程序拆分成独立编写和测试的类,更易维护和扩展;类为现实世界实体建模,设计更易理解;多态让同一个调用适用于不同对象。

伪代码中的类,如试卷 3 所设:

CLASS Car
    PRIVATE Registration : STRING
    PRIVATE Year : INTEGER
    PRIVATE Mileage : INTEGER
    PUBLIC PROCEDURE NEW(NewReg : STRING, NewYear : INTEGER)
        Registration ← NewReg
        Year ← NewYear
        Mileage ← 0
    ENDPROCEDURE
    PUBLIC FUNCTION GetMileage() RETURNS INTEGER
        RETURN Mileage
    ENDFUNCTION
    PUBLIC PROCEDURE AddMileage(Extra : INTEGER)
        Mileage ← Mileage + Extra
    ENDPROCEDURE
ENDCLASS

对象用 MyCar ← NEW Car("AB12 CDE", 2020) 创建,用 MyCar.AddMileage(150) 和 OUTPUT MyCar.GetMileage() 使用。子类通过 SUPER 重用父类的构造函数:

CLASS ElectricCar INHERITS Car
    PRIVATE BatteryCapacity : REAL
    PUBLIC PROCEDURE NEW(NewReg : STRING, NewYear : INTEGER, NewCapacity : REAL)
        SUPER.NEW(NewReg, NewYear)
        BatteryCapacity ← NewCapacity
    ENDPROCEDURE
ENDCLASS

同一个类的 Python 版,如试卷 4 所期望:属性用双下划线设为私有,构造函数是 __init__,子类在括号中写父类名并调用 super().__init__(…):

class Car:
    def __init__(self, reg, year):
        self.__registration = reg
        self.__year = year
        self.__mileage = 0
    def get_mileage(self):
        return self.__mileage
    def add_mileage(self, extra):
        self.__mileage = self.__mileage + extra

class ElectricCar(Car):
    def __init__(self, reg, year, capacity):
        super().__init__(reg, year)
        self.__capacity = capacity

cars = []
cars.append(Car("AB12 CDE", 2020))
cars.append(ElectricCar("EV21 XYZ", 2023, 75.0))
cars[1].add_mileage(150)
print(cars[1].get_mileage())

在 Java 中同样的想法是 private/public 字段、与类同名的构造函数、extends 和 super(…);在 VB.NET 中是 Private/Public、Sub New、Inherits 和 MyBase.New。多态方法在父类中写出、在子类中用同名重写;通过父类类型变量的调用运行子类的版本。

作为对象的数据结构。 试卷 4 用一个 Node 类构建栈、链表或二叉树,其属性是数据和指向其他节点的一或两个引用;一个 Tree(或 LinkedList)类保存根(或起点)和各方法。

CLASS Node
    PUBLIC Data : INTEGER
    PUBLIC Left : Node          // 没有子节点时为 NULL
    PUBLIC Right : Node
    PUBLIC PROCEDURE NEW(NewData : INTEGER)
        Data ← NewData
        Left ← NULL
        Right ← NULL
    ENDPROCEDURE
ENDCLASS

CLASS Tree
    PRIVATE Root : Node
    PUBLIC PROCEDURE Insert(NewData : INTEGER)
        DECLARE NewNode, Current : Node
        DECLARE Placed : BOOLEAN
        NewNode ← NEW Node(NewData)
        IF Root = NULL THEN
            Root ← NewNode
        ELSE
            Current ← Root
            Placed ← FALSE
            WHILE NOT Placed
                IF NewData < Current.Data THEN
                    IF Current.Left = NULL THEN
                        Current.Left ← NewNode
                        Placed ← TRUE
                    ELSE
                        Current ← Current.Left
                    ENDIF
                ELSE
                    IF Current.Right = NULL THEN
                        Current.Right ← NewNode
                        Placed ← TRUE
                    ELSE
                        Current ← Current.Right
                    ENDIF
                ENDIF
            ENDWHILE
        ENDIF
    ENDPROCEDURE
ENDCLASS

查找方法沿同一路径走,Current.Data = Target 时返回 TRUE,到达 NULL 时返回 FALSE;中序输出方法是递归的:输出左子树、该节点、然后右子树。对链表,节点有一个引用 Next,链表类保存 Start;对由链表构建的栈,压入和弹出都在 Start 进行。

例题。 一个游戏有角色。每个角色有名字、生命值(初始 100)和由 X、Y 给出的位置。写一个类 Character,带构造函数和一个改变位置的方法 Move(DX, DY);再写一个子类 Wizard,增加 Mana(初始 50)和一个方法 CastSpell(),消耗 10 点法力,若法力足够则返回 TRUE。

CLASS Character
    PRIVATE Name : STRING
    PRIVATE Health : INTEGER
    PRIVATE X : INTEGER
    PRIVATE Y : INTEGER
    PUBLIC PROCEDURE NEW(NewName : STRING, StartX : INTEGER, StartY : INTEGER)
        Name ← NewName
        Health ← 100
        X ← StartX
        Y ← StartY
    ENDPROCEDURE
    PUBLIC PROCEDURE Move(DX : INTEGER, DY : INTEGER)
        X ← X + DX
        Y ← Y + DY
    ENDPROCEDURE
ENDCLASS

CLASS Wizard INHERITS Character
    PRIVATE Mana : INTEGER
    PUBLIC PROCEDURE NEW(NewName : STRING, StartX : INTEGER, StartY : INTEGER)
        SUPER.NEW(NewName, StartX, StartY)
        Mana ← 50
    ENDPROCEDURE
    PUBLIC FUNCTION CastSpell() RETURNS BOOLEAN
        IF Mana >= 10 THEN
            Mana ← Mana - 10
            RETURN TRUE
        ELSE
            RETURN FALSE
        ENDIF
    ENDFUNCTION
ENDCLASS

分数在于私有属性、设置每个属性的构造函数、继承行、对父类构造函数的调用,以及使用并改变对象自身数据的方法。当题目要求类图时,画一个三部分的方框(名字;属性,私有用 -;方法,公有用 +),并用指向父类的箭头把子类连到父类。

Declarative programming

在声明式编程(declarative programming)中,你说要计算什么,而不是怎么——运行时算出步骤。两种:

• 函数式编程(functional programming)——从纯函数(pure functions,无副作用(side effects);同样的输入总是给出同样的输出)组合而成。例子:Haskell、Lisp。
• 逻辑编程(logic programming)——陈述事实和规则;引擎通过推理回答一个目标(goal,查询)。例子:Prolog。

一个熟悉的声明式例子是 SQL(结构化查询语言):SELECT * FROM Customer WHERE Country = 'UK' 说你想要什么,而不是怎么走过记录。

事实、规则和目标是考试在声明式范式中考查的内容。给定这些事实(facts)(为真的陈述)和一条规则(rule)(条件成立时成立的结论):

01 type(leopard, wild).
02 type(lion, wild).
03 type(tabby, domestic).
04 size(leopard, large).
05 size(lion, large).
06 size(tabby, small).
07 dangerous(X) IF type(X, wild) AND size(X, large).

"写出目标 type(X, wild) 的结果":X = leopard, X = lion。引擎把目标依次与每条事实匹配;每次匹配都是一个解,大写字母是由匹配填入的变量。"写一条事实表示猎豹是野生的":type(cheetah, wild). "解释第 07 行的作用":它定义了一条结论为 dangerous(X) 的规则,对任何既野生又大型的 X 为真,所以 dangerous(A) 返回 A = leopard, A = lion。"写一条规则:若 F 是特性、B 是车身样式且 F 对 B 不是不可用的,则特性 F 可能对车身样式 B 可用":may_be_available(F, B) IF feature(F) AND body_style(B) AND NOT unavailable(F, B)。照抄题目事实中的谓词名和参数顺序;新事实以句号结尾,规则的条件用 AND 连接。

Comparing paradigms

现代语言常常混合范式——Python 支持过程式、OOP 和函数式全部。正确的那个取决于问题。

这扩展主题 10 的文件(file)处理,处理串行、顺序和随机(直接存取)文件。伪代码操作:OPENFILE name FOR READ | WRITE | APPEND(READ 打开一个现有文件,WRITE 创建/覆盖,APPEND 加到末端);READFILE name, line;WRITEFILE name, value;CLOSEFILE name;以及 EOF(name),它在末端为 TRUE。

读整个文件:

OPENFILE "names.txt" FOR READ
WHILE NOT EOF("names.txt") DO
    READFILE "names.txt", thisName
    OUTPUT thisName
ENDWHILE
CLOSEFILE "names.txt"

搜索一个文件(找到时停止):

found ← FALSE
OPENFILE "people.txt" FOR READ
WHILE NOT EOF("people.txt") AND NOT found DO
    READFILE "people.txt", line
    IF line = target THEN found ← TRUE
ENDWHILE
CLOSEFILE "people.txt"

Updating a file in place

大多数语言不能原地编辑一个文本文件。而是:打开原始文件为 READ、一个临时文件为 WRITE;对每行,若它应当改变就写新版本,否则写原始;关闭两者;然后用临时文件替换原始文件。同样的模式处理删除行(跳过它们)和插入行。

记录和随机访问文件

打开模式。 READ:文件必须存在,从开头读取。WRITE:创建一个新文件,同名的已有文件被覆盖。APPEND:写入添加到已有文件的末尾。每个打开的文件都用 CLOSEFILE 关闭,读完最后一项后 EOF(name) 为 TRUE。

三种文件组织。 串行文件中记录按加入顺序排列;顺序文件中按键的顺序排列;两者都从头读取。随机文件(random file)(直接访问文件)把每条记录存放在由哈希(hashing)函数根据其键计算出的地址上,所以不用读其他记录就能找到一条记录。记录声明为用户定义类型:

TYPE AccountRecord
    DECLARE AccNo : INTEGER
    DECLARE Name : STRING
    DECLARE Balance : REAL
    DECLARE Active : BOOLEAN
ENDTYPE

伪代码中的随机文件操作是 OPENFILE "Acc.dat" FOR RANDOM、SEEK "Acc.dat", Address(把文件指针移到该记录)、GETRECORD "Acc.dat", Rec(读那里的记录)和 PUTRECORD "Acc.dat", Rec(把记录写到那里)。按账号查找客户,如试卷 3 所设:

DECLARE Rec : AccountRecord
DECLARE Target, Address : INTEGER
INPUT Target
Address ← Target MOD 1000              // 哈希函数
OPENFILE "Acc.dat" FOR RANDOM
SEEK "Acc.dat", Address
GETRECORD "Acc.dat", Rec
WHILE Rec.AccNo <> Target AND Rec.AccNo <> 0    // 0 表示空槽
    Address ← Address + 1               // 冲突:试下一个槽
    SEEK "Acc.dat", Address
    GETRECORD "Acc.dat", Rec
ENDWHILE
IF Rec.AccNo = Target THEN
    OUTPUT Rec.Name, Rec.Balance
ELSE
    OUTPUT "No such account"
ENDIF
CLOSEFILE "Acc.dat"

要存储一条记录,对其键哈希、SEEK 到该地址并 PUTRECORD,越过已被占用的槽。分数给哈希、GET 或 PUT 之前的 SEEK、与目标的比较、冲突的处理,以及关闭文件。

例题。 ActiveFile.dat 保存 AccountRecord 记录。写伪代码把每条 Active 字段为 FALSE 的记录复制到 ArchiveFile.dat 的末尾。

DECLARE Rec : AccountRecord
OPENFILE "ActiveFile.dat" FOR READ
OPENFILE "ArchiveFile.dat" FOR APPEND
WHILE NOT EOF("ActiveFile.dat")
    READFILE "ActiveFile.dat", Rec
    IF Rec.Active = FALSE THEN
        WRITEFILE "ArchiveFile.dat", Rec
    ENDIF
ENDWHILE
CLOSEFILE "ActiveFile.dat"
CLOSEFILE "ArchiveFile.dat"

Python 中的文本文件(试卷 4):file = open("HighScore.txt", "r"),然后 for line in file:,用 line.strip() 和 line.split(",") 分开各字段,用 int(…) 转换分数,再 file.close();写入用 open(name, "w")(或 "a" 追加)和 file.write(str(score) + "\n")。高分表被读入一个记录列表,新分数插入其位置,再把整个列表写回。评分看用正确模式打开、读取每一行的循环、文本到数字的转换,以及关闭。

Pitfalls

忘记关闭一个文件(数据可能丢失);本想 APPEND 却打开为 WRITE(覆盖一切);读过 EOF;硬编码的路径——一个像 /Users/Admin/data.txt 的路径在另一台机器上失效,所以用一个相对常量如 DataFile = "./data/scores.txt"。

一个异常(exception)是执行期间的一个错误或意外情况——除以零、文件未找到、网络失败、一个数组(array)索引越界。异常处理(exception handling)让一个程序检测它并优雅地响应,而不是崩溃。

它重要是因为真实的程序面对无法事先预防的错误(文件被移动、网络中断、坏输入);没有它,每个操作都需要它自己的 IF 检查;而且它把正常流程与错误处理分开,所以主路径读起来干净。例如,一个文件可能在你的程序检查它存在和实际打开它之间被另一个用户删除——你无法预防那个,只能在它发生时处理失败。

"举例描述异常是什么意思"(两分)。 在程序执行期间(运行时)发生并中断其正常流程的意外事件或错误;例如除以零、打开不存在的文件、把非数字输入转换为整数、数组下标越界,或内存耗尽。 **"指出异常的两个可能原因"**从该列表作答,再加上"设备或网络不可用"和"输入了无效的数据类型"。

"说明包含异常处理的理由"(三分)。 为了阻止程序崩溃(意外终止);为了向用户输出有意义的消息而不是系统错误;为了让程序能恢复并继续,例如再次要求输入,或在结束前安全地关闭文件;以及因为有些错误在编写程序时无法预测。**"描述如何避免因异常导致程序终止":把可能引发异常的语句放在 TRY 块内;为该异常写一个 EXCEPT(catch)块来处理它,例如输出一条消息,使执行在该块之后继续而不是停止。"解释异常处理是什么意思":**在异常发生时检测到它并运行处理它的代码(处理程序),使程序得以继续。

Pattern

TRY
    OPENFILE "data.txt" FOR READ
    READFILE "data.txt", line
    OUTPUT line
    CLOSEFILE "data.txt"
EXCEPT FileNotFound
    OUTPUT "Sorry, the file does not exist."
EXCEPT ReadError
    OUTPUT "Sorry, error reading the file."
ENDTRY

TRY 块容纳可能失败的代码;第一个匹配的 EXCEPT 块运行。真实的语言也有一个包罗一切的 EXCEPT 和一个 FINALLY 块,它无论异常是否发生都运行——对清理(关闭文件)有用。

Raising an exception

一个检测到错误的子程序能抛出(raise)一个异常,以便调用者处理它:

PROCEDURE Divide(a : INTEGER, b : INTEGER) RETURNS INTEGER
    IF b = 0 THEN
        RAISE DivideByZero
    ENDIF
    RETURN a DIV b
ENDPROCEDURE

Where to handle exceptions

若响应简单(一个消息、一次重试)就在贴近错误处处理它们,或若只有外层代码知道怎么做就在调用栈(call stack)更高处(一个顶层 GUI 循环记录错误并显示一个友好的对话框)。不要静默地吞掉异常——至少记录它们,否则调试变得不可能。

常见异常:FileNotFound、IOError、DivisionByZero、IndexOutOfRange、InvalidArgument、NullReference、OutOfMemory。把每个可能失败的操作包在一个带正确 EXCEPT 处理程序的 TRY 中,给出一个优雅降级而不是崩溃的程序。

例题(试卷 4)。 写一个函数,从名字作为参数传入的文件中逐行读取整数并以列表返回。文件不存在或某行不是整数时它不能崩溃。

def read_scores(filename):
    scores = []
    try:
        file = open(filename, "r")
        for line in file:
            scores.append(int(line))
        file.close()
    except FileNotFoundError:
        print("The file", filename, "does not exist")
    except ValueError:
        print("A line in the file was not a whole number")
    return scores

try 块容纳可能失败的代码(打开和转换);每个 except 指明一种异常并做有用的事;函数仍然返回一个列表,所以调用者可以继续。在 Java 中同样的形式是 try { … } catch (FileNotFoundException e) { … } catch (NumberFormatException e) { … };在 VB.NET 中是 Try … Catch ex As FileNotFoundException … End Try。分数:有风险的语句在 try 内部、正确的异常名、每种异常一条消息、程序之后继续;笼统的 except: 得到"不崩溃"的分,得不到"恰当的异常"的分。

例题。 一个会员文本文件需要修改某位会员的电话号码。为什么程序不能直接覆盖那一行?正确的模式是什么?文本文件中各行的长度不同,而文件中并没有空隙来吸收长度差:更长的新内容会侵入下一条记录,更短的则会把旧行的尾巴留在那里。所以正确的模式是:以读方式打开原文件,以写方式打开一个临时文件,逐行读取,对需要修改的那一行写入新版本,其余各行则写入原来的内容,关闭两个文件,然后用临时文件替换原文件。删除(跳过该行)和插入(多写一行)也是同样的套路。注意每一行都要被写出,而不是只写改动的那一行 - 只写新记录、把文件其余部分弄丢,是经典的失误。

定义题按固定措辞评分。准确学会这些,只给一个答案。

• 范式:记住每种的一句话描述,并准备好从代码样本说出范式;低级题要五种寻址方式和累加器得到什么。
• OOP 定义每次考试都出现:类、对象、属性、方法、封装、继承、多态、构造函数。用伪代码写一个带 PRIVATE 属性、PUBLIC NEW 和 getter 的类;用 INHERITS 和 SUPER.NEW 写子类。
• 声明式:带变量的目标返回每条匹配的事实;规则是结论 IF 用 AND 连接的条件;照抄题目的谓词名。
• 文件:三种模式及各自对已有文件的作用;WHILE NOT EOF 循环中的 READFILE;随机文件用哈希、SEEK、GETRECORD 和 PUTRECORD,冲突时向后步进。
• 异常:带例子的定义、处理它们的三个理由,以及让程序继续的带具名 EXCEPT 的 TRY。

常见错误

• 把声明式程序描述为"给出答案的一系列步骤";它陈述什么为真、想要什么,而不是如何做。
• 混淆对象和类,或实例和属性;"一个对象的出现"要答实例。
• 把属性声明为 PUBLIC,或从类外直接访问它们而不是通过 getter,这会丢掉封装分。
• 子类构造函数直接设置父类的属性而不调用 SUPER.NEW。
• 把多态解释为"许多对象";它是同名方法对不同类行为不同。
• 用 FOR WRITE 打开文件来添加记录,这会毁掉已有内容;要用 APPEND。
• 从头读随机文件;先 SEEK 到哈希地址。
• 把异常处理程序套在不会失败的代码外,或不带消息地捕获一切,或把异常处理描述为"用 IF 检查输入"。