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

《北航研究生课程程序语言设计原理教程第06章.ppt》由会员分享，可在线阅读，更多相关《北航研究生课程程序语言设计原理教程第06章.ppt（23页珍藏版）》请在三一办公上搜索。

1、第6章 函数和过程,命令式语言中子程序有两种形式：函数(必须返回值)也叫函数，过程(实施一组动作)也叫子例程subroutine。它们是程序的第一次分割，这种分割的好处：实施的功能单一，便于调试；相对独立，便于多人分工完成，且时间不受约束；相对封闭，人们易于控制，是分解复杂性的有力措施。子程序和主程序联系的接口特别重要。在这个界面上要指出该例程的数据特征，即输入什么输出什么。而整个子程序体是完成从输入到输出的实现手段。界面指出“做什么？”，而子程序体回答“怎么做”。80年代程序完成第二次分割：将子程序定义(即界面)和子程序体显式的分开，成为相对独立的规格说明(Specification)和体(

2、body)。,6.1 函数和过程抽象,函数抽象是用一个简单的名字抽象代表一个函数。函数由函数型构(Signature)和函数体(body)组成。函数计算的目的是求值。函数体等同于一个复合的表达式。函数抽象是对表达式的抽象过程抽象是用一个简单的名字抽象代表一个计算过程。过程由过程型构和过程体组成。过程调用的目的是执行一组命令过程抽象是对命令(即语句)集的抽象函数由函数型构和函数体组成。形式是：,function FUNC(fp1,fp2,.)：returntype；/函数型构 B;/函数体，可包括任何声明和语句 其中fp1，fp2，为形式参数，也叫形式变元(argument)returntype

3、 为函数返回值的类型 函数引用是应用函数的唯一手段，它在同名的函数名之下给出实 在参数(实在变元)：FUNC(ap1,ap2,.);,各种语言函数定义(a)FORTRAN INTEGER FUNCTION FACT(N)/前缀指明返回类型 INTEGER N,I,F/参数类型在此声明 F=1 DO 10 I=2,N F=F*1 10 CONTINUE FACT=F/必须至少定义函数名一次 RETURN/至少有一返回语句 END(b)Pascal FUNCTION fact(n:Integer):Integer；/参数类型在变元表中定义，BEGIN/后缀指明返回类型 fact=1；IF n=1

