Modular Programming

INF 441 - TD 4

 Login :  Mot de passe :

Setup

If you already have a version of OCaml ≥ 4.02.3, skip this section.

We will first need to set up to use OCaml version 4.02.3 or later. By default, the computers in the salles info are set up to use 3.10.2.

  1. Go to Window > Preferences and type in paths in the search box. Select OcaIDE > Paths. In the OCaml Binaries Directory field type in:
    /usr/local/ocaml-4.02.3/bin
    then click on apply next to browse.
  2. Scroll down to the field of camlp4 and delete its contents.
  3. Scroll down to the field OCaml lib path and change it to:
    /usr/local/ocaml-4.02.3/lib
  4. Click on Ok.
  5. If you already have a project open, you will have to recompile everything. Use Project > Clean.
  6. If you already have an OCaml toplevel open, close it by clicking on the X icon, and then open a new one from Window > Show View > OCaml Toplevel. You should see it print OCaml version 4.02.3 before the # prompt.

Context: a graph library

This TD is designed to introduce you to the OCaml module system. During this TD you will build a flexible graph library that achieves a high level of modularity and genericity by exploiting the module system, particularly the notion of a higher-order module, also known as a functor.

The core idea of a graph is a set of vertices and a set of edges linking pairs of vertices. However, there are many variations of this idea depending on different choices of attributes for representing graphs, some of which we list below in the table.

Edges: Directed Undirected
Labeled Unlabeled
Weighted Unweighted
Vertices: Labeled Unlabeled
Usage Mode: Persistent Imperative
Density: Sparse Dense

It is beneficial to represent each of these possibilities with a different data structure that exploits its specific features. Nevertheless, we would like to derive common algorithms such as traversal and finding spanning trees regardless of which graph is being used. In this TD we will explore a few of these variations with an eye towards writing modular code. Our aim is to be flexible and reuse as much code as possible without sacrificing efficiency.

Warmup: from polymorphic types to functors

Let us begin by exploring the isomorphism between polymorphic types and functors that you have already seen in Amphi 4. This warmup exercise will familiarize you with module types and functors, in particular how to instantiate abstract types. Consider the following type of a printer and a small collection of obvious printers.

type 'a printer = 'a -> string

let p_int  : int printer = string_of_int ;;
let p_bool : bool printer = string_of_bool ;;
let p_pair : 'a printer -> 'b printer -> ('a * 'b) printer =
  fun pa pb (x, y) ->
    String.concat "" ["(" ; pa x ; "," ; pb y ; ")"] ;;

We are going to recast this code in the form of a collection of modules and functors.

  1. Create a file print.ml and start by defining the module type of printers.
    module type Printer = sig
      type t
      val print : t -> string
    end
  2. Complete the definition of the following modules.
    module IntPrinter  : Printer with type t = int  = struct (* ... *) end
    module BoolPrinter : Printer with type t = bool = struct (* ... *) end
    Note the specific use of the with type declaration that instructs OCaml to instantiate the abstract type t in Printer with a concrete type (int, bool, etc.).
  3. Complete the definition of the following functor.
    module PairPrinter (P1 : Printer) (P2 : Printer) : Printer with type t = P1.t * P2.t =
    struct (* ... *) end
    What is the type of let module M = PairPrinter(IntPrinter)(BoolPrinter) in M.print?
  4. Write this functor using your own design for the output:
    module ListPrinter (P : Printer) : Printer with type t = P.t list =
    struct (* ... *) end
  5. Complete this function using your printer modules above:
    let p_listpairintbool : (int * bool) list -> string =
      let module P = (* ... *) in
      P.print
    You are only allowed to modify the module declaration and you must use the modules and functors you defined earlier.
  6. What would happen if you were to change all the instances of with type t = ... to with type t := ... in the above module declarations? Try it now. This latter form performs a replacement instead of adding a new type abbreviation, so the old abstract type name becomes inaccessible.
Submit print.ml

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

Graph traversal

The module type Printer above defines a type t that is endowed with a print function. It can be seen as a kind of contract for modules ascribing to that signature. There are a number of such contracts that will be useful for us, so let us collect them together in the module Cs, written in the file cs.ml:

module type Ordered = sig
  type t
  (** compare x y : positive if x > y, 0 if x = y, negative if x < y *)
  val compare : t -> t -> int
end

module type Hashable = sig
  type t
  val hash : t -> int
  val equal : t -> t -> bool
end

(* combination of Ordered and Hashable *)
module type Comparable = sig
  include Ordered
  include Hashable with type t := t
end

