大多数语言有表达式，对象的类型两个概念
类型为操作提供了隐式的上下文环境
如传递给函数类型根据类型重载函数
类型支持实现了一部分接口，限制了程序中可执行操作的集合
好的类型捕捉无意义操作导致的错误
7.1类型的意义与作用
7.2类型等价与相容
7.3-9复合类型的语法，语义，实现
7.10对象相等，对象赋值
7.1类型系统
硬件 用不同方式 解释 存储器上的 一组二进制位
解释为：指令，地址，字面量（字符，数字）
二进制位本身无类型
标识符——地址——值（二进制位）
高级语言将值与类型相联系，提供上下文信息与错误检查
类型系统包括：
1 定义类型，与特定语言结构相关联
2 一组类型等价，类型相容，类型推理规则
具有类型的结构：有值的，或引用值的 结构
结构包括：命名常量，变量，记录域，参数，（有时）函数
及包含这些结构的表达式
类型等价：两个类型相等的条件
类型相容：一个类型支持另一个类型的接口
类型推理：确定表达式的值，部分类型运算后得到的值的类型指定
有多态性变量或参数的语言中，区分引用的类型 被引用的对象的类型
引用——类型——对象
两两打包
同一名字不同时刻可能引用不同类型对象
不能动态创建子程序 且用静态作用域的语言中，编译器总能确定名字引用的子程序，保证正确调用
7.1.1类型检查
保证程序遵守语言的 类型相容性规则
违背：类型冲突
强类型：禁止操作应用到不支持操作的对象。不发生强制？？
静态类型化：强类型，且所有（退一步：大多数）检查在编译时间执行
检查操作——检查类型
类型的来源：声明，或推理
携带类型信息：引用携带，值携带
C语言漏洞：联合，可变个数参数，指针和数组的互操作性
不做运行时检查
动态类型检查：迟约束的一种形式
python强类型化
动态作用域规则：动态类型化
因为编译器不知道名字引用了什么对象，无法知道其类型
7.1.2多态性
参数多态性，子类型多态性
同一代码体可用于多个类型的对象
需要运行时动态检查，对象是否实现了操作
动态类型化 又称支持隐式的参数多态性
运行时开销，推迟错误报告
用类型推理系统，通过静态类型化，支持隐式的参数多态性
推断每个对象与表达式的类型
编译器任务：对程序中对象静态确定一种 一致性的类型指派
面向对象中，子类型多态性允许父类型引用子类型
因为派生类要求支持基类的所有操作
子——>转化——>父
简单继承模型：编译时实现类型检查
使用这种实现的语言提供了显式的参数多样性：泛型
允许程序员定义带类型参数的类
泛型用于集合
python检查推迟到运行时
编译时推断
运行时跟踪
7.1.3 类型的含义
编译时推断
运行时跟踪
除此之外，
声明对象的类型，
声明非内部类型的特征
指称的
构造的
基于抽象的
观点
指称：一个类型是一组值（域）
值属于值集合——对象属于类型
构造：类型：由内部类型 迭代 构造出的复合类型
抽象：类型是一个接口，由一组定义良好的相互协调的 语义操作组成
指称语义学：一组值：一个论域：一个类型
表达式：论域中的一个值
函数：一个存储映射到另一个存储
存储：名字到值的映射
赋值：赋值前内容映射到赋值后内容
可以基于集合上的数学运算，描述用户定义类型
枚举类型：一组值
7.1.4类型分类
内部类型：处理器硬件支持的类型
整数，字符，布尔，实数
离散类型：可数，有序——枚举，子界
标量类型：简单类型
枚举类型：一组命名元素
排序，比较，前驱后继，枚举控制
与整数的相容性不定
子界：离散基类型的连续子集
编译器分析子界的声明，动态检查越界
复合类型：结构类型：非标量类型
记录：一组域，各域类型的笛卡尔积
变体：各个域类型的并集
数组：下标元素映射到成员类型
集合：基类型的数学幂集
指针：左值，直接用地址实现。
用于实现递归的数据类型
表（链表）：没有映射与下标。长度可变
文件：位于大规模存储设备，内存之外的数据，
有当前位置的概念，在顺序操作中隐式使用下标，
反映了物理设备的固有特性，如顺序访问
7.1.5正交性
高度正交的语言，容易理解，使用，
容易做形式化的推理
C消除语句，表达式的差别？提高正交性
语句只为提供值：返回空类型（如函数返回值void）
数组元素类型，数组下标多样性：正交性体现
非正交性：数组的长度要求编译时确定
复合文字量：聚集值：JS对象字面量
用于静态数据结构的初始化/赋值
7.2类型检查
大多数静态类型的语言中,定义对象时必须指定类型
对象出现的上下文也是有类型的（上下文究竟是什么？）
上下文：对象周围环境对对象的要求、期待？作用于对象的规则要求？
语言包含了规则，限制了上下文中可以合法出现的对象类型：上下文文法？
类型相容：正确，弱于类型等价的要求
类型变换，类型强制，非变换转换
类型推理：子表达式类型——整体类型
7.2.1类型等价
结构等价：成分相同
名字等价：每个定义的类型只与自身类型相等。新语言的选择
结构等价：低级的，基于实现的
潜在区别
域的声明顺序
编译器递归展开定义——类型名序列
递归与基于指针的展开
名字等价：既然定义了两次，则，定义的是不同的类型语义
类型别名
严格名字等价：别名类型互不相同
宽松
严格，宽松的区别——声明与定义的区别？？？
type A=B
严格：这是定义
宽松：这是声明
类型变换与转换
期望实参与形参类型匹配：相同，相容（转化后相同）
显式类型转换：
1.结构等价，名字不等价
2.不同值集合有交集，判断是否为交集情况，否则报错
3.不同的底层表示，处理器用于变换的机器指令。存在信息损失，算数溢出
非变换类型转换：临时值
颠覆了语言的类型系统，绕过检查机制
强制上下文相容
7.2.2类型相容
类型等价——上下文相容
运算符：运算对象支持 公共类型，对公共类型操作
实参 相容于 形参
返回值
C 类型双关，指定方式解读二进制位
自动隐式变换：类型强制
强制也可能需要动态类型检查（复合？继承？），或底层表示间变化
强制削弱了语言安全性
C混用数组与指针
趋势：静态类型化，远离类型强制
重载：一个名字，不同对象
上下文信息解析
强制：一个对象，不同类型
匹配规则
文字字面常量：重载的
通用引用类型：可保存任意类型对象的引用
为写出通用的容器
c void*
java c# object
当赋值给特定引用类型对象时，保持类型安全性！
通用类型到专门类型的 赋值合法性
更普遍问题——保证任意赋值的合法性
解决方式：
对象具有自描述——面向对象语言
值模型：指针类型与引用对象类型
引用模型：值自带类型
名字——地址——值
类型解释地址中的值
需要动态 方法约束？（为子类选择合适的父类方法继承）
类型强制，产生合适异常
容器类型，保存通用引用类型对象
通用引用类型对象：与对象本身属性无关
没有类型标志的语言
不可能检查赋值时的类型转变
凭借不检查的类型转换
表达式的类型
运算符结果：运算符类型（函数签名）
函数调用结果：函数声明返回类型
赋值结果：左值类型
内部运算符——内部数据类型
内部运算符——复合类型
声明对象类型
字面量推断类型
类型不确定——多态
7.3记录（结构），变体（联合）
记录：不同类型，相关数据 打包成整体
c++ struct class 成员可见性区别
域：记录中成员
访问域：.运算符
C++允许结构标记作为类型名
不需要struct前缀
实现为typeof的语法糖
嵌套记录域
存储布局
编译器 符号表 保存每个记录类型中 各个域的偏移
访问域：位移寻址，加载/存储
局部对象：基址寄存器：帧指针，位移值：偏移量之和
内存空洞
压缩：未对齐：优化空间，降低速度
记录赋值
相等比较：空洞一致填充（0） 或按域比较
折中方案：对齐条件排序域
重排的优点：需要频繁访问的域集中在一起：同一缓存行：空间局部性
重排只是个实现问题，可以指定对齐方式
with语句
pascal：省略引用
python:添加作用域？
变体（联合）：共享内存相同字节
系统程序：同一字节不同时刻不同解释
意图：彼此用于不相关的目的：数据不同时存在
非转换类型强制：显式绕过语言的类型系统
继承：代码重用，内存重用，类型安全
7.4数组
下标类型到成员类型的映射
正交性：
下标可选类型
成员可选类型
成员是否必须同类型
非离散下标：关联数组：散列表
与字典类型相似
离散的下标：允许连续的内存分配：高效
定长:更高效
声明：
构造符
字面量赋值
7.4.1语法与操作
[]运算符，返回引用，显式的左值
否则，get，set
多维数组
数组的数组
切片支持
c：指针与数组之间的集成导致不支持切片？
数组运算
7.4.2维度个数，上下界，分配
声明描述形状
静态形状：栈中分配
动态形状：堆
加工前不知道形状，或动态改变
加工？？？
分配空间，生成形状信息（支持索引）
编译的语言：可以允许上下界动态，通常要求维度个数静态
内情向量：运行时 保存形状信息
内情向量
编译期间 符号表 维护每个数组的维度与边界信息
每个记录：域偏移量
如果数组维度数目与边界在编译
已知：符号表中找出，计算数组元素的地址
未知：生成代码，运行时从内情向量中查找
内情向量包含：每个维度的下界，
除最后一维外的各维度大小（最后一维大小=元素类型大小）
包含每个维度的上界，如需动态语义检查下标越界
下界可推导出上界，保存上界：避免反复运算
内容在加工时，或维度数目，上下界变化时 初始化
赋值语句可能需要复制内情向量
栈分配
子程序参数，动态形状数组
静态数组——传参给动态数组，生成内情向量
局部数组形状在加工时固定
帧栈分为固定大小区，可变大小区（保存指针与内情向量）
加工时？？？
任意时刻改变大小（形状），完全动态
改变的顺序与栈的进出顺序不一致
必须在堆中分配
完全动态但维度静态可知
帧栈上放置指针+内情向量
维度也可变
内情向量放在堆上，堆的开始处。避免重复复制？？？
废料回收
退出栈，回收堆上分配的内存空间
7.4.3内存布局
行优先，列优先
内存布局方式：影响迭代顺序
缓存效率：缓存缺失
行指针布局：java
允许不规则数组（字符串数组）
加快访问元素
间接访问/地址计算
连续布局地址计算
寻找计算中的编译时常数
公共表达式
地址计算中的动态部分——部分信息编译已知——转化为静态部分
静态消除检查：特别是枚举控制的
C数组维度上的下标下界为0
数组与指针的互操作性
7.5字符串
换意序列：增加一位，扩充字符集
字符串是一维的，不包含引用
7.6集合
公共类型任意数目
基类型：元类型
位向量：元素个数少
散列表
数组，散列表，树
7.7指针与递归类型
指针：值是引用（对象地址）的变量
指针与递归类型
指向指针的指针
递归类型：包含 本类型对象的引用
用于构造链式结构：表，树，图
引用模型：每个对象都是引用
容易实现递归
值模型：需要指针概念，值为其他对象的引用
指针：高级概念，特定对象的引用
地址：低级概念，内存单元的位置
显式回收：语言实现简单
自动回收：区分废料与活动对象
指针操作：
堆中对象的分配、释放，间接操作：访问引用的对象，赋值，重载运算符
java：内部对象值模型，自定义对象引用模型
需要相互引用：编译器中符号表的记录 语法树的节点~~
C没有可用于连接数据结构的聚集值写法
分配内存：
c： malloc 库函数，返回void*
c++：new 类型安全
访问指针引用的对象：显式的间接运算符
c指针，数组
无下标数组名自动转换——指针：数组第一个元素
传递数组，传递指针
下标运算基于指针运算定义：自举，语法糖
指针+-整数，指针-指针，比较
加工时需要分配空间！！！！
数组：整个数组空间
指针：一个指针空间
指针：使得两个左值的别名判断变难
声明必须使编译器确定元素大小，等价的，指针引用对象的大小
sizeof：字节数
编译时计算，除了可变长数组
悬空引用：活动指针 不再引用合法对象，可能破坏堆栈结构
指向栈内局部变量的指针
多个指针同时指向，一个指针显式回收，剩余指针
指针和被引用对象都可能作为实参传递？？？后果
废料收集：
消除了检查悬空引用的必要性
引用计数
对象无效：不存在指向它的指针
递归地工作
java：显式创建 作用域存储区域，线程不再访问，整体回收
正确识别指针的位置
只有在语言强类型情况，引用计数工作
无法回收循环引用结构？？？
追溯式收集：
废料：堆外不可访问的对象
理想：不会再使用的对象
堆外指针出发：递归遍历探查堆，确定有用的东西（标记），清扫
必须找到所有指针：块开头放置类型描述符
遍历：栈——无可用空间
隐式栈：指针反转用于回溯
标记好翻转的指针，每个时刻只有一个指针翻转？
图图图！
停顿并复制
堆分为两个区间：一个区间分配，满，压缩到另一个区间，语义交换
实际使用虚拟空间，不会造成浪费
分代式收集
最动态的是最短命的
存活久的先保留着
？？？废料不再访问，为何保留？？？
保守式收集：
在全局与栈中扫描按字对其的量，分析是否包含堆中地址
看着像指针的，都保留着指向的地址
需要程序员不隐藏指针：指针转换为其他类型
不能做压缩？？？
7.8表
表：
递归定义的结构：
空，
有序对：对象（原子），表
从成分 构造 表
在表中提取 成分
判断空
长度
索引
翻转
匹配
应用函数构造新表
7.9文件 IO
交互式IO，依赖顺序
文件：程序地址空间外的存储器，OS实现
临时文件：因为内存放不下，
持久文件：读写存数据
file数据类型
7.10相等性检测，赋值
赋值需要相等性检测，赋给自身
别名
引用相同（地址相同）
值相同
相等定义：归结于左值与右值的区分
比较左值：比较地址
引用同一对象：浅比较
比较右值：比较值
深比较
赋值
浅赋值：复制引用
深赋值：复制副本，值
复合对象的比较：递归比较
复合类型
类型大小形状
数组大小形状
自定义类型
自定义比较