An implementation in Rust of the examples from the OCaml manual chapter on modules and funtors

functor.rs

//! This file is a translation of the example code in the OCaml manual
//! chapter two,"The module system", into Rust code.
//!
//! The intent is to translate as directly as possible, to show OCaml
//! users a way to implement their functionality. This means that
//! later, more complex sections are neither idiomatic Rust nor a
//! perfect translation of the OCaml. Further study would be required,
//! but hopefully this helps explain some of the concepts.
//!
//! There are two constructs in Rust that might match OCaml modules,
//! namespaces (called "modules" in Rust) and implementations of types
//! and traits. Rust modules are concrete code blocks and generally
//! distinguish files from one another in a project (called a "crate"
//! in Rust). Types may have functions "implemented" on them, and may
//! also be polymorphic in a type variable. Traits function as
//! interfaces to types, allowing greater flexibility with their own
//! type variables and associated types. Traits must be implemented
//! for types, providing the code and optionally some type variables.
//!
//! Rust is actually capable of more abstraction than was used in
//! these examples. Traits, which correspond to OCaml signatures, may
//! themselves be parametrized. Trait parameterizations are best used
//! for behavior abstractions, while type parameterizations are for
//! data abstractions. This separation is an important feature of the
//! user-defined type system in Rust. Using a parametrized trait, Rust
//! code may emulate type functions (rather than the type constructors
//! use below). This is demonstrated below. The syntax is terrible, but
//! the use is pretty straight-forward.
//!
//! All the abstractions used below are _static_, or handled at
//! compile-time. This is preferred in Rust where possible, because it
//! makes for faster code. Dynamic dispatch is available, by binding
//! or taking as a parameter a variable with a trait as its type.
//! Theses are called "trait objects" and usually "boxed", or after a
//! pointer. More complex use of OCaml modules would require trait
//! objects to handle the run-time variability. 
//!
//! Rust code cannot have static visibility (OCaml's concrete vs
//! abstract types within modules) changed at run-time. At compile-time,
//! traits with different visibility could be defined, but conversion
//! would be difficult if even possible.
//!
//! The first section of the manual introduces modules without
//! abstraction. Rust modules are sufficient for this use, and
//! demonstrated in the translation. The rest of the manual deals with
//! signatures and functors, which require types and traits.
//! 
//! Most of the code can be translated line-for-line, but there are a
//! few major differences between the languages. Rust makes pointers
//! and data copying explicit, so references, dereferences and calls to
//! `clone()` appear in the Rust code. Rust also lacks exceptions,
//! so code returns the sum type `Result<SuccessType,FailureType>`.

/// allows `<A:OCaml>` rather than <A:Clone+PartialEq+Eq>`
pub trait OCaml : Clone + PartialEq + Eq {}
impl<A:Clone+PartialEq+Eq> OCaml for A {}

/// Compile-time example from the OCaml manual 2.1
///
/// "A primary motivation for modules is to package together related definitions..."
/// ```ocaml
/// module PrioQueue =
///   struct
///     type priority = int
///     type 'a queue = Empty | Node of priority * 'a * 'a queue * 'a queue
///     let empty = Empty
///     let rec insert queue prio elt =
///       match queue with
///         Empty -> Node(prio, elt, Empty, Empty)
///       | Node(p, e, left, right) ->
///           if prio <= p
///           then Node(prio, elt, insert right p e, left)
///           else Node(p, e, insert right prio elt, left)
///     exception Queue_is_empty
///     let rec remove_top = function
///         Empty -> raise Queue_is_empty
///       | Node(prio, elt, left, Empty) -> left
///       | Node(prio, elt, Empty, right) -> right
///       | Node(prio, elt, (Node(lprio, lelt, _, _) as left),
///                         (Node(rprio, relt, _, _) as right)) ->
///           if lprio <= rprio
///           then Node(lprio, lelt, remove_top left, right)
///           else Node(rprio, relt, left, remove_top right)
///     let extract = function
///         Empty -> raise Queue_is_empty
///       | Node(prio, elt, _, _) as queue -> (prio, elt, remove_top queue)
///   end;;
/// ```
pub mod prio_queue {
  // modules do not have full access to outer scope by default
  use super::OCaml;
  // needed for shared data structures
  use std::rc::Rc;
  // avoids explicit scoping, contrary to idiomatic Rust
  use self::Queue::*;

