Transcript Maclennan-chap10

Functional Programming: Lisp
MacLennan Chapter 10
Control Structures
• Atoms are the only primitives: since they are the
only constructs that do not alter the control flow.
– Literals (represent themselves)
• Numbers
• Quoted atoms
• lists
– Unquoted atoms are bound to
• Functions (if they have expr property)
• Data values (if they have apval property)
• Control-structure constructors
– Conditional expression
– Recursive application of a function to its arguments
2
• In LISP we have conditional expression.
• While in Fortran and Pascal we have to
drop from expression level to instruction
level to make a choice.
3
The logical connectives are
evaluated conditionally
• (or x y) = (if x t y)
• (or (eq (car L) ‘key) (null L) )
• What happen if L is null?
• (or (null L) (eq(car L) ‘key) )
• Does this work?
• (if (null L) t (eq (car L) ‘key))
4
Iteration is done by recursive
(defun getprop (p x)
(if (eq (car x) p)
( cadr x)
(getprop p (cddr x)) ))
5
• Reduction : reducing a list to one value
(defun plus-red (a)
(if (null a)
0
(plus (car a) (plus-red (cdr a)) )) )
(plus-red ‘(1 2 3 4 5))
>> 15
6
• Mapping: mapping a list into another list of the
same size
(defun add1-map (a)
(if (null a)
nil
(cons (add1 (car a)) (add1-map (cdr a)) )) )
(add1-map ‘(1 9 8 4))
>>(2 10 9 5)
7
• Filtering: forming a sublist containing all
the elements that satisfy some property
(defun minus-fil (a)
(cond ((null a) nil)
(( minusp (car a))
(cons (car a) minusp-fil (cdr a)) ))
(t (minusp-fil (cdr a)) )) )
8
• Some thing like Cartesian product , which
needs two nested loop
• For example:
(All-pairs ‘(a b c) ‘(x y z))
>>((a x) (a y) (a z) (b x) (b y) (b z) (c x) (c y) (c z))
We use distl (distribute from left)
(distl ‘b ‘(x y z))
>>((b x) (b y) (b z))
9
(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)) )) )
(the list function makes a list out of its argument)
10
• Recursion for Hierarchical structures
(defun equal (x y)
( or (and (atom x) (atom y) (eq x y))
(and (not (atom x)) (not (atom y))
(equal (car x) (car y))
(equal (cdr x) (cdr y)) )) )
11
• Recursion and Iteration are theoretically
equivalent
12
Functional arguments allow
abstraction
• mapcar: a function which applies a given function to
each element of a list and returns a list of the results.
(defun mapcar (f x)
(if (null x)
nil
(cons (f (car x)) (mapcar f (cdr x)) )) )
(mapcar ‘add1 ‘(1 9 8 4))
>> (2 10 9 5)
(mapcar ‘zerop ‘(4 7 0 3 -2 0 1))
>> (nil nil t nil nil t nil)
(mapcar ‘not (mapcar ‘zerop ‘(4 7 0 3 -2 0 1)))
>> (t t nil t t nil t)
13
Functional arguments allow
programs to be combined
• They simplify the combination of already
implemented programs.
14
Lambda expressions are
anonymous functions
• Instead of defining a name for a function
(defun twotimes (x) (times x 2)
(mapcar ‘twotimes L)
• We may write:
(mapcar ‘(lambda (x) (times x 2)) L)
15
Name Structures
• The primitive name structures are the
individual bindings of names (atoms) to
their values.
• Bindings are established through
– Property lists
• By pseudo-functions
– set (like declaring a variable)
– Defun (like declaring a procedure)
– Actual-formal correspondence
16
• Application binds Formals to Actuals
17
• Temporary bindings are a simple, syntactic
extension (with let )
18
• Dynamics scoping is the constructor
• Dynamic scoping complicates functional
arguments
19