Transcript Chapter 14a - McGraw Hill Higher Education

Programming Languages
2nd edition
Tucker and Noonan
Chapter 14
Functional Programming
It is better to have 100 functions operate one one data structure,
than 10 functions on 10 data structures.
A. Perlis
Copyright © 2006 The McGraw-Hill Companies, Inc.
Contents
14.1 Functions and the Lambda Calculus
14.2 Scheme
14.2.1 Expressions
14.2.2 Expression Evaluation
14.2.3 Lists
14.2.4 Elementary Values
14.2.5 Control Flow
14.2.6 Defining Functions
14.2.7 Let Expressions
14.2.8 Example: Semantics of Clite
14.2.9 Example: Symbolic Differentiation
14.2.10 Example: Eight Queens
14.3 Haskell
Copyright © 2006 The McGraw-Hill Companies, Inc.
Overview of Functional Languages
• They emerged in the 1960’s with Lisp
• Functional programming mirrors mathematical
functions: domain = input, range = output
• Variables are mathematical symbols: not associated
with memory locations.
• Pure functional programming is state-free: no
assignment
• Referential transparency: a function’s result
depends only upon the values of its parameters.
Copyright © 2006 The McGraw-Hill Companies, Inc.
14.1 Functions and the Lambda Calculus
The function Square has R (the reals) as domain and range.
Square : R  R
Square(n) = n2
A function is total if it is defined for all values of its domain.
Otherwise, it is partial. E.g., Square is total.
A lambda expression is a particular way to define a function:
LambdaExpression  variable | ( M N) | (  variable . M )
M  LambdaExpression
N  LambdaExpression
E.g., (  x . x2 ) represents the Square function.
Copyright © 2006 The McGraw-Hill Companies, Inc.
Properties of Lambda Expressions
In ( x . M), x is bound. Other variables in M are free.
A substitution of N for all occurrences of a variable x in M is
written M[x  N]. Examples:
A beta reduction (( x . M)N) of the lambda expression ( x . M) is
a substitution of all bound occurrences of x in M by N. E.g.,
(( x . x2)5) = 52
Copyright © 2006 The McGraw-Hill Companies, Inc.
Function Evaluation
In pure lambda calculus, expressions like (( x . x2)5) = 52
are uninterpreted.
In a functional language, (( x . x2)5) is interpreted normally (25).
Lazy evaluation = delaying argument evaluation in a
function call until the argument is needed.
– Advantage: flexibility
Eager evaluation = evaluating arguments at the beginning
of the call.
– Advantage: efficiency
Copyright © 2006 The McGraw-Hill Companies, Inc.
Status of Functions
In imperative and OO programming, functions have
different (lower) status than variables.
In functional programming, functions have same status
as variables; they are first-class entities.
– They can be passed as arguments in a call.
– They can transform other functions.
A function that operates on other functions is called a
functional form. E.g., we can define
g(f, [x1, x2, … ]) = [f(x1), f(x2), …], so that
g(Square, [2, 3, 5]) = [4, 9, 25]
Copyright © 2006 The McGraw-Hill Companies, Inc.
14.2 Scheme
A derivative of Lisp
Our subset:
– omits assignments
– simulates looping via recursion
– simulates blocks via functional composition
Scheme is Turing complete, but
Scheme programs have a different flavor
Copyright © 2006 The McGraw-Hill Companies, Inc.
14.2.1 Expressions
Cambridge prefix notation for all Scheme expressions:
(f x1 x2 … xn)
E.g.,
(+ 2 2)
(+ (* 5 4) (- 6 2))
(define (Square x) (* x x))
(define f 120)
; evaluates to 4
; means 5*4 + (6-2)
; defines a function
; defines a global
Note: Scheme comments begin with ;
Copyright © 2006 The McGraw-Hill Companies, Inc.
14.2.2 Expression Evaluation
Three steps:
1. Replace names of symbols by their current bindings.
2. Evaluate lists as function calls in Cambridge prefix.
3. Constants evaluate to themselves.
E.g.,
x
(+ (* x 4) (- 6 2))
5
‘red
; evaluates to 5
; evaluates to 24
; evaluates to 5
; evaluates to ‘red
Copyright © 2006 The McGraw-Hill Companies, Inc.
14.2.3 Lists
A list is a series of expressions enclosed in parentheses.
– Lists represent both functions and data.
– The empty list is written ().
– E.g., (0 2 4 6 8) is a list of even numbers. Here’s how it’s
stored:
Copyright © 2006 The McGraw-Hill Companies, Inc.
List Transforming Functions
Suppose we define the list evens to be (0 2 4 6 8). I.e.,
we write (define evens ‘(0 2 4 6 8)). Then:
(car evens)
(cdr evens)
(cons 1 (cdr evens))
(null? ‘())
(equal? 5 ‘(5))
(append ‘(1 3 5) evens)
(list ‘(1 3 5) evens)
; gives 0
; gives (2 4 6 8)
; gives (1 2 4 6 8)
; gives #t, or true
; gives #f, or false
; gives (1 3 5 0 2 4 6 8)
; gives ((1 3 5) (0 2 4 6 8))
Note: the last two lists are different!
Copyright © 2006 The McGraw-Hill Companies, Inc.
14.2.4 Elementary Values
Numbers
integers
floats
rationals
Symbols
Characters
Functions
Strings
(list? evens)
(symbol? ‘evens)
Copyright © 2006 The McGraw-Hill Companies, Inc.
14.2.5 Control Flow
Conditional
(if (< x 0) (- 0 x))
(if (< x y) x y)
; if-then
; if-then-else
Case selection
(case month
((sep apr jun nov) 30)
((feb) 28)
(else 31)
)
Copyright © 2006 The McGraw-Hill Companies, Inc.
14.2.6 Defining Functions
( define ( name arguments ) function-body )
(define (min x y) (if (< x y) x y))
(define (abs x) (if (< x 0) (- 0 x) x))
(define (factorial n)
(if (< n 1) 1 (* n (factorial (- n 1)))
))
Note: be careful to match all parentheses.
Copyright © 2006 The McGraw-Hill Companies, Inc.
The subst Function
(define (subst y x alist)
(if (null? alist) ‘())
(if (equal? x (car alist))
(cons y (subst y x (cdr alist)))
(cons (car alist) (subst y x (cdr alist)))
)))
E.g., (subst ‘x 2 ‘(1 (2 3) 2))
returns (1 (2 3) x)
Copyright © 2006 The McGraw-Hill Companies, Inc.
14.2.7 Let Expressions
Allows simplification of function definitions by
defining intermediate expressions. E.g.,
(define (subst y x alist)
(if (null? alist) ‘()
(let ((head (car alist)) (tail (cdr alist)))
(if (equal? x head)
(cons y (subst y x tail))
(cons head (subst y x tail))
)))
Copyright © 2006 The McGraw-Hill Companies, Inc.
F
Functions as arguments
(define (mapcar fun alist)
(if (null? alist) ‘()
(cons (fun (car alist))
(mapcar fun (cdr alist)))
))
E.g., if (define (square x) (* x x)) then
(mapcar square ‘(2 3 5 7 9)) returns
(4 9 25 49 81)
Copyright © 2006 The McGraw-Hill Companies, Inc.