第三章 过程式程序设计语言 基本观点： 计算实现的模型如果按冯诺依曼原理强制改变内存中的值叫命令(或译 指令、强制Imperative式)的。由于强制改变值，程序状态的变化没有一定 规则，程序大了就很难查错，很难调试，不易证明其正确。 组织程序的范型即:算法过程+数据结构（计算控制+计算对象） 3.1 计算对象表示值与类型 3.2 计算对象实现存储 3.3 计算对象连接束定 3.4 计算组织-程序控制 3.5 计算组织-函数与过程 3.6 计算组织-抽象与封装 类型是计算机可能实现的结构和约定对客观世界差异的刻划。 同一类型的外延，即同一结构表示所有可能的值构成一个域。 分类原则：同样表示结构,同样语义解释,同样的操作。 同类型值运算结果：同类型。 无符号整数： 二进制解释的值 整数：符号 值 3.1 计算对象-值与类型 0 10 0 0 1 1 11 11 0 1 0 0 0 1 0 1 0 1 00 0 0 0 1 0 1 0 1 0 1 1 浮点数： 符号 阶码 尾数 程序语言中：基元(primitive)类型：整型/实（定，浮）/字符/真值/枚举 结构（structured）类型：元组/数组/记录（结构）/表/串 3.1.1 字面量、变量、常量 名字操纵值, 名: 字面量 从名字即知类型 字面值不变 变量 符号名要声明类型 值可变 常量 符号名要声明类型 值不变 基元值的名字是地址的别名, 地址值在计算机中不恒定 操纵地址的名字是指针(地址变量) float *p, x = 37.32; p= (p)203C(x)117F 117F37.32 续 名值可分导致 x = x + 1; 按名 按名取值: 引用reference 存值 左值 右值 int x 既是右值也是左值 3.1.2 值是头等程序对象 程序语言中的值 字面量(整、实、布尔、字符、枚举、串) 复合量(记录、数组、元组、结构、表、联合、集合、文件) 指针值 变量引用(左值、右值) 函数和过程抽象，数学对象参与运算的权利是一样的，值是 计算对象也要按一致性原则： 可出现在表达式中并求值 可作函数返回值 可单独存储 可以构成复杂的数据结构 可作函数参数 3.1.3 类型系统 类型定义 值的集合和值上操作集合（V，Op) 类型系统 一组可直接使用的类型 类型规则 类型检查机制 3.1.3 类型系统 静态与动态 静 动 变量 有类型 无类型 动态简洁、灵活 参数 有类型 无类型 静态清晰、死板 值 有类型 有类型 弱/强类型 无类型 LISP , Smalltalk 弱类型 变量有类型。类型兼容性大, 系统不作检查 强制类型 隐式类型强制（转换），自动截尾, 补零。显式 类型强制 PL/1 伪强类型 静态均有类型且作检查,由于不严,导出等价准则 Pascal 强类型 类型有严格定义, 均作检查 Ada 类型等价 按结构等价 type A is array (range 1. 100) of INTEGER； type B is array (range 1.100) of INTEGER； OA1， 0A2： A； OB1， OB2： B； OC1： array (range 1. 100) of INTEGER； OD1， OD2： array (range 1.100) of INTEGER； OE1： A； OA1，OA2，OB1，OB2，OC1，OD1，OD2，OE1均等价 续 按名等价 OA1， OA2 是同一类型(都用A声明) OA1， OB1， OC1是不同类型(类型名为A，B， 无) OD1， OD2 是同一类型(同时声明， 虽无名) OD1， OC1 是不同类型(两次声明) OA1， OE1 是同一类型(虽两次声明， 但同名) 类型完整性准则 涉及值的类型中不能随意限定操作, 力求没有第二类的值 续 3.1.4 类型兼容 不同类型值混合运算, 人为定出计算级别，由低 层升 格为高层, 结果值是高层的 隐式转换 弱类型 I := R； 显式转换 强类型 I := Integer(R); 强类型按名判定，不同类型名则不兼容只有子类型 不同名可以兼容 显式和隐式混合 type BASE is INTEGER； subtype SON_TYPE is BASE range 1.1000； -子类型 type DIVERSE is new BASE range 1.1000； -派生类型 A， B： BASE； C， D： SON_TYPE； E： DIVERSE； A:= B+C， -合法，结果为B类型赋给A A:= C+E； -不合法 A:= C + SON_TYPE(E)； -合法，有显式强制 A:= E ; -不合法，两个类型 E:= B+BASE(E); -不合法 续 3.2 计算对象的实现- 存 储 存储对象是程序对象在计算机中的实现 程序对象不一一对应为存储对象 x:=0; x,0是两程序对象 只有一个存储对象x加指令清零 初值常量也不作为单独存储对象 3.2.1 程序变量的时空特性 引用和指针 P指针是地址变量 *P是P所指的内容, 也有左值和右值 *P左值是P所指地址值，即P的值 *P右值是所指地址内的内容值 引用是常指针是变量的别名, 但实现是不一样的 递引用 dereference 通过指针变量引用变量的值为递引用 *P1右值即递引用 有些语言显式递引用算符如FORTH的 1 13 VARIABLE xx (声明变量xx并赋初值13) 2 0 VARIABLE Y (声明变量Y并赋初值0) 3 xx 2 * Y ! (相当于Y=xx*2) 如果只写xx 2 * 则为将xx的地址乘以2放在Y之中 3.2.1 变量的时态 分配/未分配/除分配 分配: 为程序对象创建存储对象 编译时分配叫静态分配 allocate 运行时分配叫动态分配如声明指针p, 执new才分配 未分配: 声明了未分配运行时分配 除分配: 取消存储对象(程序对象) delete操作显式 自动除配: 无用单元收集Garbage collection 动态语言有，静态可有Ada可没有C 续 43? ? a b c d e f 声明和定义：定义必然声明；反之不然 声明的两个作用 ：给出对象, 该对象的时间有效性 出了声明的作用域该对象失去定义。在声明的作用 域内显式删除也失去定义 定义/未定义/失去定义 只要分配存储对象必然有残值, 无意义即未定义 赋值或初值变量得以定义 a,b:分配且有定义 c,d:分配未定义或失去定义 e,f:未分配或除配 3.2.2 存储模型 基元类型值 仅除数组 记录、构造、表 不可更新其中一元素 函数抽象, ML重过程 变量引用 可存储值Storable：指最小的可直接访问的可存储单元中的值 Pascal可存储值:集合不选择更新某一元素是可存储值，Pascal, C ，Ada数组可选择更新, 不是可存储值。 引用非可存储(C+可存储), 过程和函数名也非可存储 ML几乎都是可存储值, 也带来毛病：每次更新结构数据都要重 来。它们是： ( if exp then sin else cos ) (x) 得sin(x)cos(x) 可存储值 存储对象的生存期 全局变量 和引用程序寿命一样长 局部变量 和程序中的一个模块寿命一样长 持久变量 比程序寿命长除非显式撤销 文件变量 瞬间变量（transient)持久变量的逆 每个存储对象都有创建(生), 可用(活着)，撤销(死)的 生命期。按生命期长短分： 静态存储对象 编译时分配存储对象, 近代语言类属对象直到装入后 确立(elaboration)之时才定下存储对象叫静态分配 一旦执行不再改动其存储，直至所在存储单元无效叫 静态(Static)存储对象 全局变量均为隐式的静态对象, COBOL,BASIC全 静态，ALGOL，C是显示声明静态，Pascal除全局，Ada 不能。 C语言的静态变量是既私有又不随所在声明块中消逝, 全局于所在文件。auto是静态分配动态装入不叫静态对象 。Extern是静态对象。 extern static auto 动态存储对象 把寿命特长的（如文件，全局量）排出来归到栈底的某一组，把寿命特 短的（如循环控制变量）另立嵌套组，这个问题也就解决。 块5块66块1块2块3块4 54 6 6 5 46 寿 命 动态存储对象 二叉树其大小由输入值定在运行中确立。内存开 辟堆（heap)随生成随堆放动态存储对象。指针（即 堆变量）所指程序对象用堆存放 问题：多次重分，内存成了小洞 解决办法：按寿命分组寿命最长的放在较低（按 其所在块生命期）。 重复使用 无法再分 堆栈帧管理 由动态堆栈联想到一般嵌套式语言可按动态堆栈式管 理, 多数变量和所在块寿命一样长(语言称之为自动变量) 动态堆栈式存储 按程序动态执行, 以动态堆栈管理局部数据和动态生成 数据 运行时堆栈Run-time stack其底压入程序代码和全局， 静态量。每执行到调用时生成一个堆栈帧(frame)记录该 块数据信息, 每当返回则局部量自动撤销对于递归块的局 部量可多次生成多次消除。 动态链描述调用父辈地址, 返回地址是继续执行的下一 地址。 静态链描述词法父辈lexical parent块地址, 按该块复制 局部变量。 参数 返回地址 动态链 静态链 返回值 局部变量 程序代码 全局静态存储 首先调用块 堆栈帧 第二调用块 堆栈帧 最新调用块 堆栈帧 临时变量空间 栈顶 堆栈帧组织运行时堆栈 续 调 用 块 首 地 址 本 帧 词 法 父 辈 举例 求整数连乘积之递归程序: function product (jj： Integer)： Integer； var kk： Integer; begin if jj (运行时动作指令， 取下标) 5 rangecheck (函数调用， 检查下标) 6 if (如果不越界) 7 linearsub (函数调用， 计算线性下标值) 8 then (给出数组基地址和位移) 9 ； (；切换成解释执行， 数据类型定义毕) 10 11 2by3array box (声明并分配名为box的数组变量) 12 10 1 2 box (给box(1，2)赋值10) 3.3.3 无类型语言束定 名字 束定 length age 符号表 运行时内存存储对象：类型标签 scalar number array