Lecture 15: Modularity cont.
---

:::warning
Announcements
- **Please sit in the first 2 rows of the room**.
- Quiz 2 Thursday, 11/6. [Page with practice quiz.](https://hackmd.io/@avh/BJpd6df1bx)
- Progress reports sent Friday, mid-semester survey **due Tuesday** for participation credit.
- Next help hours:
- Mine 6-8pm tonight, L037
- Grace's 1-2pm Weds., Zoom
:::
:::success
Agenda for today
- Modularity continued
- Signature matching rules
- Practicalities of OCaml files
- Differing implementations of data structures
:::

Recall from last class that a `signature` is the abstract specification of a `module type`. We saw informally that a `module` `M` type checks against a `signature` if it had all the necessary bindings, but let's consider this more explicitly.

## Signature Matching Rules

The type `type rational` in our previous example was *abstract*: the module specified that it existed, but not what the type is defined to be.

`module M : S` type-checks if:
1. Every non-abstract type in `S` is defined in `M`
2. Every abstract type in `S` is defined somehow
3. Every `val` in `S` appears in `M`
4. Every `exception` in `S` appears in `M`

The `struct` can have more internal bindings that are not exposed.

# OCaml modules and files

OCaml automatically provides implicit modules based on file names.

E.g., on your previous assignment, the file `a6.ml` defines an implicit:

module A6 = struct ... end

around the file contents.

For other files to use those functions, they either need to:

1. Specify the namespace with e.g., `A6.caching_assoc`.
2. Include an `open A6` to access the `A6` module's bindings *without* the module prefix.

## `.mli` files

If a file e.g. `a6.mli` is present in the same directory as `.ml`, then that file defines the interface for the `a6` module.

Implicitly, code in an `<modulename>.mli` that is not within an explicit `module type` has an *implicit*:

module type X = sig ... end

around the `.mli` contents.

OCaml then type-checks the implementation file `<modulename>.ml` against the implicit `sig` `X`.

Other code outside of those two files can then only access bindings exposed in the `.mli` file, with other code in `.ml` hidden.

If no `.mli` file is present, then no code is hidden.

## Using `open`

Using `open` is convenient for testing especially, when you can assume your functions are necessarily what you want to us.

In general, it's better to **not** call open on modules like `List`, since readers of your code should be able to easily tell that e.g. `fold_left` refers to the `List` module's definition.

## Alternative implementations

Different modules can share the same interface but differ internally.

This allows different implementations to be equivalent / interchangeable!

A key purpose of abstraction:
– Client typically cannot tell which implementation you are using, maximizing flexibility.
– Can improve/replace/choose implementations later.
– Easier with more abstract signatures (reveal only what you must, on a need-to-know basis).

## Functional data structures

module type STACK = sig
  type 'a t
  exception PopFromEmpty
  exception OutOfBounds
  val empty : 'a t
  val is_empty : 'a t -> bool
  val push : 'a -> 'a t -> 'a t
  val pop : 'a t -> ('a, a t)
  val nth : int -> 'a t -> 'a
end

# Group exercises: different stacks

:::success
Implement the `Stack` interface using a `'a list`. Call your module `Stack1`.

Note that this is a *functional* data structure: it returns new stacks, rather than mutating the passed in stack.

Discuss: what are the `O(...)` runtimes of each operation, where `n` is the number of elements on the stack?
:::

:::spoiler

module Stack1 : STACK = struct
    type 'a t = 'a list
    exception PopFromEmpty
    exception OutOfBounds

    (* O(1) *)
    let empty = []

    (* O(1) *)
    let is_empty s = (s = [])

    (* O(1) *)
    let push x s = x :: s

    (* O(1) *)
    let pop s = match s with
     | [] -> raise PopFromEmpty
     | x :: xs -> (x, xs)

    (* O(n) *)
    let rec nth i s =
    match (i, s) with
     | 0, x :: _ -> x
     | n, _ :: xs when n > 0 -> nth (n - 1) xs
     | _ -> raise OutOfBounds
end

:::

:::success
Imagine we care much more about the time efficiency of `nth` than the efficiency of `push`/`pop`. Discuss: what is another implementation you could use, other than `'a list`, that provides the fastest `O(...)` access for `nth`?

Check with me before you start implementing this alternative strategy. Call your module `Stack2`.
:::

:::spoiler

(* Use an array, copy on push/pop. Keep the array the same length as the stack.
  Note that you could also double the capacity of the array on writes, but this 
  is less useful here because the array needs to be copied anyway to match the 
  functional STACK interface.
*)
module Stack2 : STACK = struct
    type 'a t = 'a array
    exception PopFromEmpty
    exception OutOfBounds

    (* O(1) *)
     let empty = [||]

    (* O(1) *)
    let is_empty s = (s = [||])

    (* O(n) *)
    let push x s =
      Array.append s [|x|]

    (* O(n) *)
    let pop s =
      (* Uses array utilities, could also use loop *)
      let n = (Array.length s) - 1 in
      if n = 0 then raise PopFromEmpty else
      (s.(n), Array.sub s 0 n)

    (* O(1) *)
    let rec nth i s =
      if i < 0 || i >= (Array.length s) then raise OutOfBounds;
      s.(i)
end

:::

## Using alternative implementations

Your `Stack1` and `Stack2` both implement the module type:

module type STACK = sig
  ...
end

Clients can then choose to use either as a `STACK`.

However:

Stack1.push 1 Stack2.empty1

fails—the types are distinct! One uses a `list`, the other uses some composite type with an `array`.

This distinction is crucial for type system and module properties. Different modules have different internal invariants! And different type definitions!

E.g., `Stack1.push` looks like `Stack2.push`, but clients and type-checker do not know that they have different underlying implementations of `type 'a t`.

# Multiple type parameters

We can also have functional data structures that use multiple type parameters. For example, consider `Map` (analogous to dictionary in Python):

module type Map = sig
  exception KeyNotFound

  (* the type of maps that bind keys of type 'k to values of type 'v *)
  type ('k, 'v) t

  (* empty produces a new map with no keys and values *)
  val empty  : ('k, 'v) t

  (* (insert k v m) produces a map with all the key value pairs in m, that
  additionally maps k to v. If k was already mapped in m, v should supersede
  the old binding. *)
  val insert : 'k -> 'v -> ('k, 'v) t -> ('k, 'v) t

  (* (lookup k m) produces they value k maps to in m. Raises: KeyNotFound if k
  is not mapped in m. *)
  val lookup : 'k -> ('k, 'v) t -> 'v

Assignment 7: Modularity (after Quiz 2) will have you work with different implementations of `Map`s.