Transcript Functional Programming Basics

Functional Programming Basics
Correctness > Clarity > Efficiency
cs776 (Prasad)
L1FP
1
• Function Definition
• Equations ; Recursion
• Higher-order functions
• Function Application
• Computation by expression evaluation
• Choices : parameter passing
Reliability
Types
Strong typing, Polymorphism, ADTs.
Garbage Collection
cs776 (Prasad)
L1FP
2
Imperative Style vs Functional Style
• Imperative programs
– Description of WHAT is to be computed is
inter-twined with HOW it is to be computed.
– The latter involves organization of data and the
sequencing of instructions.
• Functional Programs
– Separates WHAT from HOW.
– The former is programmer’s responsibility; the
latter is interpreter’s/compiler’s responsibility.
cs776 (Prasad)
L1FP
3
• Functional Style
– Value to be computed:
a+b+c
• Imperative Style
– Recipe for computing the value
• Intermediate Code
– T := a + b; T := T + c;
– T := b + c; T := a + T;
• Accumulator Machine
– Load a; Add b; Add c;
• Stack Machine
– Push a; Push b;
cs776 (Prasad)
Add; Push c; Add;
L1FP
4
GCD : functional vs imperative
fun gcd(m,n) =
if m=0 then n
else gcd(n mod m, m);
function gcd(m,n: int) : int;
var pm:int;
begin while m<>0 do
begin
pm := m; m := n mod m;
end;
return n
end;
cs776 (Prasad)
L1FP
n := pm
5
Pitfalls : Sequencing
(define (factorial n)
(define (iter prod counter)
(if (> counter n) prod
(iter (* counter prod)
(+ counter 1) ) ))
(iter 1 1)
)
cs776 (Prasad)
L1FP
6
(define (factorial n)
(let ((prod 1)(counter 1))
(define (iter)
(if
(> counter n)
prod
(begin
(set! prod (* counter prod))
(set! counter (+ 1 counter))
(iter))
))
))
cs776 (Prasad)
L1FP
7
Function
• A function f from domain A to co-domain
B, denoted f : A -> B, is a map that
associates with every element a in A, a
unique element b in B, denoted f(a).
– Cf. Relation, multi-valued function, partial
function, …
– In mathematics, the term “function” usually
refers to a total function; in computer science,
the term “function” usually refers to a partial
function.
cs776 (Prasad)
L1FP
8
Representation of functions
• Intensional :
Rule of calculation
fun double n = 2 * n;
fun double n = n + n;
• Extensional : Behavioral (Table)
… -2 -1 0
1 2 3 …
… -4 -2 0
2 4 6 …
• Equality:
f = g iff for all x: f(x) = g(x)
cs776 (Prasad)
L1FP
9
Expression Evaluation : Reduction
fun double x = x + x;
double ( 3 * 2)
double(6)
6+6
(3*2) + (3*2) (3*2) + o
6 + (3 * 2)
Applicative-Order
Normal-Order
(call by value)
(call by name)
cs776 (Prasad)
L1FP
6 + o
Lazy
(call by need)
10
Role of variable
• In functional style, a
variable stands for an
arbitrary value, and is
used to abbreviate an
infinite collection of
equations.
• In imperative style, a
variable is a location
that can hold a value,
and which can be
changed through an
assignment.
x := x + 1;
0+0=0
0+1=1
…
for all x : 0 + x = x
cs776 (Prasad)
• Functional variable can be
viewed as assign-only- once
imperative variable.
L1FP
11
Referential Transparency
• The only thing that matters about an
expression is its value, and any subexpression can be replaced by any other
expression equal in value.
• The value of an expression is independent
of its position only provided we remain
within the scopes of the definitions which
apply to the names occurring in the
expression.
cs776 (Prasad)
L1FP
12
Examples
let x = 5 in
x + let x = 4 in x + x;
val y = 2;
val y = 6;
var x : int;
begin
x := x + 2;
end;
address of x
cs776 (Prasad)
x := x + 1;
value stored in location for x
L1FP
13
(x=2) /\ (x+y>2)
(2+y>2)
vs
fun f (x : int) : int ;
begin
y := y + 1;
return ( x + y)
end;
(y=0) /\ (z=0) /\ (f(y)=f(z))
=
false
(y=0) /\ (z=0) /\ (f(z)=f(z))
=/= (y=0) /\ (z=0) /\ (f(z)=1)
cs776 (Prasad)
L1FP
14
• Common sub-expression elimination is an
“incorrect optimization” without referential
transparency.
– In functional style:
E + E = let x = E in x + x
– In imperative style:
return (x++ +
x++)
=/=
y := x++; return (y + y)
• Parallel evaluation of sub-expressions
possible with referential transparency.
cs776 (Prasad)
L1FP
15
Strict vs Non-strict
• A function is strict if it returns welldefined results only when the inputs are
well-defined.
– E.g., In C, “+” and “*” are strict, while “&&”
and “||” are not.
– E.g., In Ada, “and” and “or” are strict, while
“and then” and “or else” are not.
– E.g., constant functions are non-strict if called
by name, but are strict if called by value.
cs776 (Prasad)
L1FP
16
Benefits of Programming in a Functional
Language
• Convenient to code symbolic computations
and list processing applications.
• Automatic storage management
• Improves program reliability.
• Enhances programmer productivity.
• Abstraction through higher-order functions
and polymorphism.
• Facilitates code reuse.
• Ease of prototyping using interactive
development environments.
cs776 (Prasad)
L1FP
17
Summary
Programming Languages
Imperative
Functional
C, Pascal
Logic
Prolog
Dynamically Typed
(Meta-programming)
Statically Typed
(Type Inference/Reliable)
LISP, Scheme
Lazy Eval /
Pure
Haskell
cs776 (Prasad)
L1FP
Eager Eval
/ Impure
SML
18