1、第6章第98页第6章 函数和过程程序表达的计算本身近似于代数演算，演算在符号上进行。只要给出实际的输入值即可得到输出值或所需要的计算机动作。一般说来，程序是通用的，适合于一组输入值。如果把程序中某一段实施某种功能的计算单独划出来，给它取个名字并给出本段所需的参数，即将名字束定于执行某种功能的代码块。在程序世界里这段程序叫子程序。50年代人们就理解了这种分割的好处：它实施的功能单一，便于调试；它相对独立，便于多人分工完成，且时间不受约束；它相对封闭，所有数据从接口出入，人们易于控制，是分解复杂性的有力措施。命令式语言中子程序有两种形式：函数(必须返回值)和过程(实施一组动作)，有时叫函数过程和子
2、例程subroutine。它们是程序的第一次分割。子程序开创程序世界里局部性、模块性的先河。由于子程序是程序的一个相对独立部分， 它和主程序联系的接口特别重要。在这个界面上要指出该例程的数据特征，即输入什么输出什么。而整个子程序体是完成从输入到输出的实现手段。因此，界面指出“做什么？”而子程序体回答“怎么做”。于是，在80年代程序完成第二次分割：将子程序定义(即界面)和子程序体显式的分开，成为相对独立的规格说明(Specification)和体(body)。这样在程序设计的早期只写规格，详细设计时再选算法、数据结构实现它的体。只要规格说明不变，即使过程体作重大的修改或换掉也不会影响整个程序系统
3、。Ada 和C+即是完成第二次分割的实例。本章我们首先研究函数和过程的定义和调用。关注的焦点在第二章中讨论，它们的接口和数据传送机制。原则上所有的程序值都可以作参数传递，第三节讨论实参求值策略，最后讨论参数本身为函数或返回值及函数的高阶函数。6.1 函数和过程抽象函数抽象是用一个简单的名字抽象代表一个函数。该函数由函数型构(Signature)和函数体(body)组成。函数计算的目的是求值。函数体等同于一个复合的表达式。所以，函数抽象是对表达式的抽象。同样，过程抽象是用一个简单的名字抽象代表一个计算过程。该过程由过程型构和过程体组成。过程调用的目的是执行一组命令以更新数据，过程抽象是对命令(即
4、语句)集的抽象。6.1.1 函数定义与引用函数定义定义了一个程序世界的函数，它有名字，输入、输出参数(组成函数型构)， 和实现函数从输入到输出的映射的函数体组成：function FUNC (fp1,fp2,.)：returntype; /函数型构B; /函数体，可包括任何声明和语句函数型构中fp1，fp2，为形式参数，也叫形式变元(argument).returntype为返回值类型，函数引用是应用函数的唯一手段，它在同名的函数名之下给出实在参数(实在变元)：第6章第99页FUNC (ap1,ap2,.);其应用过程是：先匹配函数名，找到函数定义模块，然后匹配形、实参数。匹配后程序控制转而执
5、行函数体。实参以形参别名参与运行直至函数体结束，或至显式的Return语句。主调程序的引用处此时得到一函数返回值。函数引用可出现在任何求值的表达式中。返回的参数值在程序的下文显式引用。(1) 函数定义的形式早期语言函数定义和子程序一样，都是过程的一种。但函数要返回值，于是函数名同时起到携带返回值的作用，函数返回值的类型加在函数关键字之前，如例6-1(a)。函数名至少要出现在赋值号之前一次；局部量和参数的类型在型构之后语句开始之前声明；至少要有一个RETURN语句。Pascal和Ada函数返回值的类型放在型构后，且参数类型在参数表中声明，和局部量声明明显分开，且Return只作中途返回之用，不用
6、Return从块末出口也可以。由于Pascal支持递归，它承袭了函数名至少在赋值号左边出现一次，于是造成名字含义不同，见例6-1(b)，左边的函数名是变量引用，右边是函数引用。Ada（见例6-1(d)）就避免了这个缺点：函数名仅仅是函数名，返回值由return关键字后跟的表达式表示，其求值结果为某个临时的中间变量，程序员不可见。return机制同pascal。这样，和充当块结束括号的关键字end分工也明确了(一指程序行文结束，一指执行结束)。C语言，见例6-1(c)，在函数型构和局部量声明的形式与Pascal同。用return加表达式指明返回值与Ada同。但由于C只有函数形式，若为主函数或过程
7、则无return语句，且缺省的函数返回值类型等同于int型。ANSI C和C+进一步吸取在参数表中指明参数类型的优点。例6-1 各种语言函数定义(a) FORTRAN的函数定义INTEGER FUNCTION FACT(N)INTEGER N,I,F /参数类型在此声明F = 1DO 10 I = 2,NF = F*110 CONTINUEFACT = F /必须至少定义函数名一次RETURN /至少有一返回语句END(b) Pascal的函数定义FUNCTION fact (n:Integer) :Integer;BEGINfact = 1;IF n = 1 OR n = 0 THENRet
8、urnELSEfact = n*fact(n-1) /两fact意义不同END.(c) C的函数定义int fact (n) /和fact(n)等效int n;int i, f;f = 1;if(n1)for (i = 2; iif n = 1 then 1 else n*fact (n-1)ML是函数式语言，见例6-1(e)，它的函数定义即为对表达式的求值.示例中给出函数抽象的型构后，函数体为一条件表达式。在函数引用处得该表达式结果值(临时中间变量传递)。参数类型在参数表中声明。即使是ML的值定义也用函数定义实现，因函数必然求值， 此时则用抽象符号fn代表函数，指明参数后用=带出函数体，以便
9、和=带出的函数定义的函数体区别。语义是一样的。(2) 引用或调用的形式函数引用源于代数中参数置换的思想。以同名的函数名带实参表，运行时置换形参表，谓之参数结合(association)。显然，形实参数表中元素个数，次序，类型应一致。早期语言都严格遵此准则。近代语言提供了较多的灵活表示法。例6-2 Ada的参数结合表示法本例为一自动洗衣机控制程序的函数型构部分。设事先已将CLOTH_TYPE(衣服类型)、SOIL_TYPE (弄脏类型)、ERROR_TYPE(错误类型)作了枚举类型定义。function WASH_CYCLE(WEIGHT : in INTEGER;FABRIC : in CLO
10、TH_TYPE = COTTONKNIT;SOIL_LEVER: in SOIL_TYPE = AVERAGE;DARK : in BOOLEAN = FALSE;DELICATE : in BOOLEAN = FALSE;) return ERROR_TYPE is其中五个形参四个给出初值。Ada允许以下引用：RESULT = WASH_CYCLE (5, WOOL, SLIGHT, TRUE);-5公斤毛织品，不太脏，深色，不娇贵的衣服-实参与形参按位置一一对应。最后一个有缺省值则不另重复。RESULT = WASH_CLCLE(10);-10公斤，棉织品，一般程度的脏，浅色，不娇贵-除第
11、一参数外其余全用缺省值RESULT = WASH_CYCLE(8, SOIL_LEVEL=FILTHY);-8公斤，棉织品，脏得很，浅色，不娇贵-第三个是指名参数结合，第一个按位，其余按缺省。RESULT = WASH_CYCLE(WEIGHT=2,DELICATE = TURE,SOIL_LEVEL = SLIGHT,FABRIC = WOOL,DARK = TRUE);-2公斤毛织品，深色，不太脏但娇贵-全部用指名结合，故参数次序可以随意颠倒。本例未用缺省值。除此而外，C语言允许任意多个参数的调用。例如，内定义函数printf()调用时可以写：第6章第101页printf(“The sum
12、 is %d and the average is %dn “,sum,sum/count);/第一参数中两个%d指明它有两个实参sum和sum/count。printf(“%3c %3c %3c %5d %l7e %l7en “,c1,c2,c3,k,x,y);/第一参数指明有六个实参要打印。c1，c2，c3是占3位的字符，/k为占5位的整数，x，y为占7位的长浮点数也就是说，它的参数个数随意，但必须和第一参数中格式符个数、位置对应。6.1.2 过程定义与调用过程子程序定义形式与函数定义极为相似：procedure PROC (fp1,fp2,.) /过程型构B; /子程序体包含局部声明对应
13、的过程调用是：PROC (ap1, ap2, .);早期语言在过程名前加关键字CALL，近代语言取消。过程子程序的调用与函数过程同。因不返回过程值， 故不能出现在表达式中，只能作为单独的命令(语句)。过程返回的修改值只能在参数表之中。因而参数表是它的输入/输出必由之路。既然有此区别，近代语言把函数和子程序的区别有意拉大，不主张对函数参数表的值作修改，只返回函数的结果值。如Ada函数的参数表只有输入模式(in)没有输出模式(out)。(1) 多重入口和指定返回早期语言强调算法，一个复杂的科学计算过程可以有上千语句。为了充分利用部分程序代码,FORTRAN设有ENTRY入口语句，如例6-3。例6-
14、3 FORTRAN 的多重入口示例SUBROUTINE DEG (R,THETA,X,Y)C = 3.14159/180.0THETA = C * THETAENTRY RAD (R,THETA,X,Y)X = R * COS(THETA)Y = R * SIN(THETA)RETURNEND若THETA是度数值时，则调用语句为：CALL DEG (R,THETA,X,Y) /入口在子程序顶部若THETA是弧度值时，则调用语句为：CALL RAD(R,THETA,X,Y) /入口在子程序中部这个子程序有两个入口，多一个ENTRY，当然可有多个入口。多重入口违背结构化一入口一出口的要求。FORT
15、RAN除了多重出口而外，还有指定返回，如下例：例6-4 FORTRAN指定返回的示例SUBROOTINE RM（X，Y，*，*，*）RETURN 2RETURN 1RETURN 3END主程序调用时CALL RM（A，B，70，80，120）第6章第102页本程序块中的语句标号END多个出口的多重返回直到近代语言都是允许的(为什么？)FORTRAN语言的规定把语句标号作形-实参数，依次RETURN i(i = 1， 2， 3，)返回到主调程序指定的实参标号上(按形参顺序)。即它调用后返回不一定是调用处，而可到任何指定的位置，但这种方便带来程序控制混乱，相当于goto语句。近代语言无论从哪个地方
16、返回都返回到调用处。（2）C语言的过程子程序C语言虽然没有子程序形式，一切过程，包括主程序都是函数过程。它以void(无值)关键字代替函数类型指明符，实施子程序过程语义。因而这些过程中没有return语句。有时程序员写一子程序过程忘了加上void，它仍会返回值1。因为缺省类型指明符的函数是int型， 执行成功又未指定返回什么，它就返回整数1。6.1.3 无参过程函数和过程的参数表均可为空。有的语言保留()，有的干脆只有一个名字。对于充作主程序的无参过程很好理解，它不被调用，只调用其它过程。然而，一般被调用的过程，若不给出调用参数那么两次调用不是同一结果吗？除了少数过程子程序每调用一次执行同样的
17、几个动作而外，一般无参过程也要更新过程内部的值。函数过程还会返回不同的值。其原因在于函数在包容它的主调程序的作用域之内，全局量在函数中有效。改变了全局量两次调用结果值当然不一样。这就是函数的副作用(side effect)。例6-5 有副作用的函数C在很大程度上利用函数副作用，例如，当需要跳过空白时写：while (c = getch() = )；当c为字符时出循环，若无副作用则为死循环。因第一次调用getch()为空白，永远为空白，才是无副作用的。再如，Ada中常用的随机数：function RANDOM return FLOAT range 0.01.0;引用时，若FIELD已声明为常量：
18、RESULT = RANDOM*FIELD;RANDOM若无副作用两次引用RESULT值不可能改变。如果在程序员没有想到的地方出现了函数副作用，则程序错误是极难查出的。无参函数极易产生副作用。当然有参函数也会产生副作用，即同样参数的两次调用结果值不一。读者能举出一例子吗？6.2 参数机制参数(parameter)因环境条件可变的值的系统，在函数或过程中，它既可以是常量也可是变量。给定一组参数值，函数或过程就有不同的计算(结果值)。我们把传递到函数或过程上的值叫做变元(argument)。相当于数学函数自变量取值。变元一般指实参。程序中哪些值可以作变元呢？应该说所有类型值均可作变元最好，但多数语
19、言不行。例如Pascal的文件类型值，Ada的函数或过程抽象及文件都不能作变元，其它初等量、复合量、指针、变量引用均可作变元。ML的任何值都可以作变元。由于前叙变量的时空特性，传递变元的形-实参数可以有许多不同的实现结合的办法， 即所谓参数机制。不同的机制使得同一函数得出不同计算结果，我们要仔细分析它们。为了简化我们函数引用都叫调用。把过程子程序叫过程。第6章第103页6.2.1 传值调用形参表和实参表不管表示法如何，它们在结合时类型、个数总要一一结合(用缺省值补足)。它们相结合最简单的办法是把实参值拷贝到形参上，所以也称为值调用(call-by-value)。值调用语义明晰，容易实现。结合步
20、骤是：1实参表达式先求值。2将值复制给对应的形参。显然，除指针指向的存储不复制而外(只复制指针值)，形参和实参有同样大小的存储。3过程运行后一般不再将改变了的形参值复制回实参。因实参如是表达式是复制不回去的。所以，实参成了只读参数。只读参数的好处是在子程序内对形参的任何修改都不会传到主调程序中，是限制函数副作用的最有力的机制，程序模块干净，数据出入清晰，但耗费存储。为了减少双倍的存储开销，对于大的链表和记录则以指针作为形实参。next value p2 A P1 形参 P2 /结合时P2指向A P2 = P2. next； /形参对指针作了修改,P2指向B P2.value：= R: /对所指
21、值也作修改 BR C D 图6-1 指针复制机制但在复制机制下，虽然子过程对指针值的任何修改都不会影响实参指针原有的指向，如图6-1,形参P2与P1结合后它指向主调程序链表。此时子程序第一语句将P2改为指向下一元素(值为B)，返回时P1仍指A处。然而，对形参指针指向的内容作了修改，是会影响到主调程序的数据值的。如例中把P2当前指的内容换成R，返回后链表中的B也被改为R了。我们用下例演示传值调用的图示6：例6-6 Pascal中的传值调用PROCEDURE test1(J2,A2:Integer;P2:list)BEGINWriteln(J2,A2,P2.value);J2 = J2 + 1;P
22、2 = P2.next;Writeln(J2,A2,P2.value)END.调用程序有：test1(J1,A1J1,P1.next);其调用图示如图6-2第6章第104页 J1 A1P1 1264530 * $/%test1 2 J2 A2P2 130指 针 束 定 图 6-2 传 值 调 用 图 示调用程序中J1，A1，P1束定于存储对象并赋初值如图示。J2，A2，P2编译后束定自己的存储对象，复制结合后按过程中语句第一次打印为：1 30 %第二次打印为：2 30 $返回后调用程序中值未变。6.2.2 传名调用传值调用只能返回单个的函数结果值（早期语言必须给函数名赋一次以上的值）。如果是个
23、交换两个数的过程，交换的结果无法返回。于是Algol想到传名。变元的名字就是地址。如果在过程内修改形参的值，它就按结合的变元的名字（地址）找出变元值修改之，返回后实参值不就改过了吗。Algol既实现传名也实现传值。传名在过程/函数中加工的就是实参已分配的值，因此不需付出双倍存储代价。但传名过程是虚实结合时将程序体中所有形参出现的地方均以实参变元名置换。在函数/过程执行中先换变元名再算值，这样出现几次算几次效率是低的。此外，如果计算变元表达式时（如数组元素）如对其他值有影响（即副作用），则副作用要扩大影响多次。图6-3和例6-7是图6-2和例6-6的同一题目的对比：例6-7 传名调用程序示例由于
24、Pascal无传名机制，此处作一点扩充：PROCEDURE test2(NAME J2,A2:Integer;NAME P2:List);函数体同test1执行同样调用：test2(J1,A1J1,P1.next);第6章第105页名结合后如右图所示，此时打印：1 30 %执行后J1的值为2，A12的值是45，将P1.next的指针换指下一个$值，结果是：2 45 %名调用在发明引用调用后已不再采用，但C语言的宏，在预处理宏扩展中仍按名调用。6.2.3 引用调用Algol 60的传名机制， 即将程序对象名字(地址)直接传给子程序。后来发现除了简单变量名外总会有副作用使程序难以控制， Pasca
25、l则采用引用调用(call_by_reference)或称地址调用(call_by_address)，即Pascal的VAR参数。引用参数传递的是存储对象。实参必须是变量名或能得出地址的表达式，它把实参名束定的存储对象改为形参名束定。引用参数实现时，编译器在子程序堆栈中设许多中间指针，将形参名束定于此指针，而该指针的值是实参变量的地址(在主程序堆栈框架内)，于是在子程序中每次对形参变量的存取都是自动地递引用到实参存储对象上。引用参数的束定实则是设常指针，对程序员是透明的。引用参数在子程序中占空间少，递引用比复制效率高，所有对形参变量的更改直接反映到实参存储对象上。这点和传名是一样的,只是减少了
26、不必要的副作用.图6-4和例6-6是前述问题的对比.例6-8 引用调用的Pascal过程PROCEDURE test3(VAR J2,A2:Integer;VAR P2:List);函数体同test1相应的调用程序是：test3(J1,A1J1,P1.next);其中J1、A1、P1取值和上例一样如下图。编译时J2、A2、P2在子程序中束定于三个指针对象，虚实结合时它们指向参数（填入地址），也就是完成了束定，执行test3的第一次打印是：1 30 %第二次打印是： 2 30 $运行后J1值变为2，P1的链表变为了虚线的。出了test3,该框架消失。* $/% test2 J2 A2 P2 J1
27、P1nextA1J图 6-3 传 名 调 用 图 示 J1 2 A1 P1 1264530第6章第106页FORTRAN所有的参数传递全是引用调用，C语言的数组参数也是，其它参数和Pascal一样由用户指定(VAR 或 VAR s,q:Integer).一看就知,x，y传值实现，它只读。s，q引用实现，可读/写。Ada倒反不限定如何实现它只规定参数模式in，out，inout， 即只读、只写、读写三种参数传递方向的模式(mode),这更有利于程序员控制程序的语义。表示法为：PROC_NAME (X,Y:in Real;S:inout Integer;Q:out Integer).in模式可不写
28、出(缺省)。函数只能有in的模式，过程都有，且出现次序不受限制。这样， x，y因在子程序中只读,传值实现可保证不受破坏。s读/写用引用实现，而q是只写参数，传值和引用都不能保证”只” 写。于是有返回调用(call_by_Return)机制。实现返回调用机制有两种办法:其一是复制。主调程序开设和返回数据一样大的实参空间，子程序运行完毕将局部变量写入只写参数，拷贝回去。另一种办法是引用实现将参数束定于实参变元,但增加”只写”保护。6.2.5 值-返回调用看起来返回调用似乎比引用调用笨拙,但是安全.特别是在多进程、并发程序。并发程 2 J1 A1P1 1264530 * $/%test1 J2 A2
29、P2 图 6-4 引 用 调 用 图 示第6章第107页序中引用机制的不安全可说明如下,若有两进程P1，P2都接受了实参变元ARG，作为写参数，则：. 若P1先执行完P2执行，ARG最终值按一般顺序执行理解，先是P1的，最后是P2的。. 若P1开始未完P2又开始了，P1结束后P2再结束，则P1对ARG的加工会被P2加工复盖， 则结果按P2。采用引用只写参数变成读/写参数,P2输出不可靠. 若P1开始未完又开始P2，但可能P2先结束再P1结束，则P2对ARG的加工为P1的加工复盖。结果按P1。同样结果,若采用返回机制时,得出的P1是可靠的。采用值与返回调用机制(call_by_value_and
30、_return)是把值引用和返回调用组合起来,以实现调用程序和被调用程序双向通道,这对于有多个存储器的多处理器系统和网络分布式系统值调用极度安全,返回调用可靠.有利于分布式并行计算的复杂性控制。在子程序执行期间因不是束定，形参变量的值不会中途改变，复制回去和拷贝进来处可设断点检查。因此，值与返回调用被认为比束定机制更适合于并发程序。6.2.6 指针参数指针作为参数其实现方式一般是复制机制，它复制的是地址(指针内容)。这样，主调程序的指针和子程序指针同指主调程序中的同一存储对象。指针调用(call_by_pointer)和引用调用都可以实现读-写参数。虽然它们都是用指针实现(一为显式、一为隐式)
31、的，但指针调用容易引起悬挂指针，而引用调用的隐式指针随引用块的堆栈帧消失而消失。相对安全。以下举例说明。例6-9 Pascal的引用调用和指针调用引用版： 交换两变量的内容PROCEDURE swap1( VAR a,b:Integer);VAR t:Integer;BEGINT = a; a = b; b = tEND;调用程序片断：j = 3; k = 5;swap1(j,k); /结果j = 5， k = 3主程序堆栈帧中有j = 3， k = 5，子堆栈帧中a，b 束定于j，k，并有局部量t， 执行后t中值为3。其图示读者可参照图6-4给出。指针版：同上题TYPE int_ptr = Integer;VAR jp, kp:int_ptr;PROCEDURE swap2 (a,b:int_ptr);VAR t:Integer;BEGINT = a; a= b; b= tEND;相应调用程序片断：NEW (jp); jp= 3;NEW (kp); kp= 5;Swap2(jp,kp);本程序调用图示如图6-6：