Module types are always compared structurally: if two module types have the same contents, then they are considered the same even if their names differ. This has some useful consequences: the Hashable module type is the same as Hashtable.HashedType from the OCaml standard library, as are Ordered and Set.OrderedType. Thus, if you want to create a hashtable out of a Hashable you can use Hashtbl.Make, and likewise you can use Set.Make and Map.Make from the standard library with modules implementing Ordered.

  1. Create the file traverse.ml containing:
    open Cs
    
    module type Graph = sig
      (* the type of graphs *)
      type t
    
      module V : Cs.Hashable
      type vertex = V.t
    
      (* run a fold over the immediately reachable vertices from a given vertex *)
      val fold_succ : (vertex -> 'acc -> 'acc) -> t -> vertex -> 'acc -> 'acc
    end
    
    module type Traverse = functor (G : Graph) -> sig
      val traverse : G.t -> G.vertex -> G.vertex list
    end
    Traverse is a higher-order module type, i.e., the module type of a functor.
  2. Complete the implementation of the following functor in traverse.ml.
    module Dfs : Traverse = (* ... *)
    Its traverse function should perform a depth-first traversal of the graph starting from the given vertex. (Recall that in a depth-first traversal, the successors of the current node are visited before sibling nodes.) The output should be all the vertices reached from the starting vertex in the order that it was first visited by a depth-first traversal.
  3. Complete the implementation of the following module in traverse.ml.
    module Bfs : Traverse = (* ... *)
    Its behavior is very similar to Dfs, except the vertices are visited in breadth-first order. (Recall that in breadth-first order, all the nodes at a given distance from the source are visited before any farther nodes.) You may find it useful to use the queue you wrote in TD 3, or you can use the Queue module from the OCaml standard library.
  4. Optional: Extend the Traverse module type with a new function:
    val fold : (G.vertex -> 'acc -> 'acc) -> G.t -> G.vertex -> 'acc -> 'acc
    that performs a fold over the visited vertices instead of returning a list of them. Update Bfs and Dfs accordingly.
Submit traverse.ml

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

You may be wondering how you can test the functors you wrote in traverse.ml. Let us try it with a graph containing numbered vertices.

  1. Create a file traverse_test.ml that starts as follows.
    open Cs
    open Traverse
    
    module Graph = struct
       module V = struct
         type t = int
         (* ... *)
       end
       type vertex = V.t
    
       type t = (vertex * vertex list) list
    
       (* ... *)
    end
    
    module DfsTest = Dfs(Graph)
    module BfsTest = Bfs(Graph)
  2. Complete the missing implementation of the Graph module.
  3. Test your traversals on the following graph. Iterate over the starting vertices. (Hint: you can use your Printer.ListPrinter functor to print out the list of vertices.)
    Example graph for traversal
Submit traverse_test.ml

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

Paths

So far we have not needed to deal with edges directly. Suppose we have edges of different lengths and we want to find the shortest path between two vertices. What more information should we add into our graphs to support this? One way to do this is to have a means of converting edges to weights.

  1. Create the file paths.ml with the following initial contents.
    open Cs
    
    module type Weight = sig
      type t
      val to_int : t -> int
    end
    
    module type Graph = sig
      type t
    
      module V : Cs.Hashable
      type vertex = V.t
    
      module E : sig
        type t
    
        val dest   : t -> vertex
      end
      type edge = E.t
    
      (* run a fold over the edges that go out of a given vertex *)
      val fold_succ_e : (edge -> 'acc -> 'acc) -> t -> vertex -> 'acc -> 'acc
    end
    
    module type Paths = functor (G : Graph) (Wt : Weight with type t = G.E.t) -> sig
      (* find g v0 v1 : find a path between v0 and v1 in g *)
      (* raise Not_found if no path exists *)
      val find : G.t -> G.vertex -> G.vertex -> G.edge list
    end
  2. Implement the following module.
    module Shortest : Paths
    Note that in order to get the length (“weight”) of an edge, it suffices to call Wt.to_int on the edge.
    Submit paths.ml

    Le nom du fichier à déposer
    Il faut se connecter avant de pouvoir déposer

  3. To test it, create paths_test.ml that tries to find the shortest paths between all pairs of vertices in the following graph.
    Example graph for paths
    Remember to instantiate with a suitable Graph such that it is possible to compute the weights of the edges.
    Submit paths_test.ml

    Le nom du fichier à déposer
    Il faut se connecter avant de pouvoir déposer

  4. Think of what implicit assumptions you may have made. Can you handle:
    • Multiple edges between a given pair of vertices?
    • Loops?
    • Negative lengths?

Spanning trees

