Transcript Introduction to functional programming

Yu-Tzu Lin (林育慈)
http://web.ntnu.edu.tw/~linyt
Information
2
Information (cont.)
 References
 ANSI Common LISP, by Paul Graham, Prentice Hall, 1995.
(A good introductory book)
 LISP, by Patrick Henry Winston and Bertbold Klaus Paul
Horn, Addison Wesley, 1989.
(A quick guide to write Lisp)
 Introduction to functional programming, by Richard Bird
and Philip Wadler, Prentice-Hall , 1988.
 Functional programming, by Jeroen Fokker, 1995. (Free for
educational purposes)
3
Information (cont.)
 Grade
 Homework: 30%
 Midterm exam: 30%
 Final project: 40%
"I can do everything through him who gives me
strength“ Phillipians 4:13
4
Syllabus










Introduction
Lists
Specialized Data Structures
Control
Functions
Input and output
Symbols
Numbers
Macros
Structure
5
Introduction-Functional Programming
 Computers are expensive in early days
→ make the programming language resemble the
computer architecture
→ imperative programming
e.g. Pascal, C, …
Statement 1;
Statement 2;
Statement 3;
…
Statement n;
6
Introduction-Functional Programming
 There were already methods to solve problems before the
invention of computers
 Functions play a much more central roles
 Function


Expresses the connection between parameters (input) and the
result (output)
Is a good way of specifying a computation
Input
Function
Output
Result=f(parameter 1, parameter 2, …, parameter p)
7
Introduction-Functional Programming
 A functional program consists of the definition of one or
more functions
Function 1
Function 2
Function 3
…
Function n
8
Introduction-Lisp
 Lisp was first conceived by John McCarthy in 1956
 The first functional programming language
 Not the language satisfies all modern demands
 Other functional programming languages came to existence
for different purposes




ML
Scheme (an adjustment to Lisp)
Haskell
…
 Designed to evolve
 You can use Lisp to define new lisp operators
9
Introduction-Lisp
 Example
; Lisp
(defun sum (n)
(let ((s 0))
(dotimes (i n s)
(incf s i ) ) ) )
/* C */
int sum(int n){
int i, s = 0;
for (i = 0; i < n; i++)
s += i;
return(s);
}
10
Introduction-Lisp
 Start to write
 CLISP



http://web.ntnu.edu.tw/~linyt/func_prog/CLisp.zip
http://web.ntnu.edu.tw/~linyt/func_prog/cltl_ps.tar
中文用法
http://joung.im.ntu.edu.tw/teaching/pl/2001/Common_Lisp/readm
e.html
11
Introduction-Lisp
 An interactive front-end (toplevel)
 > is the toplevel prompt
> 1 (you type 1)
1 (the system print its value evaluate to itself)
> (another prompt to say that it’s ready for more)
 > (+ 2 3)
5
 + is the operator
 The numbers 2 and 3 are arguments
 Prefix notation
 2+3+4
?
12
Introduction-Lisp
 > (+)
0
 > (+ 2)
2
 > (+ 2 3)
5
 > (+ 2 3 4 5)
14
13
Introduction-Atoms and Lists
 Expressions can be nested
> (/ (-7 1) (- 4 2))
?
 Lisp uses a single notation to express all ideas
 Atom
 List
14
Introduction-Evaluation
 (+ 2 3)
 + is a function
 2 and 3 are arguments
 (+ 2 3) is a function call
 Function evaluation
 1: the arguments are evaluated, from left to right
 2: the values of the arguments are passed to the function
named by the operator
15
Introduction-Evaluation
 (/ (- 7 1) (- 4 2))
 1: evaluate (- 7 1)



1.1: evaluate 7
1.2: evaluate 1
1.3: pass 7 and 1 to the function -, which returns 6
 2: evaluate (- 4 2)



2.1: evaluate 4
2.2: evaluate 2
2.3: pass 4 and 2 to the function -, which returns 2
 3: pass 6 and 2 to the function /, which returns 3
16
Introduction-Evaluation
 > (/ 1 0)
Error: Division by zero.
 > (quote (+ 3 5))
(+ 3 5)
 > ‘(+ 3 5)
(+ 3 5)
 Quote takes a single argument and just returns it verbatim
 A way to protect expressions from evaluation
17
Introduction-Data
 Lisp offers all the data types we find in most other
languages
 Integer e.g. 256
 String e.g “ora et labora”
 …
 Special data type
 Symbol

Word
 List

Is represented zero or more elements enclosed in parentheses
18
Introduction-Data
 Symbol
 Does not evaluate to itself
 If you want to refer to a symbol, you should quote it
 > ‘Artichoke
ARTICHOKE
 List
 The elements can be of any type, including lists
 You have to quote lists, or lisp would take them for functions calls
 > ‘(my 3 “Sons”)
(MY 3 “Sons”)
 > ‘(the list (a b c) has 3 elements)
(THE LIST (a b c) HAS 3 ELEMENTS)
 One quote protects a whole expression
19
Introduction-Data
 Build lists by calling list
 > (list ‘my (+ 2 1) “Sons”)
(MY 3 “Sons”)
 The list is evaluated to return
 The list itself if it is quoted
 Its value if it is not quoted
 > (list ‘(+ 2 1) (+ 2 1))
((+ 2 1) 3)
 Lisp programs are expressed as lists
 You can write programs to generate programs
20
Introduction-Data
 Empty list
 >()
NIL
 nil
NIL
 You don’t have to quote nil because nil evaluates to itself
