Comp 302
Brigitte Pientka • OCaml • Prof’s Website
Lecture 1 • 2017/09/12
 5 hw (25%), midterm (10%), final (65%)
 Office hours – McConnell Eng. 107N – Tue, Thu 11:30am – 12:30pm; Thu 4:00pm – 5:30pm
 Goals
 Introduce fundamental concepts – higherorder functions, statefull vs statefree, modelling objects & closures, exceptions to defer control, continuations to defer control, polymorphism, partial evaluation, lazy programming, etc
 Show ways to reason about programs – type checking, induction, operational semantics, QuickCheck, etc
 Introduce fundamental principles in programming language design
 Grammar & parsing, operation semantics & interpreters, type checking, polymorphism, subtyping
 Expose students to different way of thinking about problems
 Thorough notes for this class will be up on MyCourses each week
Lecture 2 • 2017/09/14
 Statically typed programs approximate runtime behaviour & analyze programs before executing them; help find & fix bugs before testing
 Functional languages are primarily expressed via functions They are firstclass (you may pass & return functions)
 Pure functional languages (eg Haskell) don’t allow any modifications for variables, and do not provide exceptions
 Not pure functions (eg OCaml) allows for other paradigms as well
 CallByValue – execute when instruction is reached
 Lazy – execute once it is needed to compute other instructions
 Keywords & Operators
 +, –, *, / are for (int, int) > int functions
 +., –., *., /. are for (float, float) > float functions
 in – keyword for using a variable locally
 When the same variable is recreated, it overshadows the previous one. It does not update the previous binding
Lecture 3 • 2017/09/15
 Tailrecursive functions are ones with nothing to do except return the final value. For such functions, saving its stack frame is redundant.

User defined data types: type suit= Clubs 
Spades 
Hearts 
Diamonds 
 Set; order doesn’t matter
 Passing Arguments
 At the same time (tuples): ‘a * ‘b, where ‘ denotes any value and * is used for creating tuple types
 One at a time: ‘a > ‘b > ‘c
 Currying: translating functions from passing one argument at a time to all at once; opposite is uncurrying
 Non recursive data types can be created like so:

type suit = Clubs 
Spades 
Hearts 
Diamonds 
 Clubs, Spades, Hearts, Diamonds are constructors
 Pattern matching is of the syntax
match [expr] with  [pattern] > [expr] ...
 An underscore (wild card) may be used as a pattern that accepts all inputs
Lecture 4 • 2017/09/19
 Recursive DataType
 type card = rank * suit

type hand = Empty 
Hand of card * hand 
 Hand is a constructor defined within hand through the keyword ‘of’
 A type ‘hand’ is either ‘Empty’ or a combination a card to an existing hand
 Types are defined with lower case, and constructors are capitalized
Lecture 5 • 2017/09/21
 Talked about lists. Up until now, the majority of our content is on syntax. I have made a page detailing some components here
Lecture 6 • 2017/09/22
 Worked on list recursion; see notes
 Induction
 Proof by structural induction on the list ‘l’
Lecture 7 • 2017/09/26
 Recursion examples; see next class
Lecture 8 • 2017/09/28
 Binary Tree

type ‘a tree = Empty 
Node of ‘a * ‘a tree * ‘a tree 
 Exercise – implement a function to verify that a tree is a binary search tree

