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
Announcements
• Newtheoryassignmentpostedyesterday,due Wednesday Oct 14, 11:59pm.
In the previous class
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.
• 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
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
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
–> –>
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
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
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
Tail recursion
• Tail recursion is the idea to write code of recursive functions in a way that the recursive call happen in the tail, i.e. as the last operation.
• Often it is implemented using some helper function that accumulates the result while performing the recursion.
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
Curried FuncKons
Currying: verb. gerund or present parAciple (1) to prepare or flavor with hot-tasKng spices
(2) to encode a mulK-argument funcKon using nested, higher-order funcKons.
(1)
fun x -> (fun y -> x+y)(* curried *) fun x y -> x + y (* curried *) fun (x,y) -> x+y (* uncurried *)
(2)
40
Factoring Code in OCaml Consider these definiKons:
let rec inc_all (xs:int list) : int list = match xs with
| [] -> []
| hd::tl -> (hd+1)::(inc_all tl)
let rec square_all (xs:int list) : int list = match xs with
| [] -> []
| hd::tl -> (hd*hd)::(square_all tl)
The code is almost idenKcal – factor it out!
23
u
u
Type of the undecorated map?
let rec map f xs =
match xs with
| [] -> []
| hd::tl -> (f hd)::(map f tl)
map : (‘a -> ‘b) -> ‘a list -> ‘b list
66
How about reduce?
let rec reduce (f:’a -> ‘b -> ‘b) (u:’b) (xs: ‘a list) : ‘b = match xs with
| [] -> u
| hd::tl -> f hd (reduce f u tl)
What’s the most general type of reduce?
(‘a -> ‘b -> ‘b) -> ‘b -> ‘a list -> ‘b
91
And this one?
let rec reduce f u xs = match xs with
| [] -> u
| hd::tl -> f hd (reduce f u tl)
let mystery2 g =
reduce (fun a b -> (g a)::b) []
let rec mystery2 g xs =
match xs with
| [] -> []
| hd::tl -> (g hd)::(mystery2 g tl) map!
100
Learning goals for today
• MoreexercisesonInductiveDataTypes
Inductive Data Types
55
InducFve data types
• We can use data types to define inducFve data
• A binary tree is:
– a Leaf containing no data
– a Node containing a key, a value, a leP subtree and a right subtree
56
InducFve data types
• We can use data types to define inducFve data
• A binary tree is:
– a Leaf containing no data
– a Node containing a key, a value, a leP subtree and a right subtree
type key = string
type value = int
type tree =
Leaf
| Node of key * value * tree * tree
InducFve data types
62
type key = int
type value = string
type tree =
Leaf
| Node of key * value * tree * tree
let rec insert (t:tree) (k:key) (v:value) : tree =
match t with
| Leaf -> Node (k, v, Leaf, Leaf)
| Node (k’, v’, left, right) ->
if k < k' then
Node (k', v', insert left k v, right)
else if k > k’ then
Node (k’, v’, left, insert right k v)
else
Node (k, v, left, right)
type sitree = int stree
match n with
Zero -> 0
General form:
InducFve data types
677
type (‘key, ‘val) tree =
• Recall, a natural number n is either: Leaf
– zero, or
| Node of ‘key * ‘val * (‘key, ‘val) tree * (‘key, ‘val) tree
– m + 1
• We use a data type to represent this definiFon exactly:
type nat = Zero | Succ of nat
let rec nat_to_int (n : nat) : int =
A more convenFonal notaFon
type ‘a stree = (string, ‘a) tree
| Succ n -> 1 + nat_to_int n
would have been (but is not ML): definiFon: definiFon:
let rec double_nat (n : nat) : nat =
match n with
type ‘x f = body type f x = body use:| Zero -> Zero use:
arg f
| Succ m -> Succ (Succ(double_nat m))
f arg
0
Write a function taking in input a tree and returning the number of leaves.
type tree = Leaf | Node of (int * string * tree * tree) let rec leaves (t:tree) : int =
Write a function taking in input a tree and returning the number of leaves.
type tree = Leaf | Node of (int * string * tree * tree)
let rec leaves (t:tree) : int =
match t with
|Leaf -> 1
| Node (_,_,t1,t2) -> (leaves t1) + (leaves t2)
Write a data type for binary trees with internal nodes and labeled by Booleans.
Write a fold function for this data type.
type `a btree =
let rec fold
Write a data type for binary trees with internal nodes labeled by elements of an arbitrary type.
Write a fold function for this data type.
type `a btree = Leaf | Node of (`a * (`a btree) * (`a btree))
let rec fold (f: `a -> `b -> `b -> `b) (a:`b) (t:`a btree): `b=
match t with
|Leaf -> a
|Node (n,l,r) -> f n (fold f a l) (fold f a r)
Write a data type for a stack of integers. Write a function push and a function pop
type stack =
let push let pop
Write a data type for a stack of integers. Write a function push and a function pop
type stack = Empty | Cons of (int * stack)
let push (i:int) (s:stack) : stack = Cons (i,s)
let pop (s:stack) :stack option = match s with Empty -> None
| Cons (_,xs) -> Some xs;;
Input/Output on files in OCaml
Input and Output Channels
The normal way of opening a file in OCaml returns a channel. There are two kinds of channels:
• channels that write to a file: type out_channel
• channels that read from a file: type in_channel
Four operations that will be useful are:
• Open input file: open_in: string -> in_channel
• Open out file: open_out: string -> out_channel
• Close input file: close_in: in_channel -> unit
• Close input file: close_out: out_channel -> unit
If you want to use a channel, you can use let, as usual.
Discarding an expression
Often we may need to discard an expression
• This happens often with unit, when it is returned and we don’t need it.
An easy way to discard an expression is by using let with a variable that does not appear in the body:
let x = printf “%s/n” str in 3+2
In this case, we can also use underscore to avoid giving a name to this variable:
let _ = printf “%s/n” str in 3+2
This is often abbreviated in ocaml using a semicolon:
printf “%s/n” str; 3+2
Reading a line
let read_line (inc:in_channel) : string option = match input_line inc with
| l -> Some l
| exception End_of_file -> None
Writing a line
Printf.fprintf ouc “%s\n” str
The types need to match
An example – copying one line:
let ic=open_in “tmp.in’’ in let oc=open_out “tmp.ou’’ in let l=read_line ic in
let _ = match l with
Some s -> Printf.fprintf oc “%s/n’’ s in |None -> ()
let _= close_in ic in let _= close_out oc in()
PracKce Problems
Using map, write a funcKon that takes a list of pairs of integers, and produces a list of the sums of the pairs.
– e.g., list_add [(1,3); (4,2); (3,0)] = [4; 6; 3] – Write list_add directly using reduce.
Using map, write a funcKon that takes a list of pairs of integers, and produces their quoKent if it exists.
– e.g., list_div [(1,3); (4,2); (3,0)] = [Some 0; Some 2; None] – Write list_div directly using reduce.
Using reduce, write a funcKon that takes a list of opKonal integers, and filters out all of the None’s.
– e.g., filter_none [Some 0; Some 2; None; Some 1] = [0;2;1]
– Why can’t we directly use filter? How would you generalize filter so that
you can compute filter_none? AlternaKvely, rig up a soluKon using filter + map. Using reduce, write a funcKon to compute the sum of squares of a list of
numbers.
– e.g., sum_squares = [3,5,2] = 38
104
Summary
• Exerciseonhigher-orderfunctions • DataTypes
• InductiveDataTypes