21
Introduction-List Operators
 Cons
 (cons <new first element> <a list>)
 > (cons ‘a ‘(b c d))
(A B C D)
 > (cons ‘a (cons ‘b nil))
(A B)
 > (list ‘a ‘b)
(A B)
22
Introduction-List Operators
 First
 > (first ‘(fast computers are nice))
FAST
 Rest
 > (rest ‘(fast computers are nice))
(COMPUTERS ARE NICE)
 Car
 > (car ‘(a b c))
A
 > (cdr ‘(a b c))
(B C)
 > (car (cdr (cdr ‘(a b c d))))

C
 Cxxxxr
 x is a or d
23
Introduction-Truth
 The symbol t is the default representation for truth
 Like nil, t evaluates to itself
 (listp object)
 Returns true when object is a list
 > (listp ‘(a b c))
T
 > (listp 27)
NIL
 A function whose return value is intended to be interpreted
as truth or falsity is called a predicate
 Common Lisp predicates often have names that end with p
24
Introduction-Truth
 (null object)
 Returns true when object is nil
 > (null nil)
T
 (not object)
 Returns true when object is nil
 > (not nil)
T
25
Introduction-Truth
 > (if (listp ‘(a b c))
(+ 1 2)
(+ 5 6))
3
 > (if (listp 27)
(+ 1 2)
(+ 5 6))
11
 > (if (listp 27)
(+ 2 3))
NIL
 > (if 27 1 2)
1
 Everything except nil also counts as true
26
Introduction-Truth
 (and expression)
 Evaluates the expression in order, returning nil immediately
if one evaluates to nil, or if they all return true, the value of
the last. Returns t if given no arguments.
 > (and t (+ 1 2))
3
27
Introduction
 Exercises
 Describe what happens when the following expressions are
evaluated




(+ (- 5 1) (+ 3 7))
(list 1 (+ 2 3))
(if (listp 1) (+ 1 2) (+ 3 4))
(list (and (listp 3) t) (+ 1 2))
28
Introduction-Functions
 defun
 > (defun our-fun (x)
(car (cdr (cdr x))))
OUR-FUN
 > (our-fun ‘(a b c d))
C

A symbol has to be quoted because otherwise it will be treated as a variable
 > (> (+ 1 4) 3)
T
 (defun sum-greater (x y z)
(> (+ x y) z))
SUM-GREATER
 > (sum-greater 1 4 3)
T
29
Introduction-Functions
 Lisp makes no distinction between a program, a procedure,
and a function
 Functions do for everything
30
Introduction-Recursion
 (defun our-member (obj lst)
(if (null lst)
nil
(if (eql (car lst) obj)
lst
(our-member obj (cdr lst)))))
 > (our-member ‘b ‘(a b c))
(B C)
 > (our-member ‘z ‘(a b c))
NIL
31
Introduction-Input and Output
 > (format t “~A plus ~A equals ~A. ~%” 2 3 (+ 2 3 ))
2 plus 3 equals 5.
NIL
 The first line is displayed by format
 The second line is the value returned by the call to format
 t indicates that the output is to be sent to standard output
 The second argument is a string that serves as a template for
output
 ~% indicates a newline
32
Introduction-Input and Output
 Read
 No arguments
 Reads from the standard input (toplevel)
 (defun ask (string)
(format t “~A” string)
(read))
 > (ask “How old are you?”)
How old are you? 20
20
33
Introduction-Variables
 Let
 One of the most frequently used operators in Common Lisp
 > (let ((x 1) (y 2))
(+ x y))
3
 (defun ask-number ( )
(format t “Please enter a number. “)
(let ((val (read)))
(if (numberp val)
val
(ask-number))))
34
Introduction-Variables
 Global variable
 > (defparameter *x* 32)
*x*
 > *x*
32
 (defconstant limit (+ *x* 1))
 (boundp symbol)
 Returns true iff symbol is the name of a special variable
 > (boundp ‘*x*)
T
35
Introduction
 Exercises
 What does this function do?
(defun enigma (x)
(and (not (null x))
(or (null (car x))
(enigma (cdr x)))))
36
Introduction-Assignment
 > (setf *x* 98)
98
 > (let ((n 10)
(setf n 2)
n)
2
 > (setf x (list ‘a ‘b ‘c))
(A B C)
 > (setf (car x ) ‘n)
N
>x
(N B C)
37
Introduction-Assignment
 (setf a b
cd
e f)
 (setf a b)
(setf c d)
(setf e f)
38
Introduction-Functional programming in Lisp
 Functional programming means writing programs that
work by returning values, instead of by modifying things
 > (setf lst ‘(c a r a t))
(C A R A T)
 > (remove ‘a lst)
(C R T)
 > lst
(C A R A T)
 (setf new_x (remove ‘a x))
39
Introduction-Iteration
 (defun show-squares (start end)
(do ((i start (+ i 1)))
((> i end) ‘done)
(format t “~A ~A~%” i (* i i))))
 > (show-squares 2 5)
 24
39
4 16
5 25
DONE
40
Introduction-Functions as Objects
 In Lisp, functions are regular objects, like symbols or
strings or lists
 (function function_name)
 Returns the function whose name is function_name
 > (function +)
#<SYSTEM-FUNCTION + >
 > #’ +
 > (apply #’+ ‘(1 2 3))
6
 > (+ 1 2 3)
6
41
Introduction
 Exercises
 Mary is trying to write a function that returns the sum of all
the non-nil elements in a list. Explain why this program
cannot give a correct answer.
 (defun summit (lst)
(remove nil lst)
(apply #’+ lst))
42