[SOLVED] scheme c/c++ Fortran compiler Java ada chain lec12

lec12

CS 314 Principles of Programming Languages

Prof. Zheng Zhang
Rutgers University

Lecture 12: Names, Scopes and Bindings

October 12, 2018

Review: Names, Scopes and Binding

2

Denotes a programming language construct
Has associated attributes

Examples: type, memory location, read/write permission, storage
class, access restrictions.

Has a meaning
Examples: represents a semantic object, a type description, an
integer value, a function value, a memory address.

Whats in a name? Each name means something!

3

Compile time: during compilation process static
(e.g.: macro expansion, type definition)

Link time: separately compiled modules/files are joined together by
the linker (e.g: adding the standard library routines for I/O (stdio.h),
external variables)

Run time: when program executes dynamic

Review: Names, Bindings and Memory

Compiler needs bindings to know meaning of names during translation
(and execution).

Bindings Association of a name with the thing it names
(e.g., a name and a memory location, a function name and its
meaning, a name and a value)

Review: How to Maintain Bindings

4

Symbol table: maintained by compiler during compilation
Referencing Environment: maintained by compiler-generated-code

during program execution

How long do bindings last for a name hold in a program?
What initiates a binding?
What ends a binding?

Question:

Scope of a binding:
The part of program the in which the binding is active.

Review: Lexical Scope v.s. Dynamic Scope

5

Non-local variables are associated with declarations at compile time
Find the smallest block syntactically enclosing the reference and

containing a declaration of the variable

Lexical Scope

Non-local variables are associated with declarations at run time
Find the most recent, currently active run-time stack frame

containing a declaration of the variable

Dynamic Scope

Lexical Scope

6

A name that is introduced in a declaration is known in the scope in
which it is declared, and in each internally nested scope, unless it is
hidden by another declaration of the same name in one or more
nested scopes.

Closest scope rule

Scope Example

7

procedure P1(A1)
var X local to P1

procedure P2(A2)

procedure P3(A3)

begin

body of P3
end

begin
body of P2

end
procedure P4(A4)

function F1(A5)

var X local to F1

begin
body of F1

end

begin
body of P4

end

begin
body of P1

end

A1 X P2

A2 P3

A3

P4

A4 F1
A5 X

Scope Example

8

procedure P1(A1)
var X local to P1

procedure P2(A2)

procedure P3(A3)

begin

body of P3
end

begin
body of P2

end
procedure P4(A4)

function F1(A5)

var X local to F1

begin
body of F1

end

begin
body of P4

end

begin
body of P1

end

A1 X P2

A2 P3

A3

P4

A4 F1
A5 X

Scope Example

9

procedure P1(A1)
var X local to P1

procedure P2(A2)

procedure P3(A3)

begin

body of P3
end

begin
body of P2

end
procedure P4(A4)

function F1(A5)

var X local to F1

begin
body of F1

end

begin
body of P4

end

begin
body of P1

end

A1 X P2

A2 P3

A3

P4

A4 F1
A5 X

Scope Example

10

procedure P1(A1)
var X local to P1

procedure P2(A2)

procedure P3(A3)

begin

body of P3
end

begin
body of P2

end
procedure P4(A4)

function F1(A5)

var X local to F1

begin
body of F1

end

begin
body of P4

end

begin
body of P1

end

A1 X P2

A2 P3

A3

P4

A4 F1
A5 X

Scope Example

11

procedure P1(A1)
var X local to P1

procedure P2(A2)

procedure P3(A3)

begin

body of P3
end

begin
body of P2

end
procedure P4(A4)

function F1(A5)

var X local to F1

begin
body of F1

end

begin
body of P4

end

begin
body of P1

end

A1 X P2

A2 P3

A3

P4

A4 F1

A5 X

Scope Example

12

procedure P1(A1)
var X local to P1

procedure P2(A2)

procedure P3(A3)

begin

body of P3
end

begin
body of P2

end
procedure P4(A4)

function F1(A5)

var X local to F1

begin
body of F1

end

begin
body of P4

end

begin
body of P1

end

A1 X P2

A2 P3

A3

P4

A4 F1

A5 X

local to P1

local to F1

X local to F1
is hidden by
X local to F1

also called a
hole

Dynamic Scope

13

The current binding for a given name is the one encountered most
recently during execution, and not yet destroyed by returning from
its scope.

Depending on the Flow of Execution at Run Time

program L;
var n: char; {n declared in L}
procedure W;
begin

write (n); {n referenced in W}
end;
procedure D;

var n: char; {n declared in D}
begin

n := D; {n referenced in D}
W

end;
begin

n := L; {n referenced in L}
W;
D

end

Dynamic Scope

14

L D W

Calling Chain:

The output is ?

Caller

D
Which n?

program L;
var n: char; {n declared in L}
procedure W;
begin

write (n); {n referenced in W}
end;
procedure D;

var n: char; {n declared in D}
begin

n := D; {n referenced in D}
W

end;
begin

n := L; {n referenced in L}

D
end

Review: Program Memory Layout

15

Static objects are given an absolute address
that is retained throughout the execution of
the program

Stack objects are allocated and deallocated in
last-in, first-out order, usually in conjunction
with subroutine calls and returns

Heap objects are allocated and deallocated at
any arbitrary time

stack

heap

static &
global

code

Procedure Activations

16

Begins when control enters activation (call)
Ends when control returns from call

Example:

Subroutine C

Subroutine B

Subroutine B

Subroutine A

procedure C:
D
procedure B:
ifthen B else C
procedure A:
B
main program:
A

sp

Direction of
stack growth

(usually lower
addresses)

Calling chain: A B B C D

parameter
return value

return address

access link

caller FP

local variables

Subroutine D

Procedure Activations

17

Run-time stack contains frames from main program & active procedure
Each stack frame includes:

1. Pointer to stack frame of caller
(control link for stack maintenance and dynamic scoping)

2. Return address (within calling procedure)
3. Mechanism to find non-local variables (access link for lexical scoping)
4. Storage for parameters, local variables and final values
5. Other temporaries including intermediate values & saved register

parameter
return value

return address

access link

caller FP

local variables

Stack Frame
or

Activation Record Frame Pointer (FP)
or Activation Record

Pointer (ARP)

Usually stored in a register

Implementation of Lexical Scope and Dynamic Scope

18

Non-local variables are associated with declarations at compile time
Find the smallest block syntactically enclosing the reference and

containing a declaration of the variable
Access link points to the most recently activated immediate lexical

ancestor

Lexical Scope

Non-local variables are associated with declarations at run time
Find the most recent, currently active run-time stack frame

containing a declaration of the variable
Control link points to the caller

Dynamic Scope

Program
x, y: integer // declarations of x and y
Procedure B// declaration of B
y, z: real// declaration of y and z
begin

y = x + z // occurrences of y, x, and z
if () call B // occurrence of B
end

Procedure C// declaration of C
x: real
begin

call B // occurrence of B
end
begin

call C // occurrence of C
call B // occurrence of B
end

19

Calling chain: MAIN C B BControl linksAccess links

fp
main

o
o

x
y

C
o

o
x

B
o

o
y
z

B
o

o
y
z

Implementation of Lexical Scope and Dynamic Scope

Context of Procedures

20

Two contexts
static placement in source code (same for each invocation)
dynamic run-time stack context (different for each invocation)

Scope Rules:
Each variable reference must be associated with a single declaration.

Context of Procedures

21

Two choices:
1. Use static and dynamic context: lexical scope
2. Use dynamic context: dynamic scope

Easier for variables declared locally: same for lexical and
dynamic scoping

Harder for variables not declared locally: not same for lexical
and dynamic scoping

Access to Non-Local Data(Lexical Scoping)

22

1. Compile-time: How do we map a name into a (level, offset) pair?
We use a block structured symbol table (compile time)
When we look up a name, we want to get the most recent declaration

for the name
The declaration may be found in the current procedure or in any

ancestor procedure
2. Run-time: Given a (level, offset) pair, whats the address?

Two classical approaches:
access link (static link)
display

Two important steps

Compile-Time

23

Symbol table generated at compile time matches declarations and occurrences.
Each name can be represented as a pair (nesting_level, local_index).

Program
(1,1), (1,2): integer // declarations of x and y
Procedure (1,3)// declaration of B
(2,1), (2,2): real// declaration of y and z
begin

(2,1) = (1,1) + (2,2) // occurrences of y, x, and z
if () call (1,3) // occurrence of B
end
Procedure (1,4)// declaration of C
(2,1): real
begin

call (1,3) // occurrence of B
end
begin

call (1,4) // occurrence of C
call (1,3) // occurrence of B
end

Program
x, y: integer // declarations of x and y
Procedure B// declaration of B
y, z: real// declaration of y and z
begin

y = x + z // occurrences of y, x, and z
if () call B // occurrence of B
end
Procedure C// declaration of C
x: real
begin

call B // occurrence of B
end
begin

call C // occurrence of C
call B // occurrence of B
end

Runtime Access to Non-Local Data (Lexical Scoping)

24

Assume current procedure level is k
If k = l, it is a local variable
If k > l, must find ls activation record (stack frame)
follow k l access link

k < l cannot occurRuntime: To find the value specified by (l, o) Assume nested procedure has higher index than its parent procedure. Using access link:Access to Non-Local Data(Lexical Scoping): Access Link25 Each AR has a pointer to most recent AR of immediate lexical ancestor Lexical ancestor does not need to be the callerUsing access links (static links) parameterregister save areareturn valuereturn addressaccess linkcallers ARPlocal variablesARPparameterregister save areareturn valuereturn addressaccess linkcallers ARPlocal variablesparameterregister save areareturn valuereturn addressaccess linkcallers ARPlocal variables Cost of access link is proportional to lexical distanceActivation RecordPointerlevel: plevel: p – 2level: p – 1Maintaining Access Links26 Calling level k + 1 procedure1.Pass the callers FP as access link2.The callers backward chain will work for lower levels Calling procedure at level i k1.Find the callers link to level i – 1 and pass it to callee2.Its access link will work for lower levelsIf the callee procedure p is nested immediately within the caller procedure q, the access link for p points to the activation record of the most recent activation of q. Setting up access link (the caller does the job):Assuming current level is k:An Improvement: The Display27 table of access links for lower levels lookup is index from known offset takes slight amount of time at call a single display or one per frameTo improve run-time access costs, use a display. Access with the display assume a value described by (l,o) find slot as DP[l] in display pointer array add offset to pointer from slotSetting up the activation frame now includes display manipulation.Access to Non – Local Data(Lexical Scoping): Display28 Global arrays of pointers to nameable array Needed ARP is an array access awayUsing a displayARPparameterregister save areareturn valuereturn addresssaved ptrcallers ARPlocal variableslevel 0level 1level 2level 3Displayparameterregister save areareturn valuereturn addresssaved ptrcallers ARPlocal variablesparameterregister save areareturn valuereturn addresssaved ptrcallers ARPlocal variablesExample: reference to looks up ps APR in display and add 16

Cost of access link is constant (APR + offset)

Display Management

29

Single global display:

On entry to a procedure at level i:
Save the level i display value
push FP into level i display slot

On return:
Restore the level i display value

parameter
register

save area
return value

return address
saved ptr

callers ARP
local variables

Procedures

30

Modularize program structure
Actual parameter: information passed from caller to callee (Argument)
Formal parameter: local variable whose value (usually) is received from

caller
Procedure declaration

Procedure names, formal parameters, procedure body with formal local
declarations and statement lists, optional result type

Example: void translate(point *p, int dx)

Parameters

31

Positional association: Arguments associated with formals one-by-one;
Example: C, Pascal, Java, Scheme

Keyword association: formal/actual pairs; mix of positional and
keyword possible;
Example: Ada

procedure plot(x, y: in real; z: in boolean)
plot (0.0, 0.0,z true)
plot (z true, x 0.0, y 0.0)

Parameter Association

Parameter Passing Modes
Pass-by-value: C/C++, Pascal, Java/C# (value types), Scheme
Pass-by-result: Ada, Algol W
Pass-by-value-result: Ada, Swift
Pass-by-reference: Fortran, Pascal, C++, Ruby, ML

Pass-by-value

32

Advantage: Argument protected from changes in callee.
Disadvantage: Copying of values takes execution time and
space, especially for aggregate values (e.g.: structs, arrays)

begin
c: array[110] of integer;
m, n: integer;
procedure r(k, j: integer)
begin
k := k + 1;
j := j + 2;
end r;

