Lecture_19_Scope
Scope
CSCI 3136: Principles of Programming Languages
Agenda
• Announcements
• Assignment 8 is out and due July 12.
• Lectures are being recorded
• Readings: Read Chapter 3.3
• Lecture Contents
• Introduction to Scope
• Lexical Scope
• Implementation of Lexical Scope
• Dynamic Scope
• Shallow vs Deep Binding
2021-07-05 8:46 AM 2
Keywords
• Scope
• Binding
• Lexical scope
• Lexical units
• Nesting of blocks
• Nested classes
• Nested functions
• Inner classes
• Static scope
• Stack frame
• Dynamic Scope
• Flow of execution
• Global reference environment
• Funarg problem
• Shallow binding
• Deep binding
• Free variables
2021-07-05 8:46 AM 3
End of this Part
CSCI 3136
2021-07-05 8:47 AM 4
Introduction to Scope
CSCI 3136
2021-07-05 8:47 AM 5
Introduction
• Idea: How we use variables (local/global/etc)
depends on the rules of scope!
• Definitions:
• Scope of a binding is the region of a program or time
interval(s) in the program’s execution during which the
binding is active.
• A scope is a maximal region of the program where no
bindings are destroyed (e.g., body of a procedure).
• Two general types of scoping rules:
• Lexical (static) scoping
• Dynamic scoping
2021-07-05 8:46 AM 6
Types of Scoping Rules
• Lexical (static) scoping
• Binding based on nesting of blocks
• Can be determined at compile time
• Is the default for most languages
• Dynamic scoping
• Binding depends on flow of execution at run time
• Can be determined only at run time
• Typically a bad idea
• Questions
• How do these work?
• When should we use them?
• What are the costs?
2021-07-05 8:46 AM 7
End of this Part
CSCI 3136
2021-07-05 8:46 AM 8
Lexical Scope
CSCI 3136
2021-07-05 8:46 AM 9
Lexical Scope
• Idea: Current binding for a name is the one
encountered in the smallest enclosing lexical unit.
• Lexical units
• Packages, modules, source files
• Classes and nested classes
• Procedures/methods/subroutines and nested subroutines
• Blocks
• Records and structures
• Common Variant: Current binding for a name is
• The one encountered in the smallest enclosing lexical unit
and
• Preceding the current point in the program text
2021-07-05 8:46 AM 10
Lexical Units
Package
File or Module: A
public int foo;
File or Module: B File or Module: C
class alpha
class beta
class gamma
int foo;
class delta
method f() {
}
{ …
}
method f() {
}
method f() {
}
{ int foo;
}
{ …
}
2021-07-05 8:46 AM 11
Languages that Use Lexical Scope
• C requires names to be declared or defined before use
• Java requires local variables to be declared before use
• Prolog definitions need to be in scope
• Scheme has a variety of constructs
• (… (define x …) fun1 fun2 … funk )
• (lambda (x …) fun1 fun2 … funk )
• (let ((x exp1) (y exp2) (z exp3))
fun1 fun2 … funk )
• (let* ((x exp1) (y exp2) (z exp3))
fun1 fun2 … funk )
• (letrec ((x exp1) (y exp2) (z exp3))
fun1 fun2 … funk )
2021-07-05 8:46 AM 12
Variants of let: let* & letrec
• In a let expression, bindings are activated after all are
evaluated
(let ((x exp1) (y exp2) (z exp3))
expression
)
• The let* variant of let activates a binding after
evaluation
(let* ((x exp1) (y exp2) (z exp3))
expression
)
• The letrec variant of let activates a binding as it is
evaluated
(letrec ((x exp1) (y exp2) (z exp3))
expression
)
2021-07-05 8:46 AM 13
x, y, and z are only visible here
x, y, and z visible here x visible here
x and y visible here
x visible here
Pascal Example
procedure P1( A1 : T1 );
var X : real;
procedure P2( A2 : T2 );
procedure P3( A3 : T3 );
begin
…
end;
begin
…
end;
procedure P4( A4 : T4 );
function F1( A5: T5) : T6;
var X : integer;
begin
… end;
begin
… end;
begin
…
end;
P1( A1 ) { // sees P1, A1, X, P2, P4
real X
P2( A2 ) { // sees P1, A1, X,
// P2, P3, A2
}
P4( A4 ) { // sees P1, A1, X,
// P2, P4, A4, F1
int X
}
F1( A5 ) {
}
P3( A3 ) { // Sees P1, A1, X,
// P2, A2, P3, A3
}
2021-07-05 8:46 AM 14
End of this Part
CSCI 3136
2021-07-05 8:46 AM 15
Nested Functions
CSCI 3136
2021-07-05 8:46 AM 16
Pascal Example
procedure P1( A1 : T1 );
var X : real;
procedure P2( A2 : T2 );
procedure P3( A3 : T3 );
begin
…
end;
begin
…
end;
procedure P4( A4 : T4 );
function F1( A5: T5) : T6;
var X : integer;
begin
… end;
begin
… end;
begin
…
end;
P1( A1 ) { // sees P1, A1, X, P2, P4
real X
P2( A2 ) { // sees P1, A1, X,
// P2, P3, A2
}
P4( A4 ) { // sees P1, A1, X,
// P2, P4, A4, FA
int X
}
F1( A5 ) {
}
P3( A3 ) { // Sees P1, A1, X,
// P2, A2, P3, A3
}
2021-07-05 8:46 AM 17
Nested Classes and Functions
• Idea: Many languages support nested classes and functions
• Why? To hide (encapsulate) functionality
This makes code easier to understand
• Nested Classes: supported in languages like Java
• Class definitions can contain class definitions, e.g.
class Apple {
…
class Seed {
…
• Inner classes have access to outer classes methods and fields
• Nested Functions: supported in languages like Pascal
• See example in previous slide
• Inner function has access to everything the outer function does,
plus it’s own parameters.
2021-07-05 8:46 AM 18
Implementation of Nested
Functions in Lexical Scope
• Challenge, inner functions must be able to access
the local variables of all outer functions
• Need reference to stack frame of outer functions
• Idea: Store references to outer functions’ stack
frame in inner functions’ stack frame.
• Why the stack frame? Recursion!
2021-07-05 8:46 AM 19
Stack Frame Links Example
func A() {
int alpha
func B() {
int beta
func C() { … }
func D() {
int delta
… C() …
}
… D() …
}
func E() {
… B() …
}
… E() …
}
• The call chain is:
• A → E → B → D → C
B()’s stack frame
E()’s stack frame
D()’s stack frame
C()’s stack frame
A()’s stack frame
beta
delta
alpha
2021-07-05 8:46 AM 20
Why Stack Frames? Recursion!
func A() {
int alpha
func B() {
int beta
func C() { … A() …}
func D() {
int delta
… C() …
}
… D() …
}
func E() {
… B() …
}
… E() …
}
A → E → B → D → C → A → E → B → D → C → …
B()’s stack frame
E()’s stack frame
D()’s stack frame
C()’s stack frame
A()’s stack frame
beta
delta
alpha
B()’s stack frame
E()’s stack frame
D()’s stack frame
C()’s stack frame
A()’s stack frame
beta
delta
alpha
2021-07-05 8:46 AM 21
End of this Part
CSCI 3136
2021-07-05 8:46 AM 22
Dynamic Scope
CSCI 3136
2021-07-05 8:46 AM 23
Dynamic Scope
Current binding for a given name is the one
• Encountered most recently during execution
• Not hidden by another binding for the same name
• Not yet destroyed by exiting its scope
• This happens when a language implementation
uses a single global reference environment instead
of linked environments
2021-07-05 8:46 AM 24
Perl Example
# Static scoping
sub f {
my $a = 1;
print “f:$a\n”;
&printa();
}
sub printa {
print “p:$a\n”;
}
$a = 2;
&f();
# Dynamic scoping
sub g {
local $a = 1;
print ”g:$a\n”;
&printa();
}
sub printa {
print “p:$a\n”;
}
$a = 2;
&g();
Output
f:1
p:2
Output
g:1
p:1
Most
recently
seen a
2021-07-05 8:46 AM 25
Static vs Dynamic Example
Static Dynamic
Output is 1 Output is 2
a : integer — global declaration
procedure first
a := 1
procedure second
a : integer — local declaration
first()
a := 2
second()
write_integer(a)
In dynamic
scoping, first()
will use this
variable
2021-07-05 8:47 AM 26
End of this Part
CSCI 3136
2021-07-05 8:47 AM 27
Functions as 1st Class
Objects
CSCI 3136
2021-07-05 8:47 AM 28
Passing Functions
• Idea: In many languages we can
• Pass a subroutine/function as a parameter
• Return a subroutine/function
I.e. functions are first class objects
• Example:
int add( int a, int b ) {
return a + b;
}
int do_op( (int)(*op)(int,int), int o1, int o2 ) {
return (*op)( o1, o2 ); /* call op() */
}
…
do_op( &add, 1, 2 );
…
2021-07-05 8:47 AM 29
Passing Functions (cont)
• Languages that allow passing functions:
• Scheme
• C, C++
• Java (as of Java 8)
• Many more
• What value does do_op() return? 10 or 16?
int add( int a, int b ) {
return a + b + offset;
}
int do_op( (int)(*op)(int,int), int o1, int o2 ) {
int offset = 7;
return (*op)( o1, o2 ); /* call op() */
}
…
int offset = 13;
do_op( &add, 1, 2 );
2021-07-05 8:47 AM 30
Aside: Free Variables
• Definition: A free variable is any variable that is not
local or a parameter.
int add( int a, int b ) {
return a + b + offset;
}
2021-07-05 8:47 AM 31
End of this Part
CSCI 3136
2021-07-05 8:47 AM 32
Shallow vs Deep Binding
CSCI 3136
2021-07-05 8:47 AM 33
Shallow vs Deep Binding
• If a subroutine is passed as a parameter, when are
its free variables bound?
• Shallow binding occurs when the routine is called
• Deep binding occurs when the routine is first passed as
a parameter
• Known as the funarg problem
2021-07-05 8:47 AM 34
Shallow vs Deep Binding Example
Shallow Deep
Output is
130
10
Output is
30
110
What is the output?
int x = 10;
function f( int a ) {
x = x + a;
}
function g( function h ) {
int x = 30;
h( 100 );
print( x );
}
function main() {
g( f );
print( x );
}2021-07-05 8:47 AM 35
Shallow or Deep Binding in Scheme?
(define increase_x
(lambda ()
(set! x (+ x 1))))
(define execute
(lambda (f)
(let ((x 20))
(display (list “inner x before:” x))
(f)
(display (list “inner x after: ” x)))))
(define x 1)
(display (list “outer x before:” x))
(execute increase_x)
(display (list “outer x after: ” x))
What is the output?
(outer x before: 1)
(inner x before: 20)
(inner x after: 20)
(outer x after: 2)
2021-07-05 8:47 AM 36
End of this Part
CSCI 3136
2021-07-05 8:47 AM 37
How are the SRIs used?
ü Course and program (re) design.
ü Evaluation of teaching effectiveness.
ü Promotion and tenure applications for instructors, and
other personnel decisions.
ü Preparation of supporting evidence for teaching awards
and grants.
ü Quality assurance processes in the review and restructure
of institutional, faculty, department and program goals.
How to complete the SRI
ìFind the email in your Dal email account
ìSubject heading (depending on the system) is:
ì Student Ratings of Instruction; or
ì Course Name and Number
ìOpen the email and click on the link
ì Your course list should be visible
ì Select the course for which you want to complete the
evaluation
ìBe sure to hit the SUBMIT button when you FINISH
completing the form
ì You may also SAVE and return to your work later
2021-07-05 8:47 AM 39