程序代写代做代考 scheme interpreter lec15

lec15

CS 314 Principles of Programming Languages

Prof. Zheng Zhang
Rutgers University

Lecture 15: Functional Programming

October 24, 2018

Class Information

2

• HW5 posted in Sakai.
• HW6 will be posted by the end of today.
• Next week’s recitation is a review for midterm. Attendance is encouraged!
• Reminder: Midterm exam 11/7, in class, closed book, closed notes. 


Midterm covers lecture 1-12, hw 1-5, and corresponding book chapters.
• There will be extended office hours next week. 


Pay attention to Sakai announcements!

Scheme – Functions as First Class Values (Higher-Order)

3

• (f number? 0) ⇒ (number? 0) ⇒ #t
• (f length ‘(1 2)) ⇒ (length ‘(1 2)) ⇒ 2
• (f (lambda (x) (* 2 3)) 3) ⇒ ((lambda (x) (* 2 3)) 3) ⇒ (* 2 3) ⇒ 6

Functions as arguments:
(define f (lambda (g x) (g x) ) )

Scheme – Functions as First Class Values (Higher-Order)

4

Computation, i.e., function application is performed by reducing the
initial S-expression (program) to an S-expression that represents a value.

• function values (e.g.: (lambda (x) e) )
• constants (e.g.: 3, #t)

Examples for S-expressions that directly represent values, i.e., cannot be
further reduced:

Computation completes when S-expression cannot be further reduced

Reduction is performed by substitution, i.e., replacing formal by actual
parameters in the function body.

Review: Higher-Order Functions (Cont.)

5

• (plusn 5) evaluates to a function that adds 5 to its argument: 


Question: How would you write down the value of (plusn 5)?

Functions as returned value:
(define plusn
( lambda (n) 

(lambda (x) (+ n x)) 

)
) Return a function

(lambda (x) (+ 5 x))

• ((plusn 5) 6) = ?

Review: Higher-Order Functions (Cont.)

6

In general, any n-ary function
(lambda (x_1 x_2 … x_n) e)

can be rewritten as a nest of n unary functions:
(lambda (x_1)

(lambda (x_2)
(… (lambda(x_n) e) … )))

Review: Higher-Order Functions (Cont.)

7

This translation process is called currying. It means that having
functions with multiple parameters do not add anything to the
expressiveness of the language:
( (lambda (x_1 x_2 … x_n) e) v_1 v_2 … v_n)

( … (((lambda (x_1)
(lambda (x_2)

(lambda (x_n) e )…)) v_1) v_2) … v_n)

In general, any n-ary function
(lambda (x_1 x_2 … x_n) e)

can be rewritten as a nest of n unary functions:
(lambda (x_1)

(lambda (x_2)
(… (lambda(x_n) e) … )))

Review: Higher-order Functions: map

8

• map takes two arguments: a function f and a list l
• map builds a new list by applying the function to every element of

the (old) list

(define map
(lambda ( f l )
(if (null? l)
‘( )
( cons ( f (car l) ) ( map f (cdr l) ) )
)
)
)

function

list

Apply f to the first element of l Apply map and f to the rest of l

Review: Higher-Order Functions: map

9

• Example: 

(map abs ‘(-1 2 -3 4)) ⇒ (1 2 3 4) 

(map (lambda (x) (+ 1 x)) ‘(-1 2 3) ⇒ (0 3 4)

• Actually, the built-in map can have more than two arguments: 

(map + ‘(1 2 3) ‘(4 5 6)) ⇒ (5 7 9)

Review: More on Higher-Order Functions

10

reduce Higher order function that takes a binary, associative operation
and uses it to “roll up” a list

(define reduce
(lambda ( op l id)
( if (null? l)
id
(op (car l) (reduce op (cdr l) id)) ) ) )

Example: (reduce + ‘(10 20 30) 0) ⇒
(+ 10 (reduce + ‘(20 30) 0)) ⇒
(+ 10 (+ 20 (reduce + ‘(30) 0))) ⇒
(+ 10 (+ 20 (+ 30 (reduce + ‘() 0)))) ⇒
(+ 10 (+ 20 (+ 30 0))) ⇒
60

Review: Higher-Order Functions

11

Compose higher order functions to form compact powerful functions

(define sum
(lambda (f l)
(reduce + ( map f l ) 0) ) )

(sum (lambda (x) (* 2 x)) ‘(1 2 3) ) ⇒

(reduce (lambda (x y) (+ 1 y)) ‘(a b c) 0) ⇒

Lexical Scoping and let, let*, and letrec

12

All are variable binding operations:

LET = let, let*, letrec

(LET ( (v1 e1)
(v2 e2)

(vn en) )

e
)

Lexical Scoping and let, let*, and letrec

13

• let:
– binds variables to values (no specific order), and evaluate body e

using bindings
– new bindings are not effective during evaluation of any ei

• let*:
– binds variables to values in textual order of write-up
– new binding ei-1 is effective for next ei .

• letrec:
– bindings of variables to values in no specific order
– independent evaluations of all ei to values have to be possible
– new bindings effective for all ei
– mainly used for recursive function definitions

let and let* example

14

( let ( (a 5) (b 6) )
( + a b ) ) ;; ⇒ 11

(let ( (a 5) (b (+ a 6)) )
( + a b ) ) ;; ⇒ ERROR: a: undefined

(let* ( (a 5) (b (+ a 6)) )
( + a b ) ) ;; ⇒ 16

Note: let and let* do not add anything to the expressiveness of the
language, i.e., they are only a convenient shorthand. For instance, (let
((x1 e1) (x2 e2)) e) can be rewritten as ((lambda (x y) e) v1 v2)

let and let* example

15

( let ( (a 5) (b 6) )
( + a b ) ) ;; ⇒ 11

(let ( (a 5) (b (+ a 6)) )
( + a b ) ) ;; ⇒ ERROR: a: undefined

(let* ( (a 5) (b (+ a 6)) )
( + a b ) ) ;; ⇒ 16

Note: let and let* do not add anything to the expressiveness of the
language, i.e., they are only a convenient shorthand. For instance, (let
((x1 e1) (x2 e2)) e) can be rewritten as ((lambda (x y) e) v1 v2)

let and let* example

16

( let ( (a 5) (b 6) )
( + a b ) ) ;; ⇒ 11

(let ( (a 5) (b (+ a 6)) )
( + a b ) ) ;; ⇒ ERROR: a: undefined

(let* ( (a 5) (b (+ a 6)) )
( + a b ) ) ;; ⇒ 16

Note: let and let* do not add anything to the expressiveness of the
language, i.e., they are only a convenient shorthand. For instance, (let
((x1 e1) (x2 e2)) e) can be rewritten as ((lambda (x y) e) v1 v2)

let and let* example

17

( let ( (a 5) (b 6) )
( + a b ) ) ;; ⇒ 11

(let ( (a 5) (b (+ a 6)) )
( + a b ) ) ;; ⇒ ERROR: a: undefined

(let* ( (a 5) (b (+ a 6)) )
( + a b ) ) ;; ⇒ 16

Note: let and let* do not add anything to the expressiveness of the
language, i.e., they are only a convenient shorthand. For instance, (let
((x1 e1) (x2 e2)) e) can be rewritten as ((lambda (x y) e) v1 v2)

let and let* example

18

( let ( (a 5) (b 6) )
( + a b ) ) ;; ⇒ 11

(let ( (a 5) (b (+ a 6)) )
( + a b ) ) ;; ⇒ ERROR: a: undefined

Note: let and let* do not add anything to the expressiveness of the
language, i.e., they are only a convenient shorthand. For instance, (let
((x1 e1) (x2 e2)) e) can be rewritten as ((lambda (x y) e) v1 v2)

let and let* example

19

( let ( (a 5) (b 6) )
( + a b ) ) ;; ⇒ 11

(let ( (a 5) (b (+ a 6)) )
( + a b ) ) ;; ⇒ ERROR: a: undefined

(let* ( (a 5) (b (+ a 6)) )
( + a b ) ) ;; ⇒ 16

Note: let and let* do not add anything to the expressiveness of the
language, i.e., they are only a convenient shorthand. For instance, (let
((x1 e1) (x2 e2)) e) can be rewritten as ((lambda (x y) e) v1 v2)

let and let* example

20

( let ( (a 5) (b 6) )
( + a b ) ) ;; ⇒ 11

(let ( (a 5) (b (+ a 6)) )
( + a b ) ) ;; ⇒ ERROR: a: undefined

(let* ( (a 5) (b (+ a 6)) )
( + a b ) ) ;; ⇒ 16

Note: let and let* do not add anything to the expressiveness of the
language, i.e., they are only a convenient shorthand. For instance, (let
((x1 e1) (x2 e2)) e) can be rewritten as ((lambda (x y) e) v1 v2)

letrec examples

21

Typically used for local definitions for recursive functions

(letrec ( (a 5)
(b ( lambda() (+ a 6) ) ) )

( + a (b) ) ) ;; ⇒ 16

(letrec ( (b (lambda () (+ a 6) ) )
(a 5) )
( + a (b) ) ) ;; ⇒ 16

(letrec ( (even? (lambda (x)
( or (= x 0) (odd? (- x 1)) ) ) )
(odd? (lambda (x)
( and (not (= x 0)) (even? (- x 1)) ))) )
( list (even? 3) (even? 20) (odd? 21) ) ) ;; ⇒ (#f #t #t)

letrec examples

22

Typically used for local definitions for recursive functions

(letrec ( (b (lambda () (+ a 6) ) )
(a 5) )
( + a (b) ) ) ;; ⇒ 16

(letrec ( (even? (lambda (x)
( or (= x 0) (odd? (- x 1)) ) ) )
(odd? (lambda (x)
( and (not (= x 0)) (even? (- x 1)) ))) )
( list (even? 3) (even? 20) (odd? 21) ) ) ;; ⇒ (#f #t #t)

(letrec ( (a 5)
(b ( lambda () (+ a 6) ) ) )

( + a (b) ) ) ;; ⇒ 16

letrec examples

23

Typically used for local definitions for recursive functions

(letrec ( (even? (lambda (x)
( or (= x 0) (odd? (- x 1)) ) ) )
(odd? (lambda (x)
( and (not (= x 0)) (even? (- x 1)) ))) )

( list (even? 3) (even? 20) (odd? 21) ) ) ;; ⇒ (#f #t #t)

letrec examples

24

Typically used for local definitions for recursive functions

(letrec ( (even? (lambda (x)
( or (= x 0) (odd? (- x 1)) ) ) )
(odd? (lambda (x)
( and (not (= x 0)) (even? (- x 1)) ))) )

( list (even? 3) (even? 20) (odd? 21) ) ) ;; ⇒ (#f #t #t)

Lexical (Static) Scoping

25

• The occurrence of a variable matches the lexically closed binding
occurrence.

• An occurrence of a variable without a matching binding occurrence is
called free.

• A variable can occur free and bound in an expression.

We only substitute free occurrences of the formal arguments in
the function body when making a function application!

Free and Bound

26

Consider the following function definition:
(define plusn
( lambda (n) 

( lambda (x) (+ n x) ) 

)
) n is free

Free and Bound

27

Consider the following function definition:
(define plusn
( lambda (n) 

( lambda (x) (+ n x) ) 

)
) n is bound

Environment and Closure

28

• Record the bindings for the variables. If we need the value that
a variable denotes, we just look it up in the environment.

Environment:

An environment is a finite map from variables to values
ρ ∈ Env = Variables → Values

Closures

29

Pair the environment with a function (lambda abstraction). The
environment must contain values for all free variables of the function.
The function can only be evaluated in its attached environment.

Such a pairing is called a Closure.

A closure is a pair consisting of an environment and a function definition.

cl ∈ Closure = {⟨λ, ρ⟩ | FreeVar(λ) ⊆ DOM(ρ)}

Closures can be used to implement lexical scoping.
They represent lexically scoped function values.

How to Apply a Closure?

30

• Let cv be the closure value < (lambda (x) e), ρ >
• Apply cv to a value av as follows:

How to apply a closure value to actual argument values?

Evaluate the body e of the function in the environment ρ of
the closure extended by the mapping of the formal
parameter x to the actual parameter av (ρ[x —> av]).

How to Apply a Closure: Examples

31

((lambda(x) 

((lambda(z) ((lambda(x)(z x)) 3)) (lambda(y)(+ x y)))) 1)

closure interpreter
{ }

((lambda(z) ((lambda(x)(z x)) 3))

(lambda(y)(+ x y)) )
{ x → 1 }

((lambda(x) (z x))
3 )

{ x → 1,
z→⟨ (lambda(y)(+ x y)),{x→1}⟩ }

(z x) { x→3,
 z→⟨(lambda(y)(+ x y)),{x→1}⟩ }

(+ x y)

4

{ x → 1, y → 3}

Next Lecture

32

• Scott, Chapter 11.1 – 11.3
• Scott, Chapter 11.7

Reading: