Transcript Functional

CS 363 Comparative
Programming Languages
Functional Languages: Scheme
Fundamentals of Functional
Programming Languages
• The objective of the design of a functional programming
language (FPL) is to mimic mathematical functions to the
greatest extent possible
• The basic process of computation is fundamentally
different in a FPL than in an imperative language
– 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
CS 363 Spring 2005 GMU
2
Fundamentals of Functional
Programming Languages
• In an FPL, the evaluation of a function
always produces the same result given the
same parameters
– This is called referential transparency
CS 363 Spring 2005 GMU
3
Functions
• A function is a rule that associates to each x from
some set X of values a unique y from another set Y
of values:
– y = f(x) or f: X  Y
range
domain
• Functional Forms
– Def: A higher-order function, or functional form, is one
that either takes functions as parameters, yields a
function as its result, or both
CS 363 Spring 2005 GMU
4
Lisp
• Lisp – based on lambda calculus (Church)
– Uniform representation of programs and data
using single general data structure (list)
– Interpreter based (written in Lisp)
– Automatic memory management
– Evolved over the years
– Dialects: COMMON LISP, Scheme
CS 363 Spring 2005 GMU
5
Scheme
(define (gcd u v)
(if ( = v 0)
u
(gcd v (remainder u v))
)
)
(define (reverse l)
(if (null? l) l
(append (reverse (cdr l))(list (car l)))
)
)
CS 363 Spring 2005 GMU
6
Introduction to 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
CS 363 Spring 2005 GMU
7
Scheme
(define (gcd u v)
(if ( = v 0)
u
(gcd v (remainder u v))
)
)
• Once defined in the interpreter:
 (gcd 25 10)
5
CS 363 Spring 2005 GMU
8
Scheme Syntax
simplest elements
 atom | list
 number | string
| identifier | character | boolean
list
 ‘(‘ expression-sequence ‘)’
