Jakob's Blog Personal insights into technologies

Versatile Rust - Part 2 of Rust in a coding competition

What does define a multi-paradigm programming language? And why should we care?

This is the second post in a series. Follow the link to read part 1 first.

Rust is imperative-procedural and functional at the same time. It also comes along with object-oriented features like methods, inheritance, and polymorphism, although it is technically not an object-oriented programming language. And even syntactically, many ideas from other languages have been adopted in Rust. This is why people say Rust embraces multiple paradigms and it is what makes Rust such a versatile language. Thus, in Rust, many drastically different solutions are viable for the same problem.

To demonstrate that, let us revisit the task of decoding, as described and solved in the previous post. There, the first solution presented I have described as Java-like and afterwards I have shown solutions in other languages, namely Haskell, Python and C.

In this post, I will show you only Rust code. But I will try to imitate the style of the other languages I just mentioned. For a direct comparison, you might want to open the previous solutions in a separate window.

Haskell-like Rust

fn h_decode(input: &[u8], key: u8) -> String {
    match input {
        &[.., a, b] => push(h_decode(&input[..input.len()-2], key), (key ^ (16*a + b)) as char),
        _ => String::new()
    }
}

Now, while above code is working perfectly fine and solves the problem just like the other examples, I did have to make some tweaks to make it look as Haskell-like as I could.

For one, I am using the experimental slice pattern feature. But even with that, I cannot write &[a:b:xs] and let xs be the rest of the slice, as one would do in Haskell. The only way of getting the cut-off slice is to access the input slice once more like so &input[..input.len()-2].

Further, due to the verbosity of function declarations and calls in Rust, I decided to inline the decode_digit function, in contrast to the Haskell implementation from before.

Also, I reversed the order of decoding, so that I could efficiently push at the end of the string. But because the push method on std::string::String does not return itself, I also had to add this little helper function to avoid an additional variable:

fn push(mut s: String, c: char) -> String {
    s.push(c);
    s
}

And because the function signature has changed to take a slice of numbers rather than a string, here is a wrapper function that could be used to adapt to the initial signature (even if it might look complicated, it is nothing but a type conversion and no division into chunks is performed here):

fn decode_h_wrapper(input: &str, key: u8) -> String {
    h_decode(input.chars()
    .map(|c| { c.to_digit(16).unwrap() as u8})
    .collect::<Vec<_>>().as_slice(), key)
}

Python-like Rust

fn p_decode(msg: &str, key: u8) -> String {
    list_comprehension![
        p_decode_digit(&msg[i..i+2], key); 
        for i in (0..msg.len()).step_by(2)
        ].collect()
}

fn p_decode_digit(s: &str, key: u8) -> char {
    (key ^ u8::from_str_radix(s, 16).unwrap()) as char
}

The big difference to the actual Python implementation is that I had to use a macro list_comprehension![] to mimic what Python can already do natively. However, the macro is generic and can pretty much do anything that Python’s list comprehension can. So really, if you want to use list comprehension in Rust, just bring this macro prepared with you.

For those who are interested, the definition of the macro has been heavily inspired by this Reddit post and looks as follows:

macro_rules! list_comprehension(
    ($r:expr; for $x:pat in $J:expr; if $pred:expr) => (
        ($J).filter_map(|$x| if $pred { Some($r) } else { None })
    );
    ($r:expr; for $x:pat in $J:expr) => (
        ($J).map(|$x| $r)
    )
);

If this looks just confusing to you, I recommend ignoring the macro definition. Rust macros directly access the AST of the program code, which is already complicated enough. And the syntax Rust uses for macro definitions almost feels like a completely new language on its own. But if you are willing to spend some time to learn it, you will not regret it, as the capabilities of macros in Rust are great indeed.

C-like Rust

This is definitely not the cleanest way to write a C-like decoding function but it is the literal translation of the previous C-code snippet.

fn c_decode(input: &str, key: u8) -> String {
    let input_vec = input.as_bytes();
    let mut output = String::new();
    for i in 0..(input_vec.len()/2) {
        let hexdigit = vec![input_vec[2*i], input_vec[2*i+1], 0]; 
        let character = unsafe {
            ffi::strtol(hexdigit.as_ptr() as *const c_char, ptr::null_mut(), 16) as u8
        };
        output.push((character ^ key) as char);
    }
    output
}

// Declaration of the external function strtol in libc
mod ffi {
    use std::ffi::CString;
    use std::os::raw::c_char;
    extern {
        pub fn strtol(s: *const c_char, endptr: *const *mut c_char, base: u32 ) -> u64;
    }
}

Huh, that became ugly! While the signature of the function contains only Rust strings, internally we deal with NULL-terminated C-strings. And with those, we call strtol from the C standard library.

Alternatively, we can have a cleaner solution if we allow ourselves to handle strings in a rusty way.

fn c_decode(input: &str, key: u8) -> String {
    let mut output = String::new();
    for i in 0..(input.len()/2) {
        let hexdigit = &input[2*i..2*i+2]; 
        let character = u8::from_str_radix(hexdigit, 16).unwrap();
        output.push((character ^ key) as char);
    }
    output
}

Going back to the final statement in the previous post that the C implementation was more competitive than my initial rust implementation, it is hard to say the same about this bit of Rust code. I think it basically has all advantages from the C snippet and on top, we do not have to worry about memory allocation or NULL-termination of strings.

Wrapping up this post

I do not think any of the presented code snippets is perfect by any means. I am sure there could be much cleaner and more efficient ways of solving the problem in Rust. But I hope I could demonstrate that with Rust, the programmer is not locked into a single schema of solving a given task.

Some programmers like to have such a wide variety of tools in a language, others have claimed having to decide between different approaches would only distract them from solving the task at hand. I can agree with both to some degree, sometimes I find myself wasting a lot of time just to find the design I like most when the solution could be written down very quickly anyway. But I like to increase the number of tools in my arsenal, even if it means I am investing some of my time into discovering those tools and often times I end up doing something too complicated.

If I have not convinced you, yet, that learning a multitude of programming languages and paradigms is a good thing, here is a lovely little quote for you by Abraham Kaplan, taken from The Conduct of Inquiry: Methodology for Behavioral Science:

Give a small boy a hammer, and he will find that everything he encounters needs pounding.

Next post in series: Rust in a coding competition (Part 3) - Filling in the gaps

Technology Stack

Rust

The Rust programming languages had its first stable release in May 2015. It has been designed with performance and low-level programming as a high priority. Therefore, it is well suited for applications that would otherwise be done in C++. The huge improvements of Rust over C++ are its strong safety guarantees like data-race freedom and memory safety at compile time.