CS 461
Lambda Calculus 8: Functional Programming in Racket (2)
Yanling Wang
Computer Science and Engineering Penn State University
Carnegie Mellon
1
PSU CMPSC courses are practical!
¢ Last lecture in chat that most PSU CMPSC courses are geared for research
§ I whole heartedly disagree based on all the courses I have taught
§ 131/132 basics of python programming – practical, learning basics
of programming
§ 221 basics of Java programming – practical, learning the OO paradigms, SQLs, webservers
§ 311 systems programming – using Linux system, shell commands, C programming, memory management, sooo practical
§ 360 – graph theory (foundation for many algorithms), counting, probability, number theory (encryption)
§ 461 – programming languages (see more)
Carnegie Mellon
2
PSU CMPSC courses are practical!
¢ Other courses I haven’t taught but know that are important
§ 473 – operating systems, multi-thread programming, extension of 311
§ 465 — trust me on this: interviewing for any software engineering jobs means reviewing every algorithms you have learned.
§ I reread my algorithm textbook cover to cover (mine was 2nd edition) before I nailed my Google interview
– https://www.amazon.com/Introduction-Algorithms-3rd- MIT-Press/dp/0262033844
§ If you are working LeetCode to prepare for your interview, use an algorithm book as a reference
– Algorithms on Sorting, Graph, Dynamic Programming and complexity analysis
Carnegie Mellon
3
Why is 461 important in industry?
¢ Learn a new language faster
§ Learn syntax quickly – RE and CFG
§ Lexical tokens (variable names, constant values, operators)
§ Parsing of your program
§ Get the different programming paradigm
§ Imperative?
§ Functional?
§ Object-Oriented?
§ Understand the meaning/semantics of the language to write correct and efficient programs
§ Master basic constructs needed (conditionals, loops, functions)
§ Understand variable scopes
§ Understand types of values and use different types of values properly § Understand memory layout and internals of the language
Carnegie Mellon
4
Why is 461 important in industry?
¢ Understand recursion and induction
§ Functional programming uses recursions and inductions
§ Fundamental way of computational thinking (big problems->small problems)
§ Lambda calculus
§ Structural Induction – a common way of breaking a big problems into smaller problems of different cases by structure.
Carnegie Mellon
5
Why is 461 important in industry?
¢ You can implement your own Domain-Specific Language § Boiler-plate code for similar tasks in work
§ Domain-Specific Language to make these tasks easy
§ You learn the building blocks to create your own DSL
§ Example:
§ In Google, a Site-Reliability Engineer (SRE) is someone who monitors the datacenter machine’s health (hardware and software)
§ Boiler plate monitoring code to be put on every machine that periodically checks the health of the machine and reports data/problems to SRE.
§ Borgmon (a DSL just for this purpose)
– https://sre.google/sre-book/practical-alerting/
Carnegie Mellon
6
Functional Programming in Racket
¢ Definitions: (define …)
¢ Functions: (lambda (…) …)
¢ Numbers and Booleans § +,-,*,/
§ comparisons
¢ Conditional: (if … … …) (cond [… …] [… …] [else …]) ¢ List: (cons … …), (car …), (cdr …)
¢ Local Bindings (let …) (let* …) (letrec …)
Carnegie Mellon
7
Parenthesis in Scheme
In Scheme, () is used for lists, and both code and
data are lists ¢ (+ 2 3) ¢ (2 3 4)
Lists are evaluated as function calls
¢ (+ 2 3)
¢ ((+ 2 3)) ¢ (2 3 4)
Evaluates to 5
Exception: 5 is not a procedure Exception: 2 is not a procedure
Lists w/o evaluation: use apostrophe (’)
¢ ’(234)
Returns ’(2 3 4)
Carnegie Mellon
8
8
Expressions
Arithmetic: Relational: Conditional: Type test:
Carnegie Mellon
(* 1 2 3 4)
(+ (* 1 2) (* 2 4))
(< (* 1 2) (+ 1 1))
(and (> 2 4) #f)
(if (< 2 3) 1 (+ 2 3))
(* 2 (if (< 3 5) 3 “abc”))
(number? 2) (number? #f)
(string? “a”) (string? 1)
(boolean? #t) (boolean? 1)
9
9
Environment
Environment binds identifiers to values
¢ +,*,-,/ are identifier bound to values ¢ Functions are values in Scheme
Built-in identifiers in initial environment
¢ +, sqrt, positive?, max, ...
Add bindings to the environment ¢ Key word: define
Carnegie Mellon
10
10
Definition Built-in identifiers
(max 1 2 3)
“define” introduce global identifiers
Carnegie Mellon
(define pi 3.14159)
(define radius 2)
(* pi (* radius radius))
(define circumference (* 2 pi radius))
circumference
11
11
Local Definition Let Expr.:
General form:
Carnegie Mellon
(let [(x 3)
(y (sqrt 7))]
(+ x y))
(let [(x1 exp1)
(x2 exp2)
...
(xn expn)]
body_exp)
x1,x2,...,xn can be used in body_exp
12
12
Local Definition Let* Expr.:
General form:
Carnegie Mellon
(let* ((x 3)
(y x))
(+ x y))
(let* ((x1 exp1)
(x2 exp2)
...
(xn expn))
body_exp)
x1 can be used in exp2, exp3, ..., body_exp x2 can be used in exp3, exp4, ..., body_exp ...
13
13
Anonymous Function
Anonymous functions are introduced by lambda
Examples
parameters
func. body
Carnegie Mellon
(lambda (x y z) expr)
((lambda (x) x) 1)
((lambda (x y z) (+ x y z)) 1 2 3)
14
14
((lambda (f) (f 3))(lambda (x)(cons x ‘(2))))
Named Function
(define pi 3.14159)
In Scheme, function is a first-class value, so similarly, we can define named functions
Carnegie Mellon
(define f (lambda (x) (+ x
1)))
(f 1)
(let ((f (lambda (x) (+ x 1)))
(g (lambda (y) (* y 2))))
(+ (f 1) (g 2)))
15
15
Named Function
In Scheme, named functions can be introduced in a more concise way:
(define (f x) (+ x 1))
func. name parameter
is the same as
(define f (lambda (x) (+ x 1)))
Carnegie Mellon
16
16
Named Function
Name Parameter
Carnegie Mellon
(define (sqr x) (* x x))
(sqr 5)
(define (area x y) (* x y))
(area 5 10)
Common use:
(define (f x y z)
(let ((x1 exp)
(x2 exp))
f’s body))
17
17
Function Examples
Carnegie Mellon
(define (test x)
(cond ((number? x) "num")
((string? x) "str")
((list? x) "list")
(else "other")))
(define (abs x)
(cond ((< x 0) (- x))
(else x)))
(define (factorial n)
(if (= n 0) 1
(* n (factorial (- n 1)))))
18
18
Scheme: Key Points
Evaluation of expressions (e0 e1 e2 e3)
Carnegie Mellon
Key words
No static type system
define, if, cond, ‘
(define (f x) (+ x “abc”))
(* 2 (if (< 3 5) 3 “abc”))
19
19
Scheme: Key Points
No assignments, no iterations (loops)
All variables are immutable (mathematical symbols)
Carnegie Mellon
20
20
Higher Order Functions in Functional Programming
¢ Second-Order Functions
§ Languages where it allows a function as an argument to another
function.
¢ First-Order Functions
§ Languages where it allows a function to be:
§ An argument to another function (second order) § The return value of a function (first order)
Carnegie Mellon
21
Function as Argument Repeat any function twice?
Carnegie Mellon
(define (double x) (* x 2))
(define (quad x) (double (double x))
(define (square x) (* x x))
(define (fourth x) (square (square
x))
More reusable code
(define (twice f x) (f (f x)))
(twice double 2)
(twice square 3)
22
22
Examples w/o Higher-Order Functions Find all numbers > 5 in a list
Find all strings in a list
Carnegie Mellon
newlist = empty
foreach (elem in lst)
if (elem > 5)
add elem to newlist
newlist = empty
foreach (elem in lst)
if (elem is String)
add elem to newlist
23
23
Filter
filter pred lst: return a new list with elements from lst for which pred returns #t
Carnegie Mellon
24
24
Examples w Higher-Order Functions filter pred lst: return a new list with elements from
lst for which pred returns #t
(filter (lambda (x) (> x 5)) ’(1 4 7
10))
(filter string? ’(1 “1” 2 “2” 3 “3”))
Carnegie Mellon
25
25
Examples w/o Higher-Order Functions Multiple 2 to each element in a list
Square each element in a list
Carnegie Mellon
newlist = empty
foreach (elem in lst)
add elem*2 to newlist
newlist = empty
foreach (elem in lst)
add elem*elem to newlist
26
26
Map
map f l: applies function f to each element of list l
Carnegie Mellon
27
27
Examples w Higher-Order Functions map f l: applies function f to each element of list l
(map double ’(1 2 3))
(map square ’(1 2 3))
Carnegie Mellon
28
28
List Example
Define subs, which takes a b lst, and replaces a with b in lst
Carnegie Mellon
(define (subs a b lst)
(if (null? lst) ‘()
(let [(rest (subs a b (cdr lst)))]
(if (equal? (car lst) a)
(cons b rest)
(cons (car lst) rest)))))
29
29
Map
Using map, we have
Carnegie Mellon
(define (subs a b lst)
(map (lambda (c)
(if (equal? a c) b c))
lst))
30
30
Examples w/o Higher-Order Functions Compute the sum of a list
Compute the product of a list
Carnegie Mellon
init = 0
foreach (elem in lst)
init += elem
init = 1
foreach (elem in lst)
init *= elem
31
31
Foldl
foldl f a (e1 e2 en): returns f en(… (f e2(f e1 a)) …)
Carnegie Mellon
32
32
Examples with Higher-Order Functions
foldl f a (e1 e2 en): returns f en(… (f e2(f e1 a)) …)
(foldl + 0 ‘(1 2 3 4 5))
(foldl * 1 ‘(1 2 3 4 5))
Carnegie Mellon
33
33
Foldl
In previous lecture, we had:
lst)))))
Using foldl, we have
(define (lstSum lst) (foldl + 0 lst)
Carnegie Mellon
(define (lstSum lst)
(if (null? lst) 0
( + (car lst) (lstSum (cdr
34
34
Examples with Higher-Order Functions
foldl f a (e1 e2 en): returns f en(… (f e2(f e1 a)) …)
Carnegie Mellon
(foldl (lambda (x a) (+ a (* x x)))
0 ‘(1 2 3 4 5))
35
35
Function as Return Value
In Scheme, function is a first-class value (Functions can go wherever expressions go)
¢ Functions as return values
(define (addN n) (lambda (m) (+ m n)))
((addN 10) 20) (+ 10 20)
(twice (addN 10) 20) (twice (+ 10) 20)
Carnegie Mellon
36
36
Multi-Argument Functions
(define (add m n) (+ m n))
add: Int, Int → Int
Pass multiple parameters as a list?
Carnegie Mellon
(add ’(1 2))
(add 1 2)
add takes 2 parameters
37
37
Multi-Argument Functions
(define (add m n) (+ m n))
add: Int, Int → Int
Add 2 to each element in a list?
map f l: applies function f to each element of
list l
(map (add 2) ’(1 2 3)) ?
Carnegie Mellon
38
38
Multi-Argument Functions
(define (add m n) (+ m n))
add: Int, Int → Int
Add 2 to each element in a list?
map f l: applies function f to each element of list l
Carnegie Mellon
(map (add 2) ’(1 2 3))
add takes two parameters
A multi-argument function can only
be used when all parameters are ready!
39
39
Currying: Every function is treated as taking at most one parameter
(define (add m n) (+ m n))
add: Int, Int → Int
Curried version
(define (addN n) (lambda (m) (+ m n))
addN: Int → (Int → Int)
also written as: Int → Int → Int (right associative)
Carnegie Mellon
40
40
Uncurried version Curried version
Carnegie Mellon
(define (add m n)
(+ m n))
(define (addN n)
(lambda (m) (+ m n))
add: Int, Int → Int
addN: Int → (Int → Int)
(add 2 3) ((addN 2) 3)
Curried form allows partial evaluation
(map (add 2)
’(1 2 3))
(map (addN 2)
’(1 2 3))
41
41
Currying
Haskell B. Curry Penn State 1929-1966
Outside of McAllister Building
Carnegie Mellon
42
42
Currying
In terms of lambda calculus,
the curried function of 𝜆𝑥!𝑥” … 𝑥#. 𝑒 is 𝜆𝑥!. (𝜆𝑥”. … 𝜆𝑥#. 𝑒 )
Carnegie Mellon
(define (curry3 f)
(lambda (x)
(lambda (y)
(lambda (z)
(f x y z)))))
(define (curry2 f)
(lambda (x)
(lambda (y)
(f x y))))
43
43
Partial Evaluation
A function is evaluated with one or more of the leftmost actual parameters
((curry2 add) 2)is a partial evaluation of add
We can think it as a temporary result, in the form of a function
Carnegie Mellon
44
44
Partial Evaluation
A function is evaluated with one or more of the leftmost actual parameters
(map ((curry2 add) 2) ’(1 2 3))
add: 𝜆𝑥 𝑦. (+ 𝑥 𝑦) curry2add :𝜆𝑥.𝜆𝑦.(+𝑥𝑦)
curry2add 2 :𝜆𝑦.(+2𝑦)
map( curry2add 2) ’ 123 :’ 345
Carnegie Mellon
45
45
Uncurrying
In terms of lambda calculus,
the uncurried function of 𝜆𝑥!.(𝜆𝑥”. … 𝜆𝑥#.𝑒 )is 𝜆𝑥!𝑥” …𝑥#.𝑒
Carnegie Mellon
(define (uncurry2 f)
(lambda (x y)
((f x) y)))
(define (uncurry3 f)
(lambda (x y z)
(((f x) y) z)))
46
46