menu

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
  • Review for midterm
Lecture 13 • 2017/10/12
  • Midterm review
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
    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
  • Type, values, & effects
    (* 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 = }) *)