北航研究生课程程序语言设计原理教程第章.ppt

第6章函数和过程 命令式语言中子程序有两种形式 函数 必须返回值 也叫函数 过程 实施一组动作 也叫子例程subroutine 它们是程序的第一次分割 这种分割的好处 实施的功能单一 便于调试 相对独立 便于多人分工完成 且时间不受约束 相对封闭 人们易于控制 是分解复杂性的有力措施 子程序和主程序联系的接口特别重要 在这个界面上要指出该例程的数据特征 即输入什么输出什么 而整个子程序体是完成从输入到输出的实现手段 界面指出 做什么 而子程序体回答 怎么做 80年代程序完成第二次分割 将子程序定义 即界面 和子程序体显式的分开 成为相对独立的规格说明 Specification 和体 body 6 1函数和过程抽象 函数抽象是用一个简单的名字抽象代表一个函数 函数由函数型构 Signature 和函数体 body 组成 函数计算的目的是求值 函数体等同于一个复合的表达式 函数抽象是对表达式的抽象过程抽象是用一个简单的名字抽象代表一个计算过程 过程由过程型构和过程体组成 过程调用的目的是执行一组命令过程抽象是对命令 即语句 集的抽象函数由函数型构和函数体组成 形式是 functionFUNC fp1 fp2 returntype 函数型构B 函数体 可包括任何声明和语句其中fp1 fp2 为形式参数 也叫形式变元 argument returntype为函数返回值的类型 函数引用是应用函数的唯一手段 它在同名的函数名之下给出实在参数 实在变元 FUNC ap1 ap2 各种语言函数定义 a FORTRANINTEGERFUNCTIONFACT N 前缀指明返回类型INTEGERN I F 参数类型在此声明F 1DO10I 2 NF F 110CONTINUEFACT F 必须至少定义函数名一次RETURN 至少有一返回语句END b PascalFUNCTIONfact n Integer Integer 参数类型在变元表中定义 BEGIN 后缀指明返回类型fact 1 IFn 1ORn 0THENReturnELSEFact n fact n 1 也要定义函数名END c Cintfact n 前缀指明返回类型intn 参数在体中声名类型inti f ANSIC改参数原型f 1 if n 1 for i 2 i 用函数定义值ifn 1then1elsen fact n 1 续 多重入口和指定返回 FORTRAN的多重入口示例SUBROUTINEDEG R THETA X Y C 3 14159 180 0THETA C THETAENTRYRAD R THETA X Y X R COS THETA Y R SIN THETA RETURNEND若THETA是度数值时 则调用语句为 CALLDEG R THETA X Y 入口在子程序顶部若THETA是弧度值时 则 CALLRAD R THERA X Y 入口在子程序中 FORTRAN的指定返回SUBROUTINERM X Y RETURN2 返回语句标号80 RETURN1 返回语句标号70 RETURN3 返回语句标号120 ENDCALLRM A B 70 80 120 形 实参数表中元素个数 次序 类型应一致 早期语言都严格遵此准则 近代语言提供了较多的灵活表示法 Ada引入缺省参数 实参个数可少于形参个数 指明参数结合不考虑次序 Ada引入参数模式in out inout指明只读 只写 读写参数 C语言允许任意多个参数的调用 如内定义函数printf 调用时可以写任意个输出 只是第一参数中的格式个数与参数个数对应 过程定义与调用过程子程序定义形式procedurePROC fp1 fp2 过程型构B 子程序体包含局声明对应的过程调用是 PROC ap1 ap2 C语言一切过程 包括主程序都是函数过程 它以void 无值 关键字代替函数类型指明符 实施子程序过程语义 引用或调用的形式 无参过程 函数和过程的参数表均可为空 有的语言保留 有的只有一个名字 一般无参过程也要更新过程内部的值 函数过程还会返回不同的值 全局量在函数中有效 改变了全局量两次调用结果值当然不一样 这就是函数的副作用 sideeffect 有副作用的函数C在很大程度上利用函数副作用 例如 当需要跳过空白时写 while c getch Ada中常用的随机数 functionRANDOMreturnFLOATrange0 0 1 0 引用时 若FIELD已声明为常量 RESULT RANDOM FIELD RANDOM若无副作用RESULT值不可能改变 6 2参数机制 语言中第一类对象均可作函数 过程参数 由于变量的时空特性 传递的形 实参数可以有许多不同的实现结合的办法 即参数机制 6 2 1传值调用 call by value 1 实参表达式先求值 2 将值复制给对应的形参 形参和实参有同样大小的存储 3 过程运行后一般不再将改变了的形参值复制回实参 Pascal中的传值调用PROCEDUREtest1 J2 A2 Integer P2 list BEGINWriteln J2 A2 P2 value J2 J2 1 P2 P2 next Writeln J2 A2 P2 value END 调用程序有 test1 J1 A1 J1 P1 next 第一次打印为 130 第二次打印为 230 王超 6 2 2传名调用 call by name 传名在过程 函数中加工的就是实参已分配的值 因此不需付出双倍存储代价 但传名过程的虚实结合是将程序体中所有形参出现的地方均以实参变元名置换 这样出现几次算几次效率是低的 传名调用程序示例由于Pascal无传名机制 此处作一点扩充 PROCEDUREtest2 NAMEJ2 A2 Integer NAMEP2 List 函数体同test1执行同样调用 test2 J1 A1 J1 P1 next 名结合后打印 130 执行后结果是 245 6 2 3引用调用 call by reference 引用参数实现时 编译器在子程序堆栈中设许多中间指针 将形参名束定于此指针 而该指针的值是实参变量的地址 在主程序堆栈框架内 在子程序中每次对形参变量的存取都是自动地递引用到实参存储对象上 引用调用的Pascal示例 PROCEDUREtest3 VARJ2 A2 Integer VARP2 List 函数体同test1相应的调用程序是 test3 J1 A1 J1 P1 next 第一次打印是 130 第二次打印是 230 引用调用图示 王超 6 2 4参数模式与返回调用 call by return 显式指明参数传递模式 可以为编译实现提供信息fun name x y Real VARs q Integer x y传值实现 它只读 s q引用实现 可读 写Ada只规定参数模式in out inout 传递方向的模式 mode 由编译选择实现方式 proc name X Y inReal S inoutInteger Q outInteger in模式可不写出 缺省 函数只能有in的模式 过程都有 且出现次序不受限制 x y因在子程序中只读 传值实现可保证不受破坏 s读 写用引用实现 而q是只写参数 传值和引用都不能保证 只 写实现返回调用机制有两种办法 其一是复制 另一种办法是引用实现增加 只写 保护 6 2 5值 返回调用 call by value and return 是对by reference的改进 因多进程竞争数据资源时多重引用 束定 易于引起混乱 P2 返回值由P2定返回值由P1定正常顺序执行对于并发多任务宜只读 只写值与返回调用机制是把值调用和返回调用组合起来 实现调用程序双向通道 这对于有多个存储器的多处理器系统和网络分布式系统值调用极度安全在子程序执行期间因不是束定 形参变量的值不会中途改变 复制回去和拷贝进来处可设断点检查 P1 P2 P1 P2 P1 P2 6 2 6指针参数 call by point 指针作为参数其实现方式一般是复制机制 它复制的是地址 指针内容 注意和引用调用之同异 例 指针Pascal引用版 交换两变量的内容PROCEDUREswap1 VARa b Integer VARt Integer BEGINT a a b b tEND 调用程序片断 j 3 k 5 swap1 j k 结果j 5 k 3 J 3 K 5 Caller frame a t b 3 Swapl frame 指针版 变换两变量的内容TYPEint ptr Integer VARjp kp int ptr PROCEDUREswap2 a b int ptr VARt Integer BEGINt a a b b tEND 相应调用程序片断 NEW jp jp 3 NEW kp kp 5 Swap2 jp kp 王超 C语言的指针参数传递voidswap3 int a int b intt t a a b b t 形参是两指针 实参不用指针的版本 main intj 3 k 5 声明并初始化两整数swap3 类型匹配吗 王超 实参是指针的版本 main intj 3 k 5 int jp 6 3变元求值策略ML funsqr n int n n若p 2 q 5有调用sqr p q sqr 2 5 7 7 49急求值 表达式先求值再入体 正规求值 p q p q 2 5 2 5 7 7 49按 演算 先置换原表达式 体中代入值计算懒求值 p q p q 2 5 2 5 2 5 7 49只在界面置换原表达式 何时用该值何时计算 相同的只算一次Church Rosser性质 表达式的完全求值 仅当它前后一致地按正规顺序求值 几种求值方式得的结果应一致 若一表达式能以几种不同的求值次序求值 包括混合使用几种求值方案 则所有这些求值次序得到的结果值应该是一样的 急求值是严格求值 对应值调用 最安全funcand b1 bool b2 bool ifb1thenb2elsefalse有调用cand n 0 t n 0 5 若n 0 t 0 8若急求值 第二子表达式未结合即失败 正规求值 对应名调用 支持递归ifn 0thent n 0 5elsefalse上述调用等效代入置换后再求值cand false 懒求值可实现短路求值也支持递归上例用懒求值等效于正规求值C Ada 及近代函数式语言均采用懒求值 6 4高阶函数 以函数或过程作为实参变元或返回值的函数或过程 我们统称高阶函数函数作为变元LISP有映射函数 mappingfunction 它把单目 双目运算扩充到多个数据对象的数组或表上 映射函数本身以简单运算函数和表 或数组 作实参变元 LISP的mapcar函数设程序上文已有四个表x 491625 y 1234 z NILw 345 21 7936 mapcar要求的实参函数用 标记 则有 表达式 解释 返回表 mapcar 1x 把加1函数用于x诸元素 5101726 mapcar xy 加对应诸元素 5111929 mapcar 1z 把加1函数用于空表 NIL 不知应加几次 mapcar lambda 把函数 3 a b 应用到xy 11254571 ab 3a b 对应的元素上 xy mapcar caarw 消去每子表的头项两次并销毁 5 36 将一个函数作为参数传递给另一函数是十分容易实现的 只要传一个指向函数的指针 C C语言 C 其函数返回值可以是指向函数的指针 但C和C 均不能在函数中创建一个函数并把它作为返回值返回 函数式语言作用于任何一变元返回值是新函数funF x y z F x y z F1 y z F2 z F3F1x x0 x x0 x x0y y0y y0F2z z0即函数闭包 函数作为返回值 闭包 closure 是可用到表达式上的操作 闭包最有用和最容易理解的应用是部分参数化 例如 有n个变元的函数 我们将其中一个变元束定于局部定义的值上就得到一个n 1个变元的新函数 ML闭包的应用 funpowerC n b ifn 0then1 0elseb powerC n 1 b 可以显式给出valsqr powerC2andcube powerC3sqr b cube b b3显示的新函数闭包closure产生一系列函数如 f a b c fa b c fb a c fc b a fab c fbc a fca b fabc 隐式返回函数