What the Types Are For

01 — the shape

Three stanzas, not three imports

The Python architecture is legible from its import lines. Here it is declared: three small files say what the pieces are and which of them may see which.

ocaml/the dependency direction

  test/  test_pqueue.ml ──┐
                          ├──>  lib/  pqueue.mli   the contract
  bin/   solver.ml      ──┘            pqueue.ml    the implementation
         render.ml

The library depends on nothing in the lab. The executable and the tests both depend on the library, and never on each other. Two files describe that in full:

ocaml/lib/duneand ocaml/bin/dune

(library
 (name pqueue_lib)
 (modules pqueue))

(executable
 (name solver)
 (modules solver render)
 (libraries pqueue_lib unix))

(modules ...) decides membership. A file belongs to the stanza that names it — which is why tour.ml and homework.ml sit outside this directory entirely and are run with plain ocaml: they belong to no stanza and dune ignores them.
(libraries ...) is the only dependency we write. Not a list of files, and not an order. Dune reads the sources, works out which module needs which, and compiles them in an order we never state.
The test stanza is a third client, not a special case. test/dune declares (libraries pqueue_lib) exactly as the executable does. The tests see precisely what any other client sees — which is the point of the next section.

02 — the boundary

The interface is a file, and the compiler reads it

Python has _rev and _make: a leading underscore, which asks politely. OCaml has a second file, which does not ask.

ocaml/lib/pqueue.mliwhat a client may know

type 'a t                                 (* no definition given *)

val empty    : 'a t
val is_empty : 'a t -> bool
val enqueue  : 'a -> 'a t -> 'a t
val dequeue  : 'a t -> ('a * 'a t) option
val peek     : 'a t -> 'a option
val to_list  : 'a t -> 'a list
val of_list  : 'a list -> 'a t

The type is declared and never defined. Outside this module a queue has no fields, no representation and no shape: it can be produced only by empty and enqueue, and examined only through the seven functions listed. That the implementation happens to be a record of two lists is not hidden by convention — it is absent from what a client is given.

What this buys, concretely. Replace the two lists with a different representation tomorrow — a banker's queue with lazy tails, say, which is exactly session 5's repair — and every client compiles unchanged, because no client could have depended on the old shape. The compiler also checks the implementation against this file: a queue operation whose type drifts from the contract is a compile error in pqueue.ml, not a surprise in solver.ml.

The same discipline in Python is a naming convention that nothing enforces, and in Java a set of keywords — private, final — that enforce rather less than this one line does. The three are compared on the session page.

03 — the algorithm

The search never names a queue

One loop, written once. It puts positions somewhere and takes positions back out, and it does not know what the somewhere is.

ocaml/bin/solver.mlabridged

let rec loop frontier =
  match ops.take frontier with
  | None -> None                     (* nothing left to explore *)
  | Some (pos, frontier) ->
      (* settle pos, and collect its unvisited neighbours as `fresh` *)
      let frontier =
        List.fold_left (fun f p -> ops.put p f) frontier fresh in
      loop frontier

Three names appear from the container: ops.empty, ops.put, ops.take. The words queue and stack appear nowhere in the loop. Supply a queue and the loop is breadth-first; supply a stack and the very same loop is depth-first.

Note also what take returns: ('a * 'f) option — the element and the new frontier, or nothing at all. The loop cannot forget the empty case, and it cannot mutate the frontier it was handed. Every step names a new version, and the old ones remain valid — which is how --inspect can ask what the frontier held at step 40 without anything having been recorded.

04 — the frontier

A frontier is five functions — and a type

This is the one place where the OCaml version says something the Python version cannot.

ocaml/bin/solver.mlthe interface, as a type

type ('a, 'f) frontier_ops = {
  name    : string;
  empty   : 'f;
  put     : 'a -> 'f -> 'f;
  take    : 'f -> ('a * 'f) option;
  to_list : 'f -> 'a list;
}

Two type variables, and the second is the interesting one. 'a is what the frontier stores — here, positions. 'f is the frontier itself, and it differs between the two implementations:

the two frontierssame interface, different 'f

(* a position is an (int * int) pair -- row and column *)

queue_frontier : (int * int, (int * int) Pqueue.t) frontier_ops
stack_frontier : (int * int, (int * int) list)     frontier_ops

Because search is written for any 'f, it is incapable of depending on which one arrives. Not unlikely to; incapable. There is no cast to reach through the abstraction and no field to inspect, because within the loop the type 'f has no structure at all. The agnosticism the Python note describes as a discipline is here a property the compiler establishes before the program runs.

The stack needs no module behind it. queue_frontier is built from Pqueue; stack_frontier is built from nothing — its empty is [], its put is ::, and its take is a two-case match. OCaml's built-in list is the lecture's persistent stack, so the depth-first half of this lab is supplied by the language itself. That is also why --dfs runs before a single TODO is filled in.

A record whose fields are functions has a proper name, and gets it in session 5. For now it reads as a bundle of operations passed as one value.

05 — the wiring

What dune does, and one thing it is told not to do

No build order is written down. Dune reads the sources, derives the module graph and compiles what is needed. Adding a file to a stanza is the whole of adding a file.
_build/ is disposable. Everything dune produces lives there and nothing else is touched; deleting it costs a recompilation and nothing more.
Warnings are relaxed in the library, deliberately. lib/dune carries (flags (:standard -w -26-27-32)), which turns unused-variable and unused-value warnings off for that stanza only. Half-finished code compiles, so the tests can run and report which TODO is next instead of the compiler refusing the file. It is a teaching setting, not a style to copy: in the executable and the tests those warnings are on.

Build errors read bottom-up. When dune runtest fails, the first error is the one to read; the rest are usually its consequences. And an error reported in test_pqueue.ml about a type that does not match is nearly always a signature disagreement — the implementation drifting from pqueue.mli, which is the file to look at next.

06 — run it

Three commands

from ocaml/build, test, run

dune build
dune runtest

M=../mazes/medium.txt
dune exec bin/solver.exe -- $M --bfs
dune exec bin/solver.exe -- $M --dfs
dune exec bin/solver.exe -- $M --bfs --inspect=40

dune build compiles everything; dune runtest compiles and then runs the tests. The bare -- separates dune's own arguments from the program's: without it, --bfs would be read as an option to dune exec. All three solvers agree on mazes/medium.txt — 306 cells explored and a path of 75 for breadth-first — which is the cross-language check that the specification, not the language, decided the answer.