Functional Programming
Download
Report
Transcript Functional Programming
Rahman Lavaee Mashhadi
Mohammad Shadravan
Conditional expressions
LISP was the first language to contain a conditional
expression
In Fortran and Pascal we have to drop from expression
level to statement level
(cond (p1 e1) … (pn en))
( if p e1 e2) = (cond (p e1) (t e2))
example :( defun sg(x)
(cond((plusp x) 1)
((zerop x) 0)
((minusp x) -1)) )
Logical connectives
Logical connectives are evaluated conditionally
(or x y) = (if x t y)
Their operands are evaluated sequentially
(or (eq (car L) ‘key) (null L) )
wrong
Strict interpretation vs. sequential interpretation
Iteration
Iteration is done by recursion
Analogous to while-loop
(defun plus-red (a)
(if (null a) 0
(plus (car a) (plus-red (cdr a)) )) )
There is no “bounds” , no “explicit indexing” , no
“control variable”
It obeys the zero-one-infinity principle
Nested Loops
Example :
Cartesian product
(defun all-pairs (M N)
(if (null M) nil
(append (distl (car M) N)
(all-pairs (cdr M ) N )) ))
(defun distl (x N)
(if (null N) nil
(cons (list x (car N))
(distl x (cdr N)) )) )
Hierarchical structures
Are difficult to handle iteratively
example: equal function
eq only handles atoms
initial states
If x and y are both atoms (equal x y) = (eq x y)
If exactly one of x and y is atom (equal x y) = nil
(and (atom x) (atom y) (eq x y))
use car and cdr to write equal recursively
Equivalency of recursion and
iteration
it may be seemed that recursion is more powerful than
iteration
in theory these are equivalent
As we said iteration can be done by recursion
by maintaining a stack of activation records we can
convert a recursive program to an iterative one.
Functional arguments and
abstraction
Suppress details of loop control and recursion
example: applying a function to all elements of list
(defun mapcar (f x)
(if (null x)
nil
(cons (f (car x)) (mapcar f (cdr x)) )) )
(defun reduce (f a x)
(if (null x)
a
(f (car x) (reduce f a (cdr x) )) ) )
Functional arguments and
combination of programs
Functional arguments simplify the combination of
already implemented programs
example : inner product of two lists
(defun ip (u v)
(reduce ‘plus 0 (mapcar2 ‘times u v)) )
Anonymous functions
It is inconvenient to give a name to every function we
want to pass it only once
(defun consval (x) (cons val x))
An obvious solution is just to pass the function’s body
(mapcar ‘(cons val x) L)
It is ambiguous : we do not know which names are
parameters and which ones are global
“lambda expressions” come in hand
(mapcar ‘(lambda (x) (cons val x)) L)
Functionals
A functional is a function that has either(or both) of
the following:
One or more functions as arguments
A function as its result
Examples:
Mapcar, reduce ,…
Converting a binary function to a unary one
Functional can replace lambda
expressions
Specifying parameters of a function with lambda
expressions can be done by functionals
example:
(lambda (y) (f x y))
define “bu” function to fix one parameter of “f”
(defun bu (f x) (function (lambda (y) (f x y)) ))
(lambda (y) (f x y)) ~ (bu f x)
(lambda (x y) (f y x)) ~ (rev f)
Combining functions
Flexibility of combining functions can be increased by
using the uniform style.
Take a function , and return a function
((map ‘add1) L) = (mapcar ‘add1 L)
This form is called ‘combining forms’
Combining existing programs to acomplish new tasks
example: (set ‘vec-dbl (map (bu ‘times 2)) )
(vec-dbl ‘(1 4 3 2))
(2 8 6 4)
Backus style for functional
programming
alternate functional style of programming
Based on ‘combining form’
Programming at a higher level of abstraction
Simple algebraic manipulation
combining, reversing, mapping functions
Function-level vs. object-level(manipulate function
rather objects)
Backus notation
Name
Lisp
Backus
Application
Mapping
Reduction
Composition
Binding
Constant
Lists
Built-in-functions
Selectors
(f x)
(map f)
(red f a)
(comp f g)
(bu f k)
(const k)
(a b c d)
plus, times, …
cdr, car, cadr, …
f:x
αf
/f
fog
(bu f k)
k©
(a,b,c,d)
+,×,…
tail, 1 , 2
Variable-free programming
Variables (i.e. formal parameters and algol scope rules)
complicate manipulating programs
One of the goals of this notation was to eliminate
variables
Elimination of lambda expressions by using bu and rev
functionals
Example: inner product function
Trans:<<…ui…> , <…vi…>> = <….<ui,vi>…>
(α ×): (trans: <u,v>)=<u1v1,…,unvn>
Ip: <u,v> = (/+): ((α ×): (trans: <u,v>))
Variable elimination
Ip= (/+)o (α ×)o trans
Name structures
Value bindings are established in two ways:
Property lists
Established by pseudo functions such as ‘set’ and ‘defun’
example:
(set ‘text ‘(to be or not to be))
They are global
low level execution with property lists
example:
(putprop ‘add1 ‘(lambda (x) (+ x 1)) ‘expr)
Actual formal correspondence
Like argument passing in other languages
example :
(defun times (x y) (* x y))
(times 3 FACT)
the formal x will be bound to atom 3 and the formal y will be bound
to the value of actual FACT
Temporary binding
Binding names in a local context like in algol’s blocks
is done by actual
Prevents duplicate calculation
Obeys abstraction principle
(defun roots (a b c)
(list
(/ (+ (- b) (sqrt (- (expt b 2) (* 4 a c)) ))
(* 2 a))
(/ (+ (- b) (sqrt (- (expt b 2) (* 4 a c)) ))
(* 2 a)) ))
solution
(defun roots-aux (d)
(list
(/ (+ (- b) d) (* 2 a))
(/ (+ (- b) d) (* 2 a)) ))
(defun roots (a b c)
roots-aux (sqrt (- ( expt b 2)
(times 4 a c)) )) )
Let function
Function calling with let
(let ((n1 e1) … (nm em)) E)
Abbreviation for a function definition and application
(defun QQQQQ (n1 … nm) E)
(QQQQQ e1 …. em)
Allows a number of local names to be bound to values
at one time
The second argument is evaluated in the resulting
environment and is returned as the value of let
Like alogol block , Ada declare block
Dynamic scoping
review
Dynamic scoping: functions are called in the
environment of its caller
Static scoping: functions are called in the environment
of its definition
LISP uses dynamic scoping
example : roots-aux had access to the names ‘a’ and ‘b’
The ‘let’ function needs dynamic scoping
Dynamic scoping complicates
functional arguments
(defun twice (func val) (func (func val)) )
(twice ‘add1 5) returns 7
(twice ‘(lambda (x) (times 2 x)) 3) returns 12
func
val
DL
3
x
DL
3
a
(times 2 x)
Functional argument problem
(set ‘val 2)
2
(twice ‘(lambda (x) (times val x)) 3)
What is the return value of this expression?
we expect it to be 12
but it will return 27!
why?
Cause :Collision of variables
val
2
func
val
DL
3
x
3
DL
(times val x)
What’s the solution?
What should we do?
use different names
In a large program it would be impractical to ensure
that all of the names are distinct
change the scoping rule
‘function’ primitive
Use ‘function’ primitive to bind the lambda expression
to its environment of definition
(twice (function (lambda (x) (times val x)) ) 3 )
this will return 12
val
2
func
val
x
3
3
(times val x)
Syntactic structures
Convenience for programmers is not the main
intention of the S-Expression
‘cond’ syntax was improved for convenience of
programmers
(cond (p1 e1) (p2 e2) … (pn en))
(cond p1 e1 p2 e2 … pn en)
‘define’ function was used for global binding
(define ((n1 e1) … (nk ek)) )
Syntactic structures
(define ( (add1 (lambda (x) (+ x 1)) )) )
Lots of idiotic single parentheses
‘defun’ was declared
(defun (add1 x) (+ x 1))
(quote val) was improved to ‘val
(set (qutoe val) 2) was improved (setq val 2)
List representation of programs
Facilitates program manipulation’
Balances reduction of readability
Simple to write LISP programs that generate other
LISP programs
Separating parts of a function
(car A) is the name of the function A
(cdr A) is the arguments of the function A
Obeys Elegance Principle : writing LISP interpreter in
LISP