m := 5;
n := 3;
r(m, n);
write m,n;
end

Output:

5 3

Pass-by-reference

33

begin
c: array[110] of integer;
m, n: integer;
procedure r(k,j: integer)
begin
k := k + 1;
j := j + 2;
end r;

m := 5;
n := 3;
r(m, n);
write m, n;

end
Output: Advantage: more efficient than copying

Disadvantage: leads to aliasing, there are two or more
names for the storage location; hard to track side effects

6 5

Pass-by-result

34

begin
c: array[110] of integer;
m, n: integer;
procedure r(k, j: integer)
begin
k := k + 1;
j := j + 2;
end r;

m := 5;
n := 3;
r(m, n);
write m, n;

end

Output:

Program doesnt compile or has runtime error

ERROR:
CANNOT USE PARAMETERS WHICH ARE UNINITIALIZED

Pass-by-result

35

begin
c: array[110] of integer;
m, n: integer;
procedure r(k, j: integer)
begin
k := 1;
j := 2;
end r;

m := 5;
n := 3;
r(m, n);
write m, n;

end

Output: ?

HERE IS A PROGRAM THAT WORKS

Pass-by-result

36

begin
c: array[110] of integer;
m, n: integer;
procedure r(k, j: integer)
begin
k := 1;
j := 2;
end r;

m := 5;
n := 3;
r(m, n);
write m, n;

end

Output: 1 2

HERE IS A PROGRAM THAT WORKS

Pass-by-result

37

begin
c: array[110] of integer;
m, n: integer;
procedure r(k, j: integer)
begin
k := 1;
j := 2;
end r;

m := 5;
n := 3;
r(m, m);
write m, n;

end

Output: 1 or 2 for m?

Problem: order of copy back makes a difference;
implementation dependent.

NOTE: CHANGE THE CALL

Pass-by-value-result

38

begin
c: array[110] of integer;
m, n: integer;
procedure r(k, j: integer)
begin
k := k + 1;
j := j + 2;
end r;

m := 5;
n := 3;
r(m, n);
write m, n;

end

Output: 6 5
Problem: order of copy back makes a difference;
implementation dependent.

39

begin
c: array[110] of integer;
m, n: integer;
procedure r(k, j: integer)
begin
k := k + 1;
j := j + 2;
end r;

/* set c[m] = m */
m := 2;
r(m,c[m]);
write c[1], c[2], c[3], c[10];

end

Pass-by-value-result

Output:
1 4 3 4 5 10 on entry
1 2 4 4 5 10 on exit
Problem: When is the address computed for the copy-back operation?
At procedure call (procedure entry),just before procedure exit, or
somewhere in between? (Example: ADA on entry)

WHAT ELEMENT OF c IS ASSIGNED TO?

40

begin
c: array[110] of integer;
m, n: integer;
procedure r(k, j: integer)
begin
k := k + 1;
j := j + 2;
end r;

/* set c[m] = m */
m := 2;
r(m,c[m]);
write c[1], c[2], c[3], c[10];

end

Pass-by-value-result

Output:
1 4 3 4 5 10 on entry
1 2 4 4 5 10 on exit
Problem: When is the address computed for the copy-back operation?
At procedure call (procedure entry),just before procedure exit, or
somewhere in between? (Example: ADA on entry)

WHAT ELEMENT OF c IS ASSIGNED TO?

41

begin
c: array[110] of integer;
m, n: integer;
procedure r(k, j: integer)
begin
k := k + 1;
j := j + 2;
end r;

/* set c[m] = m */
m := 2;
r(m,c[m]);
write c[1], c[2], c[3], c[10];

end

Pass-by-value-result

Output:
1 4 3 4 5 10 on entry
1 2 4 4 5 10 on exit
Problem: When is the address computed for the copy-back operation?
At procedure call (procedure entry),just before procedure exit, or
somewhere in between? (Example: ADA on entry)

WHAT ELEMENT OF c IS ASSIGNED TO?

42

begin
c: array[110] of integer;
m, n: integer;
procedure r(k, j: integer)
begin
k := k + 1;
j := j + 2;
end r;

/* set c[m] = m */
m := 2;
r(m,c[m]);
write c[1], c[2], c[3], c[10];

end

Pass-by-value-result