A spanning forest of a graph is a forest (i.e, a collection of trees) built from the edges of the graph that connects all the nodes. In order to compute the spanning forest of the graph, we will use Kruskal's algorithm, which proceeds as follows.

  1. Start by putting every vertex in its own connected set.
  2. While there are edges remaining:
    1. Pick an edge.
    2. If it connects vertices in the same component, discard it.
    3. Otherwise add it to the spanning forest and equate the sets corresponding to the source and destination.

The file uf.ml contains an implementation of union-find for representing sets of things. It has the following module type.

type set

(** create a new set *)
val create : unit -> set

(** combine two sets *)
val unite : set -> set -> unit

(** find an identifier of a set. After a (unite s1 s2), it must be the case
    that (id s1) = (id s2). *)
val id : set -> int
  1. Create the file spanning_tree.ml that contains:
    module type Graph = sig
      type t
    
      type vertex (* ... *)
      type edge (* ... *)
    
      (* ... *)
    end
    
    module type Tree = functor (G : Graph) -> sig
      val spanning : G.t -> G.edge list
    end
    The spanning function merely returns the edges in a spanning forest of the input graph. We are giving you a lot of freedom to define the Graph module type. Try to keep it as minimal as you can.
  2. Implement:
    module Kruskal : Tree
    Submit spanning_tree.ml

    Le nom du fichier à déposer
    Il faut se connecter avant de pouvoir déposer

  3. Test your implementation in spanning_tree_test.ml on the following graph.
    Example graph for spanning trees
    Submit spanning_tree_test.ml

    Le nom du fichier à déposer
    Il faut se connecter avant de pouvoir déposer

  4. Optional: Modify the Tree module type to add the following additional type and function:
    type tree = {
      root : G.vertex ;
      kids : (G.edge * tree) list ;
    }
    
    val spanning_forest : G.t -> tree list
    Then, modify your implementation of Kruskal to match. Submit it using the input box above.

Putting it together

As you may have realized by now, we have been writing graph algorithms by assuming just what we need from our graph structures. If we can keep all these assumptions compatible across the various algorithms, then we can use the same graph module for each of them. In this section we will start to create such a canonical graph module.

Create graph.ml to store the signature of vertices, edges, and graphs:

open Cs

module type Vertex = sig
  type t

  (* all vertices are comparable *)
  include Comparable with type t := t
end

module type Edge = sig
  type t

  (* all edges are ordered *)
  include Ordered with type t := t

  type vertex
  val source : t -> vertex
  val dest   : t -> vertex

  type label
  val label  : t -> label

  (** edge src lab dst : edge with source src, dest dst, label lab *)
  val edge : vertex -> label -> vertex -> t
end

module type Graph = sig
  type t

  module V : Vertex
  type vertex = V.t

  module E : Edge with type vertex = V.t
  type edge = E.t

  val is_empty : t -> bool
  val cardinality_v : t -> int (* how many vertices? *)
  val cardinality_e : t -> int (* how many edges? *)

  (* Both the following raise Invalid_argument if
     the vertex is not in the graph *)
  val in_degree : t -> vertex -> int
  val out_degree : t -> vertex -> int

  (** mem_v g v : is v in g? *)
  val mem_v : t -> vertex -> bool

  (** mem_e g e : is e in g? *)
  val mem_e : t -> edge -> bool

  (** is_adj g v1 v2 : is v2 reachable with one edge from v1? *)
  val is_adj : t -> vertex -> vertex -> bool

  (* folds *)

  (** fold_v f g acc = fold f over all vertices in g using acc *)
  val fold_v : (vertex -> 'acc -> 'acc) -> t -> 'acc -> 'acc

  (** fold_e f g acc = fold f over all edges in g using acc *)
  val fold_e : (edge -> 'acc -> 'acc) -> t -> 'acc -> 'acc

  (** fold_succ f g v acc = fold f over the successor vertices of v in g using acc *)
  val fold_succ : (vertex -> 'acc -> 'acc) -> t -> vertex -> 'acc -> 'acc

  (** fold_succ_e f g v acc = fold f over the out edges of v in g using acc *)
  val fold_succ_e : (edge -> 'acc -> 'acc) -> t -> vertex -> 'acc -> 'acc

  (** fold_pred f g v acc = fold f over the predecessor vertices of v in g using acc *)
  val fold_pred : (vertex -> 'acc -> 'acc) -> t -> vertex -> 'acc -> 'acc

  (** fold_pred_e f g v acc = fold f over the in edges of v in g using acc *)
  val fold_pred_e : (edge -> 'acc -> 'acc) -> t -> vertex -> 'acc -> 'acc

  (* iterators *)

  val iter_v : (vertex -> unit) -> t -> unit
  val iter_e : (edge -> unit) -> t -> unit
  val iter_succ : (vertex -> unit) -> t -> vertex -> unit
  val iter_succ_e : (edge -> unit) -> t -> vertex -> unit
  val iter_pred : (vertex -> unit) -> t -> vertex -> unit
  val iter_pred_e : (edge -> unit) -> t -> vertex -> unit
