CS 461
Programming Language Concepts
Gang Tan
Computer Science and Engineering Penn State University
* Some slides are adapted from those by Dr. Danfeng Zhang
Supplementary Slides
Chap 11 Functional Languages
2
12
Why Study Functional Programming (FP)?
Expose you to a new programming model • FP is drastically different
– Scheme: no loops; recursion everywhere FP has had a long tradition
• Lisp, Scheme, ML, Haskell, …
• The debate between FP and imperative programming FP continues to influence modern languages
• Most modern languages are multi-paradigm languages • Delegates in C#: higher-order functions
• Python: FP; OOP; imperative programming
• Scala: mixes FP and OOP
• C++11: added lambda functions
• Java 8: added lambda functions in 2014 • Erlang: behind WhatsApp
3
A Brief History of Functional Programming
Theoretical foundation: Lambda calculus
• Alonzo Church (1930s)
• Computability: Lambda calculus = Turing Machine • Church-Turing Thesis
Lisp (McCarthy, 1950s)
• Directly based on lambda calculus
• Mostly used for symbolic computation (e.g., symbolic
differentiation)
Scheme (Steele and Sussman, 1970s)
• A relatively small language that provides constructs at the core of Lisp
OCaml; Haskell; F#;…
4
34
Scheme
5
Learning Functional Programming in Scheme
Follow the lectures
Chap 11 in the textbook
Online tutorials (links on the course website)
• TeachYourselfSchemeinFixnumDays
• AnIntroductiontoSchemeanditsImplementation
– Long and comprehensive
• OfficialSchemeStandard
– Chapter 6 lists all the predefined procedures
6
56
1
DrRacket
An interactive, integrated, graphical programming environment for Scheme
Installation
• You could install it on your own machines
– http://racket-lang.org/
Interactive environment • read-eval-print loop
– try 3.14159, (* 2 3.14159)
• Compare to typical Java/C development cycle
7
DrRacket: Configuration
Be sure that the language “Standard (R5RS)” is selected
• Click Run
Select View->Hide Definitions to focus on interpreter today
8
78
Functional Programming in Scheme
9
Scheme Variables
Variables
• (define pi 3.14)
• No need to declare types
Variables are case insensitive • piisthesameasPi
10
9 10
Scheme Expressions
Prefix notation (Polish notation):
• 3+4iswritteninSchemeas(+34)
• Parentheses are necessary
• Compare to the infix notation: (3 + 4)
4+(5 * 7) is written as
• (+4(*57))
• Parentheses are necessary
11
Scheme Expressions
General syntax: (E1 E2 Function
to invoke
… Ek)
Function arguments
• Applying the function E1 to arguments E2, …, Ek • Examples:(+34),(+4(*57))
• Uniform syntax, easy to parse
12
11 12
2
Built-in Functions
+, *
• take 0 or more parameters
• applies operation to all parameters together • (+245)
• (*324)
• zero or one parameter?
– (+) – (*)
– (+ 5) – (* 8)
13
User-Defined Functions
Mathematical functions
• Take some arguments; return some value
E.g., f(x) = x2
• f(3)=9;f(10)=100
Scheme syntax
• (define (square x) (* x x))
A two-argument function: f(x,y) = x + y2 • (define(fxy)(+x(*yy)))
• calling the function: (f 3 4)
14
13 14
Anonymous Functions
Syntax based on Lambda Calculus: x. x2 Anonymous functions
• (lambda (x) (* x x))
• Can be used only once: ((lambda (x) (* x x)) 3) • Introduce names
– (define square (lambda (x) (* x x))) – Same as (define (square x) (* x x))
15
Scheme Parenthesis
Scheme is very strict on parentheses
• which is reserved for function call (function
invocation)
• (+34)vs.(+(3)4)
• (lambda (x) x) vs. (lambda (x) (x))
– the second treats (x) as a function call
• (lambda (x) (* x x) vs. (lambda (x) (* (x) x))
15 16
Defining Recursive Functions
(define diverge (lambda (x) (diverge (+ x 1)))) • Call this a diverge function
Booleans
Boolean values
• #t, #f for true and false
Predicates: funs that evaluate to true or false • convention: names of Scheme predicates end in “?” • number?: test whether argument is a number
• equal?
– ex: (equal? 2 2), (equal? x (* 2 y)), (equal? #t #t) • =,>,<,<=,>=
– = is only for numbers
– (= #t #t) won’t work
• and, or, not
– (and (> 7 5) (< 10 20))
17 18
3
If expressions
If expressions • (ifPE1E2)
– eval P to a boolean, if it’s true then eval E1, else eval E2 • examples: max
– (define (max x y) (if (> x y) x y))
• It does not evaluate both branches
– (define (f x) (if (> x 0) 0 (diverge x)) – what is (f 1)? what is (f -1)
Mutual Rec. Functions
• even=true, ifn=0 odd(n-1), otherwise
• odd =false, ifn=0 even(n-1), otherwise
(define myeven? (lambda (n)
(if (= n 0) #t (myodd? (- n 1))))) (define myodd?
(lambda (n)
(if (= n 0) #f (myeven? (- n 1)))))
19 20
Multi-Case Conditionals
(cond (P1 E1) …
(Pn En)
(else En+1))
• “If P E1 E2” is a syntactic sugar
examples
• Problem: Write a function to assign a grade based on the value of
a test score. an A for a score of 90 or above, a B for a score of 80-
89, a C for a score of 70-79, a D for 60-69, a F otherwise. (define (testscore x)
(cond ((>= x 90) ‘A) ((>= x 80) ‘B) ((>= x 70) ‘C) ((>= x 60) ‘D)
(else ‘F)))
Higher-Order Functions
Functions that
• take functions as arguments • return functions as results
Example:
• g(f,x) = f(f(x)) • iff1(x)=x+1,
then g(f1,x) = f1(f1(x)) = f1(x+1) = (x+1) + 1 = x + 2 • if f2(x) = x2,
then g(f2,x) = f2(f2(x)) = f2(x2) = (x2 )2 = x4
22
21 22
Higher-Order Functions in Scheme
The ability to write higher-order functions Functions are first-class citizens in Scheme Examples:
(define (twice f x) (f (f x))) (define (plusOne x) (+ 1 x)) (twice plusOne 2)
(twice square 2)
(twice (lambda (x) (+ x 2)) 3)
23
A Graphical Representation of Twice
• (define (twice f x) (f (f x)))
• It takes a function f and an argument x, and returns
the result of applying f to x twice
f x
twice (f (f x))
Q: Would Scheme accept (twice plusOne)?
24
23 24
4
Writing Twice in a Different Way
(define (twiceV2 f) (lambda (x) (f (f x))))
f
twiceV2 takes a function f as its argument, and returns a function, which takes x as its argument and returns (f (f x))
Q: Would Scheme accept (twiceV2 plusOne)?
25
twiceV2
(f (f x))
x
Let constructs
(let ((x1 E1) (x2 E2) … (xk Ek)) E) • Semantics
– E1, …, Ek are all evaled; then E is evaled, with xi representing the value of Ei. The result is the value of E
– Thescopeofx1,…,xk isE • Simultaneous assignment • examples
– (* (+ 3 2) (+ 3 2)) is OK, but repetitive
– writing (let ((x (+ 3 2)) (* x x))) is better
– (+ (square 3) (square 4)) to
• (let ((three-sq (square 3)) (four-sq (square 4))) (+ three-sq four-sq))
– (define x 0)
(let ((x 2) (y x)) y) to 0
25 26
Let* constructs
(let* ((x1 E1) (x2 E2) … (xk Ek)) E)
• binds x_i to the val of E_i before E_{i+1} is evaled • Thescopeofx1 isE2,E3,… andEkandE
• example:
(define x 0)
(let ((x 2) (y x)) y) to 0 (let* ((x 2) (y x)) y) to 2
• let* is a syntactic sugar
– (let* ((x 2) (y x)) y)
= (let ((x 2)) (let ((y x)) y)
(define x 0)
(define y 1)
(let ((x y) (y x)) y) to 0 (let* ((x y) (y x)) y) to 1
Letrec constructs
(letrec ((x1 E1) (x2 E2) … (xk Ek)) E) • Thescopeofx1 isE1,E2,… andEkandE
(letrec
((fact (lambda (n)
(if (= n 0) 1 (* n (fact (- n 1))))))) (fact 3))
the let won’t work
27 28
List Programming in Scheme
29
How to Distinguish Between Function Application and Data: Quoting
A quoted item evals to itself • treating expressions as data • (+23)to5
• (quote(+23))to(+23)
• (quote pi) to pi
• ‘pi to pi Example • (fun A)
– will try to apply function fun to the variable (parameter A)
– will evaluate A to it’s value
• (fun ‘A): will apply it to the symbol “A”
29 30
5
Lists
LISP stands for list processing
A list is a sequence of zero or more items In scheme
• null list: `()
• `(it seems that): a three element list • `((it seems that) you (like) me)
– four elements, the first and third of which are lists
• Parentheses are important
– like is a symbol/atom, but (like) is a list with one element
Lists
The diff between
• (it seems that you like me)
• ((it seems that) you (like) me)
The diff between (a) and (a ()) Is(+23)aexporalist?
• Both
• Scheme interpreter interprets (+ 2 3) as an exp, and responds
with its value 5
• It’s also a list: three elements
• quoting tells Scheme to interpret it as a list
– ‘(+23)gets(+23)
31 32
(Built-in) Operations On lists
(null? x): true if x is the empty list and false otherwise
(car x): the first element of a nonempty list x
(cdr x): the rest of the list x without the first element
• It always returns a list
(cons a x): returns a list whose car (head) is a and cdr (tail) is x
List Manipulation: Length
(define (length lst) (cond ((null? lst) 0)
(else (+ 1 (length (cdr lst))))))
Programming pattern: case analysis and recursion Two cases
• When lst empty, return 0
• When lst is nonempty, the length is one plus the length of
the tail of lst Examples:
• (length ‘(a b c))
• (length ‘((a) b (a (b) c)))
33 34
Appending Two Lists
(append‘()‘(abcd))=(abcd) (append‘(abc)‘(d))=(abcd)
• Note append is different from cons Two cases for (append l1 l2)
• When l1 is null, then return l2
• When l1 is not null, put (car l1) and (append (cdr l1) l2))
together via cons
(define (append l1 l2)
(if (null? l1) l2
(cons (car l1) (append (cdr l1) l2)))))
Invocation graph for (append ‘(a b c) ‘(d))
Member
(define (member? a lst) (cond ((null? lst) #f)
((equal? a (car lst)) #t)
(else (member? a (cdr lst)))))) Examples
• (member? 3 ‘(1 3 2)) returns #t
• (member? ‘a ‘(a b c)) returns #t
• (member? ‘(a) ‘((a) b c))) returns #t
Note that equal? can also compare lists • In contrast, = compares only numbers
35 36
6
Mapping a function across list elements
(map square ‘(1 2 3 4)) = (1 4 9 16) (map plusOne ‘(3 7 8 9)) = (4 8 9 10) Two cases
• (mapf())=()
• (mapf(consay))=(cons(fa)(mapfy)) (define (map f x)
(if (null? x) ‘()
(cons (f (car x)) (map f (cdr x))))))
Mapping a function across list elements: Examples
(map square ‘(1 2 3)) = (1 4 9) • draw the invocation graph
Examples
• (map (lambda (x) (> x 10)) ‘(3 7 12 9))
• (map (lambda (x) (if (even? x) ‘Even ‘Odd)) ‘(3 7 12
9))
• (map (lambda (x) (list x (+ x 1))) ‘(3 7 12 9))
• (map length ‘((a) (a b) (a b c) ()))
37 38
Reduce
(reduce + ‘(2 4 6) 0) = 2 + 4 + 6 + 0 = 12 (reduce * ‘(2 4 6) 1) = 2 * 4 * 6 * 1 = 48 (define (reduce f l v)
(if (null? l) v
(f (car l) (reduce f (cdr l) v))))
draw the invocation graph
examples:
• (reduce (lambda (x y) (and x y)) ‘(#t #f #t) #t)
Association Lists
A list of pairs
• ((a1)(b2)(c3)…)
• Calleddictionariesinsomelanguages:mapkeystovalues
• Can be used to implement symbol tables: map a var to its
associated bindings
bind: returns an association list with a new binding for a
key
• What happens if there is already a binding for the key
– Two choices: remove the old binding, or keep it • (define (bind key value env)
(cons (list key value) env)) • Examples
– (bind‘d4‘((a1)(b2)(c3))) – (bind‘a10‘((a1)(b2)(c3)))
39 40
Association Lists
lookup: look up the value for a key in an association list; return the key-value pair
• (define (lookup key al) (cond ((null? al) #f)
((equal? key (caar al)) (car al))
(else (lookup key (cdr al))))) • a built-in Scheme function called assoc
• Examples
– (lookup ‘a ‘((a 1) (b 2) (a 3))) -> ‘(a 1) – (lookup ‘b ‘((a 1) (b 2) (a 3))) -> ‘(b 2) – (lookup ‘c ‘((a 1) (b 2) (a 3))) -> #f
Currying and uncurrying
42
41 42
7
Two styles of writing multi-parameter functions
(define (twice f x) (f (f x))
(define (twiceV2 f) (lambda (x) (f (f x))))
• twice takes two arguments, while twiceV2 takes one argument at a time
(define (add n m) (+ n m)
(define (addN n) (lambda (m) (+ n m)))
Uncurried version: take all arguments at once curried version: take one argument at a time
add: int * int -> int; addN: int -> (int -> int)
43
Uncurried version
add: int ∗ int → int
(add 2 3)
Curried version
addN: int → int → int
((addN 2) 3)
(define (add m n)
(+ m n))
(map (add 2)
’(1 2 3))
(define (addN n)
(lambda (m) (+ m n))
(map (addN 2)
’(1 2 3))
Curried form allows partial application
43 44
Currying
Haskell B. Curry Penn State 1929-1966
Outside of McAllister Building
Currying: from an uncurried function to a curried function
The curried function of
(lambda (x1 x2 … xn) e) is
(lambda (x1) (lambda (x2) (… (lambda (xn) e)…)))
(define (curry3 f)
(lambda (x)
(lambda (y)
(lambda (z)
(f x y z)))))
(define (curry2 f)
(lambda (x)
(lambda (y)
(f x y))))
45 46
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
Partial Evaluation
A function is evaluated with one or more of the leftmost actual parameters
(map ((curry2 add) 2) ’(1 2 3))
curry2 add: int → int → int) curry2 add 2: int → int
47 48
8
Uncurrying: from a curried function to an uncurried function
The uncurried function of
(lambda (x1) (lambda (x2) (… (lambda (xn) e)…))) is (lambda (x1 x2 … xn) e)
(define (uncurry2 f)
(lambda (x y)
((f x) y)))
(define (uncurry3 f)
(lambda (x y z)
(((f x) y) z)))
An Extended Example
50
49 50
DFA Simulation (Ch 11.3)
DFA: three components • start state
• the transition function
• the set of final states
Representation: a list of three items
• The transition function is a list of pairs
– the first element of each pair is a pair, whose first element is
a state and whose second element in an input symbol
– if the current state and next input symbol match the
first element of a pair, then the finite automaton enters the state given by the second element of the pair
51
52
51 52
Access functions for DFA description
53
Move one step: return a new DFA with a new start state
54
53 54
9
DFA simulation on an input string
55
Example Run
(simulate zero-one-even-dfa ‘(1 1)) produces ‘(q0 q1 q0 accept)
• Let d1=zero-one-even-dfa
• Let d2 be the same as zero-one-even-dfa except the
start state is q1
• Invocation chain
(helper ‘() d1 ‘(1 1)) ->
(helper ‘(q0) (move d1 1) ‘(1)) = (helper ‘(q0) d2 ‘(1)) -> (helper ‘(q0 q1) (move d2 1) ‘()) = (helper ‘(q0 q1) d1 ‘()) -> ‘(q0 q1 q0)
56
55 56
Discussion of Scheme Features
57
Summary: Main Functional Programming Concepts
first class and high-order functions polymorphism
• A function can process list of different types powerful list facilities
structured function returns
• Return pairs, lists, and eve functions garbage collection
58
57 58
Does C/Java Support Higher-Order Functions?
Write the twice function in C • C supports function pointers
int twice(int (*f) (int), int x) { return (*f)((*f) (x));
}
• The syntax for functions hard to write • Not polymorphic in types
• Cannot return functions as results – Do not support closures
59
Higher-Order Functions In Java
Write the twice function through one-method interfaces interface funInterface {
public int fun (int x); }
class Main {
public static int twice (funInterface f, int x) {
return f.fun (f.fun (x)); }
}
class plusOne implements funInterface {
public int fun (int x) { return x+1;
} }
59 60
10
What about returning a function?
C++11, Java 8 allow lambdas Java lambda tutorial
• http://www.oracle.com/webfolder/technetwork/tutori als/obe/java/Lambda-QuickStart/index.html
61
Java Twice Example
import java.util.function.*; public class Test{
public static
return f.apply(f.apply(x)); }
public static
return ((x) -> f.apply(f.apply(x))); }
public static void main(String[] args){
Integer i = twice ((x) -> x + 1, 3); System.out.println(i);
Function
System.out.println(i1); }
}
62
61 62
Delegates in C#
C# 1.0: Delegates • Functions
• Created only from named methods of objects C# 2.0: anonymous delegates
• delegate (int x) {return x*x;}
C# 3.0: lambda expressions with lighter syntax
• (x) => x*x
• Same as “lambda (x) (* x x)” in Scheme
63
Functional Programming in Python
Adapted from slides for CIS 530 at UPenn
64
63 64
Functions are first-class objects in Python
Functions can be used as any other data type
They can be
• Arguments to functions
• Return values of functions
• Assigned to variables
• Parts of tuples, lists, etc •…
>>> def myfun(x): return x*3
>>> def applier(q, x): return q(x)
>>> applier(myfun, 7) 21
65
Lambda Notation
Functions can be defined without giving them names.
This is most useful when passing a short function as an
argument to another function.
The first argument to applier() is an unnamed function that takes one input and returns the input multiplied by four.
Lambda notation has a rich history in program language research, AI, and the design of the LISP language.
66
>>> applier(lambda z: z * 4, 7) 28
>>> (lambda x,y: x*y) (4,7) 28
65 66
11
List Comprehensions
ApowerfulfeatureofthePythonlanguage.
• Generate a new list by applying a function to every member
of an original list.
• Python programmers use list comprehensions extensively.
You’ll see many of them in real code.
Thesyntaxofalistcomprehensionissomewhat tricky.
• Syntax suggests that of a for-loop, an in operation, or an if statement
—all three of these keywords (‘for’, ‘in’, and ‘if’) are also used in the syntax of forms of list comprehensions.
67
Using List Comprehensions 1
Note: Non-standard colors on next several slides to help clarify the list comprehension syntax.
[ expression for name in list ]
• Where expression is some calculation or operation acting
upon the variable name.
• For each member of the list, the list comprehension 1. sets name equal to that member,
2. calculates a new value using expression,
• It then collects these new values into a list which is the return value of the list comprehension.
68
>>> li = [3, 6, 2, 7]
>>> [elem*2 for elem in li] [6, 12, 4, 14]
67 68
69 70
Another Example
>>> [f(2) for f in [lambda x: x*2, lambda x:x*4]] [4, 8]
69
Using List Comprehensions 2 [ expression for name in list ]
If list contains elements of different types, then expression must operate correctly on the types of all of list members.
If the elements of list are other containers, then the name can consist of a container of names that match the type and “shape” of the list members.
70
>>> li = [(‘a’, 1), (‘b’, 2), (‘c’, 7)] >>> [ n * 3 for (x, n) in li]
[3, 6, 21]
Filtered List Comprehension 1
[expression for name in list if filter]
Filter determines whether expression is performed on each member of the list.
For each element of list, checks if it satisfies the filter condition.
If it returns False for the filter condition, it is omitted from the list before the list comprehension is evaluated.
71
Filtered List Comprehension 2
[ expression for name in list if filter ]
Only6,7,and9satisfythefiltercondition. So,only12,14,and18areproduced.
72
>>> li = [3, 6, 2, 7, 1, 9]
>>> [elem * 2 for elem in li if elem > 4] [12, 14, 18]
71 72
12
Nested List Comprehensions
Since list comprehensions take a list as input and produce a list as output, they are easily nested:
The inner comprehension produces: [4, 3, 5, 2].
So, the outer one produces: [8, 6, 10, 4].
73
>>> li = [3, 2, 4, 1] >>> [elem*2 for elem in
[item+1 for item in li] ] [8, 6, 10, 4]
73
13