Subprograms

1 .Chapter 9 Subprograms

2 .Augment Sebesta Material Programming Languages-Cheng (Fall 2004) http://www.cse.msu.edu/~cse452/Fall2004/Lectures/09-subprograms.ppt Subprograms – parameter passing https://www.cise.ufl.edu/class/cop5556sp16/Lecture_25.ppt Runtime Environment Concepts Chapter 7 of Compilers: Principles, Techniques and Tools , Aho , et al., Addison-Wesley

3 .Copyright © 2015 Pearson. All rights reserved. 1- 3 Chapter 9 Topics Fundamentals of Subprograms Design Issues for Subprograms Local Referencing Environments Runtime Environment Parameter-Passing Methods Parameters That Are Subprograms Calling Subprograms Indirectly Design Issues for Functions Overloaded Subprograms Generic Subprograms User-Defined Overloaded Operators Closures Coroutines

4 .Copyright © 2015 Pearson. All rights reserved. 1- 4 Introduction Two fundamental abstraction facilities Process abstraction Emphasized from early days Discussed in this chapter Data abstraction Emphasized in the1980s Discussed at length in Chapter 11

5 .Copyright © 2015 Pearson. All rights reserved. 1- 5 Fundamentals of Subprograms Each subprogram has a single entry point The calling program is suspended during execution of the called subprogram Control always returns to the caller when the called subprogram’s execution terminates

6 .Copyright © 2015 Pearson. All rights reserved. 1- 6 Basic Definitions A subprogram definition describes the interface to and the actions of the subprogram abstraction In Python, function definitions are executable; in all other languages, they are non-executable In Ruby, function definitions can appear either in or outside of class definitions. If outside, they are methods of Object . They can be called without an object, like a function In Lua, all functions are anonymous

7 .Copyright © 2015 Pearson. All rights reserved. 1- 7 Basic Definitions A subprogram call is an explicit request that the subprogram be executed A subprogram header is the first part of the definition, including the name, the kind of subprogram, and the formal parameters The parameter profile (aka signature ) of a subprogram is the number, order, and types of its parameters The protocol is a subprogram’s parameter profile and, if it is a function, its return type

8 .Copyright © 2015 Pearson. All rights reserved. 1- 8 Basic Definitions (continued) Function declarations in C and C++ are often called prototypes A subprogram declaration provides the protocol, but not the body, of the subprogram A formal parameter is a dummy variable listed in the subprogram header and used in the subprogram An actual parameter represents a value or address used in the subprogram call statement

9 .Copyright © 2015 Pearson. All rights reserved. 1- 9 Actual/Formal Parameter Correspondence Positional The binding of actual parameters to formal parameters is by position: the first actual parameter is bound to the first formal parameter and so forth Safe and effective Keyword The name of the formal parameter to which an actual parameter is to be bound is specified with the actual parameter Advantage : Parameters can appear in any order, thereby avoiding parameter correspondence errors Disadvantage : User must know the formal parameter’s names

10 .Keyword parameters example Copyright © 2015 Pearson. All rights reserved. 1- 10 sumer(length = my_length, list = my_array, sum = my_sum) where definition of sumer has formal parameters length, list, sum. The disadvantage to keyword parameters is that the user of the subpro- gram must know the names of formal parameters. Ada, Fortran 95+ and Python allow keyword and positional parameters can be mixed in a call, as in sumer(my_length, sum = my_sum, list = my_array)

11 .Copyright © 2015 Pearson. All rights reserved. 1- 11 Formal Parameter Default Values In certain languages (e.g., C++, Python, Ruby, PHP), formal parameters can have default values (if no actual parameter is passed) In C++, default parameters must appear last because parameters are positionally associated (no keyword parameters) pay = compute_pay(20000.0, tax_rate = 0.15) in Python Variable numbers of parameters C# methods can accept a variable number of parameters as long as they are of the same type—the corresponding formal parameter is an array preceded by params In Ruby, the actual parameters are sent as elements of a hash literal and the corresponding formal parameter is preceded by an asterisk. printf Has variable number of Parameters

12 .Variable Numbers of Parameters (continued) In Python, the actual is a list of values and the corresponding formal parameter is a name with an asterisk In Lua, a variable number of parameters is represented as a formal parameter with three periods; they are accessed with a for statement or with a multiple assignment from the three periods Copyright © 2015 Pearson. All rights reserved. 1- 12

13 .Copyright © 2015 Pearson. All rights reserved. 1- 13 The following example skeletal function definition and call illustrate the parameter structure of Ruby: list = [2, 4, 6, 8] def tester(p1, p2, p3, *p4) . . . end . . . tester(first, mon => 72, tue => 68, wed => 59, *list) Inside tester, the values of its formal parameters are as follows: p1 is first p2 is {mon => 72, tue => 68, wed => 59} p3 is 2 p4 is [4, 6, 8] Python supports parameters that are similar to those of Ruby.

