Begin at the beginning

Exec-time
Dynamic
Expressions (Syntax)
Compile-time
Static

Values (Semantics)

Types

1. Programmer enters expression

2. ML checks if expression is well-typed

Using a precise set of rules, ML tries to find a unique

type for the expression meaningful type for the expr

3. ML evaluates expression to compute value

Of the same type found in step 2

Side note: Tail Recursion

let fact n =
if n <= 0 then 1
else n * fact (n 1)

Tail recursion: for

each recursive call,
the value of the
recursive call is
immediately
returned

Side note: Tail Recursion

let rec fact n =
if n <= 0 then 1
else n * fact (n 1)

let rec fact_tr n res =

if n <= 0 then res
else fact_tr (n 1) (n*res)
let fact n = fact_tr n 1

Base Types

Base Type: int

Expressions built from sub-expressions

Types computed from types of sub-expressions
Values computed from values of sub-expressions

Base Type: int

2;

i:int

i )i

2+3;

e1 + e2

e1:int e2:int
e1+e2:int

e1)v1 e2)v2
e1+e2)v1+v2

7-4;

e1 - e2

e1:int e2:int
e1-e2:int

e1)v1 e2)v2
e1-e2)v1-v2

(2+3)*(7-4);

15

e1 * e2

e1:int e2:int
e1 * e2:int

e1)v1 e2)v2
e1*e2)v1*v2

Expressions built from sub-expressions

Types computed from types of sub-expressions
Values computed from values of sub-expressions

Base Type: float

2.0

2.0

r:float

r )r

2.0 +.3.0

5.0

e1 +. e2

e1:float e1:float
e1+.e2:float

7.0 . 4.0

3.0

e1 -. e2

e1:float e2:float e1)v1 e2)v2

e1-.e2:float
e1-.e2)v1-.v2

1.66.. e1 /. e2

e1:float e2:float e1)v1 e2)v2

e1/.e2:float
e1/.e2)v1/.v2

(2.0 +. 3.0) /.
(7.0 -. 4.0)

e1)v1 e2)v2
e1+.e2)v1+.v2

Expressions built from sub-expressions

Types computed from types of sub-expressions
Values computed from values of sub-expressions

Base Type: string

ab

ab ^ cd

ab

abcd

e1^e2

s:string

s )s

e1:string e2:string e1)v1 e2)v2

e1^e2:string
e1^e2)v1^v2

Expressions built from sub-expressions

Types computed from types of sub-expressions
Values computed from values of sub-expressions

Base Type: bool

true

true

b:bool

b )b

2 < 3

true

e1 < e2

e1:int e1:int
e1 < e2:bool

e1)v1 e2)v2
e1<e2 ) v1<v2

not(2<3)

false

not e

e : bool
not e : bool

e
)
v
not e ) not v

e1 = e2

e1:T e2:T
e1=e2 : bool

e1)v1 e2)v2
e1=e2 ) v1=v2

e1 && e2

e1:bool e2:bool
e1&&e2:bool

e1)v1 e2)v2
e1&&e2) v1 && v2

(ab=cd)
not (2<3)
&&
(ab=cd)

false

false

Base Type: bool

Equality testing is built-in for all expr,values,types
but compared expressions must have same type

except for ?
function values why ?
(ab=cd)

false

e1 = e2

e1:T e2:T
e1=e2 : bool

e1)v1 e2)v2
e1=e2 ) v1=v2

Type Errors
pq ^ 9;

e1:string e2:string
e1^e2:string

(2 + a);

e1:int e2:int
e1 + e2 : int

Expressions built from sub-expressions

Types computed from types of sub-expression
If a sub-expression is not well-typed then whole
expression is not well-typed
0 * (2 + a);

Complex types: Tuples

(2+2 , 7>8);

(4,false)

int * bool

Complex types: Tuples

(2+2 , 7>8);

(4,false)

int * bool

e1:T1 e2:T2
(e1,e2) : T1 * T2

e1)v1 e2)v2
(e1,e2)) (v1,v2)

