CS 320 : Functional
Programming in Ocaml
(based on slides from David Walker, Princeton, Lukasz Ziarek, Buffalo and myself.)
Marco Gaboardi MSC 116 gaboardi@bu.edu
In the previous classes…
What is a Functional Language
A functional language:
• defines programs in a way similar to the one we
useto define mathematical functions,
• avoids the use of mutable states (states that can
change) in describing what a program should do.
In a functional language, the information is maintained by the computation.
A good functional language part of the ML family.
• Small core language,
• Supports first-class higher order functions,
• Lexically scoped
• Statically strongly typed
• Type inference
• It has a good community: ocalm.org
Terminology: Expressions, Values, Types
• Expressions are computaCons
– 2 + 3 is a computaCon
• Values are the results of computaCons
– 5 is a value
• Types describe collecCons of values and the computaCons
that generate those values – int is a type
– values of type int include • 0, 1, 2, 3, …, max_int
• -1, -2, …, min_int
47
• Example rules:
(1)
(2) “abc” : string
0 : int
(3) ife1:intande2:int
then e1 + e2 : int
(5) if e1 : string and e2 : string
then e1 ^ e2 : string • Using the rules:
2:intand3:int. Therefore, (2 + 3) : int 5 : int
(4) ife1:intande2:int then e1 * e2 : int
(6)
Type Checking Rules
(and similarly for any other integer constant n) (and similarly for any other string constant “…”)
13
(Byrule 1) (By rule 3) (By rule 1)
if e : int
then string_of_int e : string
Type Soundness
“Well typed programs do not go wrong” Programming languages with this property have
sound type systems. They are called safe languages. Safe languages are generally immune to buffer overrun
vulnerabiliRes, uniniRalized pointer vulnerabiliRes, etc., etc. (but not immune to all bugs!)
Safe languages: ML, Java, Python, … Unsafe languages: C, C++, Pascal
38
33
Back to Let Expressions … Typing
x granted type of e1 for use in e2
let x = e1 in e2
overall expression takes on the type of e2
let x = 3 + 4 in
string_of_int x
x has type int
for use inside the let body
overall expression has type string
Another Example
subsDtute 2 for x
29
let x = 2 in
let y = x + x in y*x
Moral: Let operates by subs&tu&ng computed values for variables
let y = 2 + 2 in y*2
–>
–>
subsDtute 4 for y
let y = 4 in y*2
4*2
8
–> –>
Learning Goals for today
• FunctionType
• Tuples
• OptionTypes
Basic pattern matching
Functions
35
Defining funcDons
let add_one (x:int) : int = 1 + x
let keyword
Defining funcDons
36
let add_one (x:int) : int = 1 + x
funcDon name
type of result
type of argument
expression
that computes value produced by funcDon
argument name
Note: recursive funcDons with begin with “let rec”
Defining funcDons • Nonrecursive funcDons:
37
let add_one (x:int) : int = 1 + x
let add_two (x:int) : int = add_one (add_one x)
definiDon of add_one must come before use
38
Defining funcDons • Nonrecursive funcDons:
let add_one (x:int) : int = 1 + x
let add_two (x:int) : int = add_one (add_one x)
• With a local definiDon:
local funcDon definiDon hidden from clients
I lep off the types. O’Caml figures them out
Good style: types on top-level definiDons
let add_two’ (x:int) : int =
add_one (add_one x)
let add_one x = 1 + x in
39
Some funcDons:
Types for FuncDons
let add_one (x:int) : int = 1 + x
let add_two (x:int) : int = add_one (add_one x)
let add (x:int) (y:int) : int = x + y
Types for funcDons:
funcDon with two arguments
add_one : int -> int
add_two : int -> int
add : int -> int -> int
Rule for type-checking funcDons
General Rule:
Example:
40
If a funcDon f : T1 -> T2 and an argument e : T1 then f e : T2
add_one : int -> int
3 + 4 : int
add_one (3 + 4) : int
Rule for type-checking funcDons • Recall the type of add:
DefiniDon:
Type:
41
let add (x:int) (y:int) : int = x+y
add : int -> int -> int
42
Rule for type-checking funcDons • Recall the type of add:
DefiniDon:
Type:
Same as:
let add (x:int) (y:int) : int = x+y
add : int -> int -> int
add : int -> (int -> int)
43
Rule for type-checking funcDons
General Rule:
A -> B -> C
same as:
A -> (B -> C)
If a funcDon f : T1 -> T2 and an argument e : T1 then f e : T2
Example:
add : int -> int -> int
3 + 4 : int
add (3 + 4) : ???
44
Rule for type-checking funcDons
General Rule:
A -> B -> C
same as:
A -> (B -> C)
If a funcDon f : T1 -> T2 and an argument e : T1 then f e : T2
Example:
add : int -> (int -> int)
3 + 4 : int
add (3 + 4) :
45
Rule for type-checking funcDons
General Rule:
A -> B -> C
same as:
A -> (B -> C)
If a funcDon f : T1 -> T2 and an argument e : T1 then f e : T2
Example:
add : int -> (int -> int)
3 + 4 : int
add (3 + 4) : int -> int
46
Rule for type-checking funcDons
General Rule:
A -> B -> C
same as:
A -> (B -> C)
If a funcDon f : T1 -> T2 and an argument e : T1 then f e : T2
Example:
add : int -> int -> int
3 + 4 : int
add (3 + 4) : int -> int
(add (3 + 4)) 7 : int
47
Rule for type-checking funcDons
General Rule:
A -> B -> C
same as:
A -> (B -> C)
If a funcDon f : T1 -> T2 and an argument e : T1 then f e : T2
Example:
add : int -> int -> int
3 + 4 : int
add (3 + 4) : int -> int
add (3 + 4) 7 : int
Rule for type-checking funcDons
Example:
48
let munge (b:bool) (x:int) : ?? =
if not b then
string_of_int x
else
“hello” ;;
let y = 17;;
munge (y > 17) : ??
munge true (f (munge false 3)) : ??
f : ??
munge true (g munge) : ??
g : ??
Rule for type-checking funcDons
Example:
49
let munge (b:bool) (x:int) : ?? =
if not b then
string_of_int x
else
“hello” ;;
let y = 17;;
munge (y > 17) : ??
munge true (f (munge false 3)) : ??
f : string -> int
munge true (g munge) : ??
g : (bool -> int -> string) -> int
50
One key thing to remember
• If you have a funcDon f with a type like this:
A -> B -> C -> D -> E -> F
• Then each Dme you add an argument, you can get the type of the result by knocking off the first type in the series
fa1:B->C->D->E->F (ifa1:A)
f a1 a2 : C -> D -> E -> F f a1 a2 a3 : D -> E -> F
f a1 a2 a3 a4 a5 : F
(if a2 : B)
(if a3 : C)
(if a4 : D and a5 : E)
TopHat Q1-Q6
Tuples
52
Tuples
• A tuple is a fixed, finite, ordered collecDon of values
• Some examples with their types:
(1, 2) : int * int
(“hello”, 7 + 3, true) : string * int * bool
(‘a’, (“hello”, “goodbye”)) : char * (string * string)
Tuples
• To use a tuple, we extract its components
• General case:
53
let (id1, id2, …, idn) = e1 in e2
• An example:
let (x,y) = (2,4) in x + x + y
Tuples
• To use a tuple, we extract its components
• General case:
let (id1, id2, …, idn) = e1 in e2
• An example:
54
let (x,y) = (2,4) in x + x + y –> 2+2+4
subsDtute!
Tuples
• To use a tuple, we extract its components
• General case:
55
let (id1, id2, …, idn) = e1 in e2
• An example:
let (x,y) = (2,4) in x + x + y –> 2+2+4
–> 8
56
Rules for Typing Tuples
ife1:t1 ande2:t2 then (e1, e2) : t1 * t2
57
Rules for Typing Tuples
ife1:t1 ande2:t2 then (e1, e2) : t1 * t2
if e1 : t1 * t2 then
x1 : t1 and x2 : t2
inside the expression e2
let (x1,x2) = e1 in
e2
overall expression takes on the type of e2
58
Distance between two points
c2 =a2 +b2
a (x1, y1)
b c
Problem:
• A point is represented as a pair of floaDng point values.
• Write a funcDon that takes in two points as arguments and returns the distance between them as a floaDng point number
(x2, y2)
59
WriDng FuncDons Over Typed Data
Steps to wriDng funcDons over typed data:
1. Write down the funcDon and argument names
2. Write down argument and result types
3. Write down some examples (in a comment)
60
WriDng FuncDons Over Typed Data
Steps to wriDng funcDons over typed data:
1. Write down the funcDon and argument names
2. Write down argument and result types
3. Write down some examples (in a comment)
4. Deconstruct input data structures
• the argument types suggests how to do it 5. Build new output values
• the result type suggests how you do it
61
WriDng FuncDons Over Typed Data Steps to wriDng funcDons over typed data:
1. 2.
3. 4.
5. 6.
Write down the funcDon and argument names
Write down argument and result types Write down some examples (in a comment) Deconstruct input data structures
• the argument types suggests how to do it
Build new output values
• the result type suggests how you do it
Clean up by idenDfying repeated paZerns
• define and reuse helper funcDons
• your code should be elegant and easy to read
WriDng FuncDons Over Typed Data Steps to wriDng funcDons over typed data:
1. 2.
3. 4.
5. 6.
Write down the funcDon and argument names
Write down argument and result types Write down some examples (in a comment) Deconstruct input data structures
• the argument types suggests how to do it
Build new output values
• the result type suggests how you do it
Clean up by idenDfying repeated paZerns
• define and reuse helper funcDons
• your code should be elegant and easy to read
Types help structure your thinking about how to write programs.
62
63
Distance between two points
a type abbreviaDon
a (x1, y1)
b c
type point = float * float
(x2, y2)
Distance between two points
64
a (x1, y1)
b c
type point = float * float
let distance (p1:point) (p2:point) : float =
write down funcDon name argument names and types
(x2, y2)
Distance between two points
66
a (x1, y1)
b c
type point = float * float
let distance (p1:point) (p2:point) : float =
let (x1,y1) = p1 in
let (x2,y2) = p2 in
…
deconstruct funcDon inputs
(x2, y2)
Distance between two points
67
a (x1, y1)
b c
type point = float * float
let distance (p1:point) (p2:point) : float =
let (x1,y1) = p1 in
let (x2,y2) = p2 in
sqrt ((x2 -. x1) *. (x2 -. x1) +.
(y2 -. y1) *. (y2 -. y1))
compute funcDon results
noDce operators on floats have a “.” in them
(x2, y2)
Distance between two points
68
a (x1, y1)
b c
type point = float * float
let distance (p1:point) (p2:point) : float =
let square x = x *. x in
let (x1,y1) = p1 in
let (x2,y2) = p2 in
sqrt (square (x2 -. x1)) +.
square (y2 -. y1))
define helper funcDons to avoid repeated code
(x2, y2)
69
Distance between two points
a (x1, y1)
b c
type point = float * float
let distance (p1:point) (p2:point) : float =
let square x = x *. x in
let (x1,y1) = p1 in
let (x2,y2) = p2 in
sqrt (square (x2 -. x1) +. square (y2 -. y1))
let pt1 = (2.0,3.0)
let pt2 = (0.0,1.0)
let dist12 = distance pt1 pt2
(x2, y2)
tesDng
TopHat Q7-Q10
Unit
73
Tuples
• Here’s a tuple with 2 fields:
(4.0, 5.0) : float * float
• Here’s a tuple with 3 fields:
(4.0, 5, “hello”) : float * int * string
• Here’s a tuple with 4 fields:
(4.0, 5, “hello”, 55) : float * int * string * int
74
Tuples
• Here’s a tuple with 2 fields:
(4.0, 5.0) : float * float
• Here’s a tuple with 3 fields:
(4.0, 5, “hello”) : float * int * string
• Here’s a tuple with 4 fields:
(4.0, 5, “hello”, 55) : float * int * string * int
• Here’s a tuple with 0 fields: () : unit
75
Unit • Unit is the tuple with zero fields!
() : unit
• the unit value is wriZen with an pair of parens
• there are no other values with this type!
76
Unit • Unit is the tuple with zero fields!
() : unit
• the unit value is wriZen with an pair of parens
• there are no other values with this type!
• Why is the unit type and value useful?
• Every expression has a type:
(print_string “hello world\n”) : ???
77
Unit • Unit is the tuple with zero fields!
() : unit
• the unit value is wriZen with an pair of parens
• there are no other values with this type!
• Why is the unit type and value useful?
• Every expression has a type:
(print_string “hello world\n”) : unit
• Expressions executed for their effect return the unit value
TopHat Q11-Q12
Options
3
Op,ons
A value v has type t op,on if it is either: – the value None, or
– a value Some v’, and v’ has type t
Op,ons can signal there is no useful result to the computa,on
Example: we look up a value in a hash table using a key.
– If the key is present, return Some v where v is the associated value – If the key is not present, we return None
Slope between two points
4
a (x1, y1)
b c
type point = float * float
let slope (p1:point) (p2:point) : float =
(x2, y2)
Slope between two points
5
a (x1, y1)
b c
type point = float * float
let slope (p1:point) (p2:point) : float =
let (x1,y1) = p1 in
let (x2,y2) = p2 in
deconstruct tuple
(x2, y2)
Slope between two points
6
a (x1, y1)
b c
type point = float * float
let slope (p1:point) (p2:point) : float =
let (x1,y1) = p1 in
let (x2,y2) = p2 in
let xd = x2 -. x1 in
if xd != 0.0 then
(y2 -. y1) /. xd
else ???
avoid divide by zero
what can we return?
(x2, y2)
Slope between two points
7
a (x1, y1)
b c
type point = float * float
let slope (p1:point) (p2:point) : float option =
let (x1,y1) = p1 in
let (x2,y2) = p2 in
let xd = x2 -. x1 in
if xd != 0.0 then
???
else
???
we need an op,on type as the result type
(x2, y2)
Slope between two points
8
a (x1, y1)
b c
type point = float * float
let slope (p1:point) (p2:point) : float option =
let (x1,y1) = p1 in
let (x2,y2) = p2 in
let xd = x2 -. x1 in
if xd != 0.0 then
Some ((y2 -. y1) /. xd)
else
None
(x2, y2)
Slope between two points
9
a (x1, y1)
b c
type point = float * float
let slope (p1:point) (p2:point) : float option =
let (x1,y1) = p1 in
let (x2,y2) = p2 in
let xd = x2 -. x1 in
if xd != 0.0 then
(y2 -. y1) /. xd
else
None
Has type float Can have type float op,on
(x2, y2)
Slope between two points
10
a (x1, y1)
b c
type point = float * float
let slope (p1:point) (p2:point) : float option =
let (x1,y1) = p1 in
let (x2,y2) = p2 in
let xd = x2 -. x1 in
if xd != 0.0 then
(y2 -. y1) /. xd
else
None
Has type float
WRONG: Type mismatch
Can have type float op,on
(x2, y2)
Slope between two points
11
a (x1, y1)
b c
type point = float * float
let slope (p1:point) (p2:point) : float option =
let (x1,y1) = p1 in
let (x2,y2) = p2 in
let xd = x2 -. x1 in
if xd != 0.0 then
(y2 -. y1) /. xd
else
None
doubly WRONG: result does not match declared result
Has type float
(x2, y2)
Remember the typing rule for if
12
if e1 : bool
and e2 : t and e3 : t (for some type t) then if e1 then e2 else e3 : t
Returning an op,onal value from an if statement:
if … then
None : t op,on
else
Some ( … ) : t op,on
13
How do we use an op,on?
slope : point -> point -> float option
returns a float op,on
14
How do we use an op,on?
slope : point -> point -> float option
let print_slope (p1:point) (p2:point) : unit =
15
How do we use an op,on?
slope : point -> point -> float option
let print_slope (p1:point) (p2:point) : unit =
slope p1 p2
returns a float op,on;
to print we must discover if it is None or Some
16
How do we use an op,on?
slope : point -> point -> float option
let print_slope (p1:point) (p2:point) : unit =
match slope p1 p2 with
How do we use an op,on?
17
slope : point -> point -> float option
let print_slope (p1:point) (p2:point) : unit =
match slope p1 p2 with
Some s ->
| None ->
There are two possibili,es
Ver,cal bar separates possibili,es
18
How do we use an op,on?
slope : point -> point -> float option
let print_slope (p1:point) (p2:point) : unit =
match slope p1 p2 with
Some s ->
| None ->
The “Some s” paLern includes the variable s The object between | and -> is called a paLern
19
How do we use an op,on?
slope : point -> point -> float option
let print_slope (p1:point) (p2:point) : unit =
match slope p1 p2 with
Some s ->
print_string (“Slope: ” ^ string_of_float s)
| None ->
print_string “Vertical line.\n”
20
•
Wri,ng Func,ons Over Typed Data
Steps to wri,ng func,ons over typed data:
1. Write down the func,on and argument names
2. Write down argument and result types
3. Write down some examples (in a comment)
4. Deconstruct input data structures
5. Build new output values
6. Clean up by iden,fying repeated paLerns
•
For op,on types:
when the input has type t op,on, deconstruct with:
when the output has type t op,on, construct with:
match … with
| None -> …
| Some s -> …
Some (…)
None
Summary
• FunctionType
• Tuples
• OptionTypes
Basic pattern matching