CS 320 : Functional Programming in Ocaml
based on slides by
David Walker (Princeton), Lukasz Ziarek (Bu alo),
and Marco Gaboardi (BU)
Assaf Kfoury MSC 118 kfoury@bu.edu
This class – CS 320
We will study different components of programming languages (PL’s), such as:
• design issues of PL’s and features they support (not all PL’s are the same – why? – some are better for some purposes, no single PL is best for all tasks)
• formal reasoning about programmable functions
• how PL’s are compiled
• runtime environment of compiled programs
• functional programming as a new paradigm
What is a Functional Language
A functional language:
• defines programs in a way similar to the way
we define mathematical functions,
• avoids the use of mutable states (states that
can change) in the execution of a program.
In pure functional languages, all information pertaining to the computation is transparent: there is “no hidden information”, “no side effects”, “what you code/see is all what you get”.
Why study functional programming?
1. Learning a different style of programming teach you that programming transcends programming in a language
2. Functional languages predict the future
3. Functional languages are more and more used in
industry
4. Functional languages help writing correct code
Copyright Nate Foster
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
TopHat Q1-Q6
Learning Goals for today
• Basic usage of Ocaml • Expressions vs values • Type checking basics • Type Safety
hello.ml:
A First OCaml Program
32
print_string “Hello COS 326!!\n”;;
hello.ml:
print_string “Hello COS 326!!\n”
f arg
“…”
hello.ml:
print_string “Hello COS 326!!\n”
compiling and running hello.ml:
$ ocamlbuild hello.d.byte
$ ./hello.d.byte
Hello COS 326!!
$
35
hello.ml:
A First OCaml Program
print_string “Hello COS 326!!\n”
interpreting and playing with hello.ml:
$ ocaml
Objective Caml Version 3.12.0
#
36
hello.ml:
A First OCaml Program
print_string “Hello COS 326!!\n”
interpreting and playing with hello.ml:
$ ocaml
Objective Caml Version 3.12.0
# 3 + 1;;
– : int = 4 #
37
hello.ml:
A First OCaml Program
print_string “Hello COS 326!!\n”
interpreting and playing with hello.ml:
$ ocaml
Objective Caml Version 3.12.0
# 3 + 1;;
– : int = 4
# #use “hello.ml”;; hello cos326!!
– : unit = ()
#
38
hello.ml:
A First OCaml Program
print_string “Hello COS 326!!\n”
interpreting and playing with hello.ml:
$ ocaml
Objective Caml Version 3.12.0
# 3 + 1;;
– : int = 4
# #use “hello.ml”;; hello cos326!!
– : unit = ()
# #quit;;
$
Functions: so confusing!
• What is the difference between calling a function in these two ways: f arg1 arg2 f (arg1, arg2)
The type of the first is:
type_of_arg1 -> type_of_arg2 -> return_type_of_f
The type of the second is:
Challenge question: How
type_of_arg1 * type_of_arg2 -> return_type_of_f
can both be true?
For now just consider both as a way to pass multiple arguments, but more is going on under the hood
Which one you use depends on how you define your function!
• Functions only take one argument (wait … but what is happening above?!?)
• Functions always return a value
No return statement
Body of a function is an Expression NOT a sequence of statements
How would you write a program summing the first n numbers?
39
A Second OCaml Program
sumTo8.ml:
a comment (* … *)
(* sum the numbers from 0 to n
precondition: n must be a natural number
*)
let rec sumTo (n:int) : int =
match n with
0 -> 0
| n -> n + sumTo (n-1)
let _ =
print_int (sumTo 8);
print_newline()
sumTo8.ml:
(* sum the numbers from 0 to n
precondition: n must be a natural number
*)
let rec sumTo (n:int) : int =
match n with
0 -> 0
| n -> n + sumTo (n-1)
let _ =
print_int (sumTo 8);
print_newline()
41
sumTo8.ml:
A Second OCaml Program
(* sum the numbers from 0 to n
precondition: n must be a natural number
*)
let rec sumTo (n:int) : int =
match n with
0 -> 0
| n -> n + sumTo (n-1)
let _ =
print_int (sumTo 8);
print_newline()
result type int
argument named n with type int
A Second OCaml Program
deconstruct the value n using matching
42
sumTo8.ml:
paZttern
(* sum the numbers from 0 to n
precondition: n must be a natural number
*)
let rec sumTo (n:int) : int =
match n with
0 -> 0
| n -> n + sumTo (n-1)
let _ =
print_int (sumTo 8);
print_newline()
data to be deconstructed appears between
key words “match” and “with”
sumTo8.ml:
(* sum the numbers from 0 to n
precondition: n must be a natural number
*)
let rec sumTo (n:int) : int =
match n with
0 -> 0
| n -> n + sumTo (n-1)
let _ =
print_int (sumTo 8);
print_newline()
_
Each branch of the match statement constructs a result
sumTo8.ml:
44
A Second OCaml Program
(* sum the numbers from 0 to n
precondition: n must be a natural number
*)
let rec sumTo (n:int) : int =
match n with
0 -> 0
| n -> n + sumTo (n-1)
let _ =
print_int (sumTo 8);
print_newline()
construct the result 0
construct
a result using a recursive
call to sumTo
45
sumTo8.ml:
A Second OCaml Program
(* sum the numbers from 0 to n
precondition: n must be a natural number
*)
let rec sumTo (n:int) : int =
match n with
0 -> 0
| n -> n + sumTo (n-1)
let _ =
print_int (sumTo 8);
print_newline()
print the result of calling sumTo on 8
print a new line
Expressions, Values, Simple Types
specify computations
Both are valid in OCaml, but different
TopHat Q7-Q9
Type Checking Basis
Type Checking
• Every value has a type and so does every expression
• We write (e : t) to say that expression e has type t. eg:
6
2 : int “hello” : string 2+2:int “Isay”^”hello”:string
Type Checking Rules
• You can always start up the OCaml interpreter to find out a type of a simple expression:
18
$ ocaml
Objective Caml Version 3.12.0
#
Type Checking Rules
• You can always start up the OCaml interpreter to find out a type of a simple expression:
19
$ ocaml
Objective Caml Version 3.12.0
# 3 + 1;;
Type Checking Rules
• You can always start up the OCaml interpreter to find out a type of a simple expression:
press return and you find out the type and the value
20
$ ocaml
Objective Caml Version 3.12.0
# 3 + 1;;
– : int = 4 #
Type Checking Rules
• You can always start up the OCaml interpreter to find out a type of a simple expression:
press return and you find out the type and the value
21
$ ocaml
Objective Caml Version 3.12.0
# 3 + 1;;
– : int = 4
# “hello ” ^ “world”;;
– : string = “hello world” #
Type Checking Rules
• You can always start up the OCaml interpreter to find out a type of a simple expression:
22
$ ocaml
Objective Caml Version 3.12.0
# 3 + 1;;
– : int = 4
# “hello ” ^ “world”;;
– : string = “hello world” # #quit;;
$
Suppose we have an expression of the shape:
e1 + e2
How can we check if it has the type int?
Suppose we have an expression of the shape:
e1 ^ e2
How can we check if it has the type string?