Complex types: Tuples

Can be of any fixed size
(9-3,ab^cd,7>8)

(6, abcd, false)

(int * string * bool)

e1:T1 e2:T2

en: Tn
(e1,e2,,en) : T1 * T2* * Tn

e1)v1 e2)v2 en ) vn
(e1,e2,,en)) (v1,v2,,vn)

Elements can have different types

Tuples can be nested in other tuples

Complex types: Records

{name=sarah ;
age=31;
pass=false}

{ name : string, age : int, pass : bool}

Records are tuples with named elements

31

int

{age=31;name=sarah;pass=false}.age

31

int

{age=31;name=sarah;pass=false}.pass

false

bool

{name=sarah;age=31;pass=false}.age

But wait
All evaluation rules look like:
e1)v1 e2)v2
e1 OP e2 ) v1 OP v2

Complex types: Lists

[1+1;2+2;3+3;4+4]

[2;4;6;8]

int list

[a;b;c^d];

[a;b;cd]

string list

[(1;a^b);(3+4,c)];

[(1,ab);(7,c)]

(int*string) list

[[1];[2;3];[4;5;6]];

[[1];[2;3];[4;5;6]];

(int list) list

Unbounded size
Can have lists of anything (e.g. lists of lists)

Complex types: Lists

Complex types: Lists

[]
[e1;e2;e3;]

[]:a list

[] ) []

e1:T e2: T e3: T

e1)v1 e2)v2 e3)v3
[e1;e2;e3;] : T list
[e1;e2;] ) [v1;v2;]

All elements have the same type

[1; pq]

Complex types: list ..construct

Complex types: list ..construct

Cons operator

1::[2;3] [1;2;3]
int list

e1:T e2: T list

e1::e2 : T list

e1)v1 e2 ) v2
e1::e2 ) v1::v2

1::[b; cd];
Can only cons element to a list of same type

Complex types: list construct

Append operator

[1;2]@[3;4] [1;2;3;4]
int list

e1:T list e2: T list

e1@e2 : T list

e1)v1 e2 ) v2
e1@e2 ) v1@v2

1@[b; cd];
[1]@[b; cd];

Can only append lists of the same type

Complex types: list deconstruct

Reading the elements of a list:
Two operators: hd (head) and tl (tail)
[1;2;3;4;5]

hd [1;2;3;4;5] 1

[2;3;4;5]

tl [1;2;3;4;5]

int

[a;b; cd]

hd [a;b;cd]

int list

tl [a;b;cd]

[b; cd]

string

[(1,a);(7,c)]

hd [(1,a);(7,c)](1,a) tl [(1,a);(7,c)] [(7; c)]

Int * string

[[];[1;2;3];[4;5]]

string list

hd [[];[1;2;3];4;5]

int list

(int * string) list

tl [[];[1;2;3];4;5]

[2;3;4;5]
int list list

List: Heads and Tails

List: Heads and Tails

Head
Tail

e :T list
hd e : T

e )v1::v2
hd e ) v1

e :T list
tl e : T list

e ) v1::v2
tl e ) v2

(hd [[];[1;2;3]]) = (hd [[];[a]])

int list

e1:T e2:T
e1=e2 : bool

string list

Recap
Exec-time
Dynamic
Expressions (Syntax)
Compile-time
Static

Values (Semantics)

Types

1. Programmer enters expression

2. ML checks if expression is well-typed

Using a precise set of rules, ML tries to find a unique

type for the expression meaningful type for the expr

3. ML evaluates expression to compute value

Of the same type found in step 2

Recap

Integers: +,-,*
floats: +,-,*
Booleans: =,<, andalso, orelse, not
Strings: ^

Tuples, Records: #i
Fixed number of values, of different types

Lists:

::,@,hd,tl,null

Unbounded number of values, of same type

If-then-else expressions
5

if (1 < 2) then 5 else 10

int

if (1 < 2) then [ab,cd] else [x]

[ab,cd]
string list

If-then-else is also an expression!

Can use any expression in then, else branch
if e1 then e2 else e3