In class code
```ocaml
(* Tree definition *)
type tree = Empty  Node of 'a * 'a tree * 'a tree
(*
Element insertion in a Binary Search Tree
Note that elements are Nodes containing a keyvalue pair
('a * 'b) > ('a * 'b) tree > ('a * 'b) tree
*)
let rec insert ((x, dx) as e) t = match t with
 Empty > Node (e, Empty, Empty)
 Node (((y, dy) as f), l, r) >
if x = y then Node (e, l, r)
else if x < y then Node (f, insert e l, r)
else Node (f, l, insert e r)
(*
Element lookup in a BST
Takes in the key and a tree, and returns the value if it exists
'a > '('a * 'b) tree > 'b option'
*)
let rec lookup x t = match t with
 Empty > None
 Node ((y, dy), l, r) >
if x = y then Some dy
else lookup x (if x < y then l else r)
(*
Collection function to convert a tree into a list with infix ordering
*)
let rec collect t = match t with
 Empty = []
 Node (x, l, r) > (collect l) @ [x] @ (collect r)
```
 Theorem: For all trees t, keys x, and data dx, lookup x (insert (x, dx) t) ⇒* Some dx
 Proof by structural induction
 Case t = Empty
 lookup x (insert (x, dx) Empty) ⇒ lookup x (Node ((x, dx), Empty, Empty) ⇒ Some dx
 Case t = Node ((y, dy), l, r)
 Induction Hypothesis 1 – For all x, dx, lookup x (insert (x, dx) l) ⇒* Some dx
 Induction Hypothesis 2 – For all x, dx, lookup x (insert (x, dx) r) ⇒* Some dx
 Show that insertion and lookup lead to the IH in all cases
Lecture 9 • 2017/09/29
 Higher order functions
 Programs can be short & compact
 Programs are reusable
 Functions are first class – can be passed as parameters and returned as a result

In class code
```ocaml
(*
Given function and range,
compute sum of given function applied to each number in given range
*)
let rec sum f (a, b) =
if a > b then 0
else f(a) + sum f(a + 1, b)
let sumInts (a, b) =
let id x = x in
sum id (a, b)
(* We may use anonymous functions *)
let sunSquare (a, b) = sum (fun x > x * x) (a b)
(* We may also declare functions outside and use pattern matching
functions take only one argument *)
(function 0 > 0  n > n + 1)
(* Which is equivalent to *)
(fun x > match x with 0 > 0  n > n + 1)
```
 We can define functions on the fly without naming them by using anonymous functions
Lecture 10 • 2017/10/03
 Currying
 Methods in languages like JavaScript are uncurried. (such as test(a, b, c)). All values need to be passed in at once, or the function cannot be called. The process of currying involves separating such inputs so that any number of them can be called to return a function needing only the remaining inputs (‘a > ‘b > ‘c)
Lecture 11 • 2017/10/05
 Lambda Calculus
 Simple language consisting of variables, functions (λx.t) & function application
 Can define all computable functions
 Boolean encoding
 T = λx.λy.x (keep first arg)
 F = λx.λy.y (keep second arg)
 Recall currying: let curry f = (fun x y > f (x,y))
 let deriv (f, dx) = fun x > f(x +. dx) . f x) /. dx
Lecture 12 • 2017/10/06
Lecture 13 • 2017/10/12
Lecture 14 • 2017/10/13
 Expressions in OCaml have types, and evaluates to a value or diverges
 Today, we’ll see that expressions may also have an effect

In class code
```ocaml
let x = ref 0 (* Allocate reference x with initial value 0 *)
a == b (* Compare by reference *)
a = b (* Compare by content *)
!x (* Read value *)
x := 3 (* Update value *)
let imperative_fact n =
begin
let result = ref 1 in
let i ref 0 in
let rec loop () =
if !i = n then ()
else (i := !i + 1; result := !result * !i; loop ())
in
(loop (); !result)
end
```
Lecture 15 • 2017/10/17

Types, values, & effects
```ocaml
(* Types *)
3 + 2
(* int; 5; no effect *)
55
(* int; 55; no effect *)
fun x > x + 3 * 2
(* int > int; or fun x > x + 2 * 3 *)
((fun x > match x with [] > true  y::ys > false), 2.3 *. 2.0)
(* ('a list > bool) * float; (, 6.4); no effect *)
let x = ref 3 in x := !x * 2
(* unit = (); no effect; x is disposed (removed from stack after evaluation) *)
fun x > x := 3
(* int ref > unit; ; effect: updated x to 3 *)
(fun x > x := 3) y
(* unit = (); updates y : int ref to 3 *)
fun x > (x := 3; x)
(* int ref > int ref; updates x & returns reference *)
fun x > (x := 3; !x)
(* int ref int; updates x & returns value *)
let x = 3 in print_string (string_of_int x)
(* unit = (); prints 3 to screen *)
(* 
Linked List Demo
 *)
type 'a rlist = Empty  RCons of 'a * ('a rlist) ref;;
let l1 = ref (RCons (4, ref Empty));;
let l2 = ref (RCons (5, l1));;
(* The 'a rlist ref of l2 is l1, same address *)
l1 := !l2;;
(* We've created a circular list *)
!l1;;
(* int rlist = RCons(5, {contents = }) *)
```
</details>
Lecture 16 • 2017/10/19

