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.
14.2.8 Example: Semantics of Clite
Program state can be modeled as a list of pairs. E.g.,
((x 1) (y 5))
Function to retrieve the value of a variable from the state:
(define (get id state)
(if (equal? id (caar state)) (cadar state)
(get id (cdr state))
))
E.g., (get ‘y ‘((x 5) (y 3) (z 1)))
= (get ‘y ‘((y 3) (z 1)))
=3
Copyright © 2006 The McGraw-Hill Companies, Inc.
State transformation
Function to store a new value for a variable in the state:
(define (onion id val state)
(if (equal? id (caar state))
(cons (list id val) (cdr state))
(cons (car state) (onion id val (cdr state)))
))
E.g.,
(onion ‘y 4 ‘((x 5) (y 3) (z 1)))
= (cons ‘(x 5) (onion ‘y 4 ‘((y 3) z 1)))
= (cons ‘(x 5) (cons ‘(y 4) ‘((z 1))))
= ‘((x 5) (y 4) (z 1))
Copyright © 2006 The McGraw-Hill Companies, Inc.
Modeling Clite Abstract Syntax
Skip
Assignment
Block
Loop
Conditional
Expression
Value
Variable
Binary
(skip)
(assignment target source)
(block s1 s2 … sn)
(loop test body)
(conditional test thenbranch elsebranch)
(value val)
(variable id)
(operator term1 term2)
Copyright © 2006 The McGraw-Hill Companies, Inc.
Semantics of Statements
(define (m-statement statement state)
(case (car statement)
((skip) (m-skip statement state))
((assignment) (m-assignment statement state))
((block) (m-block (cdr statement) state))
((loop) (m-loop statement state)
((conditional) (m-conditional statement state))
(else ())
))
Copyright © 2006 The McGraw-Hill Companies, Inc.
Skip, Block, and Loop
(define (m-skip statement state) state)
(define (m-block alist state)
(if (null? alist) state
(m-block (cdr alist) (m-statement (car alist) state))
))
(define (m-loop) statement state)
(if (m-expression (car statement) state)
(m-loop statement (m-statement (cdr statement) state))
state
))
Copyright © 2006 The McGraw-Hill Companies, Inc.
Expression
(define (m-expression expr state)
(case (car expr)
((value) (cadr expr))
((variable) (get (cadr expr) state))
(else (applyBinary (car expr) (cadr expr) (caddr expr) state))
))
(define (applyBinary) op left right state)
(let ((leftval (m-expression left state))
((rightval (m-expression right state)))
(case op
((plus) (+ leftval rightval))
…
))
Copyright © 2006 The McGraw-Hill Companies, Inc.
To Do:
1. Show that these definitions give 5 as the meaning of y+2 in the
state ((x 5) (y 3) (z 1)). I.e., show that
(m-expression ‘(plus (variable y) (value 2)) ‘((x 5) (y 3) (z 1)))
…
=5
2. Give a definition of m-assignment.
3. What about defining m-conditional?
Copyright © 2006 The McGraw-Hill Companies, Inc.
14.2.9 Example: Symbolic Differentiation
Symbolic Differentiation Rules
Fig 14.2
d
(c )  0
dx
d
c is a constant
(x)  1
dx
d
dx
d
(u  v ) 
(u  v ) 
du
dx
du


dv
dx
dv
dx
dx
dx
d
dv
du
( uv )  u
v
dx
dx
dx
 du
d
dv  2
( u / v )  v
u
/ v
 dx
dx
dx 
Copyright © 2006 The McGraw-Hill Companies, Inc.
u and v are functions of
x
Scheme Encoding
1. Uses Cambridge Prefix notation
E.g., 2x + 1 is written as (+ (* 2 x) 1)
2. Function diff incorporates these rules.
E.g., (diff ‘x ‘(+ (* 2 x) 1)) should give an answer.
3. However, no simplification is performed.
E.g. the answer for (diff ‘x ‘(+ (* 2 x) 1)) is
(+ (+ (* 2 1) (* x 0)) 0)
which is equivalent to the simplified answer, 2.
Copyright © 2006 The McGraw-Hill Companies, Inc.
Scheme Program
(define (diff x expr)
(if (not (list? Expr))
(if (equal? x expr) 1 0)
(let ((u (cadr expr)) (v (caddr expr)))
(case (car expr)
((+) (list ‘+ (diff x u) (diff x v)))
((-) (list ‘- (diff x u) (diff x v)))
((*) (list ‘+ (list ‘* u (diff x v))
(list ‘* v (diff x u))))
((/) (list ‘div (list ‘- (list ‘* v (diff x u))
(list ‘* u (diff x v)))
(list ‘* u v)))
))))
Copyright © 2006 The McGraw-Hill Companies, Inc.
Trace of the Example
(diff ‘x ‘(+ ‘(* 2 x) 1))
= (list ‘+ (diff ‘x ‘(*2 x)) (diff ‘x 1))
= (list ‘+ (list ‘+ (list ‘* 2 (diff ‘x ‘x))
(list ‘* x (diff ‘x 2)))
(diff ‘x 1))
= (list ‘+ (list ‘+ (list ‘* 2 1) (list ‘* x (diff ‘x 2)))
(diff ‘x 1))
= (list ‘+ (list ‘+ ‘(* 2 1) (list ‘* x (diff ‘x 2)))
(diff ‘x 1))
= (list ‘+ (list ‘+ ‘(* 2 1) (list ‘* x (diff ‘x 2)))
(diff ‘x 1))
= (list ‘+ (list ‘+ ‘(* 2 1) (list ‘* x 0)) 0)
= ‘(+ (+ (* 2 1) (* x 0)) 0)
Copyright © 2006 The McGraw-Hill Companies, Inc.
14.2.10 Example: Eight Queens
A backtracking algorithm for which
each trial move’s:
1. Row must not be occupied,
2. Row and column’s SW diagonal
must not be occupied, and
3. Row and column’s SE diagonal
must not be occupied.
If a trial move fails any of these tests,
the program backtracks and tries
another. The process continues
until each row has a queen (or
until all moves have been tried).
Copyright © 2006 The McGraw-Hill Companies, Inc.
Checking for a Valid Move
(define (valid move soln)
(let ((col (length (cons move soln))))
(and (not (member move soln))
(not (member (seDiag move col) (selist soln)))
(not (member (swDiag move col) (swlist soln)))
)))
Note: the and encodes the three rules listed on the previous slide.
Copyright © 2006 The McGraw-Hill Companies, Inc.
Representing the Developing Solution
Positions of the queens kept in a list soln whose nth entry gives
the row position of the queen in column n, in reverse order.
E.g., soln = (5 3 1) represents queens in (row, column)
positions (1,1), (3,2), and (5,3); i.e., see previous slide.
End of the game occurs when soln has N (= 8) entries:
(define (done soln) (>= (length soln) N))
Continuing the game tests hasmore and generates nextmove:
(define (hasmore move) (<= move N))
(define (nextmove move) (+ move 1)
Copyright © 2006 The McGraw-Hill Companies, Inc.
Generating Trial Moves
(define (trywh move soln)
(if (and (hasmore move) (not (car soln)))
(let ((atry (tryone move (cdr soln))))
(if (car atry) atry (trywh (nextmove move) soln))
)
soln
))
The try function sets up the first move:
(define (try soln) (trywh 1 (cons #f soln)))
Copyright © 2006 The McGraw-Hill Companies, Inc.
Trying One Move
(define (tryone move soln)
(let ((xsoln (cons move soln)))
(if (valid move soln)
(if (done xsoln)
(cons #t xsoln)
(try xsoln))
(cons #f soln))
))
Note: the #t or #f reveals whether the solution is complete.
Copyright © 2006 The McGraw-Hill Companies, Inc.
SW and SE Diagonals
(define (swdiag row col) (+ row col))
(define (sediag row col) (- row col))
(define (swlist alist)
(if (null? Alist) ‘()
(cons (swDiag (car alist) (length alist))
(swlist (cdr alist)))))
(define (selist alist)
(if (null? Alist) ‘()
(cons (seDiag (car alist) (length alist))
(selist (cdr alist)))))
Copyright © 2006 The McGraw-Hill Companies, Inc.
Descargar

Programming Languages Chapter 2: Syntax