CS计算机代考程序代写 scheme prolog chain Java c++ Lecture_19_Scope

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