expression-sequence  expression
| expression-sequence expression
expression
atom
CS 363 Spring 2005 GMU
9
Scheme atoms
• Constants:
– numbers, strings, #T = True, …
• Identifier names:
• Function/operator names
– pre-defined & user defined
CS 363 Spring 2005 GMU
10
Scheme Expression vs. C
In Scheme:
In C:
(+ 3 (* 4 5 ))
(and (= a b)(not (= a 0)))
(gcd 10 35)
3+4*5
(a = = b) && (a != 0)
gcd(10,35)
CS 363 Spring 2005 GMU
11
Evaluation Rules for Scheme
Expressions
1. Constant atoms (numbers, strings) evaluate to
themselves
2. Identifiers are looked up in the current
environment and replaced by the value found
there (using dynamically maintained symbol
table)
3. A list is evaluated by recursively evaluating each
element in the list as an expression; the first
expression must evaluate to a function. The
function is applied to the evaluated values of the
rest of the list.
CS 363 Spring 2005 GMU
12
Scheme Evaluation
To evaluate (* (+ 2 3)(+ 4 5))
1. * is the function – must evaluate the two
expressions (+ 2 3) and (+ 4 5)
2. To evaluate (+ 2 3)
1.
2.
3.
4.
3.
4.
+ is the function – must evaluation the two
expressions 2 and 3
2 evaluates to the integer 2
3 evaluates to the integer 3
+23=5
*
+
2
+
34
5
To evaluate (+ 4 5) follow similar steps
* 5 9 = 45
CS 363 Spring 2005 GMU
13
Scheme Conditionals
If statement:
Cond statement:
(if ( = v 0)
u
(gcd v (remainder u v))
)
(if (= a 0) 0 (/ 1 a))
(cond (( = a 0) 0)
((= a 1) 1)
(else (/ 1 a))
)
Both if and cond functions use
delayed evaluation for the
expressions in their bodies
(i.e. (/ 1 a) is not evaluated unless
the appropriate branch is chosen).
CS 363 Spring 2005 GMU
14
Example of COND
(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”))
)
)
CS 363 Spring 2005 GMU
15
Predicate Functions
1. EQ? takes two symbolic parameters; it returns #T if both
parameters are atoms and the two are the same
e.g., (EQ? 'A 'A) yields #T
(EQ? 'A '(A B)) yields ()
– Note that if EQ? is called with list parameters, the result
is not reliable
– EQ? does not work for numeric atoms (use = )
CS 363 Spring 2005 GMU
16
Predicate Functions
2. LIST? takes one parameter; it returns #T if the
parameter is a list; otherwise()
3. NULL? takes one parameter; it returns #T if the
parameter is the empty list; otherwise()
Note that NULL? returns #T if the parameter is()
4. Numeric Predicate Functions
=, <>, >, <, >=, <=, EVEN?, ODD?,
ZERO?, NEGATIVE?
CS 363 Spring 2005 GMU
17
let function
• Allows values to be given temporary names
within an expression
– (let ((a 2 ) (b 3)) ( + a b))
–5
• Semantics: Evaluate all expressions, then
bind the values to the names; evaluate the
body
CS 363 Spring 2005 GMU
18
Quote (‘) function
• A list that is preceeded by QUOTE or a quote mark (‘) is
NOT evaluated.
• 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
• Can be used to provide function arguments
– (myfunct ‘(a b) ‘(c d))
CS 363 Spring 2005 GMU
19
Output functions
• Output Utility Functions:
(DISPLAY expression)
(NEWLINE)
CS 363 Spring 2005 GMU
20
define function
Form 1: Bind a symbol to a expression:
(define a 2)
(define emptylist ‘( ))
(define pi 3.141593)
CS 363 Spring 2005 GMU
21
define function
Form 2: To bind names to lambda expressions
define (cube x)
(* x (* x x ))
)
function name and parameters
(define (gcd u v)
(if ( = v 0)
u
(gcd v (remainder u v))
)
)
CS 363 Spring 2005 GMU
function body
– lambda expression
22
Function Evaluation
• Evaluation process (for normal functions):
1. Parameters are evaluated, in no particular order
2. The values of the parameters are substituted
into the function body
3. The function body is evaluated
4. The value of the last expression in the body is
the value of the function
(Special forms use a different evaluation process)
CS 363 Spring 2005 GMU
23
Data Structures in Scheme: Box
Notation for Lists
first element (car)
rest of list (cdr)
1
List manipulation is typically
written using ‘car’ and ‘cdr’
CS 363 Spring 2005 GMU
24
Data Structures in Scheme
1
2
3
(1,2,3)
c
a
d
((a b) c (d))
b
CS 363 Spring 2005 GMU
25
Basic List Manipulation
• (car L) – returns the first element of L
• (cdr L) – returns L minus the first element
(car ‘(1 2 3)) = 1
(car ‘((a b)(c d))) = (a b)
(cdr ‘(1 2 3)) = (2 3)
(cdr ‘((a b)(c d))) = ((c d))
CS 363 Spring 2005 GMU
26
Basic List Manipulation
• (list e1 … en) – return the list created from the
individual elements
• (cons e L) – returns the list created by adding expression
e to the beginning of list L
(list 2 3 4) = (2 3 4)
(list ‘(a b) x ‘(c d) ) = ((a b)x(c d))
(cons 2 ‘(3 4)) = (2 3 4)
(cons ‘((a b)) ‘(c)) = (((a b)) c)
CS 363 Spring 2005 GMU
27
Example Functions
1. 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)))
))
CS 363 Spring 2005 GMU
28
Example Functions
2. 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 '())
))
CS 363 Spring 2005 GMU
29
Example Functions
3. equal - takes two general lists as parameters; returns #T if the two
lists are equal; ()otherwise
(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 '())
))
CS 363 Spring 2005 GMU
30
Example Functions
(define (count L)
(if (null? L) 0
(+ 1 (count (cdr L)))
)
)
(count ‘( a b c d)) =
(+ 1 (count ‘(b c d))) =
(+ 1 (+ 1(count ‘(c d))))
(+ 1 (+ 1 (+ 1 (count ‘(d)))))=
(+ 1 (+ 1 (+ 1 (+ 1 (count ‘())))))=
(+ 1 (+ 1 (+ 1 (+ 1 0))))= 4
CS 363 Spring 2005 GMU
31
Scheme Functions
Now define
(define (count1 L) ??
)
so that (count1 ‘(a (b c d) e)) = 5
CS 363 Spring 2005 GMU
32
Scheme Functions
This function counts the individual elements:
(define (count1 L)
(cond ( (null? L) 0 )
( (list? (car L))
(+ (count1 (car L))(count1 (cdr L))))
(else (+ 1 (count (cdr L))))
)
)
so that (count1 ‘(a (b c d) e)) = 5
CS 363 Spring 2005 GMU
33
Example Functions
(define (append L M)
(if (null? L) M
(cons (car L)(append(cdr L) M))
)
)
(append ‘(a b) ‘(c d)) = (a b c d)
CS 363 Spring 2005 GMU
34
How does append do its job?
(define (append L M)
(if (null? L) M
(cons (car L)(append(cdr L) M))))
(append ‘(a b) ‘(c d)) =
(cons a (append ‘(b) ‘(c d))) =
CS 363 Spring 2005 GMU
35
How does append do its job?
(define (append L M)
(if (null? L) M
(cons (car L)(append(cdr L) M))))
(append ‘(a b) ‘(c d)) =
(cons a (append ‘(b) ‘(c d))) =
(cons a (cons b (append ‘() ‘(c d)))) =
CS 363 Spring 2005 GMU
36
How does append do its job?
(define (append L M)
(if (null? L) M
(cons (car L)(append(cdr L) M))))
(append ‘(a b) ‘(c d)) =
(cons a (append ‘(b) ‘(c d))) =
(cons a (cons b (append ‘() ‘(c d)))) =
(cons a (cons b ‘(c d))) =
CS 363 Spring 2005 GMU
37
How does append do its job?
(define (append L M)
(if (null? L) M
(cons (car L)(append(cdr L) M))))
(append ‘(a b) ‘(c d)) =
(cons a (append ‘(b) ‘(c d))) =
(cons a (cons b (append ‘() ‘(c d)))) =
(cons a (cons b ‘(c d))) =
(cons a ‘(b c d)) =
CS 363 Spring 2005 GMU
38
How does append do its job?
(define (append L M)
(if (null? L) M
(cons (car L)(append(cdr L) M))))
(append ‘(a b) ‘(c d)) =
(cons a (append ‘(b) ‘(c d))) =
(cons a (cons b (append ‘() ‘(c d)))) =
(cons a (cons b ‘(c d))) =
(cons a ‘(b c d)) =
(a b c d)
CS 363 Spring 2005 GMU
39
Reverse
Write a function that takes a list of elements and
reverses it:
(reverse ‘(1 2 3 4)) = (4 3 2 1)
CS 363 Spring 2005 GMU
40
Reverse
(define (reverse L)
(if (null? L) ‘()
(append (reverse (cdr L))(list (car L)))
)
)
CS 363 Spring 2005 GMU
41
Selection Sort in Scheme
Let’s define a few useful functions first:
(DEFINE (findsmallest lis small)
(COND ((NULL? lis) small)
((< (CAR lis) small)
(findsmallest (CDR lis) (CAR lis)))
(ELSE
(findsmallest (CDR lis) small))
)
)
CS 363 Spring 2005 GMU
42
Selection Sort in Scheme
Cautious programming!
(DEFINE (remove lis item)
(COND ((NULL? lis) ‘() )
((= (CAR lis) item) lis)
Assuming integers
(ELSE
(CONS (CAR lis) (remove (CDR lis)
item)))
)
)
CS 363 Spring 2005 GMU
43
Selection Sort in Scheme
(DEFINE (selectionsort lis)
(IF (NULL? lis) lis
(LET ((s (findsmallest (CDR lis) (CAR
lis))))
(CONS s (selectionsort (remove lis s)) )
)
)
CS 363 Spring 2005 GMU
44
Higher order functions
• Def: A higher-order function, or functional
form, is one that either takes functions as
parameters, yields a function as its result, or
both
• Mapcar
• Eval
CS 363 Spring 2005 GMU
45
Higher-Order Functions: mapcar
Apply to All - mapcar
- Applies the given function to all elements of the
given list; result is a list of the results
(DEFINE (mapcar fun lis)
(COND
((NULL? lis) '())
(ELSE (CONS (fun (CAR lis))
(mapcar fun (CDR lis))))
))
CS 363 Spring 2005 GMU
46
Higher-Order Functions: mapcar
• Using mapcar:
(mapcar (LAMBDA (num) (* num num
num)) ‘(3 4 2 6))
returns (27 64 8 216)
CS 363 Spring 2005 GMU
47
Higher Order Functions: EVAL
• 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
CS 363 Spring 2005 GMU
48
Using EVAL for adding a List of
Numbers
Suppose we have a list of numbers that must be added:
(DEFINE (adder lis)
(COND((NULL? lis) 0)
(ELSE (+ (CAR lis)
(adder(CDR lis ))))
))
Using Eval
((DEFINE (adder lis)
(COND ((NULL? lis) 0)
(ELSE (EVAL (CONS '+ lis)))
))
(adder ‘(3 4 5 6 6))
Returns 24
CS 363 Spring 2005 GMU
49
Other Features of Scheme
• Scheme includes some imperative features:
1. SET! binds or rebinds a value to a name
2. SET-CAR! replaces the car of a list
3. SET-CDR! replaces the cdr part of a list
CS 363 Spring 2005 GMU
50
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
CS 363 Spring 2005 GMU
51
COMMON LISP
• Includes:
–
–
–
–
–
–
–
–
records
arrays
complex numbers
character strings
powerful I/O capabilities
packages with access control
imperative features like those of Scheme
iterative control statements
CS 363 Spring 2005 GMU
52
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
CS 363 Spring 2005 GMU
53
ML
• Includes lists and list operations
• The val statement binds a name to a value
(similar to DEFINE in Scheme)
• Function declaration form:
fun function_name (formal_parameters) =
function_body_expression;
e.g.,
fun cube (x : int) = x * x * x;
CS 363 Spring 2005 GMU
54
Haskell
• Similar to ML (syntax, static scoped,
strongly typed, type inferencing)
• Different from ML (and most other
functional languages) in that it is purely
functional (e.g., no variables, no assignment
statements, and no side effects of any kind)
CS 363 Spring 2005 GMU
55
Haskell
• Most Important Features
– Uses lazy evaluation (evaluate no
subexpression until the value is needed)
– Has list comprehensions, which allow it to deal
with infinite lists
CS 363 Spring 2005 GMU
56
Haskell Examples
1. Fibonacci numbers (illustrates function
definitions with different parameter forms)
fib 0 = 1
fib 1 = 1
fib (n + 2) = fib (n + 1)
+ fib n
CS 363 Spring 2005 GMU
57
Haskell Examples
2. Factorial (illustrates guards)
fact n
| n == 0 = 1
| n > 0 = n * fact (n - 1)
The special word otherwise can appear
as a guard
CS 363 Spring 2005 GMU
58
Haskell Examples
3. List operations
– List notation: Put elements in brackets
e.g., directions = [“north”,
“south”, “east”, “west”]
– Length: #
e.g., #directions is 4
– Arithmetic series with the .. operator
e.g., [2, 4..10] is [2, 4, 6, 8, 10]
CS 363 Spring 2005 GMU
59
Haskell Examples
3. List operations (cont)
– Catenation is with ++
e.g., [1, 3] ++ [5, 7] results in
[1, 3, 5, 7]
– CONS, CAR, CDR via the colon operator (as in
Prolog)
e.g., 1:[3, 5, 7] results in
[1, 3, 5, 7]
CS 363 Spring 2005 GMU
60
Haskell Examples
• Quicksort:
sort [] = []
sort (a:x) = sort [b | b ← x; b <= a]
++ [a] ++
sort [b | b ← x; b > a]
CS 363 Spring 2005 GMU
61
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
CS 363 Spring 2005 GMU
62
Comparing Functional and
Imperative Languages
• Imperative Languages:
–
–
–
–
Efficient execution
Complex semantics
Complex syntax
Concurrency is programmer designed
• Functional Languages:
–
–
–
–
Simple semantics
Simple syntax
Inefficient execution
Programs can automatically be made concurrent
CS 363 Spring 2005 GMU
63