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