Programming Languages Implementation of Control Structures - Cao Hoàng Trụ

1 Programming Languages Implementation of Control Structures Cao Hoaøng Truï Khoa Coâng Ngheä Thoâng Tin Ñaïi Hoïc Baùch Khoa TP. HCM 2 Contents • Sequence control • Data control 3 Sequence Control • Expressions • Statements • Subprograms 4 Expressions • Control mechanism • Syntax • Execution-time representation • Evaluation 5 Control Mechanism • Functional composition: (A + B)*(C - A) * (+ (A, B), - (C, A)) 6 Syntax • Infix: A * B + C  binary operations only  computation order ambiguity 7 Syntax • Prefix:  ordinary * (+ (A, B), - (C, A))  Cambridge Polish (* (+ A B) (- C A))  Polish * + A B - C A 8 Syntax • Prefix:  different numbers of operands  ordinary/ Cambridge Polish: cumbersome with parentheses  Polish: number of operands known in advance 9 Syntax • Postfix:  ordinary ((A, B) +, (C, A) -) *  Polish A B + C A - *  suitable execution-time representation 10 Execution-Time Representation • Interpretation:  tree structures * + - A B C A  prefix or postfix 11 Execution-Time Representation • Compilation: machine code sequences PUSH A PUSH B ADD PUSH C PUSH A SUB MUL A A B A + B A + B C A + B C A A + B C - A (A+B)*(C-A) 12 Execution-Time Representation • Compilation: machine code sequences PUSH A PUSH B ADD PUSH C PUSH A SUB MUL A A B A + B A + B C A + B C A A + B C - A (A+B)*(C-A) A B + C A - * 13 Evaluation • No simple uniform evaluation rule is satisfactory: * + - A B C A 14 Evaluation • Side effects: A * FOO(X) + A + * A FOO(X) A 15 Evaluation • Side effects: A * B * C = 1020 * 10-20 * 10-20 (A * B) * C = 1 * 10-20 = 10-20 A * (B * C) = 1020 * 0 = 0 16 Evaluation • Short-circuit Boolean expressions: if (A = 0) or (B/A > C) then 17 Evaluation • Short-circuit Boolean expressions: if (A = 0) or else (B/A > C) then 18 Sequence Control • Expressions • Statements • Subprograms 19 Statements • GOTO • Sequencing • Selection • Iteration 20 GOTO GOTO L JMP L L 21 Sequencing begin S1; S2; Sn; end S1 codes S2 codes Sn codes 22 Selection if A = 0 then S1 else S2; S3; JEQ0 A L1 S2 codes JMP L2 S1 codes L1 S3 codes L2 • if: 23 Selection var E: 0..2; case E of 1: S1; 2: S2; else: S0 end; S3; JMP a+v E  v JMP L0 JMP L1 JMP L2 a S1 codes L1 • case: a+1 JMP L3 a+2 S2 codes JMP L3 S0 codes S3 codes L2 L0 JUMP table L3 24 Iteration for I := E1 to E2 do S; I := E1; L0: if I > E2 then GOTO L1; S; I := I + 1; GOTO L0; L1: • for: 25 Iteration while C do S; L0: if not(C) then GOTO L1; S; GOTO L0; L1: • while: 26 Iteration repeat S until C; L0: S; if not(C) then GOTO L0; • repeat: 27 Sequence Control • Expressions • Statements • Subprograms 28 Subprograms • Simple call-return • Recursive calls 29 Simple Call-Return • No recursive calls • Explicit calls • Complete execution • Immediate control transfer • Single execution sequence 30 Simple Call-Return call A I0 I1 call B I2 I3 end return I4 return MAIN A B 31 Simple Call-Return call A I0 I1 end MAIN local data MAIN I0 CIP (current instruction pointer) 32 Simple Call-Return call A I0 I1 call B I2 I3 end return MAIN A local data MAIN local data A I1 I2 CIP 33 Simple Call-Return call A I0 I1 call B I2 I3 end return I4 return MAIN A B local data MAIN local data A local data B I1 I3 I4 CIP 34 Recursive Calls call A I0 I1 call B I2 I3 end return I4 return MAIN A B call A I5 local data MAIN -- -- R0 I0 CIP R0 CEP (current environment pointer) 35 Recursive Calls call A I0 I1 call B I2 I3 end return I4 return MAIN A B call A I5 local data MAIN -- -- local data A R0 I1 R0 R1 I2 CIP R1 CEP 36 Recursive Calls call A I0 I1 call B I2 I3 end return I4 return MAIN A B call A I5 local data MAIN -- -- local data A R0 I1 local data B R1 I3 R0 R1 R2 I4 CIP R2 CEP 37 Recursive Calls call A I0 I1 call B I2 I3 end return I4 return MAIN A B call A I5 local data MAIN -- -- local data A R0 I1 local data B R1 I3 local data A R2 I5 R0 R1 R2 R3 I2 CIP R3 CEP 38 Recursive Calls call A I0 I1 call B I2 I3 end return I4 return MAIN A B call A I5 local data MAIN -- -- local data A R0 I1 local data B R1 I3 local data A R2 I5 R0 R1 R2 R3 I2 CIP R3 CEP Dynamic chain 39 Central Stack local data -- -- R0 I0 CIP R0 CEP call A I0 I1 end MAIN MAIN 40 Central Stack local data -- -- R0 I2 CIP R1 CEP call B I2 I3 return A MAIN local data R0 I1 R1 A call A I0 I1 end MAIN 41 Central Stack local data -- -- R0 I4 CIP R2 CEP call A I4 I5 return B MAIN local data R0 I1 R1 A local data R1 I3 R2 B call B I2 I3 return A 42 Central Stack local data -- -- R0 I2 CIP R3 CEP call A I4 I5 return B MAIN local data R0 I1 R1 A local data R1 I3 R2 B call B I2 I3 return A local data R2 I5 R2 A 43 Exercises • Illustrate the storage representation of A: array [0..1, 1..2, 1..3] of integer using the column-major order. Give the accessing formula for computing the location of A[I, J, K], supposing that the size of an integer is 2 bytes. 44 Exercises • Given the following program: program MAIN; function FAC(N: integer): integer; begin if N <= 1 then FAC := 1 else FAC := N * FAC(N - 1) end; begin write(FAC(3)) end. Illustrate the code segment and activation records of MAIN and FAC in the central stack during execution of the program. 45 Contents • Sequence control • Data control 46 Data Control • Basic concepts • Local data and environments • Shared data: dynamic scope • Shared data: block structure • Shared data: parameter transmission 47 Basic Concepts • Names • Referencing environments • Scope • Block structure 48 Names • Variable names • Formal parameter names • Subprogram names • Names for defined types • Names for defined constants 49 Referencing Environments • Association: Name --------> Data Object • Referencing environment = set of associations 50 Referencing Environments program MAIN; var X: integer; X := 0; object Association 51 Referencing Environments • Local • Non-Local • Global • Predefined 52 Local Environments program MAIN; var X: integer; procedure SUB1; var X: real; X := 1; object2 object1 53 Non-Local Environments program MAIN; var X: integer; procedure SUB1; var X: real; procedure SUB2; X := 2; object2 object1 54 Global Environments program MAIN; var X: integer; procedure SUB1; var X: real; procedure SUB3; X := 3; object2 object1 55 Predefined Environments program MAIN; var X: integer; X := MAXINT - 1; write(X) 65535 codes for “write” 56 Referencing Environments • Visibility of an association • Referencing operations • Local, non-local, global references 57 Visibility program MAIN; var X: integer; procedure SUB1; var X: real; X := 1; object2 object1 Hidden Visible 58 Referencing Operations • Name  Environment  Data Object 59 Referencing Operations program MAIN; var X: integer; procedure SUB1; var X: real; X := 1; object2 object1 X  (X  object2)  object2 60 Referencing Environments • Visibility of an association • Referencing operations • Local, non-local, global references 61 Local References program MAIN; var X: integer; procedure SUB1; var X: real; X := 1; object2 object1 X  (X  object2)  object2 62 Non-Local References program MAIN; var X: integer; procedure SUB1; var X: real; procedure SUB3; X := 2; object2 object1 X  (X  object2)  object2 63 Global References program MAIN; var X: integer; procedure SUB1; var X: real; procedure SUB2; X := 2; object2 object1 X  (X  object1)  object1 64 Basic Concepts • Names • Referencing environments • Scope • Block structure 65 Scope • The program part (text or execution) within which the binding is effective. 66 Dynamic Scope • The subprogram activations within which the association is effective. 67 Dynamic Scope program MAIN; var X: integer; procedure SUB1; var X: real; X := 1; procedure SUB2; X := 2; object1 MAIN SUB1 SUB2 68 Static Scope • The program text within which the declaration is effective. 69 program MAIN; var X: integer; X  integer procedure SUB1; var X: real; X := 1; procedure SUB2; X := 2; Static Scope 70 program MAIN; var X: integer; X  integer procedure SUB1; var X: real; X := 1; procedure SUB2; X := 2; Static Scope Static scopes define dynamic scopes 71 Static Referencing Environments • Local, non-local, global environments • Local, non-local, global references 72 Basic Concepts • Names • Referencing environments • Scope • Block structure 73 Block Structure program MAIN; procedure SUB1; procedure SUB3; procedure SUB4; procedure SUB2; MAIN SUB1 SUB3 SUB2 SUB4 74 Static Scope Rules 1. The declarations at the head of each block defines the local referencing environment for that block MAIN SUB1 SUB3 SUB2 SUB4 X: real 75 Static Scope Rules 2. If no local declarations exists, then refer to the nearest enclosing block having the declaration in need MAIN SUB1 SUB3 SUB2 SUB4 X: real X: integer X := 1 76 Static Scope Rules 3. Any local declaration of a block is hidden from its outer blocks MAIN SUB1 SUB3 SUB2 SUB4 X: real 77 Static Scope Rules 4. The block name is part of the local referencing environment of the containing block MAIN SUB1 SUB3 SUB2 SUB4 78 Data Control • Basic concepts • Local data and environments • Shared data: dynamic scope • Shared data: block structure • Shared data: parameter transmission 79 Local Data and Environments procedure SUB(X: integer); var Y: real; Z: array [1..3] of real; procedure SUB1; begin end; begin end; object2 SUB object2 object2 X Y Z SUB1 SUB1 code segment 80 Data Control • Basic concepts • Local data and environments • Shared data: dynamic scope • Shared data: block structure • Shared data: parameter transmission 81 Shared Data: Dynamic Scope program MAIN; procedure SUB1; var X, Y: real; procedure SUB2; var B, A, U, X: integer; procedure SUB3; var Z, Y, A, W, V: char; MAIN SUB1 SUB2 SUB3 82 Shared Data: Dynamic Scope program MAIN; procedure SUB1; var X, Y: real; procedure SUB2; var B, A, U, X: integer; procedure SUB3; var Z, Y, A, W, V: char; MAIN X Y SUB1 Return point 83 Shared Data: Dynamic Scope program MAIN; procedure SUB1; var X, Y: real; procedure SUB2; var B, A, U, X: integer; procedure SUB3; var Z, Y, A, W, V: char; MAIN X Y B A U X SUB1 SUB2 Return point Return point Dynamic chain 84 Shared Data: Dynamic Scope program MAIN; procedure SUB1; var X, Y: real; procedure SUB2; var B, A, U, X: integer; procedure SUB3; var Z, Y, A, W, V: char; MAIN X Y B A U Z Y A W V X SUB1 SUB2 SUB3 Return point Return point Return point Dynamic chain 85 Shared Data: Dynamic Scope program MAIN; procedure SUB1; var X, Y: real; procedure SUB2; var B, A, U, X: integer; procedure SUB3; var Z, Y, A, W, V: char; MAIN X Y B A U Z Y A W V X SUB1 SUB2 SUB3 Return point Return point Return point Dynamic chain 86 Shared Data: Dynamic Scope program MAIN; procedure SUB1; var X, Y: real; procedure SUB2; var B, A, U, X: integer; procedure SUB3; var Z, Y, A, W, V: char; MAIN X Y SUB1 Return point A B U V W X Y Z Central table 0 0 0 0 0 1 1 0 87 Shared Data: Dynamic Scope program MAIN; procedure SUB1; var X, Y: real; procedure SUB2; var B, A, U, X: integer; procedure SUB3; var Z, Y, A, W, V: char; MAIN X Y B A U X SUB1 SUB2 Return point Return point A B U V W X Y Z Central table 1 1 1 0 0 1 1 0 88 Shared Data: Dynamic Scope program MAIN; procedure SUB1; var X, Y: real; procedure SUB2; var B, A, U, X: integer; procedure SUB3; var Z, Y, A, W, V: char; MAIN X Y B A U Z Y A W V X SUB1 SUB2 SUB3 Return point Return point Return point Central table 1 1 1 1 1 1 1 1 A B U V W X Y Z 89 Shared Data: Dynamic Scope MAIN X Y SUB1 Return point Central table 0 0 0 0 0 1 1 0 Hidden stack A B U V W X Y Z 90 Shared Data: Dynamic Scope MAIN X Y B A U X SUB1 SUB2 Return point Return point Central table 1 1 1 0 0 0 0 0 Hidden stack X 1 1 1 1 0 0 0 A B U V W X Y Z 91 Shared Data: Dynamic Scope MAIN X Y B A U X SUB1 SUB2 Return point Return point Central table 1 1 1 0 0 0 0 0 Hidden stack X 1 1 1 1 0 0 0 A B U V W X Y Z Z Y A W V SUB3 Return point Y A 92 Data Control • Basic concepts • Local data and environments • Shared data: dynamic scope • Shared data: block structure • Shared data: parameter transmission 93 Shared Data: Block Structure program MAIN; var X, Y, Z: char; procedure SUB2; var X, Y: integer; procedure SUB3; var X: real; procedure SUB4; procedure SUB1; var Y, Z: integer; MAIN X, Y, Z: char SUB2 X, Y: integer SUB3 X: real SUB1 Y, Z: integer SUB4 94 Block Structure: Compile Time program MAIN; var X, Y, Z: char; procedure SUB2; var X, Y: integer; procedure SUB3; var X: real; procedure SUB4; procedure SUB1; var Y, Z: integer; Symbol table X 1 1 1 1 0 0 0 Y Z Scope stack 1 1 1 0 0 0  MAIN 95 Block Structure: Compile Time program MAIN; var X, Y, Z: char; procedure SUB2; var X, Y: integer; procedure SUB3; var X: real; procedure SUB4; procedure SUB1; var Y, Z: integer; Symbol table X 1 1 1 1 0 0 Y Z Scope stack 1 1 1 0 0 0  SUB2 X Y 96 Block Structure: Compile Time program MAIN; var X, Y, Z: char; procedure SUB2; var X, Y: integer; procedure SUB3; var X: real; procedure SUB4; procedure SUB1; var Y, Z: integer; Symbol table X 1 1 1 1 0 0 Y Z Scope stack 1 1 1 0 0 0  SUB3 X Y 1 X 97 Block Structure: Compile Time program MAIN; var X, Y, Z: char; procedure SUB2; var X, Y: integer; procedure SUB3; var X: real; procedure SUB4; procedure SUB1; var Y, Z: integer; Symbol table X 1 1 1 1 0 0 Y Z Scope stack 1 1 1 0 0 0  SUB4 X Y 1 X 98 Block Structure: Compile Time program MAIN; var X, Y, Z: char; procedure SUB2; var X, Y: integer; procedure SUB3; var X: real; procedure SUB4; procedure SUB1; var Y, Z: integer; Symbol table X 1 1 1 1 0 0 Y Z Scope stack 1 1 1 0 0 0 SUB4  X Y 1 X 99 Block Structure: Compile Time program MAIN; var X, Y, Z: char; procedure SUB2; var X, Y: integer; procedure SUB3; var X: real; procedure SUB4; procedure SUB1; var Y, Z: integer; Symbol table X 1 1 1 1 0 0 Y Z Scope stack 1 1 1 0 0 0 SUB3  X Y 1 X 100 Block Structure: Compile Time program MAIN; var X, Y, Z: char; procedure SUB2; var X, Y: integer; procedure SUB3; var X: real; procedure SUB4; procedure SUB1; var Y, Z: integer; Symbol table X 1 1 1 0 0 Y Z Scope stack 1 1 1 0 0 0 SUB2  X 1 X 101 Block Structure: Compile Time program MAIN; var X, Y, Z: char; procedure SUB2; var X, Y: integer; procedure SUB3; var X: real; procedure SUB4; procedure SUB1; var Y, Z: integer; Symbol table X 1 1 1 0 0 Y Z Scope stack 1 1 1 0 0 0  SUB1 X 1 X Y Z 102 Block Structure: Compile Time program MAIN; var X, Y, Z: char; procedure SUB2; var X, Y: integer; procedure SUB3; var X: real; procedure SUB4; procedure SUB1; var Y, Z: integer; Symbol table X 1 1 0 0 Y Z Scope stack 1 1 1 0 0 0 SUB1  1 X 103 Block Structure: Run Time program MAIN; var X, Y, Z: char; procedure SUB2; var X, Y: integer; procedure SUB3; var X: real; procedure SUB4; procedure SUB1; var Y, Z: integer; MAIN SUB1 SUB2 SUB3 104 Block Structure: Run Time program MAIN; var X, Y, Z: char; procedure SUB2; var X, Y: integer; procedure SUB3; var X: real; procedure SUB4; procedure SUB1; var Y, Z: integer; Y Z MAIN X -- 105 Block Structure: Run Time program MAIN; var X, Y, Z: char; procedure SUB2; var X, Y: integer; procedure SUB3; var X: real; procedure SUB4; procedure SUB1; var Y, Z: integer; Y Z SUB1 SCP Static chains Y Z MAIN X -- RP 106 Block Structure: Run Time program MAIN; var X, Y, Z: char; procedure SUB2; var X, Y: integer; procedure SUB3; var X: real; procedure SUB4; procedure SUB1; var Y, Z: integer; Y Z X Y SUB1 SUB2 SCP Static chains Y Z MAIN X -- RP SCP RP 107 Block Structure: Run Time program MAIN; var X, Y, Z: char; procedure SUB2; var X, Y: integer; procedure SUB3; var X: real; procedure SUB4; procedure SUB1; var Y, Z: integer; Y Z X Y X SUB1 SUB2 SUB3 SCP Static chains Y Z MAIN X -- RP SCP RP SCP RP 108 Block Structure: Run Time A B MAIN A B MAIN C A B C A B MAIN C A B C A B 109 Block Structure: Run Time Y Z X Y X SUB1 SUB2 SUB3 SCP Active static chain Y Z MAIN X -- RP SCP RP SCP RP Display 1 1 1 0 0 1 2 loc Y = Display[1] + offset 110 Data Control • Basic concepts • Local data and environments • Shared data: dynamic scope • Shared data: block structure • Shared data: parameter transmission 111 Parameter Transmission • Parameters:  formal parameters  actual parameters • Transmission:  by reference  by value 112 Parameter Transmission procedure SUB2(K: integer; var L: integer); begin K := K + 10; L := L + 10; write(K, L) end; procedure SUB1; begin I := 1; J := 2; SUB2(I, J); write(I, J) end; I J K L SUB1 SUB2 SCP RP SCP RP 1 2 1 113 Parameter Transmission procedure SUB2(K: integer; var L: integer); begin K := K + 10; L := L + 10; write(K, L) end; procedure SUB1; begin I := 1; J := 2; SUB2(I, J); write(I, J) end; I J K L SUB1 SUB2 SCP RP SCP RP 1 2 11 114 Parameter Transmission procedure SUB2(K: integer; var L: integer); begin K := K + 10; L := L + 10; write(K, L) end; procedure SUB1; begin I := 1; J := 2; SUB2(I, J); write(I, J) end; I J K L SUB1 SUB2 SCP RP SCP RP 1 12 11 115 Parameter Transmission procedure SUB2(K:integer; var L:integer); begin K := K + 10; L := L + 10; SUB3(K, L) write(K, L) end; procedure SUB1; begin I := 1; J := 2; SUB2(I, J); write(I, J) end; procedure SUB3(var M, N: integer); begin M := M + 10; N := N + 10; write(M, N) end; Actual parameters are formal parameters of the calling program 116 Parameter Transmission type VECT = array [1...3] of integer; procedurre SUB2 (C:VECT; var D:VECT); var I : integer; begin C [2] : = C [2] + 10; D [2] = D [2] + 10; for I : = 1 to 3 do write (C [I]); for I : = 1 to 3 do write (D [I]) end; procedurre SUB1; var A, B : VECT; J : integer; begin A [1] : = 7; A [2] = 8; A [3] : = 9; B [1] : = 7; B [2] = 8; B [3] : = 9; SUB2 (A, B); for J : = 1 to 3 do write (A [J]); for J : = 1 to 3 do write (B [J]); end; Actual parameters are structured data objects 117 Parameter Transmission type VECT = array [1...3] of integer procedurre SUB2 (I: integer; var J: integer); begin I : = I + 10; J : = J + 10; write (I, J); end; procedurre SUB1; var A : VECT; K : integer; begin A [1] := 7; A [2] := 8; A [3] := 9; SUB2 (A[1], A[2]); for K := 1 to 3 do write (A[K]) end; Actual parameters are components of structured data objects 118 Parameter Transmission type VECT = array [1...3] of integer procedurre SUB2 (var I, J: integer); begin I : = I + 1; J : = J + 1; write (I, J); end; procedurre SUB1; var A : VECT; K : integer; begin A [1] := 7; A [2] := 8; A [3] := 9; K := 2; SUB2 (K, A[K]); for K := 1 to 3 do write (A[K]) end; Actual parameters are array components with computed subscripts 119 Parameter Transmission type VECT = array [1...3] of integer; VECTPTR = ^ VECT; procedurre SUB2 (R:VECTPTR; var S:VECTPTR); begin R^[1] := R^[1] + 10; S^[1] := S^[1] + 10; if . . . then R := S else S := R end; procedurre SUB1; var A, B: VECT; P, Q: VECTPTR; begin A [1] = 7; A [2] := 8; A [3] := 9; B [1] := 7; B [2] := 8; B [3] := 9; P := @A; Q := @B; SUB2 (P, Q); end; Actual parameters are pointers 120 Parameter Transmission program MAIN; var X: real; procedurre SUB2 (X, Y: real; function F(U:real): real); var Z: real; begin Z := abs (Y - X); Z := (F(X) + F(Y)) * Z/2; write (Z) end; begin X := 3; SUB1 end. procedurre SUB1; var Y: real; function FUNC(V:real): real; begin FUNC := X*V + Y end; begin Y := 1; SUB2 (0, 1, FUNC). end; Actual parameters are subprograms 121 Parameter Transmission type VECT = array [1...3] of integer procedurre SUB2 (name I, J: integer); begin I : = I + 1; J : = J + 1; write (I, J); end; procedurre SUB1; var A : VECT; K : integer; begin A [1] := 7; A [2] := 8; A [3] := 9; K := 2; SUB2 (K, A[K]); for K := 1 to 3 do write (A[K]) end; Transmissiom by names 122 Formal Parameters and Aliases • A data object may have more than one name, called aliases. • Side effects: I := 1; J := 1; I := J + 10; J := J*10; 123 Formal Parameters and Aliases • An actual parameter is a non-local variable and is trasmitted by reference. • Actual parameters are of the same data object and transmitted by reference. 124 Exercises • Given the following program: program MAIN; var F: real; procedure PROC(N: integer; var F: real); var F1, F2: real; begin if (N = 0) or (N = 1) then F := 1 else begin PROC(N-1, F1); PROC(N-2, F2); F := F1 + F2 end end begin PROC(2, F); write(F) end. 125 Exercises • Illustrate the code segment and activation records of MAIN and PROC. • Illustrate the central stack during execution of this program.