  pub type Priority = i32;
  #[derive(Clone, PartialEq, Eq)]
  pub enum Queue<A:OCaml> { Empty, Node(Priority,A,Rc<Queue<A>>,Rc<Queue<A>>) }
  pub fn empty<A:OCaml>() -> Queue<A> { Empty }
  pub fn insert<A:OCaml>(queue: &Queue<A>, prio: Priority, elt:&A) -> Queue<A> {
    match *queue {
      Empty => Node(prio, elt.clone(), Rc::new(Empty), Rc::new(Empty)),
      Node(p,ref e,ref left,ref right) => {
        if prio <= p {
          Node(prio, elt.clone(), Rc::new(insert(&**right, p, e)), left.clone())
        } else { Node(p, e.clone(), Rc::new(insert(&**right, prio, elt)), left.clone()) }
      }
    }
  }
  #[derive(Debug)]
  pub enum Exception { QueueIsEmpty }
  pub(super) fn remove_top<A:OCaml>(q: &Queue<A>) -> Result<Queue<A>,Exception> { match *q {
    Empty => Err(Exception::QueueIsEmpty),
    Node(_, _, ref left, ref right) if **right == Empty => Ok((**left).clone()),
    Node(_, _, ref left, ref right) if **left == Empty => Ok((**right).clone()),
    Node(_, _, ref left, ref right) => match (&**left, &**right) {
      (&Node(lprio, ref lelt, _,_),&Node(rprio, ref relt,_,_)) => {
        if lprio <= rprio {
          Ok(Node(lprio, lelt.clone(), Rc::new(remove_top(&**left)?), right.clone()))
        } else { Ok(Node(rprio, relt.clone(), left.clone(), Rc::new(remove_top(&**right)?))) }
      } _ => unreachable!() //needed inner `match` to handle patterns into linked structure
    }
  }}
  pub fn extract<A:OCaml>(q: &Queue<A>) -> Result<(Priority, A, Queue<A>),Exception> { match *q {
    Empty => Err(Exception::QueueIsEmpty),
    Node(prio, ref elt, _, _) => Ok((prio, elt.clone(), remove_top(q)?)),
  }}
}

/// Compile-time example from OCaml manual 2.1
///
/// "It is also possible to copy the components of a module inside another module..."
/// ```ocaml
/// module PrioQueueOpt =
///   struct
///     include PrioQueue
///     let remove_top_opt x =
///       try Some(remove_top x) with Queue_is_empty -> None
///     let extract_opt x =
///       try Some(extract x) with Queue_is_empty -> None
///   end;;
/// ```
pub mod prio_queue_opt {
  use super::OCaml;

  pub use prio_queue::*;
  #[allow(unused)]
  pub(super) fn remove_top_opt<A:OCaml>(q: &Queue<A>) -> Option<Queue<A>> {
    // to check the exception
    match remove_top(q) {
      Err(Exception::QueueIsEmpty) => None,
      Ok(res) => Some(res),
    } 
  }
  pub fn extract_opt<A:OCaml>(q: &Queue<A>) -> Option<(Priority, A, Queue<A>)> {
    // shortcut if you don't need to check the exception
    extract(q).ok()
  }
}

/// Runtime-examples from OCaml manual 2.1
///
/// ```ocaml
/// PrioQueue.insert PrioQueue.empty 1 "hello";;
/// open PrioQueue;;
/// insert empty 1 "hello";;
///
/// let empty = []
/// open PrioQueue;;
/// let x = 1 :: empty ;;
///  
/// let open PrioQueue in
/// insert empty 1 "hello";; 
/// ````
/// 
/// This code shows off different syntax for accessing module functions.
/// It has no equivalent in Rust
/// ```ocaml
/// PrioQueue.[empty] = PrioQueue.([empty]);;
///
/// PrioQueue.[|empty|] = PrioQueue.([|empty|]);;
///
/// PrioQueue.{ contents = empty } = PrioQueue.({ contents = empty });;
///
/// PrioQueue.[insert empty 1 "hello"];;
/// ```
fn sec1() {
  // this is altered to show that `prio_queue_opt` contains the items
  // from `prio_queue`, and that the two are compatible
  prio_queue_opt::insert(&prio_queue::empty(), 1, &"hello".to_string());
  use prio_queue::*;
  insert(&empty(),1,&"hello".to_string());

  // this function causes an error in the
  // _previous_ line, but not the next!
  // fn empty() -> () { () }

  {
    use prio_queue::*;
    insert(&empty(),1,&"hello".to_string());
  }
}