Output:
1 4 3 4 5 10 on entry
1 2 4 4 5 10 on exit
Problem: When is the address computed for the copy-back operation?
At procedure call (procedure entry),just before procedure exit, or
somewhere in between? (Example: ADA on entry)

WHAT ELEMENT OF c IS ASSIGNED TO?

Aliasing

43

Aliasing:

begin
j, k, m: integer;
procedure r(a, b: integer)
begin
b := 3;
m := m * a;
end

q(m, k);
q(j, j);
write y;
end

More than two ways to name the same object within a scope

Even without pointers, you can have aliasing through
(globalformal) and (formalformal) parameter passing.

formal/formal ALIAS PAIR
global/formal ALIAS PAIR

Comparison: by-value-result vs. by-reference

44

Actual parameters need to evaluate to L-values (addresses).

begin
y: integer;
procedure p(x: integer)
begin
x := x + 1
x := x + y
end

y := 2;
p(y);
write y;
end

Output:
pass-by-reference: 6
pass-by-value-result: 5

Note: by-value-result: Requires copying of parameter values (expansive for
aggregate values); does not have aliasing, but copy-back order dependence.

ref: x and y are ALIASED
val-res: x and y are NOT ALIASED

Next Lecture

45

Read Scott, Chapter 9.1 9.3 (4th Edition) or Chapter 8.1 8.3
(3rd Edition), Chapter 11.1 11.3 (4th Edition)

Things to do:

Procedures

46

Modularize program structure
Actual parameter: information passed from caller to callee (Argument)
Formal parameter: local variable whose value is received from caller

Procedure declaration
Procedure names, formal parameters, procedure body with formal local

declarations and statement lists, optional result type

Example: void translate(point *p, int dx)

Parameters

47

Positional association: Arguments associated with formals one-by-one;
Example: C, Pascal, Java, Scheme

Keyword association: formal/actual pairs; mix of positional and
keyword possible;
Example: Ada

procedure plot(x, y: in real; z: in boolean)
plot (0.0, 0.0,z true)
plot (z true, x 0.0, y 0.0)

Parameter Association

Parameter Passing Modes
Pass-by-value: C/C++, Pascal, Java/C# (value types), Scheme
Pass-by-result: Ada, Algol W
Pass-by-value-result: Ada, Swift
Pass-by-reference: Fortran, Pascal, C++, Ruby, ML

Pass-by-value

48

Advantage: Argument protected from changes in callee.
Disadvantage: Copying of values takes execution time and
space, especially for aggregate values (e.g.: structs, arrays)

begin
c: array[110] of integer;
m, n: integer;
procedure r(k, j: integer)
begin
k := k + 1;
j := j + 2;
end r;

m := 5;
n := 3;
r(m, n);
write m,n;
end

Output:

5 3

Pass-by-reference

49

begin
c: array[110] of integer;
m, n: integer;
procedure r(k,j: integer)
begin
k := k + 1;
j := j + 2;
end r;

m := 5;
n := 3;
r(m, n);
write m, n;

end
Output: Advantage: more efficient than copying

Disadvantage: leads to aliasing, there are two or more
names for the storage location; hard to track side effects

6 5

Pass-by-result

50

begin
c: array[110] of integer;
m, n: integer;
procedure r(k, j: integer)
begin
k := k + 1;
j := j + 2;
end r;

m := 5;
n := 3;
r(m, n);
write m, n;

end

Output:

Program doesnt compile or has runtime error

ERROR:
CANNOT USE PARAMETERS WHICH ARE UNINITIALIZED

Pass-by-result

51

begin
c: array[110] of integer;
m, n: integer;
procedure r(k, j: integer)
begin
k := 1;
j := 2;
end r;

m := 5;
n := 3;
r(m, n);
write m, n;

end

Output: ?

HERE IS A PROGRAM THAT WORKS

Pass-by-result

52

begin
c: array[110] of integer;
m, n: integer;
procedure r(k, j: integer)
begin
k := 1;
j := 2;
end r;

m := 5;
n := 3;
r(m, m);
write m, n;

end

Output: 1 or 2 for m?

Problem: order of copy back makes a difference;
implementation dependent.

HERE IS ANOTHER PROGRAM THAT WORKS

