Transcript Chapter 1

Chapter 15: Functional Programming
Languages
• Introduction
• Mathematical Functions
• Fundamentals of Functional Programming
Languages (FPL)
• Introduction to Scheme
• COMMON LISP
• ML
• Applications of Functional Languages
• Comparison of Functional and Imperative
Languages
15-1
Introduction
• The design of the imperative languages is
based directly on the von Neumann
architecture
– Efficiency is the primary concern, rather than
the suitability of the language for software
development
• The design of the functional languages is
based on mathematical functions
– A solid theoretical basis that is also closer to the
user, but relatively unconcerned with the
architecture of the machines on which programs
will run
15-2
Mathematical Functions
• A mathematical function is a mapping of members
of one set, called the domain set, to another set,
called the range set
• A lambda expression (nameless function) specifies
the parameter(s) and the mapping of a function in
the following form
(x) x * x * x
for the function cube (x) = x * x * x
• Lambda expressions are applied to parameter(s) by
placing the parameter(s) after the expression
e.g., ((x) x * x * x)(2)
which evaluates to 8
15-3
Functional Forms
• A higher-order function, or functional form,
is one that either takes functions as
parameters or yields a function as its result,
or both
– Function composition
– Apply-to-all
15-4
Function Composition
• A functional form that takes two functions
as parameters, and yields a function whose
value is the first actual parameter function
applied to the result of the second
– Form: h  f ° g
which means h (x)  f ( g ( x))
– For f (x)  x + 2 and g (x)  3 * x,
h  f ° g yields (3 * x)+ 2
15-5
Apply-to-all
• A functional form that takes a single
function as a parameter, and yields a list of
values obtained by applying the given
function to each element of a list of
parameters
– Form: 
– For h (x)  x * x
( h, (2, 3, 4)) yields (4, 9, 16)
15-6
Fundamentals of Functional
Programming Languages
• The objective of the design of a FPL is to mimic
mathematical functions to the greatest extent
possible
• In an imperative language,
– operations are done and the results are stored in variables
for later use
– Management of variables is a constant concern and
source of complexity for imperative programming
• In an FPL
– variables are not necessary, as is the case in mathematics
– The simplicity and power of functional languages is due
to properties like pure values, first-class functions, and
implicit storage management.
15-7
LISP Data Types and Structures
• Data object types: originally only atoms and lists
• List form: parenthesized collections of sublists
and/or atoms
e.g., (A (B C) D (E (F G)))
15-8
LISP Interpretation
• Lambda notation is used to specify function
definitions.
• Function applications and data have the same form.
e.g., for the list (A B C)
–
interpreted as data it is a simple list of three atoms, A, B,
and C
– interpreted as a function application, it means that the
function named A is applied to the two parameters, B and C
• The first LISP interpreter
– basically a universal function that could evaluate any other
function.
– Dynamic scoping
15-9
Origins of Scheme
• A mid-1970s dialect of LISP, designed to be
a cleaner, more modern, and simpler
version than the contemporary dialects of
LISP
• Uses only static scoping
• Functions are first-class entities
– They can be the values of expressions and
elements of lists
– They can be assigned to variables and passed as
parameters
15-10
Function Evaluation
• Parameters are evaluated, in no particular
order
• The values of the parameters are
substituted into the function body
• The function body is evaluated
• The value of the last expression in the
body is the value of the function
• Will discuss this more on Page 56.
15-11
How to write an expression
• Use prefix notation, in which parentheses surround
an operator and its operands. e.g., ( * 3 5 )
15
• The operators “+” and “*” could have several
arguments, e.g., ( + 2 3 5 )
10
• Expressions with several operators are processed
by following the subexpession structure, e.g.,
(+4(*57))
39
15-12
Primitive Functions
•
Arithmetic: +, -, *, /, ABS, SQRT,
•
REMAINDER, MIN, MAX
QUOTE: takes one parameter; returns the
parameter without evaluation
–
–
QUOTE is required because the Scheme interpreter,
named EVAL, always evaluates parameters to function
applications before applying the function. QUOTE is
used to avoid parameter evaluation when it is not
appropriate
QUOTE can be abbreviated with the apostrophe prefix
operator
'(A B) is equivalent to (QUOTE (A B))
15-13
Function Definition: LAMBDA
• Lambda Expressions: anonymous
function (unnamed function)
– Form is based on  notation
e.g., (LAMBDA (x) (* x x))
x is called a bound variable
• Lambda expressions can be applied
e.g., ((LAMBDA (x) (* x x)) 7)
• Recursion is not supported since there
is no name.
15-14
Special Form Function: DEFINE
•
A Function for Constructing Functions DEFINE
1. To bind a symbol to an expression
e.g., (DEFINE pi 3.141593)
Example use: (DEFINE two_pi (* 2 pi))
Note: pi
3.14159
‘pi
pi
2. To bind names to lambda expressions
( define ( <function-name> <formal-parameters>)
<expression> )
e.g., (DEFINE (square x) (* x x))
Example use: (square 5)
25
15-15
Functions provided in Scheme
• Output Functions
– (DISPLAY expression)
– (NEWLINE)
• Numeric Predicate Functions
– Operator: =, <>, >, <, >=, <=
– names ending in ``?’’:
EVEN?, ODD?, ZERO?, NEGATIVE?
• Two boolean values:
– #T is true: any non-null list
– () is false (課本用 #F )
15-16
Control Flow: IF
• Selection: IF
(IF predicate then_exp else_exp)
e.g.,
(IF (<> count 0)
(/ sum count)
0)
15-17
Control Flow: COND
• Multiple Selection: COND
(COND
(predicate_1 expr {expr})
(predicate_1 expr {expr})
...
(predicate_1 expr {expr})
(ELSE expr {expr}))
• Returns the value of the last expr in the first pair
whose predicate evaluates to true
• Example:
(DEFINE (compare x y)
(COND
((> x y) (DISPLAY “x is greater than y”))
((< x y) (DISPLAY “y is greater than x”))
(ELSE (DISPLAY “x and y are equal”))
)
)
15-18
The Structure of lists
• A list is written by enclosing its elements within
parentheses.
• The empty list is written as ( ) in Scheme.
• The list (a) is different from the list (a ( )).
• (+ 2 3) is both an expression and a list. Quoting
will tell the interpreter to treat it as a list
– E.g,
(+23)
5
‘( + 2 3 )
(+23)
15-19
List Construction Functions: CONS and
LIST
• CONS
–
–
–
–
takes two parameters,
the first of which can be either an atom or a list
the second of which is a list
returns a new list that includes the first parameter as its
first element, and the second parameter as the remainder
of its result
– e.g., (CONS 'A '(B C)) returns (A B C)
– (cons a x) can be represented as (a . X)
• LIST
–
–
–
–
takes any number of parameters
returns a list with the parameters as elements
(list ‘x ‘y)  (x y)
e.g., (list ‘it ‘seems) = (it seems)
15-20
List Functions: CAR and CDR
• CAR takes a list parameter; returns the first
element of that list
e.g., (CAR '(A B C)) yields A
(CAR '((A B) C D)) yields (A B)
• CDR takes a list parameter; returns the list
after removing its first element
e.g., (CDR '(A B C)) yields (B C)
(CDR '((A B) C D)) yields (C D)
15-21
List Functions: CAR and CDR
(cont)
• Example of lists
• Use of car and cdr
15-22
Predicate Functions: LIST? and NULL?
• LIST? takes one parameter; it returns #T if
the parameter is a list; otherwise()
• NULL? takes one parameter; it returns #T if
the parameter is the empty list; otherwise()
–
Note that NULL? returns #T if the parameter is()
15-23
The Function member
• member takes an atom and a simple list; returns #T
if the atom is in the list; () otherwise
(DEFINE (member atm lis)
(COND
((NULL? lis) '())
((EQ? atm (CAR lis)) #T)
((ELSE (member atm (CDR lis)))
))
• Example:
(member ‘B ‘(A B C)) returns #T
(member ‘B ‘(A C D E)) returns ( )
15-24
Linear functions on lists
• Most functions on lists consider the elements of a
list one by one; typically linear recursive, that is, a
function f appears just once on the function body.
fun f(x) = if list x is empty then …
else something involving (car x), (cdr x), f.
• the two phases of linear recursive functions
1. A winding phase:
in which the function examines the tail of the list;
2. An unwinding phase:
in which control unwinds back to the beginning of
the list.
15-25
The function append
•
This function concatenates or appends two lists.
–
–
•
•
•
takes two lists as parameters;
returns the first parameter list with the elements of the
second parameter list appended at the end
Ex1: (append ‘(1 2) ‘(3 4 5) )
(1 2 3 4 5)
Ex 2: (append ‘( ) z )  z
(append (cons (a y)) z)  cons(a (append (y z)))
Definitions of the function append:
(DEFINE (append lis1 lis2)
(COND
((NULL? lis1) lis2)
(ELSE (CONS (CAR lis1)
(append (CDR lis1) lis2)))
))
15-26
Evaluation of reverse and append
15-27
The function reverse
• It reverses the order of elements in a list.
• Ex 1: (reverse ‘(1 2 3) ‘( ) )
(3 2 1)
• Ex 2: (reverse ‘(2 3 4) ‘(1) )
 (reverse ‘(3 4) (cons 2 ‘(1)))
 (reverse ‘(4) (cons 3 (cons 2 ‘(1))))
 (reverse ‘( ) (cons 4 (cons 3 (cons 2 ‘(1))))) = (4 3 2 1)
• Ex 3: (reverse ‘( ) z )  z
(reverse (cons a y) z )  (reverse y (cons a z) )
• Definitions of the function reverse:
(define (reverse x z)
(cond ((null? x) z)
(else (reverse (cdr x) (cons (car x) z)))
15-28
))
Predicate Function: EQ?
• EQ? takes two symbolic parameters; it returns #T if
the two parameters are the same
– e.g., (EQ? 'A 'A) yields #T
– e.g., (EQ? 'A 'B) yields ()
– Note that if EQ? is called with list parameters, the result is
not reliable (see below)
• equal? : if both objects are structurally equal, e.g.,
> (define x '(1 2)) ;assign the value of x
> (define y '(1 2))
> (eq? x y)
()
> (equal? x y)
#t
15-29
The Function equalsimp
• equalsimp takes two simple lists as parameters;
returns #T if the two simple lists are equal; ()
otherwise
(DEFINE (equalsimp lis1 lis2)
(COND
((NULL? lis1) (NULL? lis2))
((NULL? lis2) '())
((EQ? (CAR lis1) (CAR lis2))
(equalsimp(CDR lis1)(CDR lis2)))
(ELSE '())
))
15-30
The Function equal
• equal takes two general lists as parameters;
returns #T if the two lists are equal; ()otherwise
– Need to process sublist, atom
(DEFINE (equal lis1 lis2)
(COND
((NOT (LIST? lis1))(EQ? lis1 lis2))
((NOT (LIST? lis2)) '())
((NULL? lis1) (NULL? lis2))
((NULL? lis2) '())
((equal (CAR lis1) (CAR lis2))
(equal (CDR lis1) (CDR lis2)))
(ELSE '())
))
15-31
Example Scheme Function: LET
• General form:
(LET (
(name_1 expression_1)
(name_2 expression_2)
...
(name_n expression_n))
body
)
• Factor out common subexpressions and name
them.
• Evaluate all expressions, then bind the values to
the names; evaluate the body
15-32
LET Example
(DEFINE (quadratic_roots a b c)
(LET (
(root_part_over_2a
(/ (SQRT (- (* b b) (* 4 a c)))(* 2 a)))
(minus_b_over_2a (/ (- 0 b) (* 2 a)))
(DISPLAY (+ minus_b_over_2a root_part_over_2a))
(NEWLINE)
(DISPLAY (- minus_b_over_2a root_part_over_2a))
))
15-33
let and let*
• The let* function binds name_i to the value of
expression_i before expression_i+1 is evaluated,
that is, sequential binding.
• Example:
(define x 0)
( let ( ( x 2 ) ( y x ) ) y )
;bind y before redefining x
0
( let* ( ( x 2 ) ( y x ) ) y ) ;bind y after redefining x
2
15-34
Scheme Functional Forms
• Composition
– The previous examples have used it
– (CDR (CDR ‘(A B C))) returns (C)
• Apply to All
– One form in Scheme is map (課本叫mapcar)
applies the given function to all elements of the given list;
• Example: (map car ‘((a 1) (b 2) (c 3) (d 4)))
(a b c d)
• Definition
(DEFINE (map fun lis)
(COND
((NULL? lis) '())
(ELSE (CONS (fun (CAR lis))
(map fun (CDR lis))))
))
15-35
More higher-order functions
• (define (remove-if f x)
(cond ((null? x) ‘() )
((f (car x)) (remove-if f (cdr x)))
(else (cons (car x)
(remove-if f (cdr x))))))
• (define (reduce f x v)
(cond ((null? x) v)
(else (f (car x) (reduce f (cdr x) v)))))
(see pages 54-55 for explanations in ML)
15-36
Functions That Build Code
• It is possible in Scheme to define a function
that builds Scheme code and requests its
interpretation
• This is possible because the interpreter is a
user-available function, EVAL
15-37
Adding a List of Numbers
• Example:
((DEFINE (adder lis)
(COND
((NULL? lis) 0)
(ELSE (EVAL (CONS '+ lis)))
))
• The parameter is a list of numbers to be added;
adder inserts a + operator and evaluates the
resulting list
– Use CONS to insert the atom + into the list of numbers.
– Be sure that + is quoted to prevent evaluation
– Submit the new list to EVAL for evaluation
15-38
Association list
• An association list, or a-list, is a list of
pairs. Each pair is an association or binding,
consisting of a key and a value, e.g.,
((a1) (b2) (c3))
• There are three operations:
– ( bind key value a-list ): returning an association
list with a new binding for a key.
– ( bind-all keys values a-list ): pairing each key
with the corresponding value.
– (assoc key a-list ): returning the most recent
binding for the key.
15-39
Association list
(cont)
• Example:
( bind-all ‘(a b c) ‘(1 2 3) ‘())
( (a 1) (b 2) (c 3) )
( assoc ‘a ‘((a 1 ) ( b 2 ) ( a 3 ) ) )
(a1)
15-40
Association list
(cont)
• Definition:
– (define (bind key value env)
(cons (list key value) env) )
– (define (bind-all keys values env)
(append (map list keys values) env))
15-41
Storage allocation for lists
• Lists are built out of cells capable of holding pointers to the
head (car) and tail (cdr) of a list.
• Each execution of cons returns a pointer to a newly allocated
cell.
e.g., ( cons ‘it ( cons ‘seems ( cons ‘that ‘( ) ) ) )
()
it
seems
that
• car (contents of the address part of the register): returns the
pointer in the first field.
• cdr (contents of the decrement part of the register): returns
the pointer in the second field.
15-42
Notions of Equality
• Example:
(define x ‘(it seems that))
x
(define y (cons (car x) (cdr x)))
y
(equal? x y)
#t
(eq? x y)
()
15-43
COMMON LISP
• A combination of many of the features of the
popular dialects of LISP around in the early 1980s
• A large and complex language--the opposite of
Scheme
• Features include:
–
–
–
–
–
–
–
records
arrays
complex numbers
character strings
powerful I/O capabilities
packages with access control
iterative control statements
15-44
ML
• A static-scoped functional language with syntax
that is closer to Pascal than to LISP
• Uses type declarations, but also does type
inferencing to determine the types of undeclared
variables
• It is strongly typed (whereas Scheme is essentially
typeless) and has no type coercions
• Includes exception handling and a module facility
for implementing abstract data types
• Includes lists and list operations
15-45
ML Specifics
• The val statement binds a name to a value
(similar to DEFINE in Scheme)
– See the next page for examples.
• Function declaration form:
fun name (parameters) = body;
e.g., fun cube (x : int) = x * x * x;
15-46
Lexical scope
• It uses the program text to determine the context
in which nonlocal names are evaluated.
• Val binding:
let val x = E1 in E2 end is called a binding of x.
e.g., let val x = 2 in x + x end
– All occurrences of x in E2 are said to be within
the scope of this binding, but occurrences x in
E1 are not in the scope of this binding of x.
– For nested binding of the same variable, first
applying renaming to the inner binding.
e.g., let val x=2 in let val x = x+1 in x+x end end
(y)
(y) (y)
15-47
Type Inferencing
• ML infers the type of an expression if possible:
2 + 2 ; ( input to the interpreter; an semicolon
marks the and of an expression.)
val it = 4 : int (response from the interpreter)
• Explicit types can be given to resolve overloading.
e.g., fun add (x, y) = x + y;
Error: overloaded variable “+” cannot be
resolved.
e.g., fun add (x, y): int = x + y;
val add = fn : int * int -> int
e.g., fun add (x, y) = x + (y: int);
val add = fn : int * int -> int
15-48
Parameterized type (polymorphism)
• ML uses a leading quote, e.g, ‘a, to identify a
type parameter.
• Example (see the next page for list
representation)
hd [1, 2, 3];
val it = 1 : int
hd [ “a”, “b”, “c”] ;
val it = “a”: string
hd;
val it = fn : ‘a list -> ‘a
(a function from a list of any type ‘a to type ‘a ) .
15-49
Basic operations on lists
• A list in ML is a sequence of zero or more
elements of the same type, written between
brackets [ and ], e.g., [1, 2, 3].
• An empty list is written as [ ] or nil.
• Basic operations :
– Null - null; test for emptiness;
– hd - head; return first element;
– t1
- tail; return all except the first element;
– ::
- cons; infix list constructor.
15-50
Functions as first-class values
• A function is called higher order if either its
arguments or its results are themselves functions.
• ML provides the function map to apply a function f
to each element of a list x.
• Example: square ( 3 ) = 9
map square [1, 2, 3, 4, 5] = [1, 4, 9, 16, 25]
• Definitions of the function map:
fun map f [ ] = [ ]
| map f ( a :: y ) = ( f a ) :: ( map f y )
15-51
Example of Using Map
• Example:
map square [1, 2, 3];
val it = [1, 4, 9]: int list
map first [(1, “a”), (2, “b”), (3, “c”)];
val it = [1, 2, 3]: int list
map square (map first [(1, “a”), (2, “b”), (3, “c”)]);
val it = [1, 4, 9]: int list
• Example:
hd [ [11, 12, 13, 14], [21, 22, 23, 24], [31, 32, 33, 34]];
val it = [11, 12, 13, 14]: int list <- the first row
map hd [ [11, 12, 13, 14], [21, 22, 23, 24],
[31, 32, 33, 34]];
val it = [11, 21, 31]: int list
<- the first column
15-52
Anonymous functions in ML
• functions without a name; having the form:
fn < formal-parameter > => < body >
• It helps for adapting exiting functions.
• Example:
The function map expects a change function to be
unary. Anonymous functions are used to adapt the
binary operator *.
map ( f n x => x * 2 ) [ 1, 2, 3, 4, 5 ] ;
val it = [ 2, 4, 6, 8, 10 ] : int list
15-53
The function remove_if
• It provides “selective copying”, that is, it copies
list elements a, unless predicate f is true on a.
• Definitions of the function remove_if:
fun remove_if f [ ] = [ ]
| remove_if f ( a :: y ) =
if f ( a ) then remove_if f y
else a :: (remove_if f y )
• Example:
Define the function odd:
fun odd x= (x mod 2) = 1
remove_if odd [0, 1, 2, 3, 4, 5];
val it = [0, 2, 4] : int list
15-54
The function reduce
• It accumulates a result, such as computing the
sum or product of a list of integers.
• The function reduce has three parameters: a
binary operator f, a list, and an initial value v.
• Definitions of the function reduce:
fun reduce f [] v = v
| reduce f (a::y) v = f (a, reduce f y v)
• Example:
Define the function add:
fun add (x, y): int = x + y;
reduce add [1, 2, 3, 4, 5] 0;
val it = 15: int
15-55
Approaches to expression evaluation in
functional languages
• The innermost-evaluation rule for the function
application <name> <actual-parameter> :
– Evaluate the expression represented by <actualparameter>.
– Substitute the result for the formal in the
function body.
– Evaluate the body.
– Return its value as the answer.
• Example: fun successor n = n + 1
The application: successor ( 2 + 3 ) -> activate
plus -> get value 5 -> activate successor -> get
value 6
15-56
Outermost-evaluation
• Outermost-evaluation from left to right:
– Substitute the actual for the formal in the
function body.
– Evaluate the body.
– Return its value as the answer.
• Sometimes outermost evaluation does redundant
work because it re-evaluates an actual parameter.
A clever implementation would have kept track of
the substituted copies and recognize that its value
has already been computed.
• Example : The 91-function:
fun f(x) = if x > 100 then x-10 else f(f(x+11))
15-57
Evaluation of f(100) of the 91-function
15-58
Short-circuit evaluation
• Innermost and outermost evaluation produce the
same result if both terminate with a result.
• Sometimes innermost evaluation does not
terminate; while outermost evaluation terminate.
• Example : innermost evaluation for or (true, F)
results in a non terminating computation if the
evaluation of F does not terminate. However, for
outermost evaluation, the nonterminating
computation F is never reached.
(Suppose F=f(3); fun f (x)=if x>0 then f(x+1))
• In ML, andalso and orelse performs short-circuit
evaluation of boolean expressions, in which the
right operand is evaluated only if it has to be.
15-59
Applications of Functional Languages
• LISP is used for artificial intelligence
–
–
–
–
Knowledge representation
Machine learning
Natural language processing
Modeling of speech and vision
• Scheme is used to teach introductory
programming at a significant number of
universities
15-60
Comparing Functional and Imperative
Languages
• Imperative Languages:
– Efficient execution
– Complex semantics
– Complex syntax
• Functional Languages:
– Simple semantics
– Simple syntax
– Inefficient execution
15-61