4、OR n=0 THEN Return ELSE Fact=n*fact(n-1)；/也要定义函数名 END,(c)C int fact(n)/前缀指明返回类型 int n;/参数在体中声名类型 int i,f;/ANSI C改参数原型 f=1;if(n1)for(i=2;i/用函数定义值 if n=1 then 1 else n*fact(n-1),续,多重入口和指定返回,FORTRAN 的多重入口示例 SUBROUTINE DEG(R,THETA,X,Y)C=3.14159/180.0 THETA=C*THETA ENTRY RAD(R,THETA,X,Y)X=R*COS(THETA)Y=R

5、*SIN(THETA)RETURN END若THETA是度数值时，则调用语句为：CALL DEG(R,THETA,X,Y)/入口在子程序顶部若THETA是弧度值时，则：CALL RAD（R，THERA，X，Y）/入口在子程序中,FORTRAN的指定返回SUBROUTINE RM（X，Y，*，*，*）.RETURN2/返回语句标号80.RETURN1/返回语句标号70.RETURN3/返回语句标号120.END CALL RM(A,B,70,80,120),形实参数表中元素个数，次序，类型应一致。早期语言都严格遵此准则。近代语言提供了较多的灵活表示法。Ada引入缺省参数，实参个数可少于形参个数；

6、指明参数结合不考虑次序；Ada引入参数模式in,out,inout指明只读，只写，读写参数。C语言允许任意多个参数的调用。如内定义函数printf()调用时可以写任意个输出，只是第一参数中的格式个数与参数个数对应。过程定义与调用 过程子程序定义形式 procedure PROC(fp1,fp2,.)/过程型构 B;/子程序体包含局声明 对应的过程调用是：PROC(ap1,ap2,.)；C语言一切过程，包括主程序都是函数过程。它以void(无值)关键字代替函数类型指明符，实施子程序过程语义,引用或调用的形式,无参过程,-函数和过程的参数表均可为空。有的语言保留()，有的只有一个名字。一般无参过程

7、也要更新过程内部的值。函数过程还会返回不同的值。全局量在函数中有效。改变了全局量两次调用结果值当然不一样。这就是函数的副作用(side effect)。-有副作用的函数 C 在很大程度上利用函数副作用，例如，当需要跳过空白时写：while(c=getch()=)；-Ada中常用的随机数：function RANDOM return FLOAT range 0.01.0;引用时，若FIELD已声明为常量：RESULT=RANDOM*FIELD；RANDOM若无副作用RESULT值不可能改变。,6.2 参数机制,语言中第一类对象均可作函数/过程参数。由于变量的时空特性，传递的形-实参数可以有许多不

8、同的实现结合的办法，即参数机制。,6.2.1 传值调用（call-by-value）,1实参表达式先求值2将值复制给对应的形参。形参和实参有同样大小的存储3过程运行后一般不再将改变了的形参值复制回实参,Pascal中的传值调用 PROCEDURE test1(J2,A2:Integer;P2:list)BEGINWriteln(J2,A2,P2.value);J2=J2+1;P2=P2.next;Writeln(J2,A2,P2.value)END.调用程序有：test1(J1,A1J1,P1.next);,第一次打印为：1 30%第二次打印为：2 30$,6.2.2 传名调用(call-by

9、-name),传名在过程/函数中加工的就是实参已分配的值，因此不需付出双倍存储代价。但传名过程的虚实结合是将程序体中所有形参出现的地方均以实参变元名置换。这样出现几次算几次效率是低的。传名调用程序示例由于Pascal无传名机制，此处作一点扩充：PROCEDURE test2(NAME J2,A2:Integer;NAME P2:List);函数体同test1执行同样调用：test2(J1,A1J1,P1.next);,名结合后打印：1 30%执行后结果是：2 45$,6.2.3 引用调用(call_by_reference),引用参数实现时，编译器在子程序堆栈中设许多中间指针，将形参名束定于此

10、指针，而该指针的值是实参变量的地址(在主程序堆栈框架内)，在子程序中每次对形参变量的存取都是自动地递引用到实参存储对象上。引用调用的Pascal示例：PROCEDURE test3(VAR J2,A2:Integer;VAR P2:List);函数体同test1相应的调用程序是：test3(J1,A1J1,P1.next);,第一次打印是：1 30%第二次打印是：2 30$,引用调用图示,6.2.4 参数模式与返回调用(call-by-return),显式指明参数传递模式,可以为编译实现提供信息 fun_name(x,y:Real;VAR s,q:Integer).x，y传值实现，它只读。s，

11、q引用实现，可读/写Ada只规定参数模式in，out，inout，传递方向的模式(mode)。由编译选择实现方式：proc_name(X，Y:in Real;S:inout Integer;Q:outInteger)in模式可不写出(缺省)。函数只能有in的模式，过程都有，且出现次序不受限制。x，y因在子程序中只读,传值实现可保证不受破坏。s读/写用引用实现，而q是只写参数，传值和引用都不能保证”只”写实现返回调用机制有两种办法:其一是复制。另一种办法是引用实现增加”只写”保护,6.2.5 值-返回调用（call-by-value-and-return）,是对by-reference的改进，因

12、多进程竞争数据资源时多重引用(束定)易于引起混乱,P2,返回值由P2定 返回值由P1定 正常顺序执行对于并发多任务宜只读只写 值与返回调用机制是把值调用和返回调用组合起来,实现调用程序双向通道,这对于有多个存储器的多处理器系统和网络分布式系统值调用极度安全在子程序执行期间因不是束定，形参变量的值不会中途改变，复制回去和拷贝进来处可设断点检查,P1,P2,P1,P2,P1,P2,6.2.6 指针参数（call_by_point）,指针作为参数其实现方式一般是复制机制，它复制的是地址(指针内容)注意和引用调用之同异,例：指针Pascal引用版：交换两变量的内容PROCEDURE swap1(VAR

13、 a,b:Integer)；VAR t:Integer;BEGIN T=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,指针版：变换两变量的内容 TYPE int_ptr=Integer;VAR jp,kp:int_ptr;PROCEDURE swap2(a,b:int_ptr);VAR t:Integer;BEGIN t=a;a=b;b=t END;相应调用程序片断：NEW(jp);jp=3;NEW(kp);kp=5;Swap2(jp,kp)

14、;,C语言的指针参数传递 void swap3(int*a,int*b)int t;t=*a;*a=*b;*b=t;形参是两指针，实参不用指针的版本：main()int j=3;k=5;/声明并初始化两整数 swap3(/类型匹配吗？,实参是指针的版本：main()int j=3,k=5;int*jp=,6.3 变元求值策略ML：fun sqr(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)

15、*(p+q)=(2+5)*(2+5)=(2+5)*7=49只在界面置换原表达式，何时用该值何时计算，相同的只算一次Church-Rosser性质:表达式的完全求值，仅当它前后一致地按正规顺序求值，几种求值方式得的结果应一致。若一表达式能以几种不同的求值次序求值（包括混合使用几种求值方案），则所有这些求值次序得到的结果值应该是一样的。,急求值是严格求值，对应值调用，最安全 fun cand(b1：bool，b2:bool)=if b1 then b2 else false有调用cand(n0，t/n0.5)若n=0，t=0.8若急求值，第二子表达式未结合即失败 正规求值，对应名调用，支持递归 i

16、f n0 then t/n 0.5 else false 上述调用等效代入置换后再求值cand=false 懒求值可实现短路求值也支持递归 上例用懒求值等效于正规求值 C、Ada，及近代函数式语言均采用懒求值,6.4 高阶函数,以函数或过程作为实参变元或返回值的函数或过程，我们统称高阶函数函数作为变元LISP有映射函数(mapping function)它把单目、双目运算扩充到多个数据对象的数组或表上。映射函数本身以简单运算函数和表(或数组)作实参变元,LISP 的mapcar函数设程序上文已有四个表 x:(4 9 16 25)，y:(1 2 3 4),z：NILw:(3 4 5)(2 1)(

17、7 9 3 6)。mapcar要求的实参函数用标记，则有：表达式 解释 返回表(mapcar+1 x)把加1函数用于x诸元素(5 10 17 26)(mapcar+x y)加对应诸元素(5 11 19 29)(mapcar+1 z)把加1函数用于空表 NIL(不知应加几次)(mapcar(lambda 把函数(3*a)-b)应用到x y(11 25 45 71)(a b)(-(*3 a)b)对应的元素上 x y)(mapcar caar w)消去每子表的头项两次并销毁(5(3 6)将一个函数作为参数传递给另一函数是十分容易实现的，只要传一个指向函数的指针（C）,C语言、C+其函数返回值可以是指

18、向函数的指针。但C和C+均不能在函数中创建一个函数并把它作为返回值返回。函数式语言作用于任何一变元返回值是新函数fun F(x)(y)(z)=F(x,y,z)=F1(y,z)=F2(z)=F3 F1 x=x0 x=x0 x=x0 y=y0 y=y0 F2 z=z0 即函数闭包,函数作为返回值,闭包(closure)是可用到表达式上的操作。闭包最有用和最容易理解的应用是部分参数化。例如，有n个变元的函数，我们将其中一个变元束定于局部定义的值上就得到一个n-1个变元的新函数。ML闭包的应用,fun powerC(n)(b)=if n=0 then 1.0 else b*powerC(n-1)(b)可以显式给出val sqr=powerC 2 and cube=powerC 3sqr(b)cube(b)b 3 显示的新函数闭包closure产生一系列函数如：f(a)(b)(c)，fa(b)(c)，fb(a)(c)，fc(b)(a)，fab(c)，fbc(a)，fca(b)，fabc,隐式返回函数,