An implementation in Rust of the examples from the OCaml manual chapter on modules and funtors
//! 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(); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment