Transcript 517211_ch08

Functional Programming
Element of Functional Programming
Functional Programming
 Functional Programming began as computing
with expressions.
 The following are examples:
2
X
log n
2+3
An integer constant
A variable
Function log applied to n
Function + applied to 2 and 3
Functional Programming
 Expressions can also include conditionals
and function definitions.
Example: The value of following condition
expression is the maximum of x and y:
if (x > y) then x else y
Functional Programming
 For concreteness, specific ML examples will be
written in a typewriter-like font;
 For example:
2 + 2;
val it = 4 : int
 Computing with expressions will be introduced by
designing a little language of expressions.
A LITTLE LANGUAGE OF
EXPRESSIONS
 Basic Values
 Constants: Names for Basic Values
 Operations
 Expressions
 Convenient Extensions
 Local Declarations
A LITTLE LANGUAGE OF
EXPRESSIONS
 Expressions are formed by giving names to
values and to operations on them
 The little language manipulates just one type
of value: geometric objects called quilts.
Example : Quilt
What is Quilt?
Little Quilt
 Little Quilt manipulates geometric objects
with
 Height
 Width
 Texture
Basic Values
 Given two primitive objects in the language are the
square pieces:
 Each quilt has




A fixed direction or orientation
A height
A width
A texture
Operations
 Quilt can be turned and can be sewn together
turn
turn
turn
sew
turn
Rules
Quilts and the operations on them are specified
by the following rules:
1. A quilt is one of the primitive pieces, or
2. It is formed by turning a guilt clockwise 90, or
3. It is formed by sewing a quilt to the right of
another quilt of equal height
4. Nothing else is a quilt
Constants: Names for Basic Values
 The first step in construction a language to
specify quilts is to give names to the
primitive pieces and to the operations on
quilts
Name “a”
Name “b”
Operation called
• turn
• sew
Expressions
 The syntax of expressions mirrors the
definition of quilts:
<exp> ::=
|
|
|
a
b
turn(<exp>)
sew(<exp>,<exp>)
 Complex expressions are built up from
simpler ones,
Expressions
Sew(turn(turn(b)),a)
No
expression
1
b
2
turn(b)
3
turn(turn(b))
4
a
5 sew(turn(turn(b)),a)
quilt
Convenient Extensions
 Expressions will now be extended by
allowing functions from quilts to quilts.
 It would be convenient to give names to the
operations.
 Once defined, functions like unturn and pile
can used as if they were built in
Fun unturn(x) = turn(turn(turn(x)))
Fun pile(x,y) = unturn(sew(turn(y),turn(x)))
Local Declarations
 Let-expressions or let-bindings allow
declarations to appear within expressions.
 Let-expression Form
Let <declaration> in <expression> end
For example
let fun unturn(x) = turn(turn(turn(x)))
fun pile(x,y) = unturn(sew(turn(y),turn(x)))
in
pile(unturn(b),turn(b))
end
User-Defined Names for Values
 The final extension is convenient for writing
large expressions in terms of simpler ones.
 A value declaration form:
val <name> = <expression>
 Gives a name to a value
 Value declarations are used together with letbindings.
 An expression of the form
let val x=E1 in E2 end
Rewrite
Pile(unturn(b),turn(b))
let val bnw = unturn(b)
in
pile(bnw,turn(b))
end
Review: Design of Little Quilt
 The language Little Quilt was defined by starting
with values and operations.
 The values are quilts, built up from two square
pieces;
 The operations are for turning and sewing quilts.
 The language began with the name a and b for the
square pieces and
 The names turn and sew for the operations
Specification of a quilt
Let fun unturn(x) = turn(turn(turn(x)))
fun pile(x,y) = unturn(sew(turn(y),turn(x)))
val aa = pile(a,turn(turn(a)))
val bb = pile(unturn(b),turn(b))
val p = sew(bb,aa)
val q = sew(aa,bb)
In
pile(p,q)
end
Summary of Little Quilt
<exp>
<exp>
<exp>
<decs>
<dec>
<formals>
<exp>
<actuals>
<dec>
<exp>
::=
::=
::=
::=
::=
::=
::=
::=
::=
::=
a | b
turn(<exp>) | sew(<exp>,<exp>)
let <declarations> in <exp> end
<dec> | <dec> <decs>
fun <name> (<formals>) = <exp>
<name> | <name>, <formals>
<name> (<actuals>)
<exp> | <exp>, <actuals>
val <name> = <exp>
<name>
TYPEs:Values and Operations
 A types consists of a set of elements called
values together with a set of functions called
operations.
 We will consider methods for defining
structured values such as products, lists, and
functions.
The syntax of type expressions
<type-exp> ::=
|
|
|
<type-name>
<type-exp>  <type-exp>
<type-exp> *<type-exp>
<type-exp> list
Structured value
 Structured values such as lists can be used as
freely in functional languages as basic values
like integers and strings
 Value in a function language take advantage
of the underlying machine, but are not tied to
it.
Operations for Constructing
and Inspecting Values
 The structuring methods will be presented by
specifying a set of values together with a set
of operations.
 Concentrate on operations for constructing
and inspecting the elements of the set.
 For example
• To Extend a list by adding a new first element
• To test whether a list is empty
Operations for Constructing
and Inspecting Values
 Basic Types
 Operations on Basic Values
 Products of Types
 Operations on Pairs
 List of Elements
 Operations on Lists
Basic Types
 A type is basic if its values are atomic
 If the values are treated as whole elements,
with no internal structure.
For example
The boolean values in the set {true,false}
Operations on Basic Values
 Basic values have no internal structure, so
the only operation defined for all basic types
is a comparison for equality;
For example
The equality 2 = 2 is true,
The inequality 2!=2 is false
Operations on Basic Values
 Technically, an operation is a function
 The equality test on integers is a function
from pairs of integers to boolean.
The type
int*int  bool
Products of Types
 The product A*B of two types A and B
consists of ordered pairs written as
(a,b) ; where a is a value of type A and
b is a value of type B
For Example
(1,“one”) is a pair consisting of int:1 and string: “one”
Products of Types
 A product of n types A*A*A*…*A consists
of tuples written as
(a1, a2 , a3 ,…, an ) ; where ai is a value of type A1
Operations on Pairs
 A pair is constructed from a and b by writing (a,b)
 Associated with pairs are operations called
projection functions to extract the first and second
elements from a pair.
 The first element of the pair (a,b) is a
 The second element is b
 Projection functions can be readily defined:
fun first(x,y) = x
fun second(x,y) = y
Lists of Elements
 A list is a finite-length sequence of elements.
The type A list consists of all lists of elements, where each
element belongs to type A
For Example
int list ; consists of all lists of integers.
Lists of Elements
 List elements will be written between
brackets [ and ]
 List elements will be separated by commas
 The empty list is written equivalently as [ ]
For Example
[1, 2, 3]
is a list of three integers
[“red”, “white”, “blue”] is a list of three strings
Operations on Lists
 Lists-manipulation programs must be prepared
to construct and inspect lists of any length.
 The following operations on list are from ML:
null(x)
hd(x)
tl(x)
a::x
True is x is the empty list
The first or head element of list x.
The tail or rest of the list.
Construct a list with head a and tail x
Operations on Lists
For Example
Given x is [1, 2, 3]
Null(x) false
Hd(x)
1
Tl(x)
[2, 3]
From the following equalities:
[1, 2, 3] = 1::[2, 3] = 1::2::[3] = 1::2::3::[]
Functions from a Domain to a
Range
 The type A  B is the set of all functions
from A to B
For Example
If Q is the set of quilt then
function turn from quilts to quilts is Q  Q
function sew form pairs of quits to quilts is Q*Q  Q
Functions from a Domain to a
Range
 A function f in A B is total
If it associates an element of B with each element of A
A is called the domain and B is called the range of f.
 A function f in A B is partial
It is possible for there to be no element of B associated
with an element of A
Function Application
 The set A  B is application which takes a
function f in A B and an element a in A
and yields and element b of B.
For Example
 A function is applied in ML; f a is the
application of f to a.
APPOACHES TO EXPRESSION
EVALUATION
 The rules for expression are base on the
structure of expressions
E1 + E2
1.
2.
3.
Evaluate the subexpressions E1 and
Evaluate the subexpressions E2 and
Add two values
Innermost Evaluation
<name> <actual-parameter>
 Evaluate the expression represented by
<actual-parameter>
 Substitute the result for the formal in the
function body
 Evaluate the body
 Return its value as the answer
Selection Evaluate
If <condition> then <expression1>
else <expression2>
 <condition> is an expression that evaluates
to either true or false.
 True : <expression1> is evaluated
 False : <expression2> is evaluated
Evaluation of Recursive Functions
 The actual parameters are evaluated and
substituted into the function body.
Length(X) ((cond (null X) 0 (+ 1 (length(cdrX)))))
Length([“hello”, “world”]) = 1 + length([“world”])
= 1 + 1 + length([])
=1+1+0
=2
Othermost Evaluation
 Substitute the actual for the formal in the
function body
 Evaluate the body
 Return its value as the answer.
Example Function
Fun f(x) =
if x > 100 then x-10 else f(f(x+11))
Innermost Evaluate
F(100) = if 100>100 then 100-10 else f(f(100+11))
= f(f(100+11))
= f(f(111))
= f( if 111> 100 then 111-10 else f(f(111+11)) )
= f(111-10)
= f(101)
= if 101>100 then 101-10 else f(f(101+11))
= 101 – 10 = 91
Outermost Evaluate
F(100) = if 100>100 then 100-10 else f(f(100+11))
= f(f(100+11))
= if f(111> 100) then
f(111+11)-10 else f(f(f(100+11)+11)) )
F(100+11) = if 100+11> 100 then
100+11-10 else f(f(100+11+11))
= if 111>100 then
100+11-10 else f(f(100+11+11))
= 100+11-10 = 111-10 = 101
LEXICAL SCOPE
 Renaming is made precide by introducing a
notion of local or “bound” variables;bound
occurrences of variables can be renamed
without changing the meaning of a program
fun successor(x) = x + 1
fun successor(n) = n + 1
Val Bindings
let val x=E1 in E2 end
 Binding occurrence or simply binding of x
 All occurrences of x in E2 are said to be
within the scope of this binding
 Occurrences of x in E1 are not in the scope
of this binding of x
let val x=2 in x+x end
Fun Bindings
let fun f(x)=E1 in E2 end
 This binding of the formal parameter x is
visible only to the occurrences of x in E1
 This binding of the function name f is visible
to all occurrences of f in both E1 and E2
let fun f(x)=x+1 in 2*f(x) end