NOTE: CHANGE THE CALL

Pass-by-value-result

53

begin
c: array[110] of integer;
m, n: integer;
procedure r(k, j: integer)
begin
k := k + 1;
j := j + 2;
end r;

m := 5;
n := 3;
r(m, n);
write m, n;

end

Output: 6 5
Problem: order of copy back makes a difference;
implementation dependent.

54

begin
c: array[110] of integer;
m, n: integer;
procedure r(k, j: integer)
begin
k := k + 1;
j := j + 2;
end r;

/* set c[m] = m */
m := 2;
r(m,c[m]);
write c[1], c[2], c[3], c[10];

end

Pass-by-value-result

Output:
1 4 3 4 5 10 on entry
1 2 4 4 5 10 on exit
Problem: When is the address computed for the copy-back operation?
At procedure call (procedure entry),just before procedure exit, or
somewhere in between? (Example: ADA on entry)

WHAT ELEMENT OF c IS ASSIGNED TO?

55

begin
c: array[110] of integer;
m, n: integer;
procedure r(k, j: integer)
begin
k := k + 1;
j := j + 2;
end r;

/* set c[m] = m */
m := 2;
r(m,c[m]);
write c[1], c[2], c[3], c[10];

end

Pass-by-value-result

Output:
1 4 3 4 5 10 on entry
1 2 4 4 5 10 on exit
Problem: When is the address computed for the copy-back operation?
At procedure call (procedure entry),just before procedure exit, or
somewhere in between? (Example: ADA on entry)

WHAT ELEMENT OF c IS ASSIGNED TO?

56

begin
c: array[110] of integer;
m, n: integer;
procedure r(k, j: integer)
begin
k := k + 1;
j := j + 2;
end r;

/* set c[m] = m */
m := 2;
r(m,c[m]);
write c[1], c[2], c[3], c[10];

end

Pass-by-value-result

Output:
1 4 3 4 5 10 on entry
1 2 4 4 5 10 on exit
Problem: When is the address computed for the copy-back operation?
At procedure call (procedure entry),just before procedure exit, or
somewhere in between? (Example: ADA on entry)

WHAT ELEMENT OF c IS ASSIGNED TO?

57

begin
c: array[110] of integer;
m, n: integer;
procedure r(k, j: integer)
begin
k := k + 1;
j := j + 2;
end r;

/* set c[m] = m */
m := 2;
r(m,c[m]);
write c[1], c[2], c[3], c[10];

end

Pass-by-value-result

Output:
1 4 3 4 5 10 on entry
1 2 4 4 5 10 on exit
Problem: When is the address computed for the copy-back operation?
At procedure call (procedure entry),just before procedure exit, or
somewhere in between? (Example: ADA on entry)

WHAT ELEMENT OF c IS ASSIGNED TO?

Aliasing

58

Aliasing:

begin
j, k, m: integer;
procedure r(a, b: integer)
begin
b := 3;
m := m * a;
end

q(m, k);
q(j, j);
write y;
end

More than two ways to name the same object within a scope

Even without pointers, you can have aliasing through
(globalformal) and (formalformal) parameter passing.

formal/formal ALIAS PAIR
global/formal ALIAS PAIR

Comparison: by-value-result vs. by-reference

59

Actual parameters need to evaluate to L-values (addresses).

begin
y: integer;
procedure p(x: integer)
begin
x := x + 1
x := x + y
end

y := 2;
p(y);
write y;
end

Output:
pass-by-reference: 6
pass-by-value-result: 5

Note: by-value-result: Requires copying of parameter values (expansive for
aggregate values); does not have aliasing, but copy-back order dependence.

ref: x and y are ALIASED
val-res: x and y are NOT ALIASED

Next Lecture

60

Read Scott, Chapter 9.1 9.3 (4th Edition) or Chapter 8.1 8.3
(3rd Edition), Chapter 11.1 11.3 (4th Edition)

Things to do:

Look up Non-local Variable Reference

61

Access links and control links are used to look for non-local
variable references.

Static Scope:
Access link points to the stack frame of the most recently activated
lexically enclosing procedure

Non-local name binding is determined at compile time, and
implemented at run-time

Dynamic Scope:
Control link points to the stack frame of caller

Non-local name binding is determined and implemented at
run-time