/// Compile-time example from OCaml manual 2.2
/// 
/// ```ocaml
/// module type PRIOQUEUE =
///     sig
///       type priority = int         (* still concrete *)
///       type 'a queue               (* now abstract *)
///       val empty : 'a queue
///       val insert : 'a queue -> int -> 'a -> 'a queue
///       val extract : 'a queue -> int * 'a * 'a queue
///       exception Queue_is_empty
///     end;;
/// ```
pub trait PrioQueueSig where Self:Sized {
  // Concrete types cannot be defined here, use an external definition
  // for types Priority and Exception

  // In Rust we have a self type, which can naturally assume the role
  // of the OCaml `'a queue` (or more generally, Module.t). That
  // leaves us with just the `'a` needing a definition.
  type A : OCaml;
  fn empty() -> Self;
  fn insert(&self, Priority, &Self::A) -> Self;
  fn extract(&self) -> Result<(Priority, Self::A, Self),Exception>;
}

// The following are implementations for using a Rust type like an OCaml
// module. Normally, the code above would be here, but it's all correctly
// typed so we can just call back to it.
pub type Priority = prio_queue::Priority;
pub type Exception = prio_queue::Exception;
pub type PrioQueue<A> = prio_queue::Queue<A>;
impl<A:OCaml> PrioQueueSig for PrioQueue<A> {
  type A = A;
  fn empty() -> Self { prio_queue::empty() }
  fn insert(&self, p: Priority, elt: &A) -> Self {
    prio_queue::insert(&self, p, elt)
  }
  fn extract(&self) -> Result<(Priority, Self::A, Self),Exception> {
    prio_queue::extract(&self)
  }
}
// This is not part of the sig, but part of the original
impl <A:OCaml> PrioQueue<A> {
  pub fn remove_top(&self) -> Result<Self,Exception> {
    prio_queue::remove_top(&self)
  }
}

/// Run-time examples from OCaml manual 2.2
///
/// ```ocaml
/// module AbstractPrioQueue = (PrioQueue : PRIOQUEUE);;
/// AbstractPrioQueue.remove_top ;;
/// AbstractPrioQueue.insert AbstractPrioQueue.empty 1 "hello";;
/// ```
///
/// This section is a bit different in Rust, because visibility cannot
/// be adjusted in this way. You can reduce visibility within a function
/// that takes the type (analog to OCaml module) as a parameter. However,
/// this reduces the visibility to the compiler as well, so it cannot
/// use the concrete type, even if it's passed to the function. This
/// issue is present in OCaml in other situations and will be demonstrated
/// in a later section.
///
/// Finally, the trait (analog to OCaml sig) can be used directly as if
/// it were an abstract type, but Rust's type inference is not able to
/// handle this situation without a type annotation, since it's the
/// compiler that chooses the implementation.
fn sec2() {
  #[allow(path_statements)] // supress warning generated in body
  fn reduce_visibility<AbstractPrioQueue:PrioQueueSig>() {
    // error: function not found
    // AbstractPrioQueue::remove_top;

    // warning: no effect
    AbstractPrioQueue::insert;

    // types don't match because of abstraction, solution in later section
    // AbstractPrioQueue::insert(&AbstractPrioQueue::empty(), 1, &"hello".to_string());
  }
  reduce_visibility::<PrioQueue<String>>();

  // Rust requires an annotation here
  let _:PrioQueue<String> = PrioQueueSig::insert(&PrioQueueSig::empty(),1,&"hello".to_string());
}

/// Compile-time example from OCaml manual 2.2
///
/// ```ocaml
/// module type PRIOQUEUE_WITH_OPT =
///   sig
///     include PRIOQUEUE
///     val extract_opt : 'a queue -> (int * 'a * 'a queue) option
///   end;;
/// ```
trait PrioQueueSiGWithOpt : PrioQueueSig {
  fn extract_opt(&self) -> Option<(Priority,Self::A,Self)>;
}
impl<A:OCaml> PrioQueueSiGWithOpt for PrioQueue<A> {
  fn extract_opt(&self) -> Option<(Priority,Self::A,Self)>{
    prio_queue_opt::extract_opt(&self)
  }
}

