程序设计--数据类型的设计、实现与语义.ppt

1 第四章数据类型 补充 程序设计语言原理 东南大学计算机科学与工程系 2 数据类型的设计 实现与语义 数据类型概念的早期发展简史数据类型强类型 strongtyping Ada的数据类型分类体系Ada语言的枚举类型Ada的数值类型Ada的带符号整数类型 3 数据类型的设计 实现与语义 Ada的实数类型Ada的浮点数类型Ada的定点类型Ada的数值类型总结Ada的数组类型指针类型Ada的记录类型 4 4 1数据类型概念的早期发展简史 简单说来 数据类型就是数据对象的分类及该分类上的操作 5 4 1 1基本指令系统中的类型因素 指令系统 数据传送指令INAL PORT 字节 INAX PORT 字 算术运算MUL无符号数乘法指令IMUL有符号数乘法指令 6 4 1 1基本指令系统中的类型因素 符号扩展指令CBW convertbytetoword CWD convertwordtodoubleword 逻辑运算ANDORNOTXOR 7 4 1 1基本指令系统中的类型因素 字符串处理MOVS movestring CMPS comparestring 控制转移JMPSHORTOPRJMPWORDPTROPR 8 4 1 1基本指令系统中的类型因素 数据类型 字节 字 双字 无符号整数 有符号整数 布尔值 值或向量 字符 字符串评注 抽象程度低 以原子类型为主 分类不严格 缺乏原则 主要基于硬件功能和应用需要 转换自由 基本在使用者的主观中 缺乏明显的转换标志 9 4 1 2汇编语言中的类型 数据定义伪指令DB DW DDDATA BYTEDB10 4 10HDATA WORDDW100 100H 5DATA DWDD3 20 0FFFDHMESSAGEDB HELLO ARRAYDB100DUP 10 4 1 2汇编语言中的类型 结构定义伪指令 C语言 personstrucfnamedb Firstname lnamedb lastname monthdw daydw yeardw personends 11 4 1 2汇编语言中的类型 属性 类型 修改操作符TYPEvariable返回类型LENGTHvariable返回分配给该变量的单元数SIZEvariable返回分配给该变量的字节数 SIZE LENGTH TYPEOFFSETvariable返回变量的偏移地址SEGvariable返回变量的段地址值 12 4 1 2汇编语言中的类型 类型指定操作符MOVAX WORDPTROPER1 1 13 4 1 2汇编语言中的类型 评注 复合 聚集 类型能力有所提高 但其中的数组类型没有明确化 开始支持用户定义类型 地址概念是类型的核心概念 占有等量存储空间的类型就兼容 类型转换显式化 但缺乏语义上的约束 出现属性的雏形 14 4 1 3FORTRAN语言 静态 不支持用户定义类型对数值类型支持也十分有限 整数 实数 双精度 复数 15 4 1 4C语言 枚举类型 用户定义类型 数组 结构 支持动态数据结构 动态数组 联合 不具备支持抽象数据类型的能力 灵活 但理论基础不足 有些方面带有明显的汇编语言的痕迹 数组名同时表示数组第一个元素的地址 结构标志符本身不作为类型区分符使用 标准对类型之间的关系没有详细说明 boolean numeration 转换比较随意 尤其在指针的问题上 图1 16 4 1 5Ada 类型丰富 全面 支持用户定义类型 抽象数据类型和面向对象概念 具备坚实的理论基础 概念一致 完整 同时提供以上语言中所具有的灵活性Ada的类型定义机制 17 4 1 5 1Ada的类型定义机制 用户定义类型 subtype用户定义类型 newtype exampleofsubtype subtypeDay Numberisintegerrange1 31 subtypeFeb DayisDay Numberrange1 28 18 4 1 5 1Ada的类型定义机制 续 subtype类似与pascal的子界类型 仅对相应type的值域加以限制 其它方面没有改变 subtype和相应type及同体系中其它subtypes之间进行混合运算时无需显式转换 即从本质上讲 subtype没有创造新的类型 Exampleofnewtypetypecolouris Red Amber Green typeLightisnewcolour 19 typeApplesisnewInteger typeOrangesisnewInteger No Of Apples Apples No Of Oranges Oranges No Of Apples No Of Oranges wrongNo Of Apples Apples No Of Oranges OKInteger No Of Apples Integer No Of Oranges OK 4 1 5 1Ada的类型定义机制 续 20 NewTypeVs ParentType Newtype的作用Newtype继承parenttype的预定义操作 用户定义的操作 primitivetype 用户定义的判等操作除外 21 4 2数据类型 简单来讲 数据类型就是对数据对象的分类 分类方式主要是内涵式 少数是外延式 内涵是对数据对象内在性质 静态 动态 的描述 externaldomain 问题域中的数据类型区分体系 internaldomain 编译器所能识别的存在于程序中的数据类型分类体系 我们希望该体系能够和externaldomain建立一一对应的关系 同时编译器也能识别这样的关系 参见图2 图3 22 4 2 1数据类型概念的组成 名字 结构 值集 属性集 操作集 逻辑结构与存储表示 逻辑操作与其实现 用户定义实现 系统实现 23 4 3强类型 strongtyping 强类型概念发展 ST 1 typed 必须为数据对象声明类型 ST 2 typed 每个变量都必须与一类型相联系 而且 该变量只能存储这一类型的对象 ST 3 stronglytyped ST 4 stronglytyped 24 4 3 1强类型 ST 3 所有的数据对象 变量 值 形参 均属于特定的类型 一般是有名的 这些类型可以是预定义的或用户定义的 每个数据对象仅属于一种类型 每个变量仅能存储唯一类型的对象 一个类型可以有多个变体 该类型的数据对象的变体内容可在运行时确定 程序在处理此类数据对象时 必须对变体部分予以确认 在子程序调用过程中 所有实参的类型必须与对应形参的类型相匹配 语言必须对匹配原则做出明确规定 25 unionu tag intival floatfval char sval u 联合 26 struct char name intflags intutype union intival floatfval char sval u symtab NSYM 带联合的结构 27 4 3 2强类型 ST 4 满足ST 3该语言须有系统 完整的类型体系 对类型间的关系及各种语境下使用类型概念的规则做出合理的规定 该类型体系及相关规则能够良好地反映问题域的逻辑结构和相关的约束 尽量在静态情况下完整地确定程序中的类型信息 检查出违反类型体系及相关规则的情况 给出明确的信息 对在动态情况下可能出现的类型错误给予充分的考虑 并予分类 提供预定义错误类型 提供动态检查及异常处理设施 28 强类型是一个相对的概念 有一种说法 认为必须在静态条件下检测出所有的类型错误才算是强类型的 这是一个历史上的看法 现在看来 这样的定义有失简单与片面 现在的通用语言几乎都提供一些动态的数据类型 29 4 4Ada的数据类型分类体系 elementary alltypes composite access scalar array record protected task discrete enumeration integer signed modular floating fixed decimal ordinary real 30 4 5Ada语言的枚举类型 4 5 1枚举类型举例4 5 2属性与操作4 5 3布尔类型 31 4 5 1枚举类型举例 typeDayis Mon Tue Wed Thu Fri Sat Sun typeColoris White Red Yellow Green Blue Brown Black typeHexais A B C D E F 32 4 5 2属性与操作 1基于标量类型属性的操作2第一个枚举字面值的位置为0 其后为 1 T Val T Pos X XT Succ X T Val T Pos X 1 3关系操作 33 4 5 3布尔类型 定义 typeBooleanis False True typeAnsweris False Don t Know True 预定义操作枚举类型的所有预定义操作 not and xor 34 4 6Ada的数值类型 涉及数值类型的主要问题 对机器实现的依赖 存储 界限 精度 35 4 7带符号整数类型 4 7 1设计考虑4 7 2例子4 7 3预定义操作 36 4 7 1设计考虑 设计数据类型时的考虑 范围 精度 forrealtype 硬件提供的数据类型 效率 可移植性 37 4 7 2例子 typePage Numisrange1 2 000 subtypeSmall IntisIntegerrange 10 10 subtypeBuffer SizeisIntegerrange0 Max 38 4 8Ada的实数类型 浮点类型和定点类型混合运算 39 4 9浮点类型 typeCoefficientisdigits10range 1 0 1 0 typeRealisdigits8 typeMassisdigits7range0 0 1 0E35 subtypeProbabilityisRealrange0 0 1 0 asubtypewithasmallerrange 40 4 10定点类型 typeVoltisdelta0 125range0 0 255 0 typeFractionisdeltaSystem Fine Deltarange 1 0 1 0 Fraction Last 1 0 System Fine DeltatypeMoneyisdelta0 01digits15 decimalfixedpoint 41 4 11Ada的数值类型总结 基本定义 范围 精度 表示方法 类型转换机制NumericTypeConversion如果整数之间的转换 只需转换类型标记 要检查约束 实数之间的类型转换的原则是保证精度 实数向整数转换的过程主要是取整的过程 42 4 12数组类型 数组元素 具有相同的类型数组索引 任意离散类型 43 4 12 1例子 大多数语言中 数组下标局限于整数类型 这种局限缺乏理论上的依据 Ada语言中 数组的下标可以是任意离散类型 我们通过一些例子来看看这种约束的解除带来的便利 44 Hours Worked array Day ofFloat ForDinWorkdayloopHours Worked D 8 0 Endloop Hours Worked Sat 0 0 Hours Worked Sun 0 0 45 Work Day constantarray Day ofBoolean True True True True True False False Tomorrow constantarray Day Tue Wed Thu Fri Sat Sun Mon 46 匿名类型 Examplesofobjectdeclarationswitharraytypedefinitions anonymous Grid array 1 80 1 100 ofBoolean Mix array ColorrangeRed Green ofBoolean A B array 1 80 1 100 ofBoolean ashorthand0fA array 1 80 1 100 ofBoolean B array 1 80 1 100 ofBoolean A B illegalA B Grid A B legal 47 可见正常情况下匿名类型的变量是无法和程序中的其它变量发生联系的 所以 在Ada语言中变量正常使用的前提是必须为它声明有名类型 Anonymoustypeandnamedtype的使用原则 该原则也适用于其它类型的问题 匿名类型 48 4 12 2动态数组 动态数组 N integer Inverse Matrix 1 N 1 N Nneednotbestatic 49 补充说明 C语言中Array类型 和函数类型 不能作为函数的返回类型 50 4 12 3操作 array作为整体参加操作Slice slidingS String 1 7 BARBARB S 4 7 S 1 4 51 对multidimensionalarrays采用row majororder 在与其它语言 如Fortran 混合编程时 可以采用适当的pragma提示编译器改用column majororder 4 12 4实现 52 C 语言的数组类型 rectangulararrays jaggedarray classTest staticvoidMain int a1 newint 1 2 3 int a2 newint 1 2 3 4 5 6 int a3 newint 10 20 30 int j2 newint 3 j2 0 newint 1 2 3 j2 1 newint 1 2 3 4 5 6 j2 2 newint 1 2 3 4 5 6 7 8 9 53 4 13指针类型 4 13 1指针概念 指针空挂与垃圾回收4 13 2C语言的指针类型4 13 3Ada的accesstype4 13 4C 语言的内存管理机制 54 4 13 1指针概念 指针空挂与垃圾回收 指针也是一种变量 其值是另一个变量的地址 空挂当某个对象已经不存在 而到达它的路径依然存在时 该路径即被挂空 本质上是一个生命期的问题 55 4 13 1指针概念 指针空挂与垃圾回收 2 垃圾回收当到达某个对象的所有路径均已消失 该对象即无法使用 该对象所占有的空间应该作为垃圾被回收 56 指针空挂和垃圾回收是两个相对的概念 指针空挂和垃圾回收的后果是不同的 垃圾不及时回收仅仅是消耗系统资源而已 在资源耗尽之前不会造成软件运行的错误 而指针空挂会很快导致软件运行错误 一般来说垃圾回收是操作系统的任务 解决指针空挂是语言的任务 57 4 13 2C语言的指针类型 C语言本身没有提供避免指针空挂的措施 没有考虑垃圾回收问题 指针在C语言中使用非常广泛 部分原因是指针有时是表达计算的最佳方法 部分原因是指针通常比其它方法可以生成更加高效 紧凑的代码 58 C语言中和指针使用有关的编码规范 形式 1 条目2 告警级别 error warning informational 3 理由4 实例 59 1不要修改指向未释放内存的指针告警级别 Warning 理由 可能会引起内存泄漏 对于堆变量的使用 我们采用以下约定 用于申请内存的那些指针代表该内存块 这些指针不可以被修改 最后这一块内存必须且只能通过这个指针释放 那些由其它指针赋值或取对象地址得到的指针被认为是中间变量式的指针 他们不代表相应的地址 我们也不用他们释放内存 60 2禁止使用不代表内存块的指针释放内存告警级别 Error 理由 如果使用不代表内存块的指针释放内存可能引起内存的不完全释放 越界释放 指针空挂 重复释放等问题 3从堆中申请的内存应该保存起始地址告警级别 Error 理由 如果不保存会引起内存丢失 因为我们无法释放该内存 例如 p newX n 2 一种改进方法是 q newX n p q 2 61 4尽量不要重复使用一个指针申请内存 虽然每次重复申请前都进行了释放 告警级别 Informational 理由 为了使每块堆空间有明确的代表指针 custodialpointer 我们建议一般不要使用一个指针重复申请内存 建立链表过程除外 5堆变量作用域结束时要释放相应的内存告警级别 Warning 理由 如果堆变量作用域结束时没有释放相应的内存 可能引起内存泄漏 62 6禁止将在内层申请的堆变量地址传给外层告警级别 Error 理由 将在内层申请的堆变量地址传给外层可能引起指针空挂 7memcopy和memmove中 源指针和目标指针的有效类型 effectivetype 要兼容 告警级别 Warning 8memcopy和memmove中最好整体操作 第三个参数的值等于源指针指向的对象的大小 告警级别 Informational 理由 向目的地址拷贝 移动 时 一般为整体操作 如果只有拷贝 移动 一部分 需要在文档中注明 63 9禁止内存越界使用告警级别 Error 理由 内存越界使用会引起非法操作异常 目前只能检测静态可识别的内存越界 10禁止向指针对象传送大小超过其申请范围的对象 一般来说是过大的数组 告警级别 Error 64 11禁止将内层自动变量的地址传给外层指针 包括两种情况 一种是以参数形式传回 另一种是通过return语句传出去 告警级别 Error 理由 会引起指针空挂 因为内层声明的自动变量在返回外层时自动释放 这样当外层再使用那个地址时就引起指针空挂 65 12禁止将一自动变量的地址赋给一静态变量告警级别 Error 理由 将一个自动变量的地址赋值给一个静态变量容易引起地址空挂 因为当函数返回时 静态变量还会存在 而自动变量将消逝 这样静态变量所指的变量已经释放 从而引起指针空挂 13禁止向指针或数组名赋负整数告警级别 Error 理由 内存不可能为负地址 14禁止取数组的地址告警级别 Error 理由 这种操作一般来说没有意义 66 15远 近指针相互转换告警级别 Warning 理由 可能会丢失或得到错误的地址信息 16取寄存器变量的地址告警级别 Error 理由 寄存器不在内存寻址范围内 17禁止没有左值的取地址操作告警级别 Error 理由 一元操作 必须有一个左值放在赋值号的左边用来存放地址 67 1不要修改指向未释放内存的指针2禁止使用不代表内存块的指针释放内存3从堆中申请的内存应该保存起始地址4尽量不要重复使用一个指针申请内存 虽然每次重复申请前都进行了释放 5堆变量作用域结束时要释放相应的内存6禁止将在内层申请的堆变量地址传给外层7memcopy和memmove中 源指针和目标指针的有效类型 effectivetype 要兼容 8memcopy和memmove中最好整体操作 第三个参数的值等于源指针指向的对象的大小 9禁止内存越界使用10禁止向指针对象传送大小超过其申请范围的对象 一般来说是过大的数组 11禁止将内层自动变量的地址传给外层指针12禁止将一自动变量的地址赋给一静态变量13禁止向指针或数组名赋负整数14禁止取数组的地址15远 近指针相互转换16取寄存器变量的地址17禁止没有左值的取地址操作 68 4 13 3Ada的accesstype 69 4 13 3 1设计目标 灵活性一致性 70 4 13 3 2Categoriesofaccesstypes1 accesstype accesstosubprogram general poolspecific accesstoobject accesstovariable accesstovariable accesstoconstant 71 4 13 3 3pool specificaccesstypes pool specificaccesstypesandstoragepool例 typeRef Int AisaccessInteger typeRef Int BisaccessInteger RA Ref Int A newInteger 10 RB Ref Int B newInteger 20 RA all RB all RA RB illegal 72 指向Poolspecificobjects的指针的释放 每一个poolspecificaccesstype对应一个pool 该类型的accessvariable都在且仅在该pool中申请空间 当程序运行超过了该类型的作用域时 将该pool中的所有object同时释放 73 理论依据 Poolspecificaccesstype也实行按名等价 所以 要真正使用poolspecificaccesstype必须首先声明有名的类型说明 Accessvariable的声明必须在相应的poolspecificaccesstype的声明之后 也就是说 这些accessvariable的作用域不可能超出相应的poolspecificaccesstype的作用域 74 当程序运行超出某poolspecificaccesstype的作用域时 也必然超出了该类型的accessvariable的作用域 这时 该pool中的所有objects都不可用 也没有用了 当然可以释放 当程序运行没有超出该作用域时 不释放pool中的动态对象 当然也就不会出现对象释放了但是引用路径 指针 没有释放的情况 即不会出现指针空挂现象 75 该方式没有对每个动态object进行及时释放 会造成少量的垃圾没有及时回收的情况 但是由于一般一个模块中申请的动态对象不会太多 所以此法不会造成严重问题 事实上 在军方的嵌入式系统中 一般硬件资源都比较紧张 该方法没有遇到明显的资源浪费问题 76 4 13 3 4generalaccesstype generalaccesstypes whosevaluescandesignatetheelementsofanystoragepool aswellasaliasedobjectscreatedbydeclarationsratherthanallocators andaliasedsubcomponentsofotherobjects 前提是必须在该component的说明前加aliased 77 4 13 3 5accessibility Thebasicruleisthatthelifetimeofanaccessedobjectmustbeatleastaslongasthatoftheaccessobject 各模块之间的调用关系形成了一个动态的层次嵌套关系 同一层的变量具有相同的生命期 78 这样 我们对变量生命期的比较就转换为对变量所在的模块的当次执行所在的层次的比较 于是 我们要求被引用对象所在的层次应该处于引用对象 指针 的外层或者同层 基于这种意义 我们把模块执行中的动态层次关系叫做引用层次 accesslevel 79 Ada语言要求在引用类型变量 指针 赋值和引用类型转换的过程中检查源操作数和目标操作数的accesslevel 当accesstype作为形参时必须是匿名类型 Accesslevel信息在引用类型变量赋值时的传递 为了实现静态检查 将规则改为 Thebasicruleisthatthelifetimeofanaccessedobjectmustbeatleastaslongasthatoftheaccesstype 80 例1 procedureMainisTypeAIisaccessallInteger Ref1 AI begindeclareRef2 AI I aliasedInteger beginRef2 I Access Ref1 Ref2 end declare someothervariablesbeginRef1 all 0 end endmain 81 例2 declaretypeAIisaccessallInteger I aliasedInteger RefI AI I Access begin declaretypeAJisaccessallInteger J aliasedInteger RefJ AJ J Access begin RefI AI RefJ illegal end end 82 4 13 3 6间接引用的对象的消亡 从以上分析可以看出 间接引用对象的消亡 其所占用空间的释放 由系统实现 这样大大减轻了程序员的负担 而且可以有效避免诸如指针空挂及反复释放同一存储空间等问题 83 4 13 3 7自由指针 unckecked deallocation 84 4 13 3 8类型转换的基本原则 不同的Poolspecifictype之间不允许 generalaccesstype之间 他们所指对象之间静态match 目标类型的life time必须nogreaterthan源类型 Poolspecifictogeneralaccesstype yes vice no 85 4 13 4C 语言的内存管理机制 C 语言的值类型和引用类型C supportstwokindsoftypes valuetypesandreferencetypes Valuetypesincludesimpletypes e g char int andfloat enumtypes andstructtypes Referencetypesincludeclasstypes interfacetypes delegatetypes andarraytypes 86 值类型的变量中直接存放该变量的数据 引用类型的变量中存放对其它对象的引用 两个引用类型的变量可能指向相同的对象 这样对一个引用变量的操作也就影响了另一个引用变量 对于值类型的变量来讲 每一个变量仅仅代表它自己 对一个值变量的操作不会影响到其它的变量 87 通俗地讲 多个引用变量可能代表的是同一份拷贝 而每个值变量仅仅代表它自己的拷贝 或者说