Kĩ thuật lập trình - Chapter 10: Function implementation

Programming Languages2nd editionTucker and NoonanChapter 10Function ImplementationIn theory, there is no difference between theory and practice, but not in practice. AnonymousContents10.1 Function Declaration and Call in Clite10.2 Completing the Clite Type System10.3 Semantics of Call and Return10.4 Formal Treatment of Types and Semantics10.1 Function Declaration and CallExample Clite Program Fig 10.1int h, i;void B(int w) { int j, k; i = 2*w; w = w+1;} void A(int x, int y) { bool i, j; B(h);}int main() { int a, b; h = 5; a = 3; b = 2; A(a, b);}10.1.1 Concrete Syntax Functions and Globals (new elements underlined) Program  { Type Identifier FunctionOrGlobal } MainFunction Type  int | boolean | float | char | voidFunctionOrGlobal  ( Parameters ) { Declarations Statements } | Global Parameters  [ Parameter { , Parameter } ] Global  { , Identifier } ; MainFunction  int main ( ) { Declarations Statements }Concrete Syntax (cont’d)Function Calls (new elements underlined) Statement  ; | Block | Assignment | IfStatement | WhileStatement | CallStatement | ReturnStatement CallStatement  Call ; ReturnStatement  return Expression ; Factor  Identifier | Literal | ( Expression ) | Call Call  Identifier ( Arguments ) Arguments  [ Expression { , Expression } ]10.1.2 Abstract Syntax Program = Declarations globals; Functions functions Functions = Function* Function = Type t; String id; Declarations params, locals; Block body Type = int | boolean | float | char | void Statement = Skip | Block | Assignment | Conditional | Loop | Call | Return Call = String name; Expressions argsExpressions = Expression* Return = Variable target; Expression result Expression = Variable | Value | Binary | Unary | CallAbstract Syntax for a Clite ProgramFig 10.4globals bodyProgramFunctionsDeclarationsFunctionFunctionFunctionint mainvoid Avoid B params locals bodyhiwA(a,b);a bi jx yw = w + 1;i = 2 * w;j kBlockCall10.2 Completing the Clite Type SystemType Rule 10.1 Every function and global id must be unique. E.g., h, i, A, B, and main are unique.Type Rule 10.2 Every function’s params and locals must have mutually unique id’s. E.g., function A’s locals and params have id’s x, y, i, and j.Type Rule 10.3 Every statement in the body of each function must be valid with respect to the function’s locals, params, and visible globals. Note: Combine with type rules in Chapter 6 (type systems) for the different statement types.Type Rules for Call and ReturnType Rule 10.4 A non-void function (except main) must have a Return statement, whose Expression must be the same type as the function.Type Rule 10.5 A void function cannot have a Return.Type Rule 10.6 Every Call Statement must identify a void function, and every Call Expression must identify a non-void function.Type Rule 10.7 Every Call must have the same number of args as the number of params in the function it identifies. Each such arg must have the same type as its corresponding param, reading from left to right.Type Rule 10.8 Every Call to a non-void function has the type of that function. The Expression in which the Call appears must be valid according to Type Rules 6.5 and 6.6. Type Rules for Sample ProgramType Rule 10.4 No return statement appears in main.Type Rule 10.5 No return statement appears in A or B.Type Rule 10.6 The Call Statement A(a,b) identifies the function void A(int x, int y)Type Rule 10.7 The Call Statement A(a,b) has two arguments, whose types (int) are the same as the parameters x and y.Type Rule 10.8 is not applicable. Example with Non-void Functionsint fibonacci (int n) { int fib0, fib1, temp, k; fib0 = 0; fib1 = 1; k = n; while (k > 0) { temp = fib0; fib0 = fib1; fib1 = fib0 + temp; k = k - 1; } return fib0;}int main () { int answer; answer = fibonacci(8);}Computing aFibonacci NumberFig 10.5Type Rules for Fibonacci programType Rule 10.4 return fib0; appears in int fibonacci (int n)Type Rule 10.5 is not applicableType Rule 10.6 The Call fibonacci(8) identifies the non-void function int fibonacci (int n)Type Rule 10.7 The Call fibonacci(8) has one argument, whose type (int) is the same as that of the parameter n.Type Rule 10.8 The Expression in which the Call fibonacci(8) appears is valid. 10.3 Semantics of Call and ReturnMeaning Rule 10.1 The meaning of a Call c to Function f has the following steps:Make an activation record and add f’s params and locals to it.Evaluate c’s args and assign those values to f’s corresponding params.If f is non-void, add a result variable identical with f’s name and type.Push the activation record onto the run-time stack.Interpret f’s body.Pop the activation record from the stack.If f is non-void, return the value of the result variable to the Expression where c appears.Example Program Trace (Fig 10.6)Calling Returning Visible Statemain , , , A , ,,, B , ,,, B , ,,, A , ,,, main , , , 10.3.1 Non-void FunctionsMeaning Rule 10.2 The meaning of a Return is the result of assigning the value of the result Expression to the result variable.Meaning Rule 10.3 The meaning of a Block is the aggregated meaning of its Statements when applied to the current state, up to and including the point where the first Return is encountered. Note: The first Return encountered terminates the body of a called function.Example Program Trace (Fig 10.7)Calling Returning Visible Statemain fibonacci , ,, ,, fibonacci , ,, , , main 10.3.2 Side-Effects RevisitedSide-effects can occur in Clite.E.g., in Figure 10.1, a call to B alters the value of global variable i.If B had been non-void, this side-effect could have subtly affected an expression like B(h)+i.In the semantics of Clite, evaluation of operands in a Binary is left-to-right. Thus, the result of B(h)+i is always the same, and always different from i+B(h).Side-effects often create distance between mathematics and programming. E.g., Clite expressions with + are clearly not commutative, while in mathematics they are.