/// Compile-time example from OCaml manual 2.3
///
/// ```ocaml
/// type comparison = Less | Equal | Greater;;
/// module type ORDERED_TYPE =
///   sig
///     type t
///     val compare: t -> t -> comparison
///   end;;
/// module Set =
///   functor (Elt: ORDERED_TYPE) ->
///     struct
///       type element = Elt.t
///       type set = element list
///       let empty = []
///       let rec add x s =
///         match s with
///           [] -> [x]
///         | hd::tl ->
///            match Elt.compare x hd with
///              Equal   -> s         (* x is already in s *)
///            | Less    -> x :: s    (* x is smaller than all elements of s *)
///            | Greater -> hd :: add x tl
///       let rec member x s =
///         match s with
///           [] -> false
///         | hd::tl ->
///             match Elt.compare x hd with
///               Equal   -> true     (* x belongs to s *)
///             | Less    -> false    (* x is smaller than all elements of s *)
///             | Greater -> member x tl
///     end;;
/// module OrderedString =
///   struct
///     type t = string
///     let compare x y = if x = y then Equal else if x < y then Less else Greater
///   end;;
/// ```
pub mod ordered_type {
  use std::rc::Rc;
  use super::OCaml;

  pub enum Comparison { Less, Equal, Greater }
  /// The property of a type with an inherent order
  pub trait OrderedType {
    fn compare(&self, other:&Self) -> Comparison;
  }
  /// Rust lacks cons-lists, they're not efficent and they're easily defined
  #[derive(Clone,PartialEq,Eq)]
  pub enum Set<A> { Nil, Cons(A,Rc<Set<A>>) }

  impl<Elt:OCaml+OrderedType> Set<Elt> {
    pub fn empty() -> Self { Set::Nil }
    pub fn add(&self, x:Elt) -> Self {
      match self {
        &Set::Nil => Set::Cons(x,Rc::new(Set::Nil)),
        &Set::Cons(ref hd,ref tl) => {
          match Elt::compare(&x,hd) {
            Comparison::Equal => self.clone(),
            Comparison::Less => Set::Cons(x,Rc::new(self.clone())),
            Comparison::Greater => Set::Cons(hd.clone(), Rc::new(tl.add(x))),
          }
        }
      }
    }
    pub fn member(&self, x:&Elt) -> bool {
      match self {
        &Set::Nil => false,
        &Set::Cons(ref hd,ref tl) => {
          match Elt::compare(x,hd) {
            Comparison::Equal => true,
            Comparison::Less => false,
            Comparison::Greater => tl.member(x)
          }
        }
      }
    }
  }
  impl OrderedType for String {
    fn compare(&self, other:&Self) -> Comparison {
      if self == other { Comparison::Equal }
      else if self < other { Comparison::Less }
      else { Comparison::Greater }
    }
  }
}

/// Run-time example from OCaml manual 2.3
///
/// ```ocaml
/// module StringSet = Set(OrderedString);;
/// StringSet.member "bar" (StringSet.add "foo" StringSet.empty);;
/// ```
fn sec3() {
  use ordered_type::*;

  // in Rust this is a simple alias, and not worth writing here
  // type StringSet = Set<String>;

  Set::empty().add("foo".to_string()).member(&"bar".to_string());
}


/// Compile-time examples from OCaml manual 2.4
///
/// ```ocaml
/// module type SETFUNCTOR =
///   functor (Elt: ORDERED_TYPE) ->
///     sig
///       type element = Elt.t      (* concrete *)
///       type set                  (* abstract *)
///       val empty : set
///       val add : element -> set -> set
///       val member : element -> set -> bool
///     end;;
/// 
/// module type SET =
///   sig
///     type element
///     type set
///     val empty : set
///     val add : element -> set -> set
///     val member : element -> set -> bool
///   end;;
///   
/// module NoCaseString =
///   struct
///     type t = string
///     let compare s1 s2 =
///       OrderedString.compare (String.lowercase_ascii s1) (String.lowercase_ascii s2)
///   end;;
/// ```
pub mod man24 {
  use std::rc::Rc;
  use super::OCaml;
  use ordered_type::*;

  // A type may be
  // 'abstract' by keeping its internal structure private. The following
  // is a public interface to a struct with private elements. It can only be
  // constructed and deconstructed by its own methods.
  #[derive(Clone,PartialEq,Eq)]
  pub struct AbstractOrderedSet<A:Ordering> { set: Set<A::Type> }

  // To allow multiple combinations of type and order, we can create a more
  // general trait that more closely matches the OCaml version. We also require
  // that the implementing type is clonable.
  pub trait Ordering : Clone {
    type Type: OCaml + OrderedType;
    fn compare(one: &Self::Type, two: &Self::Type) -> Comparison;
  }

