将抽象定义成一种过程
名字 映射到复杂的程序片段
从用途与功能角度考虑
而非具体实现
控制抽象:执行良好定义的操作
数据抽象:表示数据
局部变量:执行代码语句相关的变量
参数:输入
返回值:输出
将以上三个限制于子程序作用域内
子程序代表调用方执行操作:任务委托
参数化
传递参数:传递信息(控制子程序行为),提供数据(值)
实参在调用时映射到形式参数
形参:子程序内局部变量 ?
返回值:函数
不返回:过程
大多数要求函数在使用前已有声明
c没有
声明:编译器可以检查调用与函数签名是否一致
调用序列:调用前后,被调用前后
8.1回顾栈布局
调用栈上分配空间问题
子程序被调用时,栈顶部分配一个新栈帧:活动记录
包含:实参、返回值,簿记信息(返回地址,保存的寄存器),局部变量、临时值
在任意给定时刻,栈指针寄存器保存最后一个已用位置,或第一个未用地址
帧指针保存栈顶帧内的一个地址
帧中对象访问:相对帧指针位移寻址
对象大小编译时未知,放在帧顶部大小可变区域,地址与内情向量保存在某个固定区域
不存在未知大小对象:帧中对象相对栈指针偏移量静态可知,不用帧指针
参数大小编译时未知:参数放在其他参数下方大小可变区域,地址与内情向量放在相对帧指针的已知偏移量处
或调用方只传递临时地址与内情向量,被调方复制实参到栈顶可变区域
图
允许嵌套与静态作用域的语言:
对象可能在外围子程序中
维护静态链,找到这些非局部非全局对象
栈帧包含一个 对词法上外围帧的引用——静态链(指针)
为子程序返回时恢复而保存的帧指针——动态链(指针)
一个活动的子程序,其外围子程序是活动的
只有通过外围子程序才能见到且调用内层子程序
嵌套定义的子程序,只能从外围子程序进入。因为函数名对其他函数不可见。
局部子程序:词法静态嵌套关系表示可见性
8.2调用序列:完成调用工作的实现
维护子程序调用栈
调用前后处理代码,被调前后处理代码
进入子程序的过程完成的工作
传递参数
保存返回地址
修改程序计数器
修改栈指针与分配空间!!
保存子程序可能修改的寄存器值(包括帧指针)
修改帧指针,指向新帧栈
执行新帧上的对象初始化代码
离开时的工作
传递返回参数,返回值
局部变量终结代码,释放空间
释放帧栈(恢复栈指针)
恢复保存的帧指针
所有工作中一部分只能由调用方完成(只有调用方知道的信息:传递参数,返回地址?静态链)
其他可以共同完成
调用方做工作
被调方做工作:可以节省空间,子程序不止一次被调用???
##调用树图
保存恢复寄存器
理想模式:调用方正在使用,而被调方用于其他目的。则将之保存(寄存器集合的子集)
实际:调用方保存所有正在使用的寄存器 被调方保存所有将要修改的寄存器
寄存器分组:调用方保存有价值的一组 被调方改写没有价值的一组(可能存在语义一致的资源)
静态链维护
一部分维护工作必须由调用方完成:调用方的词法外层
调用方计算被调方的静态链,作为隐式参数传递
具体分两种情况:
1.被调方直接嵌套在内层
被调方静态链引用调用方的栈帧。调用方传递帧指针
2.被调方在调用方外k层
调用方对静态链做k次间接引用,传递给被调方
典型调用序列
调用方
保存寄存器
计算参数值,移入栈或寄存器
计算静态链,作为隐式参数传递
执行子程序调用指令,跳入子程序,返回地址放在栈,寄存器中
被调方
分配帧
保存原有帧值,赋予新值
保存寄存器
子程序结束
被调方
返回值移入寄存器或栈
恢复寄存器
恢复fp,sp
跳回返回地址
调用方
保存返回值
恢复寄存器
优化:
没有局部变量
不需要帧栈,参数来自寄存器
区头向量
取代静态链的小数组,缓存地址计算结果。空间换时间
寄存器窗口滑动
内联展开
增加了代码量
保持语义(相对宏)
编译器可了解语义,可优化
8.3参数传递
传递值,引用,闭包
规则唯一:c
规则不唯一:python?
8.3.1参数模式
值调用,传递副本。得到值
引用调用:传递地址。形参为实参的新名字,别名。
传递的必须是左值
引用传递为了修改参数
值传递+返回值:形参赋值回实参
讨论值模型与引用模型只对使用值模型的语言有意义
变量的引用模型,不一定要求所有对象通过地址访问。java,python
java内部类型值模型,自定义为引用模型
无论变量是值还是引用,都通过复制来传递
与赋值语句语义一致
函数意图
修改实参
保持实参
间接访问的代价
复制对象的代价(大型值)
只读参数:同时获得引用参数的效率与值参数的安全性
c:const声明:加工时常量
const指针:保证不引用其他对象 或 引用的对象不被修改
c++
引用参数&
不引用其他对象 const 指针
引用作为返回值
闭包作为参数
闭包:子程序的引用,并带有子程序引用环境
代码地址+引用环境
带环境的可调用对象
c:指向程序的指针
面向对象:模仿闭包行为,闭包对象,单方法类
类是对象:有属性(静态方法,类变量)
类是类型:创建类实例对象,提供方法,实例属性
8.3.3特殊目的的参数
相似数组:不同语言,数组维数与边界的约束时间不同:编译时,加工时,执行时
语言中,针对参数的规则 比 针对变量的规则 宽松
推迟到运行时确定形状的数组参数:相似数组参数,开放数组参数
默认参数
提供值:修改函数默认行为
缺省实参:使用默认值,默认行为
默认值为:值,字面量,不可变
:对象,可变
命名参数:相对于位置参数:关键字参数:调用时的按名传参行为
混合使用:先位置参数
可变个数参数表
对静态类型不安全,无法静态检查(不知道个数,不可能检查)
对动态类型安全?运行时检查,动态检查
类型安全的静态类型:要求可变长参数表类型相同
8.3.4函数返回
不区分表达式与语句的语言:函数的值=函数体(本身是一个表达式)的值???
显式return:副作用:函数停止
正交性:返回值类型限定
返回复合值,元组
正交性:弱化限制
设计限制了出现的对象必须满足的特征:第一类,第二类,第三类 类型 静态已知
8.4泛型子程序与模板
需要在不同类型对象上使用同一操作
OS:队列:保存进程、存储描述符、文件缓冲区、设备控制块、等
队列数据结构的特征与数据项的特征无关
8.4.1不同的实现方法
隐式参数多态性:参数类型无描述,但依然是类型安全的
类型检查推迟到运行时
显式多态的泛型机制
C++模板
用于创建容器
容器:数据抽象,保存一组对象。操作与对象类型无关(不要求提供接口,要求极少的接口)
泛型模块(或类)需要泛型子程序,实现操作
泛型参数:
java c#只允许传递类型
ada c++允许传递常规类型的值?子程序或类?
泛型代码:对类型参数的最低特性要求(最小接口)
适当的限制条件:显示描述,或编译器推断
编译器的工作是隐式的 写于程序正文的是显示的
不同的实现方法
Ada c++静态机制:编译时 创建使用泛型代码的多个实例,每个实例独立代码副本
C++:安排独立的类型检查
优化:共享代码
类型检查:要求特定的类型——函数签名(运算符)
要求提供接口——泛型
java:一个泛型所有实例运行时共享代码
标准基类object的实例(语义转化为子类多态性)
子类运行父方法
静态泛型与宏 有共性
泛型 宏
内联函数 宏
编译器理解的 事后添加的,预处理器展开的
类型检查
常规作用域规则
8.4.2泛型参数的约束条件
泛型也是种抽象:接口提供所有信息
Ada,java:限制泛型参数,显示说明参数类型支持的操作
java:从父类继承的接口实现
c++:摒弃显示限制,提供参数检查
参数类型不支持操作:静态语义错误避免隐式使用泛型参数类型的操作
8.4.3隐式实例化(函数)
泛型函数看做重载(重载是否一定要求函数签名不相同?需要声明,需要强类型)
c++隐式实例化规则比 重载子程序 严格
编译器不对子程序实参作类型强制
8.5异常
子程序调用栈的回退
难以在局部上下文处理
不妨碍正常的流程
错误处理移到主流之外
控制转移
致命异常
可恢复异常
处理程序与异常的动态约束:容易造成语义模糊
静态约束:词法位置约束的代码块。作为原始代码块相并存在的补充(if else)。
调用点引发异常,调用方(&调用方的调用方)处理
沿动态链返回,(依然存在动态约束,但是受限得多)
在调用方代码块(静态约束)中寻找局部处理程序,检查匹配,处理/重新抛出/终止并打印
沿动态链寻找调用方,在调用方代码块(静态环境)寻找局部处理程序
匹配——处理
不匹配——重新引发(传播)
8.5.1异常的定义
预定义异常
异常类型
参数:类的域(字典)
try
throw,raise主动引发
传播(接收并重发)
catch
最终未处理的情况
清理操作:类似调用序列语义(子集),但是未完成工作
离开作用域:内存释放
final
with——exit?
8.5.3异常的实现
处理程序的链接表栈(解释数据结构?)
控制进入保护区:处理程序加入表
为实现沿动态链的反向传播,对于中间层子程序无处理程序:隐式处理程序:子程序的后续代码,重新引发异常
编译时记录表格:处理程序与受保护块的对应关系(指针)
异常发生:程序计数器为key,对表格折半搜索
特别处理隐式处理程序:返回地址作为key
独立编译:各个子程序独立表格
无异常机制:模拟行为
8.6协程
需要闭包,保持环境
继续:常量,创建后不改变
协程:每次运行时变化:跳进时位置为上次退出时位置
一组协程:同时存在的上下文,但每个时刻只有一个在执行,主函数调用
用于离散时间的模拟
要求顺序的完整性检查,替代深层循环
控制权转移
独立的程序计数器
线程比协程好用
协程是并发的,不能共享栈
如果栈帧在堆中分配,可以避免溢出与内部碎片问题???
但会增加子程序调用开销
仙人掌栈
表示协程或进程:上下文块
协程转移
8.7事件
程序外部发生
时间不可预测
需要程序响应
等待输入:同步,阻断式
回调函数
处理程序:特定时间调用
异步设备活动
中断机制
切换栈到回调函数
信息缓冲区
基于线程处理程序
事件:单独控制进程