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

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.