  // impl mostly copied from above, but with `Elt` changed to `Order` or 
  // `Order::Type` as appropriate and using our new defn of AbstractOrderedSet
  impl<Order:Ordering> AbstractOrderedSet<Order> {
    pub fn empty() -> Self { AbstractOrderedSet{set: Set::Nil} }
    pub fn add(&self, x:Order::Type) -> Self {
      match self.set {
        Set::Nil => AbstractOrderedSet{set:Set::Cons(x,Rc::new(Set::Nil))},
        Set::Cons(ref hd,ref tl) => {
          match Order::compare(&x,hd) {
            Comparison::Equal => (*self).clone(),
            Comparison::Less => AbstractOrderedSet{set:Set::Cons(x,Rc::new(self.set.clone()))},
            Comparison::Greater => AbstractOrderedSet{set:Set::Cons(hd.clone(), Rc::new(tl.add(x)))},
          }
        }
      }
    }
    pub fn member(&self, x:&Order::Type) -> bool {
      match self.set {
        Set::Nil => false,
        Set::Cons(ref hd,ref tl) => {
          match Order::compare(x,hd) {
            Comparison::Equal => true,
            Comparison::Less => false,
            Comparison::Greater => tl.member(x)
          }
        }
      }
    }
  }

  // helper for types that have an inherent order as defined previously. This is
  // to be used as a 'marker type' and we won't ever use the value consructor.
  // This is a blanket implemetation, all types with a order defined may now be used
  // with our new abstract `Set` by e.g. `AbstractOrderedSet<DefaultOrdering<String>>`
  #[derive(Clone,PartialEq,Eq)]
  pub struct DefaultOrdering<A>(A);
  impl<A:OCaml+OrderedType> Ordering for DefaultOrdering<A> {
    type Type = A;
    fn compare(one: &Self::Type, two: &Self::Type) -> Comparison {
      A::compare(one, two)
    }
  }

  // new string ordering
  #[derive(Clone,PartialEq,Eq)]
  pub struct NoCaseString;
  impl Ordering for NoCaseString {
    type Type = String;
    fn compare(one: &Self::Type, two: &Self::Type) -> Comparison {
      String::compare(&one.to_lowercase(),&two.to_lowercase())
    }
  }

  // As seen above, Rust does not have the same semantics of
  // abstract interfaces as OCaml. However, there is still the
  // problem of matching two of them up, and Rust has its own
  // `with` clause, `where`:
  #[derive(Clone,PartialEq,Eq)]
  pub struct DoubleOrder<A,B>(A,B);
  impl<A:Ordering,B:Ordering,C:OCaml+OrderedType> DoubleOrder<A,B> where
    A:Ordering<Type=C>,
    B:Ordering<Type=C>
  {
    // without the where clause above, these are different types.
    pub fn compare(a:&A::Type,b:&B::Type) -> Comparison {
      A::compare(a,b)
    }
  } 

  // A type function for the AbstractOrderedSet constructor, using the
  // associated type of a parametrized trait
  trait Func<In> { type Out; }
  #[allow(unused)]
  struct AOSfn;
  impl<In: Ordering> Func<In> for AOSfn { type Out = AbstractOrderedSet<In>; }
  #[allow(unused)]
  type Derived = <AOSfn as Func<NoCaseString>>::Out;
}

/// Run-time examples from OCaml manual 2.4
///
/// ```ocaml
/// module AbstractSet = (Set : SETFUNCTOR);;
/// module AbstractStringSet = AbstractSet(OrderedString);;
/// AbstractStringSet.add "gee" AbstractStringSet.empty;;
/// module WrongSet = (Set : functor(Elt: ORDERED_TYPE) -> SET);;
/// module WrongStringSet = WrongSet(OrderedString);;
/// WrongStringSet.add "gee" WrongStringSet.empty ;;
/// module AbstractSet2 = (Set : functor(Elt: ORDERED_TYPE) -> (SET with type element = Elt.t));;
/// module NoCaseStringSet = AbstractSet(NoCaseString);;
/// NoCaseStringSet.add "FOO" AbstractStringSet.empty ;;
/// ```
fn sec4() {
  use man24::*;
  // As before, visibility is not adjustable at runtime.
  // module AbstractSet = (Set : SETFUNCTOR);;

  #[allow(unused)]
  type AbstractStringSet = AbstractOrderedSet<DefaultOrdering<String>>;

  // The `WrongSet` examples would be meaningless in static Rust, because the
  // compiler does know that the types match (They're both litterally the same).
  // The demonstration of the `with` clause is unnessecary here, but a different
  // one was included above (see DoubleOrder).

  #[allow(unused)]
  type NoCaseStringSet = AbstractOrderedSet<NoCaseString>;

  // Error: two different types
  // NoCaseStringSet::add(&AbstractStringSet::empty(), "FOO".to_string());
}



fn main() {
  sec1();
  sec2();
  sec3();
  sec4();
}