Control Structures

Principles of Programming Languages Control Structures

Outline     

Sequence Control Activation & Activation Record Central Stack Dynamic Scope and Referencing Environment Parameter Passing Mechanisms

Sequence Control •

Expressions

•

Statements

•

Subprograms

Expressions •

Control mechanism

•

Syntax

•

Execution-time representation

•

Evaluation

Control Mechanism •

Functional composition: (A + B)*(C - A) * (+ (A, B), - (C, A))

Syntax •

Infix:  

A*B+C binary operations only computation order ambiguity

Syntax •

Prefix: 

ordinary * (+ (A, B), - (C, A))



Cambridge Polish (* (+ A B) (- C A))



Polish *+AB-CA

Syntax •

Prefix:  



different numbers of operands ordinary/ Cambridge Polish: cumbersome with parentheses Polish: number of operands known in advance

Syntax •

Postfix: 

ordinary ((A, B) +, (C, A) -) *



Polish AB+CA-*



suitable execution-time representation

Execution-Time Representation •

Interpretation: 

tree structures

*

+ A  prefix or postfix

B C

A

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)

Execution-Time Representation •

Compilation: machine code sequences PUSH A PUSH B ADD PUSH C PUSH A SUB MUL

A

A+B C

A B

A+B

A+B C A

A+B C-A

AB+CA*

(A+B)*(C-A)

Evaluation •

No simple uniform evaluation rule is satisfactory: *

+ A

B C

A

Evaluation •

Side effects: A * FOO(X) + A

+ * A

A FOO(X)

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

Evaluation •

Short-circuit Boolean expressions: if (A = 0) or (B/A > C) then …

Evaluation •

Short-circuit Boolean expressions: if (A = 0) or else (B/A > C) then …

Sequence Control •

Expressions

•

Statements

•

Subprograms

Statements •

GOTO

•

Sequencing

•

Selection

•

Iteration

GOTO

JMP L

GOTO L

L

Sequencing begin

end

S1; S2; … Sn;

S1 codes S2 codes

Sn codes

Selection • if: if A = 0 then S1 else S2; S3;

L1 L2

JEQ0 A L1

JNEQ0 A L1

S2 codes

S1 codes

JMP L2

JMP L2

S1 codes S3 codes

L1 L2

S2 codes S3 codes

Selection • case:

var E: 0..2; case E of 1: S1; 2: S2; else: S0 end; S3;

a a+1 a+2

L1 L2 L0 L3

Ev JMP a+v JMP L0 JMP L1 JMP L2 S1 codes JMP L3 S2 codes JMP L3 S0 codes S3 codes

JUMP table

Iteration • for: for I := E1 to E2 do S; I := E1; L0: if I > E2 then GOTO L1; S; I := I + 1; GOTO L0; L1: …

Iteration • while: while C do S; L0: if not(C) then GOTO L1; S; GOTO L0; L1: …

Iteration • repeat: repeat S until C; L0: S; if not(C) then GOTO L0;

Sequence Control •

Expressions

•

Statements

•

Subprograms

Subprograms •

Simple call-return

•

Recursive calls

Simple Call-Return •

No recursive calls

•

Explicit calls

•

Complete execution

•

Immediate control transfer

•

Single execution sequence

Simple Call-Return MAIN I0

A I2

call A I1

I3

end

B I4

call B

return

return

Simple Call-Return MAIN I0

call A I1

en d local data MAIN I0

CIP (current instruction pointer)

Simple Call-Return MAIN

A

I0

I2

call A I1

I3

return

end local data MAIN I2

call B

local data A I1 CIP

Simple Call-Return MAIN

A

I0

I2

call A I1

I3

local data MAIN I4

I4

call B return

end

local data A I1 CIP

B

return local data B I3

Recursive Calls MAIN

A

I0

I2

I4

call A

call B

I1

call A

I3

end R0

B

I5

return

return

--local data MAIN

I0

CIP

R0

CEP (current environment pointer)

Recursive Calls MAIN

A

I0

I2

call A

I4

call B

I1

call A

I3

