---
# System prepended metadata

title: CS51 Midterm 2 Notes

---

# CS51 Midterm 2 Notes
# --------------------



# Substitution Semantics
## Syntax Rules
```ocaml=
n ⇓ n                                      (R_int)

fun x -> B ⇓ fun x -> B                    (R_fun)

P + Q ⇓
      | P ⇓ m
      | Q ⇓ n                              (R_+)
      ⇓ m + n
      
P / Q ⇓
      | P ⇓ m
      | Q ⇓ n                              (R_/)
      ⇓ m / n
      
let x = D in B ⇓
               | D ⇓ v_D
               | B[x -> v_D] ⇓ v_B         (R_let)
               ⇓ v_B
               
P Q ⇓
    | P ⇓ fun x -> B
    | Q ⇓ v_Q
    | B[x -> v_Q] ⇓ v_B                    (R_app)
    ⇓ v_B
```

## Examples
```ocaml=
(* Substitution *)
(x + x)[x ↦ 3] = 
x[x ↦ 3] + x[x ↦ 3] =
3 + 3

(x + x)[y ↦ 3] = 
x[y ↦ 3] + x[y ↦ 3] =
x + x

(let x = y in y + x)[y ↦ z] = 
let x = y[y ↦ z] in (y + x)[y ↦ z] = 
let x = z in y[y ↦ z] + x[y ↦ z] = 
let x = z in z + x = 
(z + x)[x ↦ z] = 
z[x ↦ z] + x[x ↦ z] = 
z + z

(let x = y in y + x)[x ↦ z] = 
let x = y[x ↦ z] in y + x = 
let x = y in y + x = 
(y + x)[x ↦ y] = 
y[x ↦ y] + x[x ↦ y] = 
y + y
  
(*  Evaluation  *)
3+5  ⇓
     | 3⇓3
     | 5⇓5 
     ⇓ 8
     
let x = 5 in x * x ⇓
                   | 5⇓5
                   | (5 * 5)⇓    (* end if substitution *)
                   |      | 5⇓5
                   |      | 5⇓5
                   |      ⇓ 25
                   ⇓ 25
                   
(* check me on these following ones *)
let x = 3 in let y = 5 in x * y 
      ⇓
      | 3⇓3
      | let y = 5 in x * y
      |       ⇓
      |       | 5⇓5
      |       | (3 * 5) ⇓    (* end if substitution *)
      |       |       | 3⇓3
      |       |       | 5⇓5
      |       |       ⇓ 15
      |       ⇓ 15
      ⇓ 15

let x = 3 in let x = 5 in x
      ⇓
      | 3⇓3
      | (let x = 5 in x)
      |       ⇓
      |       | 5⇓5
      |       | x ⇓ 5
      |       ⇓ 5
      ⇓ 5
      
let x = 3 * 4 in x + x
      ⇓ 
      | 3*4 ⇓
      |   | 3⇓3
      |   | 4⇓4
      |   ⇓ 12
      | (12 + 12) ⇓        (* end if substitution *)
      |       | 12⇓12
      |       | 12⇓12
      |       ⇓ 24
      ⇓ 24
      
let y = let x = 5 in x + 1 in y + 2
      ⇓ 
      | let x = 5 in x + 1
      |       ⇓
      |       | 5⇓5
      |       | (5 + 1) ⇓
      |       |         | 5⇓5
      |       |         | 1⇓1
      |       |         ⇓ 6
      |       ⇓ 6
      | (6+2)
      |    ⇓
      |    | 6⇓6
      |    | 2⇓2
      |    ⇓ 8
      ⇓ 8
      
(* full interpretation of lab9 solution *)
let x = 3 + 5 in (fun x -> x * x) (x - 2) 
     ⇓
     | 3+5 ⇓
            | 3 ⇓ 3          (R_int)
            | 5 ⇓ 5          (R_int)
            ⇓ 8              (R_+)
     | ((fun x -> x * x) (x - 2))
            ⇓         
            | 8 - 2 ⇓
                    | 8 ⇓ 8         (R_var)
                    | 2 ⇓ 2         (R_int)
                    ⇓ 6             (R_-)
            | fun x -> x * x ⇓ fun x -> x * x
            | 6⇓6
            | (6 * 6)                (* end if substitution *)
                ⇓
                | 6⇓6 (R_int)
                | 6⇓6 (R_int)
                ⇓ 36
            ⇓ 36
     ⇓ 36
```



# Substitution vs. Evaluation
If we are asked only to substitute, then there is no math done.
Subsitution uses = signs to show that each expression is equivalent.
Evaluation uses 
## Substitute only
```ocaml= 
(* taken from lab9 solutions *)
(x + 1)[y ↦ 50] 
      = x[y ↦ 50] + 1[y ↦ 50] 
      = x + 1
      
(x * x)[x ↦ 2] 
      = x[x ↦ 2] * x[x ↦ 2]
      = 2 * 2 (* do not evaluate *)
      
(let x = y * y in x + x)[x ↦ 3] 
      = let x = (y * y)[x ↦ 3] in x + x
      = let x = y[x ↦ 3] * y[x ↦ 3] in x + x
      = let x = y * y in x + x
      
(let x = y * y in x + x)[y ↦ 3]
      = let x = (y * y)[y ↦ 3] in (x + x)[y ↦ 3]
      = let x = y[y ↦ 3] * y[y ↦ 3] in
        x[y ↦ 3] + x[y ↦ 3]
      = let x = 3 * 3 in x[y ↦ 3] + x[y ↦ 3]
      = let x = 3 * 3 in x + x (* do not evaluate *)
```
## Evaluation (actually doing the math)
```ocaml=
2 * 25 ⇓
       | 2 ⇓ 2
       | 5 ⇓ 5
       ⇓ 50
```



# Environment Semantics
## Syntax Rules
```ocaml=
E,S ⊢ n ⇓ n,S                                          (R_int)

E,S ⊢ x ⇓ E(x),S                                       (R_var)

E,S ⊢ fun x -> P ⇓ [E ⊢ fun x -> P],S                  (R_fun)

E,S ⊢ P + Q ⇓
            | E,S ⊢ P ⇓ m,S
            | E,S ⊢ Q ⇓ n,S'                           (R_+)
            ⇓ m + n, S''

E,S ⊢ let x = D in B ⇓
                     | E,S ⊢ D ⇓ v_D,S'
                     | E{x -> v_D},S' ⊢ B ⇓ v_B,S''    (R_let)
                     ⇓ v_B, S''
                     
E_d,S ⊢ P Q ⇓
            | E_d,S ⊢ P ⇓ [E_l ⊢ fun x -> B], S'
            | E_d,S ⊢ Q ⇓ v_Q, S''
            | E_l{x -> v_Q},S'' ⊢ B ⇓ v_B, S'''        (R_app)
            ⇓ v_B, S'''
            
E,S ⊢ ref P ⇓
            | E,S ⊢ P ⇓ v_P, S'                        (R_ref)
            ⇓ l,S'{l -> v_P}
            
E,S ⊢ ! P ⇓
          | E,S ⊢ P ⇓ l, S'                            (R_deref)
          ⇓ S'(l), S'
          
E,S ⊢ P := Q ⇓
             | E,S ⊢ P ⇓ l, S'                         (R_assign)
             | E,S' ⊢ Q ⇓ v_Q, S''
             ⇓ (),S''{l -> v_Q}
```
## Examples
```ocaml=
(* addition *)
{} ⊢ 3 + 5 ⇓
           | {} ⊢ 3 ⇓ 3
           | {} ⊢ 5 ⇓ 5
           ⇓ 8
           
(* binding *)
{} ⊢ let x = 3 in x + x ⇓
                        | {} ⊢ 3 ⇓ 3
                        | {x -> 3} ⊢ x + x ⇓
                                         | {x -> 3} ⊢ x ⇓ 3
                                         | {x -> 3} ⊢ x ⇓ 3
                                         ⇓ 6
                        ⇓ 6
                        

(* Env {} *)
(* 3+5 *)
{} ⊢ 3 + 5 ⇓
           | {} ⊢ 3 ⇓ 3       (R_int)
           | {} ⊢ 5 ⇓ 5       (R_int)
           ⇓ 8                (R_+)


(* Env {x->3} *)
(* x+5 *)
{x -> 3} ⊢ x + 5 ⇓
                 | {x -> 3} ⊢ x ⇓ 3    (R_var)
                 | {x -> 3} ⊢ 5 ⇓ 5    (R_int)
                 ⇓ 8                   (R_+)


(* Env {} *)
(* let x = 3 in x + 5 *)
{} ⊢ let x = 3 in x + 5 ⇓
                        | {} ⊢ 3 ⇓ 3              (R_int)
                        | {x -> 3} ⊢ x + 5 ⇓ 8    (Above)
                        ⇓ 8                       (R_let)


(* Env {x->6} *)
(* x*x *)
{x -> 6} ⊢ x * x ⇓
                 | {x -> 6} ⊢ x ⇓ 6       (R_var)
                 | {x -> 6} ⊢ x ⇓ 6       (R_var)
                 ⇓ 36                     (R_* )
                 

(* Env {x->8} *)
(* (fun x -> x * x) (x - 2) *)
{x -> 8} ⊢ (fun x -> x * x) (x - 2) ⇓
    | {x -> 8} ⊢ (fun x -> x * x) ⇓ (fun x -> x * x)   (R_fun)
    | {x -> 8} ⊢ x - 2 ⇓ 6                             (See above)
    | {x -> 6} ⊢ x * x ⇓ 36                            (See above)
    ⇓ 36                                               (R_app)
    
    
(* Env {} *)
(* let x = 3 + 5 in (fun x -> x * x) (x - 2) *)
{} ⊢ let x = 3 + 5 in (fun x -> x * x) (x - 2)
   ⇓
   | {} ⊢ 3 + 5 ⇓ 8                              (See above)
   | {x -> 8} ⊢ (fun x -> x * x) (x - 2) ⇓ 36    (See above)
   ⇓ 36                                          (R_let)
```
## Examples with references (environment and store)
```ocaml=
(* x := 3; !y *)
{x ↦ l1; y ↦ l1},{l1 ↦ 1} ⊢ x := 3; !y 
    ⇓
    | {x ↦ l1; y ↦ l1},{l1 ↦ 3} ⊢ x := 3 ⇓
    |   | {x ↦ l1; y ↦ l1},{l1 ↦ 3} ⊢ x ⇓ l1, {l1 ↦ 1}
    |   | {x ↦ l1; y ↦ l1},{l1 ↦ 3} ⊢ 3 ⇓ 3, {l1 ↦ 1}
    |   ⇓ (), {l1 ↦ 3}
    | {x ↦ l1; y ↦ l1},{l1 ↦ 3} ⊢ !y ⇓
    |   | {x ↦ l1; y ↦ l1},{l1 ↦ 3} ⊢ y ⇓ l1, {l1 ↦ 3}
    |   ⇓ 3, {l1 ↦ 3}
    ⇓ 3, {l1 ↦ 3}
   
(* Solution from Ahan's Review *)
{}, {} ⊢ let x = ref 42 in (x := !x - 21; !x) + !x ⇓    
    | {}, {} ⊢ ref 42 ⇓    
        | {}, {} ⊢ 42 ⇓ 42, {}                                     (R_int)
        ⇓ l1, {l1 -> 42}                                           (R_ref)    
    | {x -> l1}, {l1 -> 42} ⊢ (x := !x - 21; !x) + !x ⇓    
        | {x -> l1}, {l1 -> 42} ⊢ x := !x - 21; !x ⇓    
            | {x -> l1}, {l1 -> 42} ⊢ x := !x - 21 ⇓    
                | {x -> l1}, {l1 -> 42} ⊢ x ⇓ l1, {l1 -> 42}       (R_var)    
                | {x -> l1}, {l1 -> 42} ⊢ !x - 21⇓    
                    | {x -> l1}, {l1 -> 42} ⊢ !x ⇓    
                        | {x -> l1}, {l1 -> 42} x ⇓ l1, {l1 -> 42} (R_var)    
                        ⇓ 42, {l1 -> 42}                           (R_deref)    
                    | {x -> l1}, {l1 -> 42} ⊢ 21 ⇓ 21, {l1 -> 42}  (R_int)    
                    ⇓ 21                                           (R_-)    
                ⇓ (), {l1 -> 21}                                   (R_assign)    
            | {x -> l1}, {l1 -> 21} ⊢ !x ⇓    
                | {x -> l1}, {l1 -> 21} ⊢ x ⇓ l1, {l1 -> 21}       (R_var)    
                ⇓ 21, {l1 -> 21}                                   (R_deref)    
            ⇓ 21, {l1 -> 21}                                       (R_seq)    
            | {x -> l1}, {l1 -> 21} ⊢ !x ⇓    
                | {x -> l1}, {l1 -> 21} ⊢ x ⇓ l1, {l1 -> 21}       (R_var)    
                ⇓ 21, {l1 -> 21}                                   (R_deref)
            ⇓ 21, {l1 -> 21}
        ⇓ 42, {l1 -> 21}                                           (R_+)
    ⇓ 42, {l1 -> 21}                                               (R_let)
```


# Lexical vs. Dynamic
## Lexical
Functions are ***defined*** with the current environment.

The body of a function is evaluated in the  old  dynamic  environment  that  existed  at  the  time  the  function was  defined,  not  the  current  environment  when  the  function  is applied. 

**OCaml follows lexical environment semantics.**
## Dynamic
Functions are ***applied*** with the current environment.

the body of a function is evaluated in  the  current  dynamic  environment  at  the  time  the  function  is applied,  not  the  old  dynamic  environment  that  existed  at  the  time the function was defined.

## Example
```ocaml=
(* Lexical *)
let x = 1 in (* this is the x used in f *)
let f = fun y -> x + y in 
let x = 2 in 
f 3 ;;
:- int = 4

(* Dynamic *)
let x = 1 in
let f = fun y -> x + y in 
let x = 2 in (* this is the x used in f *)
f 3 ;;
:- int = 5
```



# Reference Variables
## Good information to know
Pure programming does not include any side effects, but any program that is productive must perform an action at some point.
Impure programming involves projecting a result.
OCaml is free of buffer overflows, buffer overreads, memory corruption, and memory leaks.
## Reference/Declaration
Type: 'a -> 'a ref
```ocaml=
let count = ref 0 ;;
let str = ref "hello, world!" ;;
```
## De-reference
Type: 'a ref -> 'a
```ocaml=
!count ;;
-: int = 0
!str ;;
-: string = "hello, world!"
```
## Update
Type: 'a ref -> a -> unit
```ocaml=
count := !count + 1 ;;
str := !str ^ " hello again!" ;;
```
## Examples
```ocaml=
(* From Lab 12 *)
let gensym : string -> string =
  let count = ref 0 in
  fun s -> let str = s ^ (string_of_int !count) in
  count := !count + 1; str ;;
  
let toggle =
  let b = ref false in
  fun () -> let c = !b in 
  b := not c; not c;;
  
let remember : string -> string =
  let memory = ref "" in
  fun (msg : string) -> let previous = !memory in
                        memory := msg;
                        previous ;;
```



# Time Complexity
## CS51 Order of Speed 
Slowest to fastest (from [Lab 12](https://github.com/cs51/lab12_soln/blob/main/lab12.ml)):
| Notation| Name|
|---------|-----|
|O(1)   |     Constant
|O(log(n))  | Logarithmic
|O(n)|Linear
|O(nlog(n))|LogLinear
|O(n^2)|Quadratic
|O(n^3)|Cubic
|O(c^n)|Exponential
## Complexities of Basic Equations
Divide-and-conquer algorithms $\in O(n * log(n))$
Binary Search in a tree $\in O(log(n))$

Appending to a list $\in O(n)$
Reversing a list $\in O(n^2)$
Reversing a list w/ an accumulator $\in O(n)$ (see Tail Recursion section farther down)
Inserting into a sorted list $\in O(n)$
Merging 2 lists $\in O(n)$
Splitting a list $\in O(n)$

Insertion Sort $\in O(n^2)$
Merge Sort $\in O(n * log(n))$
## Recurrence Equations
Page 269 of the CS51 textbook.
### Appending an element to the end of a list (@ operator)
T_@(0, m) = c
T_@(n, m) = k + T_@ (n-1, m)

Further simplification:
T_@(n, m) = k + k + k + ... + T_@(n, m)
T_@(n, m) = k * n + c
### Reversing a list (List.rev lst)
T_rev(n) = (c_match + c_cons) + T_rev(n-1) + T_@(n-1,1)
T_rev(n) = r + T_rev(n) + (k * n + c)
T_rev(n) = $k * \sum_{i=1}^{n} i + (r+c-k)*n + q$
T_rev(n) = $\frac{k}{2} * n^2 + (s - \frac{k}{2}) * n + q$
T_rev(n) $\in O(n^2)$



# Records with mutability
Records have the ability to be mutable upon delcaration. This is shown in the following example with the first name attribute. Note that the last name remains static.
```ocaml= 
type person = {mutable first : string; last : string} ;;
let me = {first = "Jane"; last = "Doe"} ;;

me.first <- "John" ;; (* person changes name *)
(* me.last cannot be changed since it was not declared as mutable *)
```



# Loops
Loops are used in procedural programming (think: going linear through one procedure at a time).
Loops require impurity.
## For Loop
```ocaml=
for <variable> = <expr_start> to <expr_end> do 
    <expr_body>
done
```
For iterating by -1, use 'downto' in place of 'to.'
## While Loop
```ocaml=
while <expr_condition> do
    <expr_body>
done
```
## Examples
```ocaml=
(* From Lab 13; returns odd list from natural numbers *)
let odd_while (x : int) : int list =
  let count : int ref =
    if x mod 2 <> 0 then ref x
    else ref (x - 1) 
  in
  let lst : int list ref = ref [] in
  while !count > 0 do 
    lst :=  !count :: !lst ;
    count := !count - 2 ;
  done ;
  !lst ;;

let odd_for (x : int) : int list =
  let lst : int list ref = ref [] in
  for count = x downto 0 do 
    if count mod 2 = 1 then lst :=  count :: !lst
  done ;
  !lst ;;

(* From Lab 13; takes sum of list *)
let sum_iter (lst : int list) : int =
  let adds = ref 0 in
  let lstr = ref lst in (* copy of a pointer to lst *)
  while !lstr <> [] do
    adds := (List.hd !lstr) + !adds;
    lstr := List.tl !lstr (* the pointer's place is moved down one *)
  done;
  !adds ;;
```


# Lazy Programming
## Definition
Put simply, lazy programming is delaying computation.
This is most commonly done with the fun () -> ___ or lazy( ___ ) syntax.
It is also useful for creating infinite streams.

Note: OCaml is an *eager* language (not lazy by nature).
## Example of fun () -> ___ syntax
```ocaml=
(* for LazyStream module, see lazy stream section for more information *)
let rec ones : int stream = 
    fun () -> Cons(1, ones) ;;

(* equivalent to above but for NativeLazyStream *)
let rec ones1 : int stream = 
    lazy( Cons(1, ones1) ) ;;
```
## Memoization
When values that have already been computed are stored. This saves time as recursive step counts get larger.
A thunk datatype represents memoization with its use of the Evaluated type.
```ocaml=
type 'a thunk = 'a thunk_internal ref 
and 'a thunk_interal = 
    | Unevaluated of (unit -> 'a)
    | Evaluated of 'a ;;
```
## Force
This is when the unevaluated values are "forced" into being memoized.
```ocaml=
let rec force (t : 'a thunk) : 'a =
    match !t with 
    | Evaluated v -> v
    | Unevaluated f -> 
        t := Evaluated (f ());
        force t ;;
```




# Lazy Stream
## CS51 Module Code
```ocaml=
(* From Lab 14 *)
module LazyStream =
  struct
    type 'a stream_internal = Cons of 'a * 'a stream
     and 'a stream = unit -> 'a stream_internal ;;
      
    (* head strm -- Returns the first element of `strm`. *)
    let head (s : 'a stream) : 'a =
      let Cons (h, _t) = s () in h ;;

    (* tail strm -- Returns a stream containing the remaining elements
       of `strm`. *)
    let tail (s : 'a stream) : 'a stream =
      let Cons (_h, t) = s () in t ;;
      
    (* first n strm -- Returns a list containing the first `n`
       elements of the `strm`. *)
    let rec first (n : int) (s : 'a stream) : 'a list =
      if n = 0 then []
      else head s :: first (n - 1) (tail s) ;;
      
    (* smap fn strm -- Returns a stream that applies the `fn` to each
       element of `strm`. *)
    let rec smap (f : 'a -> 'b) (s : 'a stream) : ('b stream) = 
      fun () -> Cons (f (head s), smap f (tail s)) ;;
      
    (* smap2 fn strm1 strm2 -- Returns a stream that applies the `fn`
       to corresponding elements of `strm1` and `strm2`. *)
    let rec smap2 f s1 s2 = 
      fun () -> Cons (f (head s1) (head s2),
                      smap2 f (tail s1) (tail s2)) ;;
               
    (* filter fn strm -- Returns a stream that filters values of 
       the passed stream according to function 'fn' *)
    let rec sfilter (f : 'a -> bool) (str : 'a stream) : 'a stream = 
       fun () -> (
          if f (head str) then Cons (head str, sfilter f (tail str))
          else sfilter f (tail str) ()
       ) ;;
  end ;;
```
## Creating Streams from the LazyStream module
```ocaml=
open LazyStream ;;

(* get the nth value of a stream *)
let rec nth (s : 'a stream) (n : int) : 'a =
  if n = 0 then head s
  else nth (tail s) (n - 1) ;;

(* General streams *)
let rec ones = fun () -> Cons (1, ones) ;;
let twos = smap2 (+) ones ones ;;
let rec nats = fun () -> Cons (0, smap succ nats) ;;
let rec evens = fun () -> Cons (0, smap2 (+) twos evens) ;;
let rec odds = fun () -> Cons (1, smap2 (+) twos odds) ;;


(* Fibonacci (from Lab 15) *)
let rec fib (n : int) : int =
  if n < 2 then n
  else (fib (n - 1)) + (fib (n - 2)) ;;
(* Delayed computation of the 42nd Fibonacci number *)
let fib42 : int Lazy.t = lazy (fib 42) ;;
(* ^there is a faster fib further down *)
  
(* Geometric sequence *)
let rec geo init mult =
  lazy (Cons (init, (geo (init *. mult) mult))) ;;


(* Infinite Stream of Primes (from Lab 14) *)
let not_div_by (n : int) (m : int) : bool = 
  not (m mod n = 0) ;;
let rec sieve s = 
   fun () -> 
      Cons (head s, sieve (sfilter (fun x -> not_div_by (head s) x) (tail s))) ;;
let primes = sieve (tail (tail nats)) ;;

(* Computes the average of a stream *)
let average (s : float stream) : float stream =
  smap2 (fun x y -> (x +. y) /. 2.0) s (tail s) ;;
```



# The Lazy Module
The lazy module was created to make lazy programming easier in OCaml.
Lazy.force is the most common method used.
Documentation: https://ocaml.org/api/Lazy.html.
## Native Lazy Stream code
This is the Lazy Stream code written with help from the built-in Lazy module.
```ocaml=
(* Note how this is different from the LazyStream code above *)
module NativeLazyStream =
    struct
        type 'a stream_internal = Cons of 'a * 'a stream
         and 'a stream = 'a stream_internal Lazy.t ;;

        let head (s : 'a stream) : 'a =
          let Cons (hd, _tl) = Lazy.force s in hd ;;

        let tail (s : 'a stream) : 'a stream =
          let Cons (_hd, tl) = Lazy.force s in tl ;;

        let rec first (n : int) (s : 'a stream) : 'a list =
          if n = 0 then []
          else head s :: first (n - 1) (tail s) ;;

        let rec smap (f : 'a -> 'b) (s : 'a stream) : 'b stream =
          lazy (Cons (f (head s), smap f (tail s))) ;;

        let rec smap2 (f : 'a -> 'b -> 'c) (s1 : 'a stream) (s2 : 'b stream) : 'c stream = 
          lazy (Cons (f (head s1) (head s2), smap2 f (tail s1) (tail s2))) ;;

        let rec sfilter (pred : 'a -> bool) (s : 'a stream) : 'a stream =
          if pred (head s) then lazy (Cons (head s, sfilter pred (tail s)))
          else sfilter pred (tail s) ;;
    end ;;
```
## Lazy.force
Lazy.force has the type 'a Lazy.t -> 'a
This is used to force evaluation of the value.
See above in the implementation of NativeLazyStream for use cases.
## Creating Streams from this
```ocaml=
open NativeLazyStream ;;

(* Natural numbers *)
let rec nats = lazy (Cons (0, smap ((+) 1) nats)) ;;

(* Fibonacci sequence (from Lab 15) *)
let rec fibs : int stream =
  lazy (Cons (0, lazy (Cons (1, smap2 (+) fibs (tail fibs))))) ;;
  
(* Primes (from Lab 15) *)
let rec sieve s = 
  lazy (Cons (head s, sieve (sfilter (fun y -> not (y mod (head s) = 0)) (tail s)))) ;;
let primes = sieve (tail (tail nats)) ;;
```



# Object Oriented Programming
## Syntax
```ocaml=
class superclass_name = 
    object (this)
        val static_var = 1
        val mutable mut_var = 2
        
        method return_static = static_var
        method return_mut_var = mut_var
        method incr_mut_var = mut_var <- mut_var + 1 (* increments mutable variable *)
    end ;;

class subclass_name = 
    object (this) (* local methods now accessible with this#___ *)
        inherit superclass_name as super (* super class methods now accessible with super#___ *)
        
        val new_static = 5 (* local to this sub-class *)
        
        (* 'method!' overrides superclass methods *)
        method! return_static = new_static (* this#return_static is now 5, super#return_static is 1 *)
        method! incr_mut_var = 
            super#incr_mut_var; 
            super#incr_mut_var (* adds 2 to mut_var on each call *)
    end ;;
```
## Examples
```ocaml=
(* Vehicle Class (from lab 16) *)
class vehicle_class (capacity: float)
                    (efficiency : float)
                    (initial_energy : float)
                    (initial_pos : point) =
  object (this)
    val capacity = capacity
    val efficiency = efficiency
    val mutable energy = initial_energy
    val mutable pos = initial_pos
    val mutable odometer = 0.

    method get_distance : float = odometer

    method get_pos : point = pos 
         
    method get_energy : float = energy

   method go (distance : float) (angle : float) : unit = 
      if distance < 0. then
        raise (Invalid_argument "go: can't move in reverse")
      else
        let distance = min distance (this#get_energy *. efficiency) in
        pos <- offset this#get_pos distance angle;
        energy <- this#get_energy -. distance /. efficiency;
        odometer <- odometer +. distance
    end ;;

(* Inheritance *)
class car (initial_energy : float) (initial_pos : point) = 
  object
    inherit vehicle_class 100. 30. initial_energy initial_pos
  end ;;

class bus (initial_energy : float) (initial_pos : point) (seats : int) = 
  object (this)
    inherit vehicle_class 200. 20. initial_energy initial_pos as super

    (* Additional methods *)
    val mutable passengers = 0
    val seats = seats
    
    method get_passengers : int = passengers

    method get_seats : int = seats

    method pick_up (n : int) : unit =
      passengers <- min seats (passengers + n)
   
    method drop_off (n : int) : unit =
      passengers <- max 0 (passengers - n)
    
    (* Edits a method from the super-class *)
    method! fill = 
      this#drop_off passengers;
      super#fill
  end ;;
```



# Creating an object with a class
## Labrador Example
```ocaml= 
(* essentially a signature for any animal *)
class type organism =
  object
    method get_name : unit -> string
    method get_lifespan : unit -> float
    method get_age : unit -> float
    method set_age : float -> unit
    method get_height : unit -> float
    method set_height : float -> unit
  end ;;
  
(* superclass for any breed *)
class dog (n : string) (l : float) (a : float) (h : float) : organism =
  object
    val name = n
    val lifespan = l
    val mutable age = a
    val mutable height = h
    
    method get_name : unit -> string = fun () -> name
    method get_lifespan : unit -> float = fun () -> lifespan
    method get_age : unit -> float = fun () -> age
    method set_age : float -> unit = fun a -> age <- a
    method get_height : unit -> float = fun () -> height
    method set_height : float -> unit = fun h -> height <- h
  end ;;
  
(* subclass *)
class labrador (n : string) (l : float) (a : float) (h : float) (c : string) =
  object
    inherit dog n l a h
    val color = c
    method get_color : unit -> string = fun () -> color
  end ;;

(* creating an actual object *)
let kevin = new labrador "Kevin" 20. 3. 7. "orange" ;;

(* methods with kevin *)
kevin#get_name () ;;
-: string = "kevin"
kevin#get_age () ;;
-: float = 3. 
kevin#get_color () ;;
-: string = "orange"
```



# The :> (subtype) operator 
Equivalent to "type casting" one object to another one whose methods and variables are encompassed by the original object. 
## Syntax
(name : sub_type :> super_type)

or

(name :> super_type)
## Shape Example
```ocaml=
type shape = < area : float > ;;

type square = < area : float; width : int > ;;

let square w = 
    object
      method area = Float.of_int (w * w)
      method width = w
    end ;;

(* attempting to use the subtype without the operator *)
(square 10 : shape) ;;

Line 1, characters 2-11:
Error: This expression has type < area : float; width : int >
       but an expression was expected of type shape
       The second object type has no method width
       
       
(* using the subtype operator to convert square to type shape *)
(square 10 :> shape) ;;
- : shape = <obj>
```
## Labrador Example
See above for initial code.
```ocaml= 
(* creating an actual object *)
let kevin = new labrador “Kevin” 20. 3. 7. “orange” ;;

(* function taking the broader organism type *)
let fits_in_elevator (org : organism) (h : float) : bool =
    org#get_height () <= h ;;
    
(* using the :> operator to specify kevin should be interpreted 
   as an organism in the fits_in_elevator function *)
let does_kevin_fit = fits_in_elevator (kevin :> organism) 6. ;;
```
## More 
Page 375 of the textbook has an example.
This dictates the class type of an object. 
It's especially useful in circumstances where a certain class is needed for a function.



# Free Variables
## Definition
A let or fun *binds* a variable. 
A free variable is *not* bound.

## Semantics Approach
```ocaml= 
FV(m) = empty set                             (* integers *)
FV(x) = {x}                                   (* variables *)
FV(P + Q) = FV(P) U FV(Q)                     (* binary operators *)
FV(P Q) = FV(P) U FV(Q)                       (* applications *)
FV(fun x -> P) = FV(P) - {x}                  (* functions *)
FV(let x = P in Q) = (FV(Q) - {x}) U FV(P)    (* binding *)
```
## Real-world Free Variables
```ocaml=
(* refer to textbook page 239 for more information*)
fun x -> x + y (* x is bound, y is free *)
let x = 3 in x + y (* x is bound, y is free *)
```

## Examples with Semantic Approach
```ocaml= 
FV(let x = y in let y = x in f x y)
    = (FV(let y = x in f x y) - {x}) ∪ FV(y)
    = (((FV((f x) y) - {y}) ∪ FV(x)) - {x}) ∪ FV(y)
    = ((((FV(f x) ∪ FV(y)) - {y}) ∪ FV(x)) - {x}) ∪ FV(y)
    = (((((FV(f) ∪ FV(x)) ∪ FV(y)) - {y}) ∪ FV(x)) - {x}) ∪ FV(y) 
    = ((((({f} ∪ {x}) ∪ {y}) - {y}) ∪ {x}) - {x}) ∪ {y}
    = {f, y}

FV(let x = 3 in let y = x in f x y)
    = (FV(let y = x in f x y) - {x}) U FV(3)
    = (FV(f x y) - {y}) U FV(x)) - {x}
    = ({f, x, y} - {y}) U {x}) - {x}
    = ({f, x} U {x}) - {x}
    = {f, x} - {x}
    = {f}

FV(let x = x in let y = x in f x y)
    = (FV(let y = x in f x y) - {x}) U FV(x)
    = (FV(f x y) - {y}) U FV(x)) - {x} U {x}
    = (({f, x, y} - {y}) U {x}) - {x}) U {x}
    = (({f, x} U {x}) - {x}) U {x}
    = ({f, x} - {x}) U {x}
    = {f, x}
    
FV(let x = fun y -> x in x)
    = (FV(x) - {x}) U FV(fun y -> x)
    = ({x} - {x}) U (FV(x) - {y})
    = {} U {x}
    = {x}
    
FV(let x = x in x)
    = (FV(x) - {x}) U FV(x)
    = ({x} - {x}) U {x}
    = {x}
```



# Subclass vs. Subtype ?
Via this [Ed Post](https://edstem.org/us/courses/2964/discussion/393442):
- If A is a **supertype** of B, B implements all the types in A's signature.
- If A is a **superclass** of B, B inherits the entire implementation from A, including instance variables.
- Not all subtypes are subclasses, since they may not be related by inheritance.
- Not all subclasses are subtypes, since in the subclass, you could redefine a method to have a more restrictive signature, so it would have a narrower interface (at least for that method), not a wider one.

From page 374 of textbook:
"There would seem to be a correlation between subclasses and subtypes. Of course, not all subtypes are subclasses; they may not be related by inheritance. But in a subclass, you have all the functionality of the superclass, plus you can add some more.  So are subclasses always subtypes? No. For instance, in the subclass, you could redefine a method to have a more restrictive signature. In that case, the subclass would not be a subtype; it would have a narrower interface (at least for that method), not a wider one."



# Mutable List
Refer to textbook pages 302-304.
## Example Code
```ocaml=
type 'a mlist =
    | Nil
    | Cons of 'a * ('a mlist ref) ;;

let rec length (lst : 'a mlist) : int =
    match lst with
    | Nil -> 0
    | Cons(_hd, tl) -> 1 + length !tl ;;
    
let rec first (n : int) (lst : 'a mlist) = 
    if n < 1 then [] 
    else 
        match lst with 
        | Nil -> [] 
        | Cons (hd, tl) -> hd :: (first (n-1) !tl) ;;

(* Implementing one type of mlist with 0s and 1s alternating *)
let rec alternating = Cons(0, ref (Cons(1, ref alternating))) ;;
```



# Arrays
Declared with || lines along with the normal list stuff.
There is some useful functionality in the [Array Module](https://ocaml.org/releases/4.00/htmlman/libref/Array.html).
```ocaml=
let arr = Array.init 5 (fun x -> x * x) ;;
-: val arr : int array = [|0; 1; 4; 9; 16|]

arr.(3) <- 1000 ;;
-: unit = ()

arr ;;
-: int array = [|0; 1; 4; 1000; 16|]
```



# Tail Recursion
For more explanation go to [Cornell Textbook 3.5](https://www.cs.cornell.edu/courses/cs3110/2019sp/textbook/data/tail_recursion.html).
```ocaml=
(* NOT tail recursive *)
let rec sum (l : int list) : int =
  match l with
  | [] -> 0
  | x :: xs -> x + (sum xs) ;; (* difference *)

(* IS tail recursive *)
let rec sum_with_accu (accu : int) (l : int list) : int =
  match l with
  | [] -> acc
  | x :: xs -> sum_with_accu (accu + x) xs ;; (* difference *)
```
## Another Example
```ocaml=
(* Reverses a list with an accumulator *)
let rec rev lst accu =
  match lst with
  | [] -> accu
  | hd :: tl -> rev tl (hd :: accu) ;;
```



# List Module
This was covered first semester, but it'll probably come up again.
List documentation [here](https://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html)



# Fibonacci Sequence
[Link to more info](https://www.geeksforgeeks.org/time-complexity-recursive-fibonacci-program/)

Complexity: $O(2^n)$



# Potentially Useful Code?
```ocaml= 
(* merge two lists with lt as the compare function *)
let rec merge lt xs ys =
    match xs, ys with
    | [], _ -> ys
    | _, [] -> xs
    | x :: xst, y :: yst ->
        if lt x y
        then x :: (merge lt xst ys)
        else y :: (merge lt xs yst) ;;

(* split a list *)
let rec split lst =
    match lst with
    | []
    | [_] -> lst, []
    | first :: second :: rest ->
        let first', second' = split rest in
        first :: first', second :: second' ;;
        
(* append to the end of a list (@ operator) *)
let rec append lst elt =
    match lst with
    | [] -> elt
    | hd :: tl -> hd :: (append tl elt) ;;

(* reversing a list *)
let rec rev lst =
    match lst with
    | [] -> []
    | hd :: tl -> append (rev tl) [hd] ;;
    
(* reversing a list with an accumulator *)
let rec revappend lst accum =
    match lst with
    | [] -> accum
    | hd :: tl -> revappend tl (hd :: accum) ;;
    
(* inserting into a sorted list *)
let rec insert lst elt =
    match lst with
    | [] -> [elt]
    | hd :: tl -> 
        if elt > hd then hd :: (insert tl elt)
        else elt :: lst ;;
        
(* insertion sort *)
let rec sort (lt : 'a -> 'a -> bool) (lst : 'a list)
                : 'a list =
    match lst with
    | [] -> []
    | hd :: tl -> insert lt (sort lt tl) hd ;;
    
(* merge sort (uses the split and merge functions from above) *)
let rec msort lst =
    match lst with
    | [] -> lst
    | [_] -> lst
    | _ -> 
        let fst, snd = split lst in
        merge (<) (msort fst) (msort snd) ;;
```



# References and Sources
https://www.cs.cornell.edu/courses/cs3110/2019sp/textbook/
https://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html
https://book.cs51.io/pdfs/abstraction.pdf