end
  1. Create graph_test.ml and write a module that implements the module type Graph.Graph. You have considerable leeway in designing how you want to represent graphs:
    • The maximum number of edges is O(V2) where V is the number of vertices. If you expect nearly that many edges, which means that the graph is dense, you may consider a V×V matrix of edge labels to store the edges. This is sometimes called an adjacency matrix and is an example of a dense representation.
    • Alternatively, if you do not expect that nearly every pair of vertices has an edge between them, you can pick a sparse representation. For instance, for each vertex you can maintain a list of predecessor and successor vertices. (Don't forget the edge labels!)
    • Optional: if you are feeling clever, consider switching between the two representations when the number of edges crosses some threshold, such as V1.5.
  2. Test your module with Traverse.Dfs, Traverse.Bfs, Paths.Shortest, and Spanning_tree.Kruskal. The first three should be fine since we gave you Graph module types that were subtypes of Graph.Graph. For Spanning_tree.Kruskal you may have created an incompatible Graph module type, in which case you have to change spanning_tree.ml.
Submit graph.ml

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

Optional: Graph builders

Now that you have a full Graph module, you can start building graphs. Create a file builder.ml with the following.

  1. Imagine we are in a situation where we want to make persistent (i.e., functional) graphs. Consider the following module type (which you can put in a separate digraph.ml file).
    open Cs
    open Graph
    
    module type Digraph = struct
      include Graph
    
      val empty : t
    
      val add_vertex : t -> vertex -> t
      val add_edge   : t -> edge -> t
    
      val remove_vertex : t -> vertex -> t
      val remove_edge   : t -> edge -> t
    end
  2. Write a functor:
    module Digraph (V : Vertex) (E : Edge with type vertex = V.t)
    : Digraph with module V = V with module E = E = struct
      (* ... *)
    end
  3. Write the following module:
    module type Builders =
      functor (G : Digraph with type V.t = int
                           with type E.label = int) ->
    sig
      val vertices : int -> G.t
      val full : int -> G.t
      val divisors : int -> G.t
    end
    
    module Builders : Builders = struct
      (* ... *)
    end
    • vertices n creates a graph of n vertices and no edges. Label the vertices 0 to n - 1.
    • full n creates a graph with n vertices and edges back and forth between all pairs of vertices. Label each vertex with integers from 0 to n - 1, and label the edge between vertex i and j with j * n + i.
    • divisors n creates a graph with n vertices labeled 2 to n + 1. Add an edge from the vertex labeled i to the vertex labeled j if j mod i = 0.
Submit digraph.ml

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

Optional: Imperative vs. Persistent

  1. Now imagine we are in a situation where we are working with imperative graphs, i.e., graphs whose structure can change. Consider the following module type (which you can put in digraph_imp.ml).
    module type Digraph_imp = sig
      include Graph
    
      val empty : unit -> t
    
      val add_vertex : t -> vertex -> unit
      val add_edge : t -> edge -> unit
    
      val remove_vertex : t -> vertex -> unit
      val remove_edge : t -> edge -> unit
    
      (** copy g : create a copy of g such that modifications to g
          do not affect the copy. *)
      val copy : t -> t
    end
  2. Write an imperative version of Builders in digraph_imp.ml.
  3. How would you minimize duplication of code by sharing as much of the builder code as possible between the imperative and functional versions? Would you have functorized your code in a different way?
Submit digraph_imp.ml

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

Optional: A library of graph operations

Imagine that we want to implement a collection of operations on graphs that is captured by the following module type.

module type Graph_ops = sig
  type graph

  (** union g1 g2 = graph with all vertices and edges in either g1 or g2 *)
  val union : graph -> graph -> graph

  (** intersection g1 g2 = graph with all vertices and edges in both g1 and g2 *)
  val intersection : graph -> graph -> graph

  (* mirror g = graph where all edges are turned around *)
  val mirror : graph -> graph

  (** complement g = graph with edges where g doesn't have an edge *)
  val complement : graph -> graph
end
  1. Write two implementations of Graph_ops, one each targeting the imperative and the functional directed graphs. Remember to instantiate the types correctly.
  2. (How) would you functorize your code differently to minimize duplication between the imperative and functional variants?
Submit graph_ops.ml

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer