##### Lecture 16 • 2017/10/19
• Object & closures
``````(* Code transcript taken from Julian Lore
https://github.com/julianlore/McGill-Resources/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 cross-words, puzzles, Sudoku, etc
• Code
``````(* 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
``````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
• More on modules