Object & closures
```ocaml
(* Code transcript taken from Julian Lore
https://github.com/julianlore/McGillResources/blob/master/COMP302/C302.pdf *)
type 'a rlist = Empty  RCons of 'a * ('a rlist) ref
let l1 = ref (RCons (4, ref Empty))
let l2 = ref (RCons (5, l1));;
l1 := !l2;;
(* Value is (), effect is changing link to itself *)
(* Append for regular lists *)
let rec append l1 l2 = match l1 with
 [] > l2
 x::xs > x::(append xs l2)
(* Append for rlist *)
type 'a refList = ('a rlist) ref
(* Return unit, as the "result" is the effect *)
(* 'a refList > 'a refList > unit *)
let rec rapp (r1 : 'a refList) (r2 : 'a refList) = match r1 with
 {contents = Empty} > r1 := !r2
 {contents = RCons (x, xs)} > rapp xs r2
(* 'a refList > 'a refList > 'a rlist *)
let rec rapp' (r1 : 'a refList) (r2 : 'a refList) = match r1 with
 {contents = Empty} > {contents = r2}
 {contents = RCons (x, xs)} > rapp' xs r2
let r = ref (RCons (2, ref Empty))
let r2 = ref (RCons(5, ref Empty));;
let r3 = rapp' r r2;;
r3;;
rapp r r2;;
r;;
let (tick, reset) =
let counter = ref 0 in
(* Input is unit, always true. Not the same as void *)
let tick () = (counter := !counter + 1 ; !counter) in
let reset () = counter := 0 in
(tick, reset);;
(* Now we have 2 functions, tick and reset *)
tick ();;
tick ();;
type counter_obj = {tick : unit > int ; reset : unit > unit}
let makeCounter () =
let counter = ref 0 in
{tick = (fun () > counter := !counter + 1 ; !counter);
reset = (fun () > counter := 0)};;
(* global variable *)
let global_counter = ref 0
let makeCounter' () =
let counter = ref 0 in
{tick = (fun () > counter := !counter + 1 ; global_counter := !counter ; !counter);
reset = (fun () > counter := 0)};;
let c = makeCounter ();;
c.tick ();;
c.tick ();;
let d = makeCounter ();;
d.tick ();;
c.tick ();;
d.reset ();;
```
Lecture 17 • 2017/10/20
 Exceptions…
 Force you to consider exceptional cases
 Allows you to segregate special cases from other cases (avoids clutter)
 Diverts control flow
 Eg 3/0 raises an exception Division_by_zero
Lecture 18 • 2017/10/24
 Backtracking
 Algorithm that finds solutions incrementing, abandoning partial candidates as soon as it deems it cannot lead to a successful solution
 Important tool to solve constraint satisfaction problems such as crosswords, puzzles, Sudoku, etc

Code
```ocaml
(* Warm up; printing int list *)
let listToString l = match l with
 [] > ""
 l > let rec toString l' = match l' with
 [h] > string_of_int h
 h::t > string_of_int h ^ ", " ^ toString t
in
toString l
(* With backtracking, given list of coins (in descending order) and amount, see if we can return exact change*)
exception Change
let rec change coins amt =
if amt = 0 then []
else (match coins with
 [] > raise Change
 coin :: cs >
(* skip coin as it is too big *)
if coin > amt then change cs amt
(* try to include current coin, and skip if fail *)
else try coin :: (change coins (amt  coin)) with Change > change cs amt
)
let change' coins amt =
try Some (change coins amt)  with Change > None
```
Lecture 19 • 2017/10/26
 Modules
 Control complexity of developing & maintaining software
 Split large programs into separate piece
 Name space separation
 Allows for separate compilation
 Incremental development
 Clear specifications at module boundaries
 Programs are easier to maintain & reuse
 Enforces abstractions
 Isolates bugs
 Module Types
 Allows you to hide information
 Implementations can be more specific than the actual module type
 May use the open keyword to use module methods without specifying module name

Code
```ocaml
module type STACK =
sig
type stack
type el
val empty : unit > stack
val is_empty : stack > bool
val pop : stack > stack option
val push : el > stack > stack
(* val push : int > stack > stack *)
(* cannot be el > stack > stack as 1 isn't a Stack.el *)
(* May use further abstractions through creation functions, but that wasn't covered in class *)
end
(* Implementation *)
module Stack : (STACK with type el = int) =
struct
type el = int
type stack = int list
let empty () : stack = []
let push i ( s : stack) = i :: s
let is_empty s = match s with
 [] > true
 _::_ > false
let pop s = match s with
 [] > None
 _::t > Some t
let top s = match s with
 [] > None
 h :: _ > Some h
let rec length s acc = match s with
 [] > acc
 x::t > length t 1 + acc
end
```
Lecture 20 • 2017/10/27
Lecture 21 • 2017/10/31
 Continuation
 Representation of execution state of program at certain point in time
 Save current state of execution into object & restore state from object later on to resume execution
 Base case – called continuation
 Recursive case – build up computation that still needs to be done

Code
```ocaml
(* append: 'a list > 'a list > 'a list *)
let rec append l k = match l with
 [] > k
 h :: t > h :: (append t k)
(* Tail Recursive *)
let rec app_tl l k c = match l with
 [] > c k (* Call continuation with stack k *)
 h :: t > app_tl t k (fun r > c (h :: r))
```