上海交通大学：《编译原理》教学资源_第一周讲义_Parameter Passing Mechanisms

Parameter Passing Mechanisms CS308 Compiler Theory

Parameter Passing Mechanisms CS308 Compiler Theory

Terms and Definitions Formal Parameters:specified(together with type)when procedure is declared (a.k.a.formals) Actual Parameters:values which are passed to a procedure at call site (a.k.a.actuals) I-value:storage location represented by an expression (e.g.a register,a memory location,etc) r-value:value contained at the storage location ·I-andr-refer to the“left”and“right"side of an assignment int factorial((nt n) formal if (n =0)return 1; else return n factorial(n 1) } actual factorial(42) CS308 Compiler Theory 2

Terms and Definitions • Formal Parameters: specified (together with type) when procedure is d l d( k dec lare d (a. k.a. f l orma ls ) • Actual Parameters: values which are passed to a procedure at call site ( k a. k.a. act l ua ls ) • l-value: storage location represented by an expression (e.g. a register, a memory location etc) memory location, etc) • r-value: value contained at the storage location • l - and r - refer to the refer to the “left ” and “right ” side of an assignment side of an assignment int factorial(int n) { if (n == 0) return 1; else return n * factorial(n - 1); formal } … actual 2 factorial(42); CS308 Compiler Theory

Call-by-value Simplest possible approach: a formal is treated the same as a local (i.e.storage is allocated on the stack or in a register) the caller evaluates the actuals and passes the result to the callee Operations on the formals do not affect values in the stack frame of the caller,so the following will not work: void swap(int a,int b){ int temp; temp a;a =b;b temp; CS308 Compiler Theory 3

Call-by-value • Simplest possible approach: – a formal is treated the same as a local (i.e. storage is allocated on the stack or in a register) – the caller evaluates the actuals and passes the result to the callee • Operations on the formals Operations on the formals do not affect values in the stack frame of the affect values in the stack frame of the caller, so the following will not work: void swap( , ) { int a, int b) { int temp; temp = a; a = b; b = temp; } 3 CS308 Compiler Theory

Call-by-reference Also known as:call-by-address,call-by-location The location of the actual is passed,rather then its value: if the actual is a variable (i.e.corresponds to an assignable location in memory)its address is passed -if the actual is an expression,the expression is evaluated to a temporary location and the address of that location is passed (the compiler will warn you since this is not what you usually want) Operations on the formals do affect the values in the caller,so procedure swap now works: void swap(int&a,int&b){ int temp; temp =a;a =b;b temp; CS308 Compiler Theory 4

Call-by-reference • Also known as: call-by-address, call-by-location • The location of the actual is passed, rather then its value: – if the actual is a variable (i.e. corresponds to an assignable location in memory) its address is passed is passed – if the actual is an expression, the expression is evaluated to a temporary location and the address of that location is passed (the compiler will warn you since this is not what you usually want) usually want) • Operations on the formals do affect the values in the caller, so p ocedu e rocedure sw pa now wo s: rk void swap(int& a, int& b) { int temp; temp = a; a = b; b = temp; } 4 CS308 Compiler Theory

Copy-restore Also known as:copy-in copy-out,value-result Combination of call-by-value and call-by-reference: the actuals are evaluated before the call the expressions having only r-values, the expressions having l-values are passed by reference CS308 Compiler Theory 5

Copy-restore • Also known as: copy-in copy-out, value-result • Combination of call-by-value and call-by-reference: – the actuals are evaluated before the call – the e pressions ha ing onl r the expressions having only r-val es u , – the expressions having l-values are passed by reference 5 CS308 Compiler Theory

Call-by-Name The evaluation of actuals is delayed until their use in callee Can be thought of as in-line expansion (but isn't!) Can be implemented by using parameterless evaluation procedures (sometimes called thunks)that are created for each actual: int thunk 1()( return 1 2; } void foo(int a,int b){ int thunk 2()( …a…b… return 3; } } void foo(proc f,proc g){ fo0(1+2,3); …p()…q()… foo(thunk 1,thunk 2); CS308 Compiler Theory 6

Call-by-Name • The evaluation of actuals is delayed until their use in callee • Can be thought of as in-line expansion (but isn’t!) • Can be implemented by using parameterless evaluation procedures (sometimes called thunks) that are created for each actual: int thunk_1() { return 1 + 2; } void foo(int a, int b) { … a … b … } int thunk_2() { return 3; } … foo(1+2, 3); void foo(proc f, proc g) { … p() … q() … } … … foo(thunk_1, thunk_2); … 6 CS308 Compiler Theory

Procedures as Parameters Some languages(such as C and Scheme)proved first-class procedure values:such values may be stored in a variable or returned by functions This creates many run-time issues: int main(){ proc make incrementer(int n){ int incrementer(int x){ return x n; 3 return incrementer; } proc my incr make incrementer(42); int y my incr(5); CS308 Compiler Theory 7

Procedures as Parameters • Some languages (such as C and Scheme) proved first-class procedure values: such values may be stored in a variable or returned by functions • This creates many run-time issues: int main() { proc make incrementer(int n) { proc make _ incrementer(int n) { int incrementer(int x) { return x + n; } return incrementer; } … proc my incr make incrementer(42); proc my _ incr = make _ incrementer(42); int y = my_incr(5); } 7 CS308 Compiler Theory

Call Scenario Consider what happens when we call cllallllllllllllllllllllllle main () local:my incr local:y main ()'s stack frame is set up control link call to make_incrementer ( access link return from make incrementer ( formal:n -PROBLEM:can't call my_incr (because the stack frame in which n resides is destroyed!!! CS308 Compiler Theory

Call Scenario • Consider what happens when we call main(): i ()’ t kf i t local: my_incr local: y control link access link formal: n – main()’s stack frame is set up – call to make_incrementer() – return from make_incrementer() control link access link formal: n – PROBLEM: can’t call my_incr() because the stack frame in which n resides is destroyed!!! 8 CS308 Compiler Theory

Solutions Solution 1 (a la C):disallow nested procedures: when we have no nested procedures,we never access non-static non-locals and so we need not preserve our caller's stack frame Solution 2(a la Pascal):disallow returning procedures from the scope where they are created: when we call a procedure indirectly,we are guaranteed that the stack frames for scopes within which it is nested exist on stack this requires eliminating assignment of procedures to local variables,but allows for passing procedures as parameters Solution 3(a la Lisp/Scheme):use tree instead of stack for procedure's local data this creates a record for each procedure(called closure)when a procedure is defined(not when it is called) allocating closures is costly;freeing requires a garbage collector (to be discussed later in the course) CS308 Compiler Theory

Solutions • Solution 1 (a la C): disallow nested procedures: – when we have no nested procedures, we never access non-static non-locals and so we need not preserve our caller’s stack frame • Solution 2 (a la Pascal): disallow returning procedures from the scope Solution 2 (a la Pascal): disallow returning procedures from the scope where they are created: – when we call a procedure indirectly, we are guaranteed that the stack frames for scopes within which it is nested exist on stack – this requires eliminating assignment of procedures to local variables, but allows for passing procedures as parameters • Solution 3 (a la Lisp/Scheme): use tree instead of stack for procedure’s local data – this creates a record for each procedure (called closure) when a procedure is defined (not when it is called) – allocating closures is costly; freeing requires a garbage collector (to be discussed later in 9 the course) CS308 Compiler Theory

Implementing Object-Oriented Features CS308 Compiler Theory

Implementing Object-Oriented Features CS308 Compiler Theory