CS计算机代考程序代写 scheme python chain Java Lecture_20_Closures

Lecture_20_Closures

Closures
CSCI 3136: Principles of Programming Languages

Agenda
• Announcements

• Assignment 9 is out and due July 19.
• Lectures are being recorded
• Test 3, Thursday, July 29 – 9:00am
• Student Rating Instruction is open

• Readings: Read Chapter 3.6
• Lecture Contents

• Finish Deep vs Shallow binding from previous lecture
• Motivation
• Definition of a closure
• Linked Referencing Environments
• Implementing Closures

2021-07-12 10:56 AM 2

Keywords
• Closure

• Subroutine
• Procedure
• Function
• Parameter
• Reference to
• Scope

• Referencing environment
• Deep binding
• Shallow binding
• Active Bindings
• Bound / Unbound variable

• Linked Referencing Environments
• Frame
• Chain of frames

2021-07-12 10:56 AM 3

End of this Part
CSCI 3136

2021-07-12 10:56 AM 4

Preliminaries
CSCI 3136

2021-07-12 10:56 AM 5

A Useful Short-form of Lambda
In Scheme, this

( define add ( lambda ( a b )
( + a b )

)
)

Is equivalent to
( define (add a b)

( + a b )
)

The latter is a short form for the former, only
available for the define statement

2021-07-12 10:56 AM 6

Motivation for Closures
• A subroutine is a general term for a procedure or a function
• Idea: Passing subroutines is allowed in many languages

• Reference to a subroutine can be passed as a parameter
• Subroutine has access to all active bindings in its scope

• Idea: Referencing environment of a subroutine contains all
the active bindings
• If deep binding is used, referencing environment is created when

subroutine is passed
• If shallow binding is used, referencing environment is created when

subroutine is called
• Closures are a construct found in languages with deep

binding
• Closures are used to implement language abstractions such

as callbacks, listeners, iterators and generators.

2021-07-12 10:56 AM 8

End of this Part
CSCI 3136

2021-07-12 10:56 AM 9

Closures
CSCI 3136

2021-07-12 10:56 AM 10

Closure
• A closure consists of

• A reference to a subroutine
• A referencing environment

• Analogy: A program and its data.
• This is different from an object:

• object = data + operations on the data
• closure = subroutine (1 op) + data that it needs

• Idea: Closures can be used like objects
• Challenge: implementing closures when they can be

returned by functions
• When the subroutine is invoked, the scope it refers to may no

longer exist
• Scopes must be preserved for use in closures

Subroutine

foo : 42
bar : hello
x : 13
y : 7

2021-07-12 10:56 AM 11

(define new-counter
(lambda ()
(define c 0)
(lambda ()
(set! c (+ c 1))
c

)
)

)

Closure Example

2021-07-12 10:56 AM 12

c:2

(define new-counter
(lambda ()

(define c 0)
(lambda ()

(set! c (+ c 1))
c

)
)

)

Closure Example
> (define cnta (new-counter))
> (cnta)
1
> (cnta)
2
> (define cntb (new-counter))
> (cntb)
1

c:1c:0

c:2c:1c:0

2021-07-12 10:56 AM 13

A set! Aside
• In Scheme, the set! function modifies the value

of a bound variable
• Example:

(define answer 42)
(set! answer 7)
(display answer)

Should yield 7, not 42
• The result of a set! expression is undefined
• This operation creates a side-effect in the program
• It is the equivalent of the assignment operator and

should be used very carefully

Example

