Simple Data
Simple Data
1
slides copyright 2017, 2018, 2019, 2020
Author David Walker, updated by Amy Felty
permission granted to reuse these slides for non-commercial educational purposes
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
Why is the mathematical variable so important?
The mathematician says:
“Let x be some integer, we define a polynomial over x …”
5
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!
6
OCAML BASICS:
LET DECLARATIONS
7
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)
8
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:
• We write this one:
(2 + 3) * (2 + 3)
let x = 2 + 3 in
x * x
9
A Few More Let Expressions
let x = 2 in
let squared = x * x in
let cubed = x * squared in
squared * cubed
10
A Few More Let Expressions
let a = “a” in
let b = “b” in
let as = a ^ a ^ a in
let bs = b ^ b ^ b in
as ^ bs
let x = 2 in
let squared = x * x in
let cubed = x * squared in
squared * cubed
11
Abstraction & Abbreviation
• Two kinds of let:
let … in … is an expression that
can appear inside any other expression
The scope of x does not extend outside
the enclosing “in”
let x = 2 + 3
let y = x + 17 / x
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)
if tuesday() then
let x = 2 + 3 in
x + x
else
0
12
OCaml for the Skeptical – Let
Let Expressions
https://www2.lib.uchicago.edu/keith/ocaml-class/definitions.html
https://www.cs.cornell.edu/courses/cs3110/2019sp/textbook/basics/let_expressions.html
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
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
It does not
matter what
I write next.
add_three
will always
add 3!
14
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
let x = 4
let add_four (y:int) : int = y + x
a distinct
variable that
“happens to
be spelled the
same”
15
Binding Variables to Values
• Since the 2 variables (both happened to be named x) are
actually different, unconnected things, we can rename them
let x = 3
let add_three (y:int) : int = y + x
let zzz = 4
let add_four (y:int) : int = y + zzz
rename x
to zzz
if you want
to, replacing
its uses
16
Binding Variables to Values
• OCaml is a statically scoped (or lexically scoped) language
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
17
How do let expressions operate?
let x = 2 + 1 in x * x
18
How do let expressions operate?
let x = 2 + 1 in x * x
–>
let x = 3 in x * x
19
How do let expressions operate?
let x = 2 + 1 in x * x
–>
let x = 3 in x * x
–>
3 * 3
substitute
3 for x
20
How do let expressions operate?
let x = 2 + 1 in x * x
–>
let x = 3 in x * x
–>
3 * 3
–>
9
substitute
3 for x
21
How do let expressions operate?
let x = 2 + 1 in x * x
–>
let x = 3 in x * x
–>
3 * 3
–>
9
substitute
3 for x
Note: e1 –> e2
means e1 evaluates
to e2 in one step
22
Another Example
let x = 2 in
let y = x + x in
y * x
23
Another Example
let x = 2 in
let
y *
y
x
= x + x in
–>
substitute
2 for x
let y = 2 + 2 in
y * 2
24
Another Example
let x = 2 in
let y = x + x in
y * x
–>
–>
substitute
2 for x
let y = 2 + 2 in
y * 2
inlet y = 4
y * 2
25
Another Example
let x = 2 in
let y = x + x in
y * x
–>
–>
–>
substitute
2 for x
let y = 2 + 2 in
y * 2
inlet y = 4
y * 2
4 * 2
substitute
4 for y
26
Another Example
let x = 2 in
let
y *
y
x
= x + x in
–>
–>
–>
substitute
2 for x
let
y *
y
2
= 2 + 2 in
let y = 4 in
y * 2
4 * 2
–>
8
substitute
4 for y
Moral: Let
operates by
substituting
computed values
for variables
27
OCAML BASICS:
TYPE CHECKING AGAIN
29
Back to Let Expressions … Typing
let x = e1 in
e2
overall expression
takes on the type of e2
x given type of e1 for use in e2
30
Back to Let Expressions … Typing
let x = e1 in
e2
x given type of e1 for use in e2
let x = 3 + 4 in
string_of_int x
overall expression
takes on the type of e2
x has type int
for use inside the
let body
overall expression
has type string
31
OCAML BASICS:
FUNCTIONS
32
let add_one (x:int) : int = 1 + x
Defining functions
33
Defining functions
function name
argument name
type of argument
type of result
expression
that computes
value produced
by function
let keyword
let add_one (x:int) : int = 1 + x
Note: recursive functions begin with “let rec”
34
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
35
Defining functions
• Nonrecursive functions:
• With a local definition:
let add_one (x:int) : int = 1 + x
let add_two (x:int) : int = add_one (add_one x)
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 =
let add_one x = 1 + x in
add_one (add_one x)
36
Types for Functions
Some 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
function with two arguments
Types for functions:
add_one : int -> int
add_two : int -> int
add : int -> int -> int
37
val add_two : int -> int =
Rule for type-checking functions
Example:
add_one : int -> int
3 + 4 : int
add_one (3 + 4) : int
If a function f : T1 -> T2
and an argument e : T1
then f e : T2
General Rule:
38
Rule for type-checking functions
• Recall the type of add:
Definition:
let add (x:int) (y:int) : int =
x + y
add : int -> int -> int
Type:
39
Rule for type-checking functions
• Recall the type of add:
Definition:
let add (x:int) (y:int) : int =
x + y
add : int -> int -> int
Type:
add : int -> (int -> int)
Same as:
40
Rule for type-checking functions
add : int -> int -> int
3 + 4 : int
add (3 + 4) : ???
If a function f : T1 -> T2
and an argument e : T1
then f e : T2
General Rule:
Example:
A -> B -> C
same as:
A -> (B -> C)
41
Rule for type-checking functions
Example:
add : int -> (int -> int)
3 + 4 : int
add (3 + 4) :
General Rule:
42
A -> B -> C
same as:
A -> (B -> C)
If a function f : T1 -> T2
and an argument e : T1
then f e : T2
Rule for type-checking functions
add : int -> (int -> int)
3 + 4 : int
add (3 + 4) : int -> int
General Rule:
Example:
43
If a function f : T1 -> T2
and an argument e : T1
then f e : T2
A -> B -> C
same as:
A -> (B -> C)
Rule for type-checking functions
add : int -> int -> int
3 + 4 : int
add (3 + 4) : int -> int
(add (3 + 4)) 7 : int
General Rule:
Example:
44
If a function f : T1 -> T2
and an argument e : T1
then f e : T2
A -> B -> C
same as:
A -> (B -> C)
Rule for type-checking functions
add : int -> int -> int
3 + 4 : int
add (3 + 4) : int -> int
add (3 + 4) 7 : int
General Rule:
Example:
45
If a function f : T1 -> T2
and an argument e : T1
then f e : T2
A -> B -> C
same as:
A -> (B -> C)
Rule for type-checking functions
let munge (b:bool) (x:int) : ?? =
if not b then
string_of_int x
else
“hello”
;;
let y = 17;;
Example:
munge (y > 17) : ??
munge
f :
true
??
(f (munge false 3)) : ??
munge
g :
true
??
(g munge) : ??
46
Rule for type-checking functions
let munge (b:bool) (x:int) : ?? =
if not b then
string_of_int x
else
“hello”
;;
let y = 17;;
Example:
munge (y > 17) : ??
munge
f :
true
??
(f (munge false 3)) : ??
munge
g :
true
??
(g munge) : ??
46
string
munge : bool -> int -> string
Rule for type-checking functions
let munge (b:bool) (x:int) : ?? =
if not b then
string_of_int x
else
“hello”
;;
let y = 17;;
Example:
munge (y > 17) : ??
munge true (f (munge false 3)) : ??
f : string -> int
munge true (g munge) : ??
g : (bool -> int -> string) -> int
47
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
f a1 : B -> C -> D -> E -> F (if a1 : A)
f a1 a2 : C -> D -> E -> F (if a2 : B)
f a1 a2 a3 : D -> E -> F (if a3 : C)
f a1 a2 a3 a4 a5 : F (if a4 : D and a5 : E)
48
OUR FIRST* COMPLEX DATA STRUCTURE!
THE TUPLE
* it is really our second complex data structure since functions
are data structures too!
49
• A tuple is a fixed, finite, ordered collection of expressions
• Some examples with their types:
Tuples
(1, 2) : int * int
(“hello”, 7 + 3, true) : string * int * bool
(‘a’, (“hello”, “goodbye”)) : char * (string * string)
50
• To use a tuple, we extract its components
• General case:
Tuples
let (id1, id2, …, idn) = e1 in e2
• An example:
let (x,y) = (2,4) in x + x + y
51
• To use a tuple, we extract its components
• General case:
Tuples
let (id1, id2, …, idn) = e1 in e2
• An example:
let (x,y) = (2,4) in x + x + y
–> 2 + 2 + 4
substitute!
52
• To use a tuple, we extract its components
• General case:
Tuples
let (id1, id2, …, idn) = e1 in e2
• An example:
let (x,y) = (2,4) in x + x + y
–> 2 + 2 + 4
–> 8
53
Rules for Typing Tuples
54
if e1 : t1 and e2 : t2
then (e1, e2) : t1 * t2
Rules for Typing Tuples
let (x1,x2) = e1 in
e2
if e1 : t1 * t2 then
x1 : t1 and x2 : t2
inside the expression e2
overall expression
takes on the type of e2
55
if e1 : t1 and e2 : t2
then (e1, e2) : t1 * t2
Distance between two points
c2 = a2 + b2 (x1, y1)
a
b
c
(x2, y2)
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
56
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)
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)
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
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
6. Clean up by identifying repeated patterns
• define and reuse helper functions
• your code should be elegant and easy to read
59
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
6. 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
Distance between two points
type point = float * float
a type abbreviation (x1, y1)
(x2, y2)
a
b
c
61
c2 = a2 + b2
Distance between two points
type point = float * float
let distance (p1:point) (p2:point) : float =
write down function name
argument names and types
(x1, y1)
(x2, y2)
a
b
c
62
c2 = a2 + b2
Distance between two points
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 =
(x1, y1)
(x2, y2)
a
b
cexamples
63
c2 = a2 + b2
Distance between two points
type point = float * float
let distance (p1:point) (p2:point) : float =
let (x1,y1) = p1 in
let (x2,y2) = p2 in
…
deconstruct
function inputs
(x1, y1)
(x2, y2)
a
b
c
64
c2 = a2 + b2
Distance between two points
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
(x1, y1)
(x2, y2)
a
b
c
65
c2 = a2 + b2
Distance between two points
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
(x1, y1)
(x2, y2)
a
b
c
66
c2 = a2 + b2
Distance between two points
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 dist1
2
= distance pt1 pt2
testing
(x1, y1)
(x2, y2)
a
b
c
67
c2 = a2 + b2
MORE TUPLES
68
Tuples
• Here’s a tuple with 2 fields:
(4.0, 5.0) : float * float
69
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
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
• Here’s a tuple with 4 fields:
(4.0, 5, “hello”, 55) : float * int * string * int
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
• Here’s a tuple with 0 fields:
() : unit
72
SUMMARY:
BASIC FUNCTIONAL PROGRAMMING
76
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
77