OCaml
The PL for the discerning hacker.
Hello.
I’m Zach, one of Sorin’s students.
[email protected]
ML Anatomy 101
ML Program = ?One
? ? Giant, Complex Expression
Controlling complexity is the essence of
computer programming.
B. Kerninghan
A complex system that works is invariably
found to have evolved from a simple
system that worked.
J. Gall
Building ML Programs
ML provides tools to control complexity
Build complex exprs from simple exprs PREV
Build complex types from simple types NOW
Building Types
1. basic (recap)
2. function
3. record
4. variant
5. demo
M.C. Escher’s Relativity
in LEGO
basic
Who cares about types anyway?
Every good programmer!
(not just old timers)
Types provide:
1. Documentation
2. Early bug warning system
3. Performance!
basic
Who cares about types anyway?
Even programmers without a type system!
I think it may just be a property of large systems
in dynamic languages, that eventually you end
up rewriting your own type system, and you sort
of do it badly.
-- Twitter
basic
Expression
Type
Kind of
Type
5
int
basic
“hello”
string
basic
(5, “hello”)
int * string
tuple
[1; 2; 3; 4]
int list
list
[ (1, 1) ; (2, 2) ; (3, 3) ] (int * int) list
tuple+list
more on tuples
Expression
Type
(5, (10, 15))
int * (int * int)
((5, 10), 15)
(int * int) * int
more on tuples
Expression
Type
(5, (10, 15))
int * (int * int)
((5, 10), 15)
(int * int) * int
( [ (1, 2); (3, 4); (5, 6) ]
, (“hello”, “india”)
, (5, “int”, (1, 2, 3))
)
more on tuples
Expression
Type
(5, (10, 15))
int * (int * int)
((5, 10), 15)
(int * int) * int
( [ (1, 2); (3, 4); (5, 6) ]
(int * int) list *
, (“hello”, “india”)
(string * string) *
, (5, “int”, (1, 2, 3))
(int * string * (int * int * int))
)
basic
Don’t know how it works ?
Try it in the toplevel !
Building Types
1. basic (recap)
2. function
3. record
4. variant
5. demo
M.C. Escher’s Relativity
in LEGO
function
A -> B
Type of a function which:
expects parameter of type A
produces a value of type B
Contract:
caller satisfies A
callee satisfies B
precondition
postcondition
function
let f x = x + 5
f: int -> int
let f x = “hello “ ^ x
f: string -> string
let f x = “number “ ^ (string_of_int x)
f: int -> string
let f x y = x * x + y * y
f: int -> int -> int
function
let f x y = 1 :: x :: y
f: int -> int list -> int list
let f x y z = [1] @ x @ [y + z]
f: int list -> int -> int -> int list
let rec f = f f
ERROR
polymorphic functions
Some functions work on many types:
let id x = x
id: ‘a -> ‘a
Takes a value of any type, call it ‘a
Returns a value of that type ‘a
polymorphic functions
let f a b = a
f: ‘a -> ‘b -> ‘a
let f a b = b
f: ‘a -> ‘b -> ‘b
let pipe x f = f x
f: ‘a -> (‘a -> ‘b) -> ‘b
let (|>) = pipe
“hello” |> id |> print_string
(print_string (id (“hello”)))
binary
infix
operator
polymorphic functions
let f g x = g x
f: (‘a -> ‘b) -> ‘a -> ‘b
let f g h x = g (h x)
f: (‘a -> ‘b) -> (‘c -> ‘a) -> ‘c -> ‘b
Building Types
1. basic (recap)
2. function
3. record
4. variant
5. demo
M.C. Escher’s Relativity
in LEGO
record
type RT =
{ NM1 : T1
; ...
; NMN : TN
}
Like a tuple, but refer to members by name.
record
type person =
{ name : string
; age : int
; hair : string
; job : string
}
making a record value
let pres =
{ name = “Obama”
; age = 49
; hair = “black”
; job = “president”
}
updating a record value
let pres =
{ name = “Obama”
; age = 49
; hair = “black”
; job = “president”
}
let pres’ =
{pres with hair = “gray” }
updating a record value
let year_older p =
if p.age > 45 then
{ p with
age = p.age + 1,
hair = “gray” }
else
{ p with age = p.age + 1 }
year_older: person -> person
Building Types
1. basic (recap)
2. function
3. record
4. variant
5. demo
M.C. Escher’s Relativity
in LEGO
variant
type VT =
| C1 of T1
| ...
| CN of TN
value of type VT can
only be constructed
with one of these
C1 to CN are “constructors”
Ci like function from Ti to VT
variant
type pet =
| Dog of string
| Cat of string
| Fish of string
Value of type pet constructed with one of:
Dog, Cat, Fish
Each takes a string and returns a pet
variant values
type pet =
| Dog of string
| Cat of string
| Fish of string
let d = Dog “spot”
let c = Cat “whiskers”
let f = Fish “nemo”
matching variant values
let name pet =
match pet with
| Dog nm -> nm
| Cat nm -> nm
| Fish nm -> nm
let d = Dog “sparky” in
name d
matching variant values
let says pet =
match pet with
| Dog _ -> “woof”
| Cat _ -> “meow”
| Fish _ -> “bubble bubble”
let c = Cat “walter” in
says c
variant
type fuel_level =
| Empty
| Middle
| Full
type vehicle =
| Car of int * fuel_level
| Tank of int * fuel_level
| Boat of int * fuel_level
matching variant values
let miles v =
match v with
| Car (m, _) -> m
| Tank (m, _) -> m
| Boat (m, -) -> m
updating variant values
let reduce f =
match f with
| Empty -> Empty
| Middle -> Empty
| Full
-> Middle
let drive v =
match v with
| Car (m, f) -> Car (m, reduce f)
| Tank (m, f) -> Tank (m, reduce f)
| Boat (m, f) -> Boat (m, reduce f)
updating variant values
let refill v =
match v with
| Car (m, f) -> Car (m, Full)
| Tank (m, f) -> Tank (m, Full)
| Boat (m, f) -> Boat (m, Full)
recursive variant
type expr =
| Val of int
| Add of expr * expr
| Sub of expr * expr
| Mul of expr * expr
let e1 = Val 5
let e2 = Add (e1, e1)
let e3 = Mul (e2, e1)
recursive variant
let rec eval e =
recursive variant
let rec
match
| Val
| Add
| Sub
| Mul
eval e
e with
i
(l, r)
(l, r)
(l, r)
=
->
->
->
->
i
(eval l) + (eval r)
(eval l) - (eval r)
(eval l) * (eval r)
mutual recursion
let rec
match
| Val
| Add
| Sub
| Mul
expr_dot e =
e with
i
-> string_of_int
(l, r) -> (aux "add" l)
(l, r) -> (aux "sub" l)
(l, r) -> (aux "mul" l)
and aux
match
| Val
| Add
| Sub
| Mul
p
e
i
_
_
_
e =
with
-> p
-> p
-> p
-> p
^
^
^
^
"
"
"
"
->
->
->
->
i
^ (aux "add" r)
^ (aux "sub" r)
^ (aux "mul" r)
" ^ string_of_int i
add;\n" ^ (expr_dot
sub;\n" ^ (expr_dot
mul;\n" ^ (expr_dot
^ ";\n"
e)
e)
e)
Pattern Matching: a PL Masterpiece
match is one of ML’s very best features
simultaneous test / extract / bind
auto checks any missed cases
leads to compact, readable code
Building Types
1. basic (recap)
2. function
3. record
4. variant
5. demo
M.C. Escher’s Relativity
in LEGO
demo
Conway’s Game of Life
demo
Conway’s Game of Life
code at:
http://github.com/ztatlock/simple-life
demo
OCaml in the “real world” at JaneStreet
http://ocaml.janestreet.com/
Check out their leader, Yaron Minsky
http://ocaml.janestreet.com/?q=node/82
Building Types
1. basic (recap)
2. function
3. record
4. variant
5. demo
M.C. Escher’s Relativity
in LEGO
Descargar

Slide 1