Mutual Recursion demo in Rust and Racket (inspired by Haskell)

This is a quick post on a Rust version of the Haskell evens and odds program demonstrating mutual recursion (as shown in Hutton’s book).

First off, the Haskell code:

  evens :: [a] -> [a]
  evens [] = []
  evens (x:xs) = x : odds xs

  odds :: [a] -> [a]
  odds [] = []
  odds (_:xs) = evens xs

A sample run:

*Main> let string = "abcde"
*Main> evens string
"ace"
*Main> odds string
"bd"
*Main> string
"abcde"

So the whole ideas is to have the evens functions display all the characters in even positions (starting from 0), and then odds function likewise display all the characters in odd positions.

The evens function acts as the actual accumulator whilst odds is only used as a trampoline for continuing the recursion.

Now, for a rough Rust version of it (preserving the original character array):


fn main() {
    fn evens<T: Copy>(xs: &[T]) -> Vec<T> {
        if xs.is_empty() {
            Vec::new()
        } else {
            cons(&xs[0], &odds(&xs[1..]))
        }
    }

    fn odds<T: Copy>(xs: &[T]) -> Vec<T> {
        if xs.is_empty() {
            Vec::new()
        } else {
            evens(&xs[1..])
        }
    }

    fn cons<T: Copy>(x: &T, xs: &[T]) -> Vec<T> {
        let mut vec = Vec::new();

        vec.push(*x);

        for e in xs.iter() {
            vec.push(*e);
        }
        vec
    }

    let string = String::from("abcde");

    println!("{}",
             String::from_utf8(evens(&string.clone().into_bytes())).unwrap());
    println!("{}",
             String::from_utf8(odds(&string.clone().into_bytes())).unwrap());

    println!("{}", string);
}

And a quick run:

Macushla:EvensAndOdds z0ltan$ rustc evens_and_odds.rs
Macushla:EvensAndOdds z0ltan$ ./evens_and_odds
ace
bd
abcde

So, as can be clearly seen, the original string is left unmodified. Of course this version looks quite dirty, but the nice bit is that &[T] accepts parameters of type Vec (or reference variants) and vice-versa. This enables using slicing extensively and naturally inside the functions. The vector copying code could, of course, be made to work with an API call, but I feel this is much better in its explicit form.

The Racket version looks much nicer, being more amenable to functional constructs than Rust:

#lang racket

(define (evens xs)
  (if (null? xs)
      '()
      (cons (car xs) (odds (cdr xs)))))

(define (odds xs)
  (if (null? xs)
      '()
      (evens (cdr xs))))

(define (main)
  (let ([string "abcde"])
    (displayln (list->string (evens (string->list string))))
    (displayln (list->string (odds (string->list string))))
    (displayln string)))

And a final run for the Racket version:

evens-and-odds.rkt> (main)
ace
bd
abcde
Mutual Recursion demo in Rust and Racket (inspired by Haskell)

The Observer pattern in Rust

Here is a simple implementation of the Observer pattern in Rust. First, the code, and then a small bit of explanation of the implementation itself.

The project structure:

Macushla:rust-observer z0ltan$ tree
.
├── Cargo.lock
├── Cargo.toml
└── src
    ├── lib.rs
    └── main.rs

1 directory, 4 files

The client code:

extern crate rust_observer;

use rust_observer::*;

fn main() {
    let mut foo = EvenCounter::new();
    let (bar, baz, quux) = (Box::new(EvenObserver::new("bar".to_string())),
                            Box::new(EvenObserver::new("baz".to_string())),
                            Box::new(EvenObserver::new("quux".to_string())));

    foo.register(bar);
    foo.register(baz);
    foo.register(quux);

    foo.run();
}

Nothing special here – just creating an Observable object of type EvenCounter, and then three instances of EvenObserver, which implements the Observer type.

The idea is to have the observers get notified whenever the observable object’s counter is an even number (it runs the counter in an infinite loop).

And finally, the actual implementation:

/// the observable type
pub trait Observable<T> {
    fn register(&mut self, observer: Box<Observer<Item = T>>);
}

pub trait Observer {
    type Item;

    fn notify(&self, val: &Self::Item);
}


/// the actual structs which implement the Observable and Observer
/// traits

/// the specific Observable
pub struct EvenCounter {
    counter: u32,
    observers: Vec<Box<Observer<Item = u32>>>,
}

impl EvenCounter {
    pub fn new() -> Self {
        EvenCounter {
            counter: 0u32,
            observers: Vec::new(),
        }
    }

    pub fn run(&mut self) {
        loop {
            use std::thread;
            use std::time::Duration;

            thread::sleep(Duration::from_millis(self.get_rand_duration()));

            self.counter += 1;

            if self.counter % 2 == 0 {
                for observer in self.observers.iter() {
                    observer.notify(&self.counter);
                }
            }
        }
    }

    fn get_rand_duration(&self) -> u64 {
        if cfg!(target_os = "windows") {
            500u64
        } else {
            use std::process::Command;
            use std::str::FromStr;

            let rand_cmd = Command::new("sh")
                .arg("-c")
                .arg("echo $(( $RANDOM%1000 + 1 ))")
                .output()
                .expect("failed to get OS RNG");

            u64::from_str(&String::from_utf8(rand_cmd.stdout).unwrap().trim()).unwrap()
        }
    }
}

