CS 345 slide 249 Spring 20055 April 2005Another motivation for macros: avoiding the cost offunction calls.Again, C++ provides an alternative:In-line expansion:If f is defined with an in-line specifier:inline int f(int x){return x+3;}then during compilation of calls of f,f(e) is compiled like (e)+3Consequences:•the run-time cost of a function call is eliminated•code optimization not hindered by call/returnbranchesNote that inline is (only) a recommendation tothe compiler.In-line expansion can replace lots of macro-expansion.inline’s advantages (compared to macros):1. types are checked properly2. names’ scopes are handled staticallyA needed improvement:inline should apply to individual calls ratherthan to definitions.(but this limitation is not hard to program around)CS 345 slide 250 Spring 20055 April 2005Lifetimes of variablesIn conventional languages from Algol–60 throughPascal and C to Oberon, C++, Java, and Haskell,•a global variable’s lifetime = the duration of its computation• each local variable or parameter’s lifetime begins when control enters its scope(e.g., when its procedure is called) ends when control leaves its scope(e.g., when its procedure returns)• space allocation for locals is LIFO stackExample:time: 012345678PPPPPPPPPQQQ QQQRS• between lifetimes, a local occupies no space (thiswas the original motivation)• locals’ values are not retained between lifetimes• Exception: static variables (C/C++ only) accessibility: local lifetime: globalA consequence of the LIFO allocation model is…CS 345 slide 251 Spring 20055 April 2005Recursion supportA procedure can call itself (directly or indirectly).Example:time: 012345678PPPPPPPPPQQQQQQQPPPPPQQQPEach invocation of a procedure gets its own set oflocal variables.Global variables, however, are shared among all ofthe invocations.CS 345 slide 252 Spring 20055 April 2005Implementation of procedures in C and PascalScope: variables can be declared either• global or• local to any compound statement(including —but not limited to— function bodies).if (E ) { int c[1000]; ... }else { double d[300], e[200]; ... }syntax compound statements areeither disjoint or strictly nested (like procedure activations). storage for all variable declarationscan be handled by stack allocation.Where is “the stack”? Typical storage layout: STATICglobal variables STACKlocal variables— free — HEAPdynamic structuresCS 345 slide 253 Spring 20055 April 2005Procedure calls in Pascal/C/C++/Java/…Typical implementation:Each procedure activation generates anActivation Record (a.k.a. “frame”)which is a contiguous block of storage• taken from freespace• “pushed” (by adjusting a pointer) onto the stackCS 345 slide 254 Spring 20055 April 2005The compiler translates…a local-variable reference offset ( address)(for each procedure, the offset for its firstlocal variable is 0)a parameter reference offset<0At procedure invocation:1. caller evaluates arguments, leaving values onstack2. caller saves minimal state information(including base, pc)3. callee saves other state information, requestsframe allocation from storage manager(if refused, abort )4. callee: base := base + base( base is precomputed by the compiler)5. callee body executes;address of local-variablei = base + offsetiAt procedure return:[1. callee copies return value over first parametervalue]2. callee restores state info saved in (3)3. callee restores base, pc.4. caller resumes executionCS 345 slide 255 Spring 20055 April 2005RecursionRecursive calls:Each invocation gets its own activation record,and its own copies of local variables.Tail recursion: supposegf0f1f2andf ’s last operation is another invocation of f.Then0. the return from f2 is followed immediately by the returnfrom f1, and then by the return from f0; f2 might as wellreturn directly to g;1. the value returned by f2 to f1 is returned to f0 andfinally to g; since f1 and f0 do nothing to the value, f2might as well return it directly to g.To save activation-record space:Use the same record for f0, f1, f2.How? By translating tail recursion to iteration.CS 345 slide 256 Spring 20055 April 2005Translating tail recursion to iterationExample:Recursive Iterative int f(int x, int y) { if(x==0) return y; return f(x-1,y+1); } ... z := f(3,2); int f(int x, int y) { L: if(x==0) return y; x:=x-1; y:=y+1; goto L; } ... z := f(3,2);Either way, x and y are bound to new valuesbefore each execution of body.Advantages of iteration over recursion:1. saves time for setting up and reclaimingactivation records2. shrinks space requirements from linear (withrespect to number of iterations) to constantFor a bigger example, see Sethi, Example
View Full Document