switch( op ) {
case push: …
case pop: …
case empty: …

stack : ()

A call to new-stack
creates and returns
the closure below.

2021-07-12 10:56 AM 15

The evaluation of the (let …) will
return a lambda with the stack variable

(define new-stack (lambda ()

(let ((stack ‘()))

(lambda (op . arg)

(cond

((eq? op ‘push)

(set! stack (cons (car arg) stack))

)

((eq? op ‘pop)

(let ((top (car stack)))

(set! stack (cdr stack))

top

)

)

((eq? op ‘empty)

(null? stack)

)

)

)

)

) )

Example(define new-stack (lambda ()
(let ((stack ‘()))

(lambda (op . arg)

(cond

((eq? op ‘push)

(set! stack (cons (car arg) stack))

)

((eq? op ‘pop)

(let ((top (car stack)))

(set! stack (cdr stack))

top

)

)

((eq? op ‘empty)

(null? stack)

)

)

)

)

) )

switch( op ) {
case push: …
case pop: …
case empty: …

stack : ()

A call to new-stack
creates and returns
the closure below.

2021-07-12 10:56 AM 16

The . arg denotes a
variable list of argumentsThis is a switch

expression
This is a switch

expression

(define new-stack (lambda ()

(let ((stack ‘()))

(lambda (op . arg)

(cond

((eq? op ‘push)

(set! stack (cons (car arg) stack))

)

((eq? op ‘pop)

(let ((top (car stack)))

(set! stack (cdr stack))

top

)

)

((eq? op ‘empty)

(null? stack)

)

)

)

)

) )

Result

> (define st1 (new-stack))
> (st1 ‘push 3)
> (st1 ‘empty)
#f
> (st1 ‘push 4)
> (st1 ‘pop)
4
> (st1 ‘pop)
3
> (st1 ‘empty)
#t

st1 :

2021-07-12 10:56 AM 17

End of this Part
CSCI 3136

2021-07-12 10:56 AM 18

Linked Referencing
Environments
CSCI 3136

2021-07-12 10:56 AM 19

Linked Referencing Environments

foo : 10
bar : ”hello”
x : 42
z : 13

x : 42

z : 13
foo : 10

bar : “hello”
foo : 15

Current Reference
Environment

2021-07-12 10:56 AM 20

Linked Referencing Environments
• A frame is a collection of variable-object bindings
• Frames can point to parent frames, resulting in a

chain of frames
• A reference environment is a chain of frames

starting with the most local frame
• Variable x in environment E is unbound if none of

E’s frames binds x
• Otherwise x’s value is the value bound to it in the

closest frame that contains a binding for x

2021-07-12 10:56 AM 21

Linked Referencing Environments

foo : 10
bar : ”hello”
x : 42
z : 13

x : 42

z : 13
foo : 10

bar : “hello”
foo : 15

Current Reference
Environment

2021-07-12 10:56 AM 22

When are Frames Created?
• Idea: A frame is linked into

the environment when a new
scope is entered:

(define a 42)
(let ((b 7) (c 13))
(let ((a 64))

)
)

2021-07-12 10:56 AM 23

b : 7
c: 13

Current Reference
Environment

a : 64

a: 42

This binding
“hides” or

“covers” the
previous
binding

Referencing Environment Example

x : ?

Current Reference
Environment

(lambda (x) (* x x))(define square (lambda (x)
(* x x))

)

square :

2021-07-12 10:56 AM 24

Referencing Environment Example

x : ?

Current Reference
Environment (lambda (x) (* x x))

square :

(define sum2 (lambda (x y)
(+ (square x) (square y)))

)

(define f (lambda (a)
(sum2 (+ a 1) (* a 2)))

)

sum2 :
f :

(lambda (x y)
(+ (square x)

(square y))
)

x : ?
y : ?

(lambda (a)
(sum2 (+ a 1)

(* a 2))
)

a: ?

(define square (lambda (x)
(* x x) )

)

2021-07-12 10:56 AM 25

End of this Part
CSCI 3136

2021-07-12 10:56 AM 26

Implementing Closures
CSCI 3136

2021-07-12 10:56 AM 27

(define new-counter
(lambda ()

(define c 0)
(lambda ()

(set! c (+ c 1))
c

)
)

)
(lambda ()

(set! c (+ c 1))
c

)

Implementing Closures
> (define cnta (new-counter))
> (cnta)
1
> (cnta)
2
> (define cntb (new-counter))
> (cntb)
1

Current Reference Environment

cnta :
cntb :

c: 0c: 1c: 2

(lambda ()
(set! c (+ c 1))
c

)c: 0c: 12021-07-12 10:56 AM 28

Discussion
• Closures seem esoteric, but they are very common

in many programming languages
• Java (v8)
• Scheme
• Python
• Most functional languages
• Ruby

• Java used to use anonymous classes to create small
listeners and callbacks, where closures are more
appropriate

2021-07-12 10:56 AM 29

End of this Part
CSCI 3136

2021-07-12 10:56 AM 30