If-then-else expressions
5

if (1 < 2) then 5 else 10

int

if (1 < 2) then [ab,cd] else [x]

[ab,cd]
string list

If-then-else is also an expression!

Can use any expression in then, else branch
if e1 then e2 else e3
e1

: bool
e2: T
e3: T
if e1 then e2 else e3 : T

e1 ) true
e2 ) v2
if e1 then e2 else e3 ) v2

e1 ) false
e3 ) v3
if e1 then e2 else e3 ) v3

If-then-else expressions
if (1 < 2) then [1;2] else 5
if false then [1;2] else 5

then-subexp, else-subexp must have same type!

which is the type of resulting expression

e1

: bool
e2: T
e3: T
if e1 then e2 else e3 : T

If-then-else expressions
e1

: bool
e2: T
e3: T
if e1 then e2 else e3 : T

Then-subexp, Else-subexp must have same type!

Equals type of resulting expression
if 1>2 then [1,2] else [] []

if 1<2 then [] else [a] []

int list

string list

(if 1>2 then [1,2] else [])=(if 1<2 then [] else [a])

Next: Variables

Variables and Bindings

Q: How to use variables in ML ?
Q: How to assign to a variable ?
# let x = 2+2;;
val x : int = 4

let x = e;;
Bind the value of expression e
to the variable

Variables and Bindings

# let
val x
# let
val y
# let
val z

x
:
y
:
z
:

= 2+2;;
int = 4
= x * x * x;;
int = 64
= [x;y;x+y];;
int list = [4;64;68]

Later declared expressions can use

Most recent bound value used for evaluation

Sounds like C/Java ?

NO!

Environments (Phone Book)

How ML deals with variables
Variables = names
Values = phone number

x
y
z
x

4 : int
64 : int
[4;64;68] : int list
8 : int

Environments and Evaluation

ML begins in a top-level environment
Some names bound

let x = e;;
ML program = Sequence of variable bindings

Program evaluated by evaluating bindings in order

1. Evaluate expr e in current env to get value v : t
2. Extend env to bind x to v : t
(Repeat with next binding)

Environments
Phone book
Variables = names
Values = phone number
1. Evaluate:
Find and use most recent value of variable

2. Extend:
Add new binding at end of phone book

Example
# let x = 2+2;;
val x : int = 4

4 : int

# let y = x * x * x;;
val y : int = 64
# let z = [x;y;x+y];;
val z : int list = [4;64;68]
# let x = x + x ;;
val x : int = 8

New binding!

4 : int
64 : int

x
y

4 : int
64 : int
[4;64;68] : int list

x
y
z

x
y
z
x

4 : int
64 : int
[4;64;68] : int list
8 : int

Environments
1. Evaluate: Use most recent bound value of var
2. Extend: Add new binding at end

How is this different from C/Javas store ?

# let x = 2+2;;
val x : int = 4
# let f = fun y -> x + y;
val f : int -> int = fn
# let x = x + x ;
val x : int = 8
# f 0;
val it : int = 4

4 : int

x
f

4 : int
fn <code,

>: int->int

New binding:
No change or mutation
Old binding frozen in f

Environments
1. Evaluate: Use most recent bound value of var
2. Extend: Add new binding at end

How is this different from C/Javas store ?

# let x = 2+2;;
val x : int = 4
# let f = fun y -> x + y;
val f : int -> int = fn
# let x = x + x ;
val x : int = 8
# f 0;
val it : int = 4

4 : int

4 : int
fn <code,

x
f

>: int->int

4 : int

fn <code,

8 : int

>: int->int

Environments
1. Evaluate: Use most recent bound value of var
2. Extend: Add new binding at end

How is this different from C/Javas store ?

# let x = 2+2;;
val x : int = 4
# let f = fun y -> x + y;
val f : int -> int = fn
# let x = x + x ;
val x : int = 8
# f 0;
val it : int = 4

Binding used to eval (f )

4 : int

fn <code,

8 : int

>: int->int

Binding for subsequent x

Cannot change the world