14 .Copyright © 2015 Pearson. All rights reserved. 1- 14 Procedures and Functions There are two categories of subprograms Procedures are collection of statements that define parameterized computations Functions structurally resemble procedures but are semantically modeled on mathematical functions They are expected to produce no side effects In practice, program functions have side effects

15 .Copyright © 2015 Pearson. All rights reserved. 1- 15 Design Issues for Subprograms Are local variables static or dynamic? Can subprogram definitions appear in other subprogram definitions? What parameter passing methods are provided? Are parameter types checked? If subprograms can be passed as parameters and subprograms can be nested, what is the referencing environment of a passed subprogram?

16 .Copyright © 2015 Pearson. All rights reserved. 1- 16 Design Issues for Subprograms Are functional side effects allowed? What types of values can be returned from functions? How many values can be returned from functions? Can subprograms be overloaded? Can subprogram be generic? If the language allows nested subprograms, are closures supported?

17 .Copyright © 2015 Pearson. All rights reserved. 1- 17 Local Referencing Environments Local variables can be stack-dynamic - Advantages Support for recursion Storage for locals is shared among some subprograms Disadvantages Allocation/de-allocation, initialization time Indirect addressing Subprograms cannot be history sensitive Local variables can be static Advantages and disadvantages are the opposite of those for stack-dynamic local variables

18 .Local Referencing Environments: Examples In most contemporary languages, locals are stack dynamic In C-based languages, locals are by default stack dynamic, but can be declared static The methods of C++, Java, Python, and C# only have stack dynamic locals In Lua, all implicitly declared variables are global; local variables are declared with local and are stack dynamic Copyright © 2015 Pearson. All rights reserved. 1- 18

19 .Runtime Environment Prof. Steven A. Demurjian Computer Science & Engineering Department The University of Connecticut 371 Fairfield Way, Unit 2155 Storrs, CT 06269-3155 steve@engr.uconn.edu http://www.engr.uconn.edu/~steve (860) 486 - 4818

20 .Basic Definitions and Concepts Procedure Definition Declaration that has a Name and has a Body If Returns a value, then Function Procedure Definition Contains a Sequence of Identifiers Called the Formal Parameters Procedure Call Contains a List of Arguments passed to the Procedure or the Actual Parameters Information in Program can be Characterized Environment: Maps Name to Storage Loc (l-value) Store: Maps Location to Value it Contains (l-value to an r-value) Environment State Name Storage Value Compile Time Run Time

21 .A First Look at Activation Records Storage Organization for Program Execution Code Referenced by PC Global/Local Variables Static Data Area Stack Contains Set of Activation Records All Active Procedures and Functions Heap for Dynamic Memory Allocation Code Static Data Stack Heap

22 .A General Activation Record To the Calling Procedure Passed in to Procedure To Act. Record of Caller Referenced Non-Local Data Needed to Restart Caller Local Variables for Scope Compiler Generated Returned Value Actual Parameters Optional Control Link Temporaries Saved Machine Status Local Data Optional Access Link

23 .An Activation Record in C Actual Parameters Supplied by Caller Needed to Restart Caller Local Variables for Scope If Callee Calls Another Procedure/Function Etc. Incoming Param 2 Incoming Param 1 Saved State Info Temporary Storage Outgoing Parameters Local Variables

24 .Activation Records Procedure Activation Represents the Actions that Must Occur when a Caller Invokes a Callee: Transfer of Actuals into Formals by the Language’s Parameter Passing Mechanism Modification of Environment and State by Alloc of Memory for Variables that are Local to Callee Identification of the Control Return Point of Caller After Callee Complets Every Procedure Activation has Lifetime which is the Sequence of Steps (Code) of Procedure Body of Callee

25 .What are Possible Activations? Nested A calls B calls C Non-Overlapping A calls B B calls C Recursive A calls itself Concurrent A calls B (spawns process) A calls C (spawns process) B, C: execute in parallel and compete for Resources

26 .Activation Tree Graphical Representation of Activations over Time

27 .Copyright © 2015 Pearson. All rights reserved. 1- 40 Pass-by-Name (Inout Mode) By textual substitution Formals are bound to an access method at the time of the call, but actual binding to a value or address takes place at the time of a reference or assignment Allows flexibility in late binding Implementation requires that the referencing environment of the caller is passed with the parameter, so the actual parameter address can be calculated

28 .Call By Value Environment and State of Actual/Formals is Different Push on the stack a copy of the argument Size depends on argument type Any write operation overwrites the copy Copy automatically discarded on exit swap (x, y: integer); var temp: integer; begin temp := x; x := y; y := temp; end; . . . int a, b; . . . swap (a, b) Print(a, b) x and y are in callee’s activation record (scope) a and b are in caller’s activation record (scope) x y a b Do a and b Change?

29 .Call By Reference Actuals and Formals Refer to Same Storage Location Place the address of the actual on the stack A write operation simply follows the pointer Locations are Passed! Advantages? swap ( var x, y: integer); var temp: integer; begin temp := x; x := y; y := temp; end; . . . int a, b; . . . swap (a, b) Print(a, b) a and b are in caller’s activation record (scope) x y a b