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: