:::warning
Announcements
- Help hours 3:45-5:15pm in L037
- A4 due tonight
- A5 out tomorrow
- Late deadline: Tuesday after SB.
- Still designed as a 1 week assignment, so finish by Thursday if you prefer (and to maximize help hours!)
- DM me if interested in a partner
- Quiz 2:
- Monday (Mar 31) the week after week back from SB
- Content through Mutation (before SB)
- Assignments through A5 (type checking)
:::

:::success
Agenda for today
- Exceptions
- Including a bit more on pattern matching
- Function composition/pipelining
- Type checking (A5)
:::

# Exceptions

Across many different programming languages _exceptions_ are used for handling "exceptional cases": almost always errors or other unexpected conditions.

For example, in Java, null pointer exception indicate the exceptional case of trying to call a function on the `null` pointer instead of an actual object.

Exceptions allow you to exit from a computation early and directly. Rather than proceeding with normal control flow, exceptions propagate errors back up the call stack.

In OCaml, exception bindings declare new kinds of exceptions:

(* New exception without any carried data *)
exception NewException
(* New exception that carries an int *)
exception BadNum of int

Under the hood, there is one exception type, `exn`. Conceptually, defining an exception adds it as a variant of the `exn` type.

## Raising exceptions

`raise` expressions throw an exception:

raise NewException
raise (BadNum -1)

`try...with...` expressions can catch exceptions (similar to `try/catch` blocks in Java).

try e with NewException -> 0
try e with BadNum n -> n

## Examples of using exceptions
To walk through an example:

exception NewException
(* Want data passed along with my exception *)
exception BadNum of int

let divide x y =
  match y with
  | 0 -> raise (BadNum 0)
  (* _ is a wildcard: it matches anything, but creates no binding *)
  (* like "else" in Racket/plait: fallback case *)
  | _ -> x / y

Running this code gives:

exception NewException
exception BadNum of int
val divide : int -> int -> int = <fun>
(* Normal, non-exception case *)
utop # divide 4 2 ;;
- : int = 2
(* Exception case *)
utop # divide 4 0 ;;
Exception: BadNum 0.
(* Catch the exception with try/with *)
utop # try (divide 4 0) with
| BadNum n -> 0 ;;
- : int = 0
(* Catching a different exception still raises *)
utop # try (divide 4 0) with
| NewException -> 0 ;;
Exception: BadNum 0.
(* But a non-exceptional case is still fine with the "wrong" one *)
utop # try (divide 4 2) with
| NewException -> 0 ;;
- : int = 2
utop # try (divide 4 0) with
| NewException -> 999999 ;;
Exception: BadNum 0.
(* We can use a wildcase if we don't care about the value *)
utop # try (divide 4 0) with
| BadNum _ -> 999999 ;;
- : int = 999999

Note: just the exception name produces a value, the exception, and does not interrupt control flow. We need to `raise` to actually take the exceptional path:

utop # NewException ;;
- : exn = NewException
utop # raise NewException ;;
Exception: NewException.

## Evaluation and typing rules for `raise`

:::info
We raise (throw) exceptions with `raise e`.

**Type-checking:**
- `e` must have type `exn`
- Result type is any type you want (!)

**Evaluation rules:**
- Do not produce a result (!)
- Stop with normal control flow
- Pass the exception produced by `e` to the nearest try expression on the call stack... (sort of like dynamic scope)
:::

## Evaluation and typing rules for `try/with`

:::info
`try... with ...` expressions can catch exceptions.

**Evaluation rules:**
- Evaluate `e1`
- But if `e1` raises an exception and that exception matches the pattern, then evaluate `e2` and that is the result
- Otherwise, `e1`'s value is the result

**Type-checking:** `e1` and `e2` must have the same type and that is the overall type.
:::

## More on pattern matching (re: Assignment 4)

Let's consider some more examples of interesting match statements (see the textbook for even more):

(* Constant (here, the empty list) matches, and creates no bindings *)
(* Wildcard matches anything, and creates no bindings *)
(*      - the same as "else" in Racket/plait*)
let rec length lst =
  match lst with
  | [] -> 0
  | _ :: t -> 1 + length t

(* Variable matches anything, but creates a binding *)
let rec length lst =
  match lst with
  | [] -> 0
  | ls -> 1 + length (List.tl ls)

(* We can match on multiple values at once, just using tuples *)
(* Tuple patterns recursively match *)
let multsign (x1,x2) =
  let sign_of_num x = if x=0 then Z else if x > 0 then P else N in
  match (sign_of_num x1, sign_of_num x2) with
  | (Z,_) -> Z
  | (_,Z) -> Z
  | (P,P) -> P
  | (N,N) -> P
  | _     -> N (* questionable style; we are okay with it*)

# Function composition

Sometimes, it's convenient to define a new function that combines a series of other functions.

Canonical example of combining functions:

let compose f g = fun x -> f (g x)

Creates a closure that “remembers” what `f` and `g` are bound to

The type is:

('b -> 'c) -> ('a -> 'b) -> ('a -> 'c)

We can define it as an infix operator like so (just a style thing, not specific to it being a closure):

let (%) = compose

Note: this is not predefined in OCaml, but you can copy the two lines that define it into your homework file to use it.

For example, the following are all equivalent, but the last option is arguably the easiest to read:

let sqrt_of_abs i = sqrt (float_of_int (abs i))

let sqrt_of_abs i = (sqrt % float_of_int % abs) i

let sqrt_of_abs = sqrt % float_of_int % abs

## Pipeline composition

Function composition with the `%` we just defined is **“right to left”**
- “take absolute value, convert to real, and take square root”
- “square root of the conversion to real of absolute value”

“Pipelines” of functions are common in functional programming and many programmers prefer to have a **left-to-right**
- Predefined exactly like this in OCaml: `|>`

let (|>) x f = f x
let sqrt_of_abs i = i |> abs |> float_of_int |> sqrt

# Type checking (Assignment 5!)

Recall from the start of our OCaml unit: what is the purpose of having static types?

Answers:
- Self-documenting
- Primary answer: prevent certain errors without even running the code. This can be especially useful when shipping code: static type checking covers all possible paths through the code (for all possible inputs). Dynamic checking only considers the paths that are actually taken. This means static types can help prevent customers seeing crashes "in the wild".
- Potentially optimized interpretation/compilation.

## Dynamic vs. Static type checking

Dynamic (Racket):
- Little/no static checking.
- May try to treat a number as a function during evaluation. Report error then.

Static (OCaml, Assignment 5 MiniLangT):
- Can reject a program before it runs to prevent possibility of some errors.
- Part of the language definition, not an implementation detail.

## Type checking analysis

To type check a expression, we can think of it as the following:

:::success
1. Either the expression has a type, in which case it "type checks".
:::

:::danger
2. Otherwise, the expression does not have a type, in which case it "does not type checking" or equivalently, "has a type error".
:::
### Let's consider some examples

Do the following OCaml expressions *type check*?

`1 + 2`

:::success
This one is easy, yes!
:::

`1.0 + 2`

:::danger
No, not in OCaml, we cannot `+` a float and an int.
:::

`(fun x -> x + 1) true`

:::danger
This one is a bit harder: it does not type check. How did we know that?
:::

We needed a *type environment* to know that `x` in the function body must have type bool. The type environment, also called a static environment, maps from variables to their type.

Our conclusion is that types let us sanity check code, *without* actually running the code. In the logical extreme, this makes type checking *much* more efficient than running code.

For example, code with an infinite loop takes an infinite amount of time when run under an interpreter: you never get an final value. But code with an infinite loop *can* be type checked, typically in linear time. Type checking only needs to look at each function (really, each expression) once, rather than every time it is dynamically executed.

# Assignment 5: simple type checking

For assignment 5, we'll focus on type checking a simple, statically typed language.

We'll use the following *typed* version of MiniLang: MiniLangT!

There are a few changes re: original MiniLang:
- Static types!
- No more `string` type/operations, no more `and`/`or`
- Multi-argument lambda functions and let

For simplicity, we will not have polymorphic types in MiniLangT.

How, then, do we assign a type to the following?

(lam (x) x)

We can't! Thus, we do need _type annotations_ on function arguments, for example:

(lam (x : Int) x)

# Group exercise

Part 1: Design an OCaml recursive variant type to represent the types of values in MiniLangT: numbers, booleans, lists, or functions. Lists should be homogeneous.

Part 2: Design an OCaml recursive variant type to represent the following cases of the grammar to an OCaml

<expr> ::= <num>
         | true
         | false
         | <var>
         | (+ <expr> <expr>)
         | (let ((<id> <expr>)+) <expr>)

## Solution

The full solution to these two problems will be given to you in the stencil code for Assignment 5 (but it's good practice to derive them yourself!)

For types, we'll add a `T` at the end to make it clear these are types. `BoolT` and `NumT` are the base cases. `ListT` and `FunT` need to be recursively defined, for their element types and argument/return types, respectively.

type typ =
  | NumT
  | BoolT
  (* Element type *)
  | ListT of typ
  (* Type of the argument, then return type *)
  | FunT of typ list * typ

(* Note: longer version provided in stencil code *)
type expr =
  | BoolE of bool
  | VarE of string
  (* OpE defined in the stencil code *)
  | OpE of operator * expr * expr
  (* variable, then expression, then body *)
  | LetE of string list * expr list * expr