Simple Data
CSI 3120
Amy Felty University of Ottawa
slides copyright 2017, 2018 David Walker, Amy Felty permission granted to reuse these slides for non-commercial educational purposes
1
What is the single most important mathematical concept ever developed in human history?
2
What is the single most important mathematical concept ever developed in human history?
An answer: The mathematical variable
3
What is the single most important mathematical concept ever developed in human history?
An answer: The mathematical variable (runner up: natural numbers/induction)
4
5 Why is the mathematical variable so important?
The mathematician says:
“Let x be some integer, we define a polynomial over x …”
6 Why is the mathematical variable so important?
The mathematician says:
“Let x be some integer, we define a polynomial over x …”
What is going on here? The mathematician has separated a definition (of x) from its use (in the polynomial).
This is the most primitive kind of abstraction (x is some integer) Abstraction is the key to controlling complexity and without it,
modern mathematics, science, and computation would not exist. It allows reuse of ideas, theorems … functions and programs!
OCAML BASICS: LET DECLARATIONS
7
8
Abstraction
• Good programmers identify repeated patterns in their code and factor out the repetition into meaningful components
• In O’Caml, the most basic technique for factoring your code is to use let expressions
• Instead of writing this expression: (2 + 3) * (2 + 3)
Abstraction & Abbreviation
• Good programmers identify repeated patterns in their code and factor out the repetition into meaning components
• In O’Caml, the most basic technique for factoring your code is to use let expressions
• Instead of writing this expression: (2 + 3) * (2 + 3)
• We write this one:
9
let x = 2 + 3 in x*x
10
A Few More Let Expressions
let x = 2 in
let squared = x * x in
let cubed = x * squared in
squared * cubed
A Few More Let Expressions
11
let x = 2 in
let squared = x * x in
let cubed = x * squared in
squared * cubed
let a = “a” in
let b = “b” in
let as = a ^ a ^ a in let bs = b ^ b ^ b in as ^ bs
12
Abstraction & Abbreviation • Two kinds of let:
if tuesday() then
let x = 2 + 3 in
x+x else
0
let x = 2 + 3
let y = x + 17 / x
let … in … is an expression that
can appear inside any other expression
The scope of x does not extend outside the enclosing “in”
let … without “in” is a top-level declaration
Variables x and y may be exported; used by other modules
(Don’t need ;; if another let comes next; do need it if the next top-level declaration is an expression)
13
Binding Variables to Values
• Each OCaml variable is bound to 1 value
• The value to which a variable is bound to never changes!
let x = 3
let add_three (y:int) : int = y + x
Binding Variables to Values
• Each OCaml variable is bound to 1 value
• The value to which a variable is bound to never changes!
It does not matter what I write next. add_three will always add 3!
14
let x = 3
let add_three (y:int) : int = y + x
Binding Variables to Values
• Each OCaml variable is bound to 1 value
• The value a variable is bound to never changes!
15
let x = 3
let add_three (y:int) : int = y + x let x = 4
let add_four (y:int) : int = y + x
a distinct variable that “happens to be spelled the same”
Binding Variables to Values
• Since the 2 variables (both happened to be named x) are actually different, unconnected things, we can rename them
16
let x = 3
let add_three (y:int) : int = y + x let zzz = 4
let add_four (y:int) : int = y + zzz
let add_seven (y:int) : int =
add_three (add_four y)
rename x
to zzz
if you want to, replacing its uses
Binding Variables to Values
• Each OCaml variable is bound to 1 value
• OCaml is a statically scoped (or lexically scoped) language
17
let x = 3
let add_three (y:int) : int = y + x let x = 4
let add_four (y:int) : int = y + x
let add_seven (y:int) : int =
add_three (add_four y)
we can use add_three without worrying about the second definition of x
18
How do let expressions operate?
let x = 2 + 1 in x * x
How do let expressions operate?
–>
19
let x = 2 + 1 in x * x
let x = 3 in x * x
20
How do let expressions operate?
–>
substitute –> 3 for x
let x = 2 + 1 in x * x
let x = 3 in x * x
3*3
21
How do let expressions operate?
–>
substitute –> 3 for x
–>
let x = 2 + 1 in x * x
let x = 3 in x * x
3*3
9
22
How do let expressions operate?
–>
substitute –> 3 for x
–>
let x = 2 + 1 in x * x
let x = 3 in x * x
3*3
Note: e1 –> e2 means e1 evaluates to e2 in one step
9
23
Another Example
let x = 2 in
let y = x + x in y*x
24
Another Example
substitute 2 for x
let x = 2 in
let y = x + x in y*x
let y = 2 + 2 in y*2
–>
25
Another Example
substitute 2 for x
let x = 2 in
let y = x + x in y*x
let y = 2 + 2 in y*2
–>
–>
let y = 4 in y*2
Another Example
substitute 2 for x
26
let x = 2 in
let y = x + x in y*x
let y = 2 + 2 in y*2
–>
–>
–>
substitute 4 for y
let y = 4 in y*2
4*2
27
Another Example
substitute 2 for x
let x = 2 in
let y = x + x in y*x
Moral: Let operates by substituting computed values for variables
let y = 2 + 2 in y*2
–>
–>
substitute 4 for y
let y = 4 in y*2
4*2
8
–> –>
OCAML BASICS:
TYPE CHECKING AGAIN
29
30
Back to Let Expressions … Typing
x given type of e1 for use in e2
let x = e1 in e2
overall expression takes on the type of e2
Back to Let Expressions … Typing
x given type of e1 for use in e2
31
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
OCAML BASICS: FUNCTIONS
32
33
Defining functions
let add_one (x:int) : int = 1 + x
let keyword
Defining functions
34
let add_one (x:int) : int = 1 + x
function name
argument name
type of result
type of argument
expression
that computes value produced by function
Note: recursive functions begin with “let rec”
35
Defining functions • Nonrecursive functions:
let add_one (x:int) : int = 1 + x
let add_two (x:int) : int = add_one (add_one x)
definition of add_one must come before use
36
Defining functions • Nonrecursive functions:
let add_one (x:int) : int = 1 + x
let add_two (x:int) : int = add_one (add_one x)
• With a local definition:
local function definition hidden from clients
Note that there are no types. OCaml figures them out.
Good style: types on top-level definitions
let add_two’ (x:int) : int = add_one (add_one x)
let add_one x = 1 + x in
37
Some functions:
Types for Functions
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 functions:
function with two arguments
add_one : int -> int
add_two : int -> int
add : int -> int -> int
Rule for type-checking functions
General Rule:
Example:
38
If a function f : T1 -> T2 and an argument e : T1 then f e : T2
add_one : int -> int
3 + 4 : int
add_one (3 + 4) : int
39
Rule for type-checking functions • Recall the type of add:
Definition:
Type:
let add (x:int) (y:int) : int = x+y
add : int -> int -> int
40
Rule for type-checking functions • Recall the type of add:
Definition:
Type:
Same as:
let add (x:int) (y:int) : int = x+y
add : int -> int -> int
add : int -> (int -> int)
41
Rule for type-checking functions
General Rule:
A -> B -> C
same as:
A -> (B -> C)
If a function f : T1 -> T2 and an argument e : T1 then f e : T2
Example:
add : int -> int -> int
3 + 4 : int
add (3 + 4) : ???
42
Rule for type-checking functions
General Rule:
A -> B -> C
same as:
A -> (B -> C)
If a function f : T1 -> T2 and an argument e : T1 then f e : T2
Example:
add : int -> (int -> int)
3 + 4 : int
add (3 + 4) :
43
Rule for type-checking functions
General Rule:
A -> B -> C
same as:
A -> (B -> C)
If a function 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
44
Rule for type-checking functions
General Rule:
A -> B -> C
same as:
A -> (B -> C)
If a function 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
45
Rule for type-checking functions
General Rule:
A -> B -> C
same as:
A -> (B -> C)
If a function 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 functions
Example:
46
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 functions
Example:
47
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
48
One key thing to remember
• If you have a function f with a type like this:
A -> B -> C -> D -> E -> F
• Then each time 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)
OUR FIRST* COMPLEX DATA STRUCTURE! THE TUPLE
* it is really our second complex data structure since functions are data structures too!
49
50
Tuples
• A tuple is a fixed, finite, ordered collection 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:
51
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:
52
let (x,y) = (2,4) in x + x + y –> 2+2+4
substitute!
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 –> 2+2+4
–> 8
54
Rules for Typing Tuples
ife1:t1 ande2:t2 then (e1, e2) : t1 * t2
55
Rules for Typing Tuples
if e1 : t1 * t2 then
x1 : t1 and x2 : t2
inside the expression e2
ife1:t1 ande2:t2 then (e1, e2) : t1 * t2
let (x1,x2) = e1 in
e2
overall expression takes on the type of e2
56
Distance between two points
c2 =a2 +b2
a (x1, y1)
b c
Problem:
• A point is represented as a pair of floating point values.
• Write a function that takes in two points as arguments and returns the distance between them as a floating point number
(x2, y2)
57
Writing Functions Over Typed Data
Steps to writing functions over typed data:
1. Write down the function and argument names
2. Write down argument and result types
3. Write down some examples (in a comment)
58
Writing Functions Over Typed Data
Steps to writing functions over typed data:
1. Write down the function 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
59
Writing Functions Over Typed Data Steps to writing functions over typed data:
1.
2.
3.
4. 5. 6.
Write down the function 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 identifying repeated patterns
• define and reuse helper functions
• your code should be elegant and easy to read
Writing Functions Over Typed Data Steps to writing functions over typed data:
1.
2.
3.
4. 5. 6.
Write down the function 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 identifying repeated patterns
• define and reuse helper functions
• your code should be elegant and easy to read
Types help structure your thinking about how to write programs.
60
61
Distance between two points a type abbreviation
a (x1, y1)
b c
type point = float * float
(x2, y2)
Distance between two points
62
a (x1, y1)
b c
type point = float * float
let distance (p1:point) (p2:point) : float =
write down function name argument names and types
(x2, y2)
63
Distance between two points
examples
a (x1, y1)
b c
type point = float * float
(* distance (0.0,0.0) (0.0,1.0) == 1.0
* distance (0.0,0.0) (1.0,1.0) == sqrt(1.0 + 1.0) *
* from the picture:
* distance (x1,y1) (x2,y2) == sqrt(a^2 + b^2) *)
let distance (p1:point) (p2:point) : float =
(x2, y2)
Distance between two points
64
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 function inputs
(x2, y2)
Distance between two points
65
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 function results
notice operators on floats have a “.” in them
(x2, y2)
Distance between two points
66
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 functions to avoid repeated code
(x2, y2)
67
Distance between two points
a (x1, y1)
b c
type point = float * float
let distance (p1:point) (p2:point) : float =
let square x = x *. let (x1,y1) = p1 in let (x2,y2) = p2 in sqrt (square (x2 -.
let pt1 = (2.0,3.0) let pt2 = (0.0,1.0) let dist12 = distance
x in
x1) +. square (y2 -. y1))
pt1 pt2
(x2, y2)
testing
MORE TUPLES
68
69
Tuples • Here’s a tuple with 2 fields:
(4.0, 5.0) : float * float
70
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
71
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
72
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
SUMMARY:
BASIC FUNCTIONAL PROGRAMMING
76
77
Writing Functions Over Typed Data
Steps to writing functions over typed data:
1. Write down the function 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 identifying repeated patterns
For tuple types:
– when the input has type t1 * t2
• use let (x,y) = … to deconstruct – when the output has type t1 * t2
• use (e1, e2) to construct
We will see this paradigm repeat itself over and over