Cannot assign to variables
Can extend the env by adding a fresh binding
Does not affect previous uses of variable
Environment at fun declaration frozen inside fun value
Frozen env used to evaluate application (f )
Q: Why is this a good thing ?
# let x = 2+2;;
val x : int = 4
# let f = fun y -> x + y;;
val f : int -> int = fn
# let x = x + x ;;
val x : int = 8;
# f 0;;
val it : int = 4

Binding used to eval (f )

x
f

4 : int
fn <code,

8 : int

>: int->int

Binding for subsequent x

Cannot change the world

Q: Why is this a good thing ?
A: Function behavior frozen at declaration

Nothing entered afterwards affects function

Same inputs always produce same outputs
Localizes debugging
Localizes reasoning about the program
No sharing means no evil aliasing

Examples of no sharing
Remember: No addresses, no sharing.
Each variable is bound to a fresh instance of a value

Tuples, Lists
Efficient implementation without sharing ?
There is sharing and pointers but hidden from you
Compilers job is to optimize code
Efficiently implement these no-sharing semantics
Your job is to use the simplified semantics
Write correct, cleaner, readable, extendable systems

Recap: Environments
Phone book
Variables = names
Values = phone number
1. Evaluate:
Find and use most recent value of variable

2. Extend: let x = e ;;
Add new binding at end of phone book

Next: Functions
Values

Expressions

Types

Functions

expr

Functions are values, can bind using let

let fname = fun x -> e ;;

Problem: Cant define recursive functions !
fname is bound after computing rhs value
no (or old) binding for occurences of fname inside e

let rec fname x = e ;;

Occurences of fname inside e bound to this definition

let rec fac x = if x<=1 then 1 else x*fac (x-1)

Functions

Type

Functions

Type

e1 : T2 -> T
e1 e2 : T

e2: T2

Functions

Values

Two questions about function values:

What is the value:
1. of a function ?

2. of a function application (call) ?

(e1 e2)

Functions

Values

Two questions about function values:

What is the value:
1. of a function ?

2. of a function application (call) ?

(e1 e2)

Values of functions: Closures

Body expression not evaluated until application
but type-checking takes place at compile time
i.e. when function is defined

Function value =
<code + environment at definition>
closure
# let x = 2+2;;
val x : int = 4
# let f = fun y -> x + y;;
val f : int -> int = fn
# let x = x + x ;;
val x : int = 8
# f 0;;
val it : int = 4

Binding used to eval (f )

x

4 : int

fn <code,

8 : int

>: int->int

Binding for subsequent x

Values of function application

Application: fancy word for call
(e1 e2)

apply the argument e2 to the (function) e1

Application Value:
1. Evaluate e1 in current env to get (function) v1

v1 is code + env
code is (formal x + body e) , env is E

2. Evaluate e2 in current env to get (argument) v2

3. Evaluate body e in env E extended by binding x to v2

Example 1
let x = 1;;
let f y = x + y;;
let x = 2;;
let y = 3;;
f (x + y);;

Example 1
let x = 1;;
let f y = x + y;;
let x = 2;;
let y = 3;;
f (x + y);;

Example 2
let x = 1;;
let f y =
let x = 2 in
fun z -> x + y + z
;;
let x = 100;;
let g =(f 4);;
let y = 100;;
(g 1);;

Example 2
let x = 1;;
let f y =
let x = 2 in
fun z -> x + y + z
;;
let x = 100;;
let g = (f 4);;
let y = 100;;
(g 1);;

Example 3
let f g =
let x = 0 in
g 2
;;
let x = 100;;

let h y = x + y;;
f h;;

Static/Lexical Scoping
For each occurrence of a variable,
Unique place in program text where variable defined
Most recent binding in environment

Static/Lexical: Determined from the program text

Without executing the programy

Very useful for readability, debugging:

Dont have to figure out where a variable got assigned
Unique, statically known definition for each occurrence

Alternative: dynamic scoping

let x = 100
let f y = x + y
let g x = f 0
let z = g 0
(* value of z? *)