Transcript funcProgx

Computer Eng. Software Lab II
242-203, Semester 2, 2016-2017
Functional Programming
with Racket
Please ask
questions
Who I am:
Andrew Davison
CoE, WiG Lab Office
[email protected]
FP with Racket
1
Programming Language
Paradigms (kinds)
Imperative
(state/memorybased)
Procedural
e.g. C,
Basic,
Pascal
Object-based
e.g. C++,
Java, C#
Declarative
(math-based)
Parallelism
e.g. Erlang,
Linda, Oz,
Java, PVM
Logic
e.g. Prolog,
Mercury
FP with Racket
Functional
e.g. Lisp
Scheme,
Racket
Database
(relational)
e.g. SQL
2
Overview
1. Why Racket?
2. Constants (names)
2. Functions
8. Higher Order Functions
9. Using DrRacket
10. More Information
3. Lists
4. cond
5. Recursion
6. No-name Functions:
lambda
FP with Racket
continued
3
1. Why Racket?
• Racket is one of the simpler functional
programming languages
– a program is a collection of (math) functions
– closeness to maths makes programming easier
• Racket has plenty of advanced features
– e.g. first-class functions
• function body code can be manipulated as data
• data can be used as function body code
• Used in Artficial Intelligence (AI)
FP with Racket
4
2. Constants (names)
More details on how
to use DrRacket are
given in Section 9.
myPi is defined here
myPi is evaluated then
printed
'myPi is not evaluated
FP with Racket
'pi is pre-defined
5
First Error
FP with Racket
6
3. Functions
• A function call is written as:
(operator arg1 arg2 … argn)
• For example:
(+ 2 3)
means
FP with Racket
2+3
7
Function Call Examples
The + operator
(and other arithmetic)
operators can take
any number of
arguments.
The same as:
(2 + 3) * (1 + 2)
FP with Racket
8
Test Functions (Predicates)
• Test functions return boolean values true or
false.
• Their names end with a '?'
– e.g. number? char?
FP with Racket
9
Defining Functions
Similar C code is:
int sq(int x)
{ return x*x; }
FP with Racket
10
Similar C code is:
int myMax(int x,int y)
{ if (x > y)
return x;
else
return y;
}
FP with Racket
11
Combining Functions
• Racket functions can be easily combined
– make a function call the argument of another
function
function call
arguments
FP with Racket
12
Execute by Rewriting
•
•
•
•
•
•
•
Execute by rewriting from inside to outside.
(myMax (sq -3) (sq 4) )
"Red" means
(myMax (-3 * -3) (4 * 4) )
rewrite
(myMax
9
16 )
(if (> 9 16) 9 16)
(if false
9 16)
16
FP with Racket
13
4. Lists
• List values are placed inside (list …):
–
–
–
–
(list
(list
(list
(list
)
// an empty list
1 2 3)
// a list of numbers
'a 'b 'c)
// a list of names
(list 1 2) (list 2 3 4))
// a list of two lists
• If the language includes list abbreviations,
then (list ...) can be written as '(...)
– '(1 2 3) is the same as (list 1 2 3)
FP with Racket
14
Basic List Operations
• (null? x)
– returns true is x is an empty list; otherwise
returns false
• (car x)
– returns the first element (head) of a nonempty list x
• (cdr x)
– returns the tail of a non-empty list x
• everything except the first element
FP with Racket
continued
15
• (cadr x)
– returns the head element of the tail of x
• (cons h l)
– makes a new list where the head is h, the tail is l
FP with Racket
16
List Operation Examples
FP with Racket
17
plusList
plusList pulls out the first two arguments of a
list and adds them
FP with Racket
18
Another Error
FP with Racket
19
Other Built-in List Functions
• (length x)
– returns the length of a list x
• (append x y)
– makes a new list by appending list x onto the front of
list y
• (reverse x)
– makes a list by reversing the list x
and many, many more...
FP with Racket
continued
20
combining reverse
and append
FP with Racket
21
5. cond: the multi-branch if
Similar to the C code:
int sizer(int x)
{ if (x == 0)
return 0;
else if (x > 0)
return 1;
else
return -1;
}
FP with Racket
22
6. Recursion
• Base case:
– the function returns an answer and stops
• Recursion step:
– the body of the function calls itself (with smaller
arguments)
FP with Racket
23
length Defined
base case
recursive
step
FP with Racket
24
append Defined
33
FP with Racket
25
member Defined
mem? is a predicate
(a test function)
mem is the wrong
name
FP with Racket
26
7. No-name Functions: lambda
Similar to the C-like code:
int ??(int x)
{ return x *x; }
Similar to a C-like
function call:
??(3)
The language 'level' must be
increased for lambda to be supported.
FP with Racket
27
Defining Functions (v.2)
Similar to the C-like code:
sq2 =
int ??(int x)
{ return x * x; }
FP with Racket
28
Why have lambda?
• For simple examples (like ours), there is no
need for lambda.
• lambda becomes very useful in higher order
programming, where data and functions need
to be translated into each other
– e.g. parsing, AI
FP with Racket
29
8. Higher Order Functions
An ‘Intermediate Student’ feature
• A higher order function has 1 or more
arguments which are function names
– higher order functions are also called functionals
• Higher order functions are very important to
advanced functional programming and AI.
FP with Racket
30
apply
• (apply f x)
– same as executing (f x)
– its first argument, f, is a function name
– its second argument, x, is the input for f
FP with Racket
31
same as (+ 1 2 3)
same as (* 2 3 5)
same as (sq 5)
same as (sq 5 6)
FP with Racket
32
map
• (map f x)
(map f '(a b c ... z) ) 
( (f a) (f b) (f c) ... (f z))
– returns a list by applying the function f to each
element of the list x
 ( (sq 1) (sq 2) (sq 3) (sq 4) (sq 5) )
FP with Racket
33
map and plusList
plusList is applied
to the 4 lists in the
input list.
FP with Racket
34
9. Using DrRacket
• Download the installation program for
DrRacket from:
http://fivedots.coe.psu.ac.th/
Software.coe/LAB/FuncProg/
• The filename:
racket-6.3-i386-win32.exe
• Installs on Windows
FP with Racket
35
• Start DrRacket from the Windows Start menu
item Racket:
definitions go here
execute functions
here
FP with Racket
36
Some Notes
• Set the language mode
to “Beginning Student
with List Abbreviations”
– under the Language >
Choose Language
menu item
FP with Racket
continued37
• Press the "Run" button after adding a new
function to the definitions window
– this makes the new function visible down in the
execution window
FP with Racket
38
Create a Racket Program
using any text editor
Don't forget this line.
FP with Racket
39
Load myMax.scm
use the File/Open menu item;
or double click on the file
Press the "Run" button for the execution
window to be updated at the bottom.
FP with Racket
40
Use the myMax Function
FP with Racket
41
• Alternatively, you can type the function into
DrRacket's definition window, and save it
from there.
– you get colour-coded syntax, indenting
(tabbing), and error checking as you type
FP with Racket
42
10. More Information
• The "Help/
Racket
Documentation"
menu item:
Very nice
FP with Racket
43
PLT Scheme  Racket
• PLT Scheme v.5 was renamed to Racket
– two websites:
• http://plt-scheme.org/
• http://racket-lang.org/
(frozen in 2010)
(active)
• At the beginner's level (i.e. for us), there's no
difference between the two languages.
FP with Racket
44