end R0

B

--local data MAIN

I5

return R1

return

I1 R0 local data A

I2

CIP

R1

CEP

Recursive Calls I0

I2

call A

I4

call B

I1

call A

I3

end R0

---

return R1

local data MAIN I4

I5

I1 R0

R2

local data A

CIP

R2

return I3 R1

local data B

CEP

Recursive Calls I0

I2

call A

I4

call B

I1

call A

I3

end R0

---

return R1

local data MAIN I2

I5

I1 R0

R2

local data A

CIP

R3

return I3 R1

local data B

CEP

R3

I5 R2 local data A

Recursive Calls I0

I2

call A

I4

call B

I1

call A

I3

end R

---

0

return R 1

local data MAIN I2

I5

I1 R0

R 2

local data A

CIP

R3

return R

I3 R1

3

local data B

CEP

I5 R2 local data A

Dynamic chain

Central Stack R0

MAIN I0

CIP

call A I1 end

I0

MAIN

--local data

CEP

R0

Central Stack MAIN I0

CIP

call A I1

CEP

R0

I2 R1

MAIN R1

end A

A I2 call B I3 return

--local data

I1 R0 local data

Central Stack A I2

CIP

call B I3

CEP

R0

I4 R2

MAIN

R1

return B

R2

call A

B

local data I1 R0

A

I4

---

local data

I3 R1 local data

I5 return

B I4

CIP

call A I5 return

CEP

I2

R0 MAIN

R3

R1

I2

R2

R2

I3

return

A

I1 local data

I3 R1

B

call B

local data R0

A

A

---

local data I5 R2 local data

Dynamic Scope •

•



The subprogram activations within which the association is effective. Association : A binding between a name and a data object. Data object: a block of storage, containing data value

Dynamic Scope program MAIN; var X: integer; … procedure SUB1; var X: real; …

MAIN object1

X := 1; procedure SUB2; … X := 2;

SUB1

SUB2

Static Scope program MAIN; var X: integer; …

procedure SUB1; var X: real; … X := 1;

procedure SUB2; … X := 2;

X  integer

Static scopes define dynamic scopes

program main; var A, B, C: real; procedure Sub1 (A: real); var D: real; procedure Sub2 (C: real); var D: real; begin … C:= C+B; … end; begin … Sub2(B); … end; begin … Sub1(A); … end.

Local

Non-local

Global

Sub2

C, D

A,Sub2 B,Sub1

B,Sub1

Sub1

A,D,Sub2

B,C,Sub1

B,C,Sub1

main

A,B,C,Sub1

A,B,C,Sub1

Static referencing environment

a b c

main  sub1  sub2  sub2

obj1

obj2 obj3

a

obj4

c

obj6

c

obj8

d

obj5

d

obj7

d

obj9

sub2

sub1

main

sub1

sub2

sub2

local

non-local

global

Sub2

obj8,obj9

obj4, obj2,sub1,sub2

obj2,sub1

sub2

obj6,obj7

obj4, obj2,sub1,sub2

obj2,sub1

sub1

obj4, obj5,sub2

obj2,obj3,sub1

obj2, obj3,sub1

main

obj1,obj2,obj3,sub1

Dynamic referencing environment

obj1,obj2,obj3,sub1

a var integer 0

Implementation

b var integer 2

Compilation time

var a,b:integer; c:char; begin a := b -1; … end

c var char

4

Symbol Table

Execution Time

a

obj1

b

obj2

c

obj3

Activation Record

CEP + 0

CEP

CEP + 2

program MAIN; var X, Y, Z: char; procedure SUB2; var X, Y: integer; procedure SUB3; var X: real; procedure SUB4; begin …end begin … end begin … end procedure SUB1; var Y, Z: integer; begin …end begin … end

Symbol Table

X | char|0 1Y | char|1 1Z | char |1 Sub2 1| void -> void X| 1 integer|0 Y| 1 0 integer|4 Sub3 1 0| void -> void X| 1 0 integer|0 Sub4 1 0| void -> void

Scope Stack 1 1 1 0 0 0

