Create a gist now

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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