impl Observable<u32> for EvenCounter {
    fn register(&mut self, observer: Box<Observer<Item = u32>>) {
        self.observers.push(observer);
    }
}

/// the specific Observer type
pub struct EvenObserver {
    name: String,
}

impl EvenObserver {
    pub fn new(name: String) -> Self {
        EvenObserver { name: name }
    }

    fn name(&self) -> &str {
        &self.name
    }
}

impl Observer for EvenObserver {
    type Item = u32;

    fn notify(&self, val: &Self::Item) {
        println!("{} got {}", self.name(), val);
    }
}

As you can see, the types themselves are implemented as traits, and then the specific concrete types used for the example implement these traits.

The Observable type is quite simple – it is generic over the type that its observers can get notified about. Registration of observers is done through the required method, register. Also note the Box type being used here instead of a real trait object. Sometimes it’s much easier just to box things up than bothering about lifetimes and such.

The Observer type is more interesting. It has a single method, notify which the observable object uses to call the observers. The type of value that is retrieved from the observable object is made an “Associate Type” of the Observer trait. I find this to be a much cleaner approach than defining the trait itself to be parameterized over a generic type.

A simple test run:

Macushla:rust-observer z0ltan$ cargo run
   Compiling rust_observer v0.1.0 (file:///Users/z0ltan/Projects/Playground/DesignPatterns/Observer/Rust/rust-observer)
    Finished dev [unoptimized + debuginfo] target(s) in 0.61 secs
     Running `target/debug/rust_observer`
bar got 2
baz got 2
quux got 2
bar got 4
baz got 4
quux got 4
bar got 6
baz got 6
quux got 6
bar got 8
baz got 8
quux got 8
bar got 10
baz got 10
quux got 10
bar got 12
baz got 12
quux got 12
bar got 14
baz got 14
quux got 14
^C

Very satisfying indeed!

The Observer pattern in Rust

A visitor pattern implementation in Rust

I have recently been studying the ANTLR parser-generator framework, and one of its core approaches is separating the core parsing logic from implementation details. It achieves this using two major patterns – the Listener pattern and the Visitor pattern. This is easily achieved in an Object-oriented language like Java. I was curious to see how that would translate into a language like Rust, hence this post.

Rust, while not quite being an Object-oriented language, does support static and dynamic dispatch. In this case, we are interested in dynamic dispatch, and “Trait Objects” are the main way in which Rust support this feature. However, one problem with using trait objects is that the runtime really doesn’t directly provide us with any way of retrieving the specific type at runtime. This means that calling any struct specific methods on the fly isn’t really that straightforward. The other problem (specific to the Visitor pattern) is that Rust doesn’t have the notion of method overloading. This means that the only sane approach to implementing the pattern in Rust would be to pattern match against the trait object and invoke the appropriate logic, which leads us back to the first point.

A bit of Googling leads us to a practical (if not so elegant) approach of determining the concrete type that implemented the trait at runtime by using std::any::Any. This approach entails providing a method that returns a trait object of type Any for each concrete type that implements the trait, and also explicitly checking the concrete type during pattern matching – there really is no way of extracting the concrete type directly. Instead, we have to try downcasting the trait object to each concrete type and checking if we have a match or not. While this approach works fine for our custom types (the types and count of which we know), this clearly wouldn’t work in a scenario where we are working with third-party types.

In any case, here is the code implementing a simple Visitor pattern where we visit each component of a House type, and perform some custom processing independent of the actual data structures.

Here is the overall layout of the code:

Macushla:rust_visitor z0ltan$ tree
.
├── Cargo.lock
├── Cargo.toml
└── src
    ├── lib.rs
    ├── main.rs
    └── visitors.rs

1 directory, 5 files

Here is the client code, main.rs:

extern crate rust_visitor;

use rust_visitor::*;

fn main() {
    let house = House::new();

    // simply print out the house elements
    house.accept(&visitors::HouseElementListVisitor::new());
   
    println!();
     
    // do something with the elements of a house
    house.accept(&visitors::HouseElementDemolishVisitor::new());
}

So we can see that we create the House element, and then pass in two different implementations of the HouseElementVisitor trait.

Here is the code defining the components of a House:

use std::any::Any;

pub mod visitors;

use visitors::HouseElementVisitor;

/// This represents and element of a house.
/// Each type that implements this trait
/// supports being processed by a visitor.
pub trait HouseElement {
    fn accept(&self, visitor: &HouseElementVisitor);
    fn as_any(&self) -> &Any;
}


/// Define the house entity and its elements

pub struct House {
    components: Vec<Box<HouseElement>>,
}

impl House {
    pub fn new() -> Self {
        House {
            components: vec![Box::new(Livingroom::new()), Box::new(Bedroom::new()), 
                            Box::new(Bathroom::new()), Box::new(Kitchen::new())],
        }
    }
}

impl HouseElement for House {
    fn accept(&self, visitor: &HouseElementVisitor) {
        for component in self.components.iter() {
            component.accept(visitor);
        }

        visitor.visit(self);
    }

    fn as_any(&self) -> &Any { self }
}

struct Livingroom {}

impl Livingroom {
    fn new() -> Self {
        Livingroom{}
    }
}

impl HouseElement for Livingroom {
    fn accept(&self, visitor: &HouseElementVisitor) {
        visitor.visit(self);
    }

    fn as_any(&self) -> &Any { self }
}


struct Bedroom {}

impl Bedroom {
    fn new() -> Self {
        Bedroom {}
    }
}

impl HouseElement for Bedroom {
    fn accept(&self, visitor: &HouseElementVisitor) {
        visitor.visit(self);
    }

    fn as_any(&self) -> &Any { self }
}


struct Bathroom {}

impl Bathroom {
    fn new() -> Self {
        Bathroom {}
    }
}

impl HouseElement for Bathroom {
    fn accept(&self, visitor: &HouseElementVisitor) {
        visitor.visit(self);
    }

    fn as_any(&self) -> &Any { self }
}


pub struct Kitchen {}

impl Kitchen {
    fn new() -> Self {
        Kitchen {}
    }
}

impl HouseElement for Kitchen {
    fn accept(&self, visitor: &HouseElementVisitor) {
        visitor.visit(self);
    }

    fn as_any(&self) -> &Any { self }
}

As can be seen, each implementation of the HouseElement trait defines a method, as_any that returns self as the specific type of the trait object, &Any. This will help the visitor implementation match and find the actual concrete type to do the processing specific to that visitor and that particular HouseElement component.

Finally, here is the actual implementation of the visitors:

//! This module defines the `HouseElementVisitor` trait which defines the capabilities
//! of a type to process the components of a `HouseElement` entity, and also defines
//! a couple of visitor types that do completely different processing.

use ::*;

pub trait HouseElementVisitor {
    fn visit(&self, element: &HouseElement);
}

pub struct HouseElementListVisitor {}

impl HouseElementListVisitor {
    pub fn new() -> Self {
        HouseElementListVisitor {}
    }
}

impl HouseElementVisitor for  HouseElementListVisitor {
    fn visit(&self, element: &HouseElement) {
        if element.as_any()
            .downcast_ref::<House>()
            .is_some() {
            println!("Visiting the House...");
        }

        if element.as_any()
            .downcast_ref::<Livingroom>()
            .is_some() {
            println!("Visiting the Living Room...");
        }

        if element.as_any()
            .downcast_ref::<Bedroom>()
            .is_some() {
            println!("Visiting the bedroom...");
        }

        if element.as_any()
            .downcast_ref::<Kitchen>()
            .is_some() {
                println!("Visiting the kitchen...");
        }
    }
}


pub struct HouseElementDemolishVisitor {}

impl HouseElementDemolishVisitor {
    pub fn new() -> Self {
        HouseElementDemolishVisitor {}
    }
}

impl HouseElementVisitor for HouseElementDemolishVisitor {
    fn visit(&self, element: &HouseElement) {
        if element.as_any()
            .downcast_ref::<House>()
            .is_some() {
            println!("Annihilating the House...!!!");
        }

        if element.as_any()
            .downcast_ref::<Livingroom>()
            .is_some() {
            println!("Bombing the Living Room...!!!");
        }

        if element.as_any()
            .downcast_ref::<Bedroom>()
            .is_some() {
            println!("Decimating the bedroom...!!!");
        }

        if element.as_any()
            .downcast_ref::<Kitchen>()
            .is_some() {
                println!("Destroying the kitchen...!!!");
        }
    }
}

Dirty, but at least it works. The problem, as mentioned before, is that in order to perform specific processing using dynamic dispatch, we use the trait object &HouseElement. However, in order to match against the concrete type, we need to try and match the downcasted reference against each concrete type. This is what the element.as_any().downcast_ref::() code does.

Let’s try it out!

Macushla:rust_visitor z0ltan$ cargo run
   Compiling rust_visitor v0.1.0 (file:///Users/z0ltan/Projects/Blog/Visitor_in_Rust/rust_visitor)
    Finished dev [unoptimized + debuginfo] target(s) in 0.56 secs
     Running `target/debug/rust_visitor`
Visiting the Living Room...
Visiting the bedroom...
Visiting the kitchen...
Visiting the House...

Bombing the Living Room...!!!
Decimating the bedroom...!!!
Destroying the kitchen...!!!
Annihilating the House...!!!

Excellent! Clunky and inelegant, but at least it works.

UPDATE: The implementations of the HouseElementVisitor trait can be simplified into a more elegant match expression block and using the is method of the Any trait as shown below:

Updated HouseElementListVisitor:

impl HouseElementVisitor for  HouseElementListVisitor {
    fn visit(&self, element: &HouseElement) {
        match element.as_any() {
            house if house.is::<House>() => println!("Visiting the house..."),
            living if living.is::<Livingroom>() => println!("Visiting the Living room..."),
            bedroom if bedroom.is::<Bedroom>() => println!("Visiting the bedroom..."),
            kitchen if kitchen.is::<Kitchen>() => println!("Visiting the kitchen..."),
            _ => {}
        }
    }
}

And the HouseElementDemolishVisitor implementation:

impl HouseElementVisitor for HouseElementDemolishVisitor {
    fn visit(&self, element: &HouseElement) {
        match element.as_any() {
            house if house.is::<House>() => println!("Annihilating the house...!!!"),
            living if living.is::<Livingroom>() => println!("Bombing the Living room...!!!"),
            bedroom if bedroom.is::<Bedroom>() => println!("Decimating the bedroom...!!!"),
            kitchen if kitchen.is::<Kitchen>() => println!("Destroying the kitchen...!!!"),
            _ => {}
        }
    }
}

Much more readable in my opinion, and it also hides the somewhat ugly downcast_ref::() bit!

A visitor pattern implementation in Rust

A basic multimap prototype in Rust

Recently, I have been working on a couple of projects, and in one of them, the logic required the use of a multimap. Now, this project is in Rust, and the standard Rust map types, `HashMap` and `BTreeMap` do not support duplicate keys.
Of course, there are full-blown crates available that provide multimap functionality.

However, this being a dead simple project, I decided to roll one out myself. This version simply wraps a `HashMap<K, Vec>` instance inside the custom data structure, but the advantage is that the client API remains consistent and never the wiser about the innards of the actual multimap type. Since I just needed `insert`, `get`, and `iter`, I implemented those for the custom multimap. If needed, the entire API of the `HashMap` type could be implemented for `MHashMap` as well.

Here is the code. It is simple enough that no explanation is really required:

#![allow(dead_code)]

/// A simple wrapper around a HashMap to simulate the basic functionality
/// of a multimap.

use std::collections::HashMap;
use std::hash::Hash;
use std::collections::hash_map::Iter;


#[derive(Debug)]
struct MHashMap<K: Eq + PartialEq + Hash, V>{
    map: HashMap<K, Vec<V>>,
}

impl<K, V> MHashMap<K, V> 
    where K : Eq + PartialEq + Hash
{
    fn new() -> Self {
        MHashMap {
            map: HashMap::new(),
        }
    }

    fn iter(&self) -> Iter<K, Vec<V>> {
        self.map.iter()
        
    }

    fn insert(&mut self, k: K, v: V) {
        if self.map.contains_key(&k) {
                self.map.get_mut(&k).unwrap().push(v);
        } else {
            self.map.insert(k, vec![v]);
        }
    }

    fn get(&self, k: &K) -> Option<&Vec<V>> {
        self.map.get(&k)
    }

    fn get_mut(&mut self, k: &K) -> Option<&mut Vec<V>> {
        self.map.get_mut(&k)
    }
}


fn main() {
    let mut mmap = MHashMap::new();

    mmap.insert(1, "One");
    mmap.insert(1, "Uno");
    mmap.insert(1, "Ein");
    mmap.insert(2, "Two");
    mmap.insert(3, "Three");

    println!("{:?}", mmap);

    let key = 1;

    match mmap.get(&key) {
        Some(vals) => println!("Got {:?} for key {}", vals, key),
        None => println!("Key {} not found!", key),
    }

    for entry in mmap.iter() {
        println!("{} = {:?}", entry.0, entry.1);
    }
}

A small test run:

Macushla:tcp_study z0ltan$ rustc mhash.rs
Macushla:tcp_study z0ltan$ ./mhash
MHashMap { map: {3: ["Three"], 1: ["One", "Uno", "Ein"], 2: ["Two"]} }
Got ["One", "Uno", "Ein"] for key 1
3 = ["Three"]
1 = ["One", "Uno", "Ein"]
2 = ["Two"]

Short and simple!

A basic multimap prototype in Rust

A quick comparison of Euclid’s Algorithm in Haskell, Rust, and D

I recently procured a copy of Graham Hutton’s most excellent book, “Programming in Haskell” (2nd Edition). I had earlier worked through the first edition, and that is the book that really opened my eyes to the power of Haskell! Having become a bit rusty with my Haskell, I decided to work through the second edition book (which is considerably larger and more comprehensive). As part of that exercise, I decided to use a lazy weekend afternoon to code up Euclid’s GCD Algorithm in Haskell, Rust and in D. Just for a quick visual comparison of how the languages look. Here’s how they look:

First off, the Haskell version, which is the best looking one in my opinion:

Macushla:Playground z0ltan$ cat Euclid.hs
module Main where

euclid :: Int -> Int -> Int
euclid m n | m <= 0 && n <= 0 = error "GCD works for positive numbers only"
           | m == n = m
           | m < n = euclid m (n-m)
           | otherwise = euclid (m-n) n

main :: IO ()
main = do putStrLn "Enter the first number: "
          x <- getLine
          putStrLn "Enter the second number: "
          y <- getLine
          let x' = read x :: Int
          let y' = read y :: Int

          putStrLn $ "The GCD of " ++ x
                     ++ " and " ++ y
                     ++ " is " ++ show (euclid x' y')

Macushla:Playground z0ltan$ ghc Euclid.hs
[1 of 1] Compiling Main             ( Euclid.hs, Euclid.o )
Linking Euclid ...
Macushla:Playground z0ltan$ ./Euclid
Enter the first number:
12
Enter the second number:
18
The GCD of 12 and 18 is 6

Here’s the Rust version (a bit uglier, but the Pattern Matching is quite nice):

Macushla:Playground z0ltan$ cat euclid.rs
use std::io;
use std::str::FromStr;
use std::cmp::Ordering;

fn get_number(prompt: &str) -> u32 {
    println!("{}", prompt);

    let mut input = String::new();

    io::stdin().read_line(&mut input)
        .expect("no input!");

    u32::from_str(input.trim()).unwrap()
}

fn main() {
    let x = get_number("Enter the first number: ");
    let y = get_number("Enter the second number: ");

    println!("The GCD of {} and {} is {}", x, y, euclid(x, y));
}

fn euclid(m: u32, n: u32) -> u32 {
    assert!(m > 0 && n > 0);

    match m.cmp(&n) {
        Ordering::Equal => m,
        Ordering::Less => euclid(m, n-m),
        Ordering::Greater => euclid(m-n, n),
        }
}
Macushla:Playground z0ltan$ rustc euclid.rs && ./euclid
Enter the first number:
12
Enter the second number:
18
The GCD of 12 and 18 is 6

And finally, here is the D version – clean, succinct, and a pleasure to read as always:

Macushla:Playground z0ltan$ cat euclid.d
import std.stdio: readln, writeln, writefln;

uint get_number(string prompt) {
    writeln(prompt);

    import std.conv: to;
    import std.string: chomp;

    return readln().chomp().to!(uint);
}

void main() {
    uint x = get_number("Enter the first number: ");
    uint y = get_number("Enter the second number: ");

    writefln("The GCD of %s and %s is %s", x, y, euclid(x, y));
}

uint euclid(uint m, uint n) {
    assert(m > 0 && n > 0);

    if (m < n) {
        return euclid(m, n-m);
    } else if (m == n) {
        return m;
    } else {
        return euclid(m-n, n);
    }
}
Macushla:Playground z0ltan$ dmd -run euclid.d
Enter the first number:
12
Enter the second number:
18
The GCD of 12 and 18 is 6

One thing is for sure. Aside from syntactic differences, most modern languages are all converging in terms of paradigms and features. Hell, even keeping languages like Haskell and Idris aside, most mainstream languages are also converging on the syntactical front! Anyway, this was a fun little exercise on a slow afternoon. I personally like the Haskell version best , followed by the D version, and then finally the Rust version (ruined by the somewhat ugly I/O syntax). What do you think?

A quick comparison of Euclid’s Algorithm in Haskell, Rust, and D

A simple demo of using channels in Rust

Continuing with my study of Rust, I ventured into concurrency using Rust at long last!

The standard library in Rust provides a few basic concurrency primitives, but of them all, my favourite has to be the support for channels. I decided to try out a small program where the factorial of a number is calculated in another thread, and the result piped back into the calling function.

The code is presented as follows:

/// Factorial using channel

use std::io;
use std::str::FromStr;
use std::thread;
use std::sync::mpsc::{channel, Sender};


fn factorial(tx: Sender<u64>, n: u64) {
    fn helper(acc: u64, n: u64) -> u64 {
        if n == 0 { acc } else { helper(acc * n, n - 1) }
    }

    thread::spawn(move || { tx.send(helper(1u64, n)).unwrap(); });
}


fn get_number() -> u64 {
    println!("Enter a number");

    let mut input = String::new();

    io::stdin()
        .read_line(&mut input)
        .expect("could not read input");

    match u64::from_str(input.trim()) {
        Ok(n) => n,
        Err(e) => panic!(e.to_string()),
    }
}


fn main() {
    let n = get_number();

    let (tx, rx) = channel();

    factorial(tx, n);

    println!("The factorial of {} is {}", n, rx.recv().unwrap());
}

Pretty straightforward code. We create a channel using std::sync::mspsc::channel, which returns a (Sender, Receiver) tuple. As the names suggest, Sender is used for transmitting data on the channel, and Receiver is used for receiving data on the same channel.

This approach also precludes the need for waiting on the thread explicitly.

Let’s take it for a spin:

bash-3.2$  rustc channel_factorial.rs && ./channel_factorial
Enter a number
20
The factorial of 20 is 2432902008176640000

Short and sweet!

The contrived example without using a channel might look something like so:

/// concurrent factorial using plain threads

use std::thread;
use std::sync::{Arc, Mutex};


fn factorial(n: u64) -> u64 {
    fn helper(acc: u64, n: u64) -> u64 {
        if n == 0 { acc } else { helper(acc * n, n - 1) }
    }

    helper(1u64, n)
}


fn main() {
    let data = Arc::new(Mutex::new(0u64));

    let data_clone = data.clone(); // bump the RC count

    let handle = thread::spawn(move || {
        let mut fact_cell = data_clone.lock().unwrap();
        *fact_cell = factorial(10);
    });

    match handle.join() {
        Ok(_) => println!("Factorial of 10 = {:?}", data),
        Err(e) => panic!(e),
    }
}

Not too bad, eh? The only difference is that we wrap the actual data inside a Mutex, which is itself wrapped inside an Arc object. This is to allow for shared mutable data using reference counting (since every object has exactly one owner at any point of time).

Inside the spawned thread, we can then get a lock on the cloned data object, and then we update the wrapped data with the factorial value. The problem with this approach is that it is not trivial to extract the value out. Taking it for a test run:

bash-3.2$ rustc concurrent_factorial.rs && ./concurrent_factorial
Factorial of 10 = Mutex { data: 3628800 }

As we can see, we do get the correct result, but unfortunately it’s wrapped up inside the mutex object, and getting it out is not easy since the API itself doesn’t seem to provide any way of doing so. Suggestions on StackOverflow seem to imply wrapping the data inside an Option object beforehand (as in something like

Arc<Mutex<Option<T>>>

), but that road didn’t lead me anywhere nice and safe either. I probably need to learn more about this approach in addition to perusing the documentation for a nice and elegant way out of this jumble of wrapped generic types (if there is one). No wonder I’d rather have the nice Go-esque channels!

UPDATE: Thanks to the good folks over at #rust, I got a simple and elegant solution for the unwrapping issue! Here is the update code:

/// concurrent factorial using plain threads

use std::thread;
use std::sync::{Arc, Mutex};


fn factorial(n: u64) -> u64 {
    fn helper(acc: u64, n: u64) -> u64 {
        if n == 0 { acc } else { helper(acc * n, n - 1) }
    }

    helper(1u64, n)
}


fn main() {
    let data = Arc::new(Mutex::new(0u64));

    let data_clone = data.clone(); // bump the RC count

    let handle = thread::spawn(move || {
        let mut fact_cell = data_clone.lock().unwrap();
        *fact_cell = factorial(10);
    });

    match handle.join() {
        Ok(_) => println!("Factorial of 10 = {:?}", *data.lock().unwrap()),
        Err(e) => panic!(e),
    }
}

The change is this: *data.lock().unwrap() inside the match in main. The explanation given was this: since the data itself is wrapped inside a Mutex within an Arc, it needs to be unwrapped in the reverse order – dereference the Arc to get the Mutex, and then dereference that to get the data! The unwrap is necessary since lock() returns a LockResult object.

The Rust community is indeed one of the most helpful communities on IRC. The problem which had me vexed for an hour or so was solved within minutes!

A simple demo of using channels in Rust

A Line number closure in Rust, and an interesting battle with the Rust compiler

It had been a while since I’d played around with Rust, so I decided to implement one of my two favourite programs when learning new languages viz., a line number closure (with mutation, of course) as shown by Hoyte in his seminal book, “Let Over Lambda”. The other program is, of course, implementing a functioning Rational number class (as in the previous blog post, for instance).

Well, with Rust, it’s a very…interesting experience to say the least. The Rust Borrow Checker is a very strange beast indeed. So, let’s have a look at how we can arrive at a working version of the program.

Background

Rust does have powerful support for closures (what respectable language does not today?). However, the interesting part is that closures in Rust are simply syntactic sugar for traits. To be more precise, there are three available traits that a closure can belong to:

  • the Fn trait – this is the least permissive of all, and it allows a read-only closure (in effect). This is ideal when we want to simply have a self-contained immutable closure. For instance,
    fn square<F>(n: i32, callback: F)
        where
        F: Fn(i64) ->() {
        callback(n as i64 * n as i64);
    }
    
    fn main() {
        square(100, |n| {  println!("Received {}", n); });
    }
    

    This duly prints out:

    Received: 10000
    

    This is quite straightforward. As we can see, The type of the callback, which is the closure, is Fn(i64) -> (), which means that it takes a 64-bit integer and does some side-effect (printing to screen in this case). No mutation anywhere, no capturing of environments, and so the Fn trait works superbly here.

  • the FnMut trait is more interesting. This is needed when we need to mutate the environment captured by the closure. As a small example:
    fn process_mutating_closure<F>(mut closure: F)
        where
        F: FnMut(i32) -> () {
        closure(100);
    }
    
    fn main() {
        let mut local = 100;
    
        process_mutating_closure(|x| { 
                  local += 100; 
                  println!("Value = {}", x + local); 
        });
    
    

    which produces:

    Value = 300
    

    All right, this is a bit more complicated than the previous version. So, let’s break it down. What we intend to do is this – the closure that’s created in the main function captures a mutable variable, local, in the enclosing lexical scope. The closure then modifies this captured variable, and uses it for some dummy processing before printing the final value out.

    Since a captured variable is being modified, the type of the closure will be FnMut. This is exactly what’s reflected in the type signature when the closure is passed as an argument to process_mutating_closure.

  • , and finally, the FnOnce trait is the most restrictive of all. It basically transfers ownership of the capture to the closure itself. If you are not familiar with Rust’s wonderful (sarcasm) Ownership and Borrowing world, consider yourself lucky.
    fn move_closure_demo<F: FnOnce(i32) -> ()>(closure: F) {
        closure(100)
    }
    
    fn main() {
        let mut local = 100;
    
        move_closure_demo(move |x| {
            local += 100;
            println!("Result = {}", x + local);
        });
    
        println!("{}", local);
    }
    
    Result = 300
    

    Eh? This code looks almost identical to the previous one (except for the change in the function signature of the closure from FnMut to FnOnce and the move in front of the closure). Well, if you notice, you will also see that the function var, closure in the function move_closure_demo also does not require mut unlike in the previous case.

    What’s happening here is that because we have “moved” the closure, the closure is now the owner of the captured variable, local. Wait a minute, so how come we can still use local in main after it’s been moved? It turns out that because the binding of local is to a Copy-able type (i32 in this case), a copy of the binding’s value is actually moved. However, this won’t work for types that do not implement the Copy trait. Confused? Well, you should be. I mean, wtf?

All right, now let’s get on with the meat of the actual matter.

First attempt

Let’s put our knowledge of how closures are actually syntactic sugar for the aforementioned trifecta of traits to use. Here’s the first shot:

fn gen_line_number() -> (FnMut() -> ()) {
    let mut line_no = 0;

    || {
        line_no += 1;

        println!("Current line number: {}", line_no);
    }
}

fn main() {
    let foo = gen_line_number();

    for _ in 0..5 {
        foo();
    }
    
    println!("");

    let bar = gen_line_number();

    for _ in 0..5 {
        bar();
    }
}

Since we’re modifying the capture var, line_no, we need the closure to be of the trait type, FnMut. Looks okay, let’s take it for a spin:

bash-3.2$ rustc hoyte-blog.rs 
error[E0277]: the trait bound `std::ops::FnMut() + 'static: std::marker::Sized` is not satisfied
 --> hoyte-blog.rs:1:26
  |
1 | fn gen_line_number() -> (FnMut() -> ()) {
  |                          ^^^^^^^^^^^^^ the trait `std::marker::Sized` is not implemented for `std::ops::FnMut() + 'static`
  |
  = note: `std::ops::FnMut() + 'static` does not have a constant size known at compile-time
  = note: the return type of a function must have a statically known size

error[E0308]: mismatched types
 --> hoyte-blog.rs:4:5
  |
4 |     || {
  |     ^ expected trait std::ops::FnMut, found closure
  |
  = note: expected type `std::ops::FnMut() + 'static`
  = note:    found type `[closure@hoyte-blog.rs:4:5: 8:6 line_no:_]`

error[E0277]: the trait bound `std::ops::FnMut(): std::marker::Sized` is not satisfied
  --> hoyte-blog.rs:12:9
   |
12 |     let foo = gen_line_number();
   |         ^^^ the trait `std::marker::Sized` is not implemented for `std::ops::FnMut()`
   |
   = note: `std::ops::FnMut()` does not have a constant size known at compile-time
   = note: all local variables must have a statically known size

error[E0277]: the trait bound `std::ops::FnMut(): std::marker::Sized` is not satisfied
  --> hoyte-blog.rs:20:9
   |
20 |     let bar = gen_line_number();
   |         ^^^ the trait `std::marker::Sized` is not implemented for `std::ops::FnMut()`
   |
   = note: `std::ops::FnMut()` does not have a constant size known at compile-time
   = note: all local variables must have a statically known size

error: aborting due to 4 previous errors

Whoa! Okay, let’s read the error messages in order. Maybe that will help us fix the issue better. Right, so the first one says something about std::marker::Sized not being implemented… blah blah blah. What all this verbosity actually means is that we are returning a closure from the function, and it needs to know the size of the closure at compile time itself.

Fair enough. However, why does it work when we’re passing a closure into a function the same way (instead of returning the closure from it)? Who the hell really knows? Well, the basic problem here (as I figure it) is that we need to wrap the whole damned thing inside a heap pointer (aka the Box type) since we’re returning from the function, and the stack frame for that function is going to get de-allocated, we need to return a heap pointer to the object so that it can be used even after the current function frame’s destroyed.

This is the reason why code like the following works because the callback function, closure cannot outlive the function where the closure was generated (main):

fn foo<F: Fn() -> ()>(closure: F) {
    closure();
}

fn main() {
    foo(|| { println!("Hello, world!");});
}
Hello, world!

Okay, let’s proceed.

Second Attempt

Having gained that great insight from the first version, here’s how the second version looks like:

fn gen_line_number() -> Box<FnOnce() -> ()> {
    let mut line_no = 0;

    Box::new(move || {
        line_no += 1;

        println!("Current line number: {}", line_no);
    })
}

fn main() {
    let foo = gen_line_number();

    for _ in 0..5 {
        foo();
    }
    
    println!("");

    let bar = gen_line_number();

    for _ in 0..5 {
        bar();
    }
}

and…

bash-3.2$ rustc hoyte-blog.rs 
error[E0161]: cannot move a value of type std::ops::FnOnce(): the size of std::ops::FnOnce() cannot be statically determined
  --> hoyte-blog.rs:15:9
   |
15 |         foo();
   |         ^^^

error[E0161]: cannot move a value of type std::ops::FnOnce(): the size of std::ops::FnOnce() cannot be statically determined
  --> hoyte-blog.rs:23:9
   |
23 |         bar();
   |         ^^^

error[E0382]: use of moved value: `*foo`
  --> hoyte-blog.rs:15:9
   |
15 |         foo();
   |         ^^^ value moved here in previous iteration of loop
   |
   = note: move occurs because `*foo` has type `std::ops::FnOnce()`, which does not implement the `Copy` trait

error[E0382]: use of moved value: `*bar`
  --> hoyte-blog.rs:23:9
   |
23 |         bar();
   |         ^^^ value moved here in previous iteration of loop
   |
   = note: move occurs because `*bar` has type `std::ops::FnOnce()`, which does not implement the `Copy` trait

error: aborting due to 4 previous errors

Sigh. Just when things were looking up… theoretically. All right, before we lose our sanity, let’s read all the bloody error messages and try to make some sense of them. Okay, ignoring the first two about statically size something, we see that the other errors are complaining about foo and bar being already moved in the previous iteration of the loop. At least that makes some sort of sense – since we have the closure passed to main and assigned to foo and bar, and, as the error message says, FnOnce does not implement the Copy trait, we cannot change the owner of the closure in subsequent iterations of the for loop.

Let’s rectify that by using the FnMut trait instead, which is actually what we want since we are not using any ownership changes, and we’re mutating the captured local variable, it sounds like the perfect candidate for our use case.

In case you’re wondering about modifying the main function instead to use references inside the for loops, I assure you that it’s not an oversight on my part – down that road lies perdition! (Reflect upon the fact that I have a working copy, and I’m actually working backwards through some sane progression amongst the many that I had to endure along the way!)

Third attempt

Here’s the version with the closure type changed to FnMut:

fn gen_line_number() -> Box<FnMut() -> ()> {
    let mut line_no = 0;

    Box::new(move || {
        line_no += 1;

        println!("Current line number: {}", line_no);
    })
}

fn main() {
    let foo = gen_line_number();

    for _ in 0..5 {
        foo();
    }
    
    println!("");

    let bar = gen_line_number();

    for _ in 0..5 {
        bar();
    }
}

And yes, you guessed it, it simply doesn’t work, but you’ll love the error messages:

bash-3.2$ rustc hoyte-blog.rs 
error: cannot borrow immutable `Box` content `*foo` as mutable
  --> hoyte-blog.rs:15:9
   |
15 |         foo();
   |         ^^^

error: cannot borrow immutable `Box` content `*bar` as mutable
  --> hoyte-blog.rs:23:9
   |
23 |         bar();
   |         ^^^

error: aborting due to 2 previous errors

Hmmm… hmmm? It mentions that when I call foo and bar, it’s trying to make something mutable that’s actually immutable. Eh? Okay, let’s see. The local captured variable was “moved” to live beyond the function’s stack frame, so that’s fine. I’m using FnMut so that I can actually mutate the captured variable, that’s fine. I’m wrapping the whole damned thing inside a Box so that the whole closure can persist beyond the function call, and finally, all I’m trying to do is to increment the mutable captured line_no var inside my for loops. That also sounds fine. So when did the contents of the box become immutable?

All right, let’s see the final version first.

Final version

fn gen_line_number() -> Box<FnMut() -> ()> {
    let mut line_no = 0;

    Box::new(move || {
        line_no += 1;

        println!("Current line number: {}", line_no);
    })
}

fn main() {
    let mut foo = gen_line_number();

    for _ in 0..5 {
        foo();
    }
    
    println!("");

    let mut bar = gen_line_number();

    for _ in 0..5 {
        bar();
    }
}

and running it,

bash-3.2$ rustc hoyte-blog.rs 
bash-3.2$ ./hoyte-blog 
Current line number: 1
Current line number: 2
Current line number: 3
Current line number: 4
Current line number: 5

Current line number: 1
Current line number: 2
Current line number: 3
Current line number: 4
Current line number: 5

Wow! Glory at last! Heh. Well, if you have the eyes of a hawk, you’ll observe that the only change was adding the mut qualifier to the closure handles in main. So what that extremely useful, intuitive, and helpful error message was telling us is that we have a boxed closure containing a captured mutable local var which we’re updating in every iteration of the respective for loops, but unfortunately we have assigned the closures to immutable handles, and so the whole thing just won’t work.

Whew. And seriously, wtf?

Rust appears to be great fun when things go well, but when things go badly (and they will, of course), it can be quite a PITA. Granted, I am not an expert or even an intermediate Rust programmer, but perhaps people’s complaints about the learning curve being seriously fucked up aren’t really exaggerated. If the learning curve had been at least logical, it would be a different matter. As things stand though, the more I venture into the language, the more “patched-together” it appears to be. Also, all the various exceptions to the rules in addition to the myriad rules about exceptional scenarios aren’t really helping, folks. I doubt anything can really be done about it now, though. Heh.

A Line number closure in Rust, and an interesting battle with the Rust compiler