Data Controls
CSE – HCMUT
2009
Outline
• Basic Concepts
• Local Environment
• Shared Environment
– Dynamic Scope
– Block Structure
– Parameter Passing
CSE_HCMUT Data Controls 2
Names
• User-defined names
– Names in declarations
• Design issues for names:
– Maximum length?
– Are connector characters allowed?
– Are names case sensitive?
– Are special words reserved words or
keywords?
CSE_HCMUT Data Controls 3
Names
• Simple names
a = 1; b = a+1;
• Composite names:
a[1] = b.c[2];
CSE_HCMUT Data Controls 4
Variables and Constants
• Variables: named data object whose
values are changeable
• Constants: named data object whose
values cannot be changed
– Literals
– User-defined constant
CSE_HCMUT Data Controls 5
Binding
• Association between a program
element and a property
• Binding time:
– Dynamic Binding
• Execution time
– Static Binding
• Translation time
• Language implementation time
• Language definition time
CSE_HCMUT Data Controls 6
Binding
• X = X + 10
– Possible types of X?
– Type of X?
– Possible values of X?
– Value of X?
– Representation of 10?
– Properties of +?
CSE_HCMUT Data Controls 7
Declaration
• A static binding between an
identifier and its properties such as
type, kind
– Implicit (default) declaration
– Explicit declaration
CSE_HCMUT Data Controls 8
Association
• A dynamic binding between an
identifier and a data object or a
specific subprogram
a object 1
CSE_HCMUT Data Controls 9
Visibility of Declaration
• A declaration is visible if it can be
referenced
void main { hidden
int x;
for (;;) { int x; cout << x;}
for (;;) {cout <<x;}
cout << x;
}
CSE_HCMUT Data Controls 10
Visibility of Association
• A declaration is visible to an
activation if it can be referenced
by the activation
• Please give your own example
CSE_HCMUT Data Controls 11
Referencing Environment
• Static referencing environment:
– Set of visible declarations that a
subprogram can refer
• Dynamic referencing environment
– Set of association that an activation can
refer
CSE_HCMUT Data Controls 12
Kinds of referencing
environment
• Local
• Non-local
• Global
CSE_HCMUT Data Controls 13
var A, B, C: real;
procedure Sub1 (A: real);
var D: real;
procedure Sub2 (C: real);
var D: real;
begin
… C:= C+B; … Local Non-local Global
end; Sub2 C, D A,Sub2 B,Sub1
begin B,Sub1
… Sub2(B); … Sub1 A,D,Sub2 B,C,Sub1 B,C,Sub1
end; main A,B,C,Sub1 A,B,C,Sub1
begin
… Sub1(A); …
Static referencing environment
end.
CSE_HCMUT Data Controls 14
MainÆSub1ÆSub1ÆSub2
Main Sub1 Sub1 Sub2
A obj1 A obj4 A obj6 C obj8
B obj2 D obj5 D obj7 D obj9
C obj3 Sub2 add2 Sub2 add2
Sub1 add1
Dynamic Referencing Environment
Local Non-local Global
Sub2
Sub1
Sub1
main
CSE_HCMUT Data Controls 15
Scope
• Scope of a declaration
– Extent of program in which the
declaration is visible
• Scope of declaration: static scope
• Dynamic scope: scope of association
– Activations in which the association is
visible
CSE_HCMUT Data Controls 16
var A, B, C: real; //1
procedure Sub1 (A: real); //2
var D: real;
procedure Sub2 (C: real);
var D: real;
begin
… C:= C+B; … Declaration Scope
end;
begin
A:real //1 Main
… Sub2(B); … B:real //1 Main,Sub1,Sub2
end; C:real//1 Main,Sub1
begin
… Sub1(A); … A:real //2 Sub1,Sub2
end. …
CSE_HCMUT Data Controls 17
MainÆSub1ÆSub1ÆSub2
Main Sub1 Sub1 Sub2
A obj1 A obj4 A obj6 C obj8
B obj2 D obj5 D obj7 D obj9
C obj3 Sub2 add2 Sub2 add2
Sub1 add1
Association Scope
A↔obj1 Main
B ↔obj2 Main, Sub1, Sub1, Sub2
C ↔obj3 Main, Sub1, Sub1
…
CSE_HCMUT Data Controls 18
Block
• A part of program
• May be nested
• Containing local declarations and
statements
• Defining local referencing
environment
• May be named
CSE_HCMUT Data Controls 19
Static scope rules
Let SD be a scope of declaration DA for name A
1. DA in Block B: B in scope SD
2. DA in B, B ⊃ B1 ⊃ … ⊃ Bn, ∃ D’A in Bi∀i=1,n : Bi
in SD
3. DA in B, B’ ⊃ B: SD not include B’
4. If B⊂B ’ is named N Ù DN in B ’
CSE_HCMUT Data Controls 20
Example
var a:integer
procedure sub(a:integer) //sub-1
procedure sub(a:integer) //sub-2
begin
…
a := 1; // 1: which a?
sub(1); //1: which sub?
end
begin
…
a:= 2; // 2: which a?
sub(1); //2: which sub?
end
Begin
a:=3; //3: which a??
sub(1); //3: which sub ?
end
CSE_HCMUT Data Controls 21
Local Referencing
Environment
• Static: all declarations including its
parameters in the beginning of the
subprogram/block
• Dynamic: all associations in its
activation
CSE_HCMUT Data Controls 22
Non-local referencing
environment
• Just dynamic scope rule
– No static scope rules
– Dynamic scope rules (1)
• Block structure
– Static scope rules
– Dynamic scope rules (2)
CSE_HCMUT Data Controls 23
Dynamic scope rules (1)
• Main Æ Sub1 Æ Sub2 Æ Sub3
• If Sub3 refers to X but no declaration of
X in Sub3: non-local reference
• Dynamic scope rule:
– Find association of X in Sub2, caller of Sub3
– If there exist association of X in Sub2, use it
– Otherwise, find association of X in caller of
Sub2, and so on, until find it or give error
message
CSE_HCMUT Data Controls 24
Example
Procedure sub1
integer a = 1;
sub;
Procedure sub2
real a = 1.2
Main Æ sub1 Æ sub
sub
Procedure sub
Æ sub2 Æ sub
print a
Procedure main
sub1
sub2
CSE_HCMUT Data Controls 25
Block Structure
Static scope Dynamic scope rules (2):
var a, b:integer
main → sub → sub → sub1
procedure sub ()
var a,b:real; a obj1 a obj3
sub
begin b obj2 b obj4
…
end
a
procedure sub1() obj5
sub
var c:integer b obj6
begin
…a…b… c sub1
obj7
end
begin …a
… …b
end
CSE_HCMUT Data Controls 26
Implementation for
static scope rules
program MAIN; Symbol table Scope stack
var X, Y, Z: char;
procedure SUB2; X
var X, Y: integer; 1Y 1
procedure SUB3; 1Z
var X: real; Sub2
1 1
procedure SUB4; 1X 1
begin …end 1Y
0 0
begin … end 1
Sub3
0 0
begin … end 1X
0 0
procedure SUB1; Sub4
1
0
var Y, Z: integer;
begin …end
begin … end
CSE_HCMUT Data Controls 27
Implementation for
static scope rules
program MAIN; Symbol table Scope stack
var X, Y, Z: char;
procedure SUB2; X
var X, Y: integer; 1Y 1
procedure SUB3; 1Z
var X: real; Sub2
1 1
procedure SUB4; Sub1
1 1
begin …end 1Y
0 0
begin … end 1Z
0 0
begin … end 1
0 0
procedure SUB1; 1
0
var Y, Z: integer;
begin …end
begin … end
CSE_HCMUT Data Controls 28
Implementation for dynamic
scope rules X --
MAIN
program MAIN; Y
var X, Y, Z: char; Z
procedure SUB2; IP
var X, Y: integer; EP
SUB1 SCP
procedure SUB3;
Y
var X: real;
Z
procedure SUB4;
… IP
static
EP
procedure SUB1; link
SUB2 SCP
var Y, Z: integer;
X
…
Y
IP
MAIN SUB1 SUB2 SUB3 EP
SUB3 SCP
X
CSE_HCMUT Data Controls 29
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);
CSE_HCMUT Data Controls 30
Passing parameter
mechanisms
• In – out:
– Value - result
– Reference
– Name
• In only
– Value
– Constant value
– Constant parameter
• Out only
– Function
CSE_HCMUT Data Controls 31
In – out
• Value - result
foo(x,y) → proc foo(inout a, inout b)
x 7
5 a 7
5
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 a≡i
b ≡ x[i]
foo(i,x[i]) → proc foo(name a, name b)
CSE_HCMUT Data Controls 32
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.
CSE_HCMUT Data Controls 33
In-only
• By value x 5 a 5
7
foo(x,y) → proc foo(in a,in b) y 6 b 6
8
foo(x,y) ← proc foo(in a,in b)
• By constant value x 5 a 5
foo(x,y) → proc foo(const a,const b) y 6 b 6
foo(x,y) ← proc foo(const a,const b)
• By constant reference x 5 a
foo(x,y) → proc foo(constvar a, constvar b) y 6 b
CSE_HCMUT Data Controls 34
Out-only
• Result
foo(x,y) → proc foo(out a,out b) x 7
5 a 7
y 8
6 b 8
foo(x,y) ← proc foo(out a,out b)
• Function form
a := foo() function foo():integer
CSE_HCMUT Data Controls 35
Example
…
procedure SUB2(K:int; var L:int) .
begin IP -
K = K + 10; EP -
L = L + 10; SCP -
end I 1
procedure SUB1; J 12
2
var I,J: int IP -
begin EP -
I = 1; SCP -
J = 2; K 11
1 I
SUB2(I,J); L
end
CSE_HCMUT Data Controls 36
Example (cont’d)
procedure SUB3(var M, N: integer);
begin procedure SUB1;
M := M + 10 var I, J: integer;
N := N + 10 begin
write(M, N) I := 1;
end; J := 2;
procedure SUB2(K: integer; var L: integer); SUB2(I, J);
begin write(I, J)
K := K + 10 end;
L := L + 10
SUB3(K, L);
write(K, L)
end; SUB1 → SUB2 → SUB3
CSE_HCMUT Data Controls 37
…
I := 1 .
IP -
J := 2 EP -
SCP
SUB2(I,J) -
I 1
I→K
J 22
12
2
J→L IP -
K := K + 10 EP -
SCP -
L := L + 10
K 21
11
1
SUB1(K,L) L
K→M IP -
EP -
L→N SCP -
M := M + 10 M
N := N + 10 N
CSE_HCMUT Data Controls 38
Example
type VECT = array [1..3] of integer;
procedure SUB1;
procedure SUB2(C: VECT; var D: VECT);
var A, B: VECT; var I: integer;
J: integer; begin
begin C[2] := C[2] + 10;
D[2] := D[2] + 10;
A[1] := 7; A[2] := 8; A[3] := 9; for I := 1 to 3 do write(C[I]);
B[1] := 7; B[2] := 8; B[3] := 9; for I := 1 to 3 do write(D[I])
SUB2(A, B); end;
for J := 1 to 3 do write(A[J]);
for J := 1 to 3 do write(B[J]);
end;
CSE_HCMUT Data Controls 39
…
IP -
EP -
SCP -
A Descriptor
A[1] := 7; A[2] := 8; A[3] :=9; 7
B[1] := 7; B[2[ := 8; B[3] := 9; 8 SUB1
9 Activation
SUB2(A,B); record
B Descriptor
A→C 7
18
8
B→D 9
C[2] := C[2] + 10 J
IP -
EP
D[2] := D[2] + 10 SCP
-
-
C Descriptor
7 SUB2
Activation
18
8 record
9
D
I
CSE_HCMUT Data Controls 40
Example
type VECT = array [1..3] of integer;
VECTPTR = ^VECT;
procedure SUB1;
var A, B: VECT; procedure SUB2(R: VECTPTR;
var S: VECTPTR);
P, Q: VECTPTR;
begin
begin R^[1] := R^[1] + 10;
A[1] := 7; A[2] := 8; A[3] := 9; S^[1] := S^[1] + 10;
B[1] := 7; B[2] := 8; B[3] := 9; if . . . then R := S
P := @A; Q := @B; else S := R
end;
SUB2(P, Q);
end;
CSE_HCMUT Data Controls 41
Passing by Name
type VECT = array [1..3] of integer;
procedure SUB2 (name I, J: integer);
begin
I := I + 1; K := K + 1;
J := J + 1; A[K] := A[K] + 1;
write(I, J) write(K,A[K])
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;
CSE_HCMUT Data Controls 42
