```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
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.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
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))
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)
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 ())
))
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
))
Expression
(define (m-expression expr state)
(case (car expr)
))
(define (applyBinary) op left right state)
(let ((leftval (m-expression left state))
((rightval (m-expression right state)))
(case op
((plus) (+ leftval rightval))
…
))
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.
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 
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.
Scheme Program
(define (diff x expr)
(if (not (list? Expr))
(if (equal? x expr) 1 0)
(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)))
))))
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)
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).
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.
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)
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)))
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.
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)))))
```