K. Cooper, L. Torczon - Engineering a Compiler (2011 - 2nd edition) (798440), страница 70
Текст из файла (страница 70)
A procedure call transfers control from the call sitein the caller to the start of the callee; on exit from the callee, controlreturns to the point in the caller that immediately follows its invocation.If the callee invokes other procedures, they return control in the same way.Figure 6.1a shows a Pascal program with several nested procedures, whileFigures 6.1b and 6.1c show the program’s call graph and its executionhistory, respectively.The call graph shows the set of potential calls among the procedures.Executing Main can result in two calls to Fee: one from Foe and anotherfrom Fum. The execution history shows that both calls occur at runtime. Each6.2 Procedure Calls 273program Main(input, output);Mainvar x,y,z: integer;procedure Fee;var x: integer;Fiebegin { Fee }x := 1;Foey := x * 2 + 1end;Fumprocedure Fie;var y: real;procedure Foe;Feevar z: real;procedure Fum;(b) Call Graphvar y: real;begin { Fum }x := 1.25 * z;Fee;writeln(‘x = ’,x)end;begin { Foe }z := 1;Fee;Fumend;begin { Fie }Foe;writeln(‘x = ’,x)end;begin { Main }x := 0;Fieend.(a) Example Pascal Program1.2.3.4.5.6.7.8.9.10.Main calls FieFie calls FoeFoe calls FeeFee returns to FoeFoe calls FumFum calls FeeFee returns to FumFum returns to FoeFoe returns to FieFie returns to Main(c) Execution Historyn FIGURE 6.1 Nonrecursive Pascal Program and Its Execution History.of these calls creates a distinct instance, or activation, of Fee.
By the timethat Fum is called, the first instance of Fee is no longer active. It was createdby the call from Foe (event 3 in the execution history), and destroyed afterit returned control back to Foe (event 4). When control returns to Fee, fromthe call in Fum (event 6), it creates a new activation of Fee. The return fromFee to Fum destroys that activation.ActivationA call to a procedure activates it; thus, we call aninstance of its execution an activation.274 CHAPTER 6 The Procedure Abstraction(define (fact k)(cond[(<= k 1) 1][else (* (fact (sub1 k)) k)]))n FIGURE 6.2 Recursive Factorial Program in Scheme.When the program executes the assignment x := 1 in the first invocationof Fee, the active procedures are Fee, Foe, Fie, and Main.
These all lieon a path in the call graph from Main to Fee. Similarly, when it executesthe second invocation of Fee, the active procedures (Fee, Fum, Foe, Fie,and Main) lie on a path from Main to Fee. Pascal’s call and return mechanism ensures that, at any point during execution, the procedure activationsinstantiate some rooted path through the call graph.DivergeA computation that does not terminate normallyis said to diverge.Return addressWhen p calls q, the address in p where executionshould continue after p’s return is called itsreturn address.When the compiler generates code for calls and returns, that code must preserve enough information so that calls and returns operate correctly.
Thus,when Foe calls Fum, the code must record the address in Foe to which Fumshould return control. Fum may diverge, or not return, due to a runtime error,an infinite loop, or a call to another procedure that does not return. Still,the call mechanism must preserve enough information to allow execution toresume in Foe if Fum returns.The call and return behavior of alls can be modelled with a stack. AsFie calls Foe, it pushes the return address in Fie onto the stack. WhenFoe returns, it pops that address off the stack and jumps to the address.If all procedures use the same stack, popping a return address exposes thenext one.The stack mechanism handles recursion as well.
The call mechanism, ineffect, unrolls the cyclic path through the call graph and creates a distinctactivation for each call to a procedure. As long as the recursion terminates,this path will be finite and the stack of return addresses will correctly capturethe program’s behavior.To make this concrete, consider the recursive factorial computation shownin Figure 6.2. When invoked to compute (fact 5), it generates a series ofrecursive calls: (fact 5) calls (fact 4) calls (fact 3) calls (fact 2)calls (fact 1). At that point, the cond statement executes the clause for(<= k 1), terminating the recursion. The recursion unwinds in the reverseorder, with the call to (fact 1) returning the value 1 to (fact 2).
It, inturn, returns the value 2 to (fact 3), which returns 6 to (fact 4). Finally,(fact 4) returns 24 to (fact 5), which multiplies 24 times 5 to return theanswer 120. The recursive program exhibits last-in, first-out behavior, so thestack mechanism correctly tracks all of the return addresses.6.2 Procedure Calls 275Control Flow in Object-Oriented LanguagesFrom the perspective of procedure calls and returns, object-oriented languages (ools) are similar to alls. The primary differences between procedure calls in an ool and an all lie in the mechanism used to name thecallee and in the mechanisms used to locate the callee at runtime.More Complex Control FlowFollowing Scheme, many programming languages allow a program toencapsulate a procedure and its runtime context into an object called aclosure.
When the closure is invoked, the procedure executes in the encapsulated runtime context. A simple stack is inadequate to implement this controlabstraction. Instead, the control information must be saved in some moregeneral structure that can represent the more complex control-flow relationship. Similar problems arise if the language allows references to localvariables that outlast a procedure’s activation.SECTION REVIEWIn Algol-like languages, procedures are invoked with a call and theyterminate in a return, unless the procedure diverges. To translatecalls and returns, the compiler must arrange for the code to record, ateach call, the appropriate return address and to use, at each return, thereturn address that corresponds to the correct call.
Using a stack to holdreturn addresses correctly models the last-in, first-out behavior of returnaddresses.One key data structure used to analyze caller–callee relationships is thecall graph. It represents the set of calls between procedures, with anedge from Foe to Fum for each call site in Foe that invokes Fum. Thus, itcaptures the static relationship between callers and callees definedby the source code. It does not capture the dynamic, or runtime,relationship between procedures; for example, it cannot tell how manytimes the recursive factorial program in Figure 6.2 calls itself.Review Questions1. Many programming languages include a direct transfer of control,often called a goto.
Compare and contrast a procedure call and agoto.2. Consider the factorial program shown in Figure 6.2. Write down theexecution history of a call to (fact 5). Explicitly match up the callsand returns. Show the value of k and of the return value.Closurea procedure and the runtime context that definesits free variables276 CHAPTER 6 The Procedure Abstraction6.3 NAME SPACESScopeIn an Algol-like language, scope refers to a namespace.
The term is often used in discussions of thevisibility of names.In most procedural languages, a complete program will contain multiplename spaces. Each name space, or scope, maps a set of names to a set ofvalues and procedures over some set of statements in the code. This rangemight be the whole program, some collection of procedures, a single procedure, or a small set of statements. The scope may inherit some names fromother scopes. Inside a scope, the programmer can create names that are inaccessible outside the scope. Creating a name, fee, inside a scope can obscuredefinitions of fee in surrounding scopes, in effect making them inaccessibleinside the scope. Thus, scope rules give the programmer control over accessto information.6.3.1 Name Spaces of Algol-like LanguagesMost programming languages inherit many of the conventions that weredefined for Algol 60.
This is particularly true of the rules that govern thevisibility of names. This section explores the notion of naming that prevailsin alls, with particular emphasis on the hierarchical scope rules that applyin such languages.Nested Lexical ScopesLexical scopeScopes that nest in the order that they areencountered in the program are often calledlexical scopes.In lexical scoping, a name refers to the definitionthat is lexically closest to its use−−that is, thedefinition in the closest surrounding scope.Most alls allow the programmer to nest scopes inside one another.
Thelimits of a scope are marked by specific terminal symbols in the programming language. Typically, each new procedure defines a scope that coversits entire definition. Pascal demarcated scopes with a begin at the start andan end at the finish. c uses curly braces, { and }, to begin and end a block;each block defines a new scope.Pascal popularized nested procedures. Each procedure defines a new scope,and the programmer can declare new variables and procedures in each scope.It uses the most common scoping discipline, called lexical scoping. Thegeneral principle behind lexical scoping is simple:In a given scope, each name refers to its lexically closestdeclaration.Thus, if s is used in the current scope, it refers to the s declared in the currentscope, if one exists.
If not, it refers to the declaration of s that occurs in theclosest enclosing scope. The outermost scope contains global variables.To make lexical scoping concrete, consider the Pascal program shown inFigure 6.3. It contains five distinct scopes, one corresponding to the programMain and one for each of the procedures Fee, Fie, Foe, and Fum. Each procedure declares some set of variables drawn from the set of names x, y, and z.6.3 Name Spaces 277program Main0 (input, output);var x1 ,y1 ,z1 : integer;procedure Fee1 ;var x2 : integer;ScopexyzMainh1, 0ih2, 0ih1, 0ih1, 0ih1, 0ih1, 4ih1, 4ih2, 0ih2, 0ih4, 0ih1, 8ih1, 8ih1, 8ih3, 0ih3, 0iFeebegin { Fee1 }Fiex2 := 1;FoeFumy1 := x2 * 2 + 1end;(b) Static Coordinatesprocedure Fie1 ;var y2 : real;procedure Foe2 ;Mainvar z3 : real;procedure Fum3Feevar y4 : real;Fiebegin { Fum3 }x1 := 1.25 * z3 ;Fee1 ;Foewriteln(‘x = ’,x1 )end;Fumbegin { Foe2 }z3 := 1;(c) Nesting RelationshipsFee1 ;Fum3Mainend;begin { Fie1 }Foe2 ;FieFeewriteln(‘x = ’,x1 )end;Foebegin { Main0 }x1 := 0;Fie1Fumend.(a) Pascal Program(d) Calling Relationshipsn FIGURE 6.3 Nested Lexical Scopes in Pascal.The figure shows each name with a subscript that indicates its level number.Names declared in a procedure always have a level that is one more thanthe level of the procedure name.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
