ISBN 0-321-33025-0Chapter 10Chapter 10Chapter 10Chapter 10Implementing SubprogramsCopyright © 2006 Addison-Wesley. All rights reserved. 1-2Chapter 10 Topics• The General Semantics of Calls and Returns• Implementing “Simple” Subprograms• Implementing Subprograms with Stack-Dynamic Local Variables• Nested Subprograms• Blocks• Implementing Dynamic ScopingCopyright © 2006 Addison-Wesley. All rights reserved. 1-3The General Semantics of Calls and Returns• The subprogram call and return operations of a language are together called its subprogram linkage• A subprogram call has numerous actions associated with it– Parameter passing methods– Static local variables– Execution status of calling program– Transfer of control– Subprogram nestingCopyright © 2006 Addison-Wesley. All rights reserved. 1-4Implementing “Simple”Subprograms: Call Semantics• Save the execution status of the caller• Carry out the parameter-passing process• Pass the return address to the callee• Transfer control to the calleeCopyright © 2006 Addison-Wesley. All rights reserved. 1-5Implementing “Simple”Subprograms: Return Semantics• If pass-by-value-result parameters are used, move the current values of those parameters to their corresponding actual parameters• If it is a function, move the functional value to a place the caller can get it• Restore the execution status of the caller• Transfer control back to the callerCopyright © 2006 Addison-Wesley. All rights reserved. 1-6Implementing “Simple”Subprograms: Parts• Two separate parts: the actual code and the noncode part (local variables and data that can change)• The format, or layout, of the noncode part of an executing subprogram is called an activation record• An activation record instanceis a concrete example of an activation record (the collection of data for a particular subprogram activation)Copyright © 2006 Addison-Wesley. All rights reserved. 1-7An Activation Record for “Simple”SubprogramsCopyright © 2006 Addison-Wesley. All rights reserved. 1-8Code and Activation Records of a Program with “Simple”SubprogramsCopyright © 2006 Addison-Wesley. All rights reserved. 1-9Implementing Subprograms with Stack-Dynamic Local Variables• More complex activation record– The compiler must generate code to cause implicit allocation and de-allocation of local variables– Recursion must be supported (adds the possibility of multiple simultaneous activations of a subprogram)Copyright © 2006 Addison-Wesley. All rights reserved. 1-10Typical Activation Record for a Language with Stack-Dynamic Local VariablesCopyright © 2006 Addison-Wesley. All rights reserved. 1-11Implementing Subprograms with Stack-Dynamic Local Variables: Activation Record• The activation record format is static, but its size may be dynamic• The dynamic linkpoints to the top of an instance of the activation record of the caller• An activation record instance is dynamically created when a subprogram is called• Run-time stackCopyright © 2006 Addison-Wesley. All rights reserved. 1-12An Example: C Functionvoid sub(float total, int part){int list[4]; float sum;…}[4][3][2][1][0]Copyright © 2006 Addison-Wesley. All rights reserved. 1-13An Example Without Recursionvoid A(int x) {int y;...C(y);...}void B(float r) {int s, t;...A(s);...}void C(int q) {...}void main() {float p;...B(p);...}main calls BB calls AA calls CCopyright © 2006 Addison-Wesley. All rights reserved. 1-14An Example Without RecursionCopyright © 2006 Addison-Wesley. All rights reserved. 1-15Dynamic Chain and Local Offset• The collection of dynamic links in the stack at a given time is called the dynamic chain, or call chain• Local variables can be accessed by their offset from the beginning of the activation record. This offset is called the local_offset• The local_offset of a local variable can be determined by the compiler at compile timeCopyright © 2006 Addison-Wesley. All rights reserved. 1-16An Example With Recursion• The activation record used in the previous example supports recursion, e.g.int factorial (int n) {<-----------------------------1if (n <= 1) return 1;else return (n * factorial(n - 1));<-----------------------------2}void main() {int value;value = factorial(3);<-----------------------------3}Copyright © 2006 Addison-Wesley. All rights reserved. 1-17Activation Record for factorialCopyright © 2006 Addison-Wesley. All rights reserved. 1-18Nested Subprograms• Some non-C-based static-scoped languages (e.g., Fortran 95, Ada, JavaScript) use stack-dynamic local variables and allow subprograms to be nested• All variables that can be non-locally accessed reside in some activation record instance in the stack• The process of locating a non-local reference:1. Find the correct activation record instance2. Determine the correct offset within that activation record instanceCopyright © 2006 Addison-Wesley. All rights reserved. 1-19Locating a Non-local Reference• Finding the offset is easy• Finding the correct activation record instance– Static semantic rules guarantee that all non-local variables that can be referenced have been allocated in some activation record instance that is on the stack when the reference is madeCopyright © 2006 Addison-Wesley. All rights reserved. 1-20Static Scoping• A static chainis a chain of static links that connects certain activation record instances• The static link in an activation record instance for subprogram A points to one of the activation record instances of A's static parent• The static chain from an activation record instance connects it to all of its static ancestorsCopyright © 2006 Addison-Wesley. All rights reserved. 1-21Example Pascal Programprogram MAIN_2;var X : integer;procedure BIGSUB;var A, B, C : integer;procedure SUB1;var A, D : integer;begin { SUB1 }A := B + C; <-----------------------1end; { SUB1 }procedure SUB2(X : integer);var B, E : integer;procedure SUB3;var C, E : integer;begin { SUB3 }SUB1;E := B + A: <--------------------2end; { SUB3 }begin { SUB2 }SUB3;A := D + E; <-----------------------3end; { SUB2 }begin { BIGSUB }SUB2(7);end; { BIGSUB }beginBIGSUB;end; { MAIN_2 }Copyright © 2006 Addison-Wesley. All rights reserved. 1-22Example Pascal Program (continued)• Call sequence for MAIN_2MAIN_2 calls BIGSUBBIGSUB calls SUB2SUB2 calls SUB3SUB3 calls SUB1Copyright © 2006 Addison-Wesley. All rights reserved. 1-23Stack Contents at Position 1Copyright © 2006