Formal Parameters and Actual Parameters 



Formal parameters: data objects specified at function declartion Ex: function foo(x:integer; y:real); Actual parameters: data objects passed from caller to callee Ex: foo(a,b);

Passing parameter mechanisms 

In – out: – – –



In only – – –



Value - result Reference Name Value Constant value Constant parameter

Out only –

Function

In – out 



Value - result

x 7 5

a 7 5

foo(x,y)  proc foo(inout a, inout b)

y 8 6

b 8 6

foo(x,y)  proc foo(inout a, inout b)

x 5 7

a

Reference

y 6 8

b

foo(x,y)  proc foo(var a, var b)



Name foo(i,x[i])  proc foo(name a, name b)

ai

b  x[i]

Example var x: array[1..5] of integer; i: integer; procedure swap(a,b:integer); var t:integer; begin t := a; a := b; b := t; end begin for i := 1 to 5 do x[i] := 6 – i; i := 2; swap(i, x[i]); end.

In-only 

By value foo(x,y)  proc foo(in a,in b) foo(x,y)  proc foo(in a,in b)



By constant value foo(x,y)  proc foo(const a,const b) foo(x,y)  proc foo(const a,const b)



By constant reference foo(x,y)  proc foo(constvar a, constvar b)

x 5

a 7 5

y 6

b 8 6

x 5

a 5

y 6

b 6

x 5

a

y 6

b

Out-only 

Result foo(x,y)  proc foo(out a,out b)

foo(x,y)  proc foo(out a,out b)



Function form a := foo() function foo():integer

x 7 5

a 7

y 8 6

b 8



Example

.

procedure SUB2(K:int; var L:int) begin K = K + 10; L = L + 10; end procedure SUB1; var I,J: int begin I = 1; J = 2; SUB2(I,J); end

IP

-

EP

-

SCP

-

I

1

J

2 12

IP

-

EP

-

SCP

-

K L

1 11

I

Example (cont’d) procedure SUB1; var I, J: integer; begin

procedure SUB3(var M, N: integer); begin M := M + 10 N := N + 10 write(M, N)

end; procedure SUB2(K: integer; var L: integer); begin K := K + 10 L := L + 10 SUB3(K, L); write(K, L)

end;

I := 1; J := 2; SUB2(I, J); write(I, J)

end;

SUB1  SUB2  SUB3

 .

I := 1 J := 2 SUB2(I,J)

IP

-

EP

-

SCP

-

IK

I

1

JL

J

22 2 12

IP

-

EP

-

SCP

-

K

1 21 11

K := K + 10 L := L + 10 SUB1(K,L) KM LN

L IP

-

EP

-

SCP

-

M := M + 10

M

N := N + 10

N

Example type VECT = array [1..3] of integer; procedure 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;

procedure 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;

 IP

-

EP

-

SCP

-

A

A[1] := 7; A[2] := 8; A[3] :=9;

Descriptor 7 8

B[1] := 7; B[2[ := 8; B[3] := 9;

9

SUB2(A,B);

B

A C

7 18 8

BD C[2] := C[2] + 10 D[2] := D[2] + 10

Descriptor

SUB1 Activation record

9 J IP

-

EP

-

SCP

-

C

Descriptor

7 18 8 9 D I

SUB2 Activation record

Example type VECT = array [1..3] of integer; procedure SUB2(R: VECTPTR; var S: VECTPTR); VECTPTR = ^VECT; begin procedure SUB1; R^[1] := R^[1] + 10; var A, B: VECT; S^[1] := S^[1] + 10; P, Q: VECTPTR; if . . . then R := S begin else S := R A[1] := 7; A[2] := 8; A[3] := 9; end; B[1] := 7; B[2] := 8; B[3] := 9; P := @A; Q := @B; SUB2(P, Q); end;

Passing by Name type VECT = array [1..3] of integer; procedure SUB2 (name I, J: integer); begin I := I + 1; J := J + 1; write(I, J) end; procedure 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;

K := K + 1; A[K] := A[K] + 1; write(K,A[K])