The Expression Problem in Rust

Eli Bendersky’s website is fantastic and you should read it. In one series of posts he discusses the expression problem: a software design problem where in some languages it is easy to add new data types and in others it is easy to add new operations on data types. I like thinking about the expression problem because similar concepts appear in the design of so-called “deep learning” frameworks like MXNet and Tensorflow where operations and data types are abstracted out and treated symbolically.

To summarize his excellent post, in object-oriented languages it is easy to add new data types. However, to add a new operation you need to modify the object interface and revisit each data type definition to implement the new operation. (The key word here, I believe, is revisit in the sense that the modification violates the open-closed principle.) Alternately, in functional programming languages the situation is reversed: adding a new data type means having to modify the definition of each operation, also violating the open-closed principle.

I believe that Rust solves this problem using traits. In this post I will demonstrate how this is so. My knowledge of Rust is really elementary at the time of writing this so hopefully I haven’t violated any major Rust principles. My code may not be of top-level Rust design but it works.

A Motivating Example

Let’s replicate Eli’s example in Rust: a simple expression evaluator. Although he brings up this example in the context of compilers and interpreters expression construction and evaluation is also the bread and butter of deep learning frameworks.

Eli’s examples use a base class (in OOP) or enum (in FP) called Expr from which all expression types are derived. From my reading of Rust such a notion may not be necessary, or perhaps even appropriate, if the goal is to perform operations on data types. Therefore, in my definition of Constant I will omit any “inheritance” from a parent type. See my final thoughts at the end of this post for more about design decision.

We begin with the definition of a Constant data type,

#[derive(Debug)]
struct Constant<T> {
    value: T
}

We include the derive(Debug) macro to auto-magically make the data type printable for debugging purposes. Below is some code using this struct,

fn main() {
    let c1 = Constant {value: 1.2};
    let c2 = Constant {value: 3.4};

    println!("c1 = {:?}", c1);  // output: c1 = Constant { value: 1.2 }
    println!("c2 = {:?}", c2);  // output: c2 = Constant { value: 3.4 }
}

Let’s now make Constant expressions “evaluatable”. To do so, we’ll create a new trait Eval which implements an eval() method. For Constant expressions eval() should simply return a copy of stored value. Note that we could implement eval() as a struct method but the end goal, here, is to have shared operation functionality across multiple data types.

trait Eval<T> {
    fn eval(&self) -> T;
}

impl<T> Eval<T> for Constant<T>
    where T: Clone
{
    fn eval(&self) -> T {
        self.value.clone()
    }
}

Because of Rust’s ownership model we return a copy/clone of Constant.value so that the struct can retain ownership of its value. Otherwise, the contents of value are moved out of the Constant struct to the caller. (Aside: is there a better way to do this?) Let’s test that (a) the eval() implementation works and (b) that the ownership properties are indeed satisfied.

Continuing the main() function from above,

fn main() {
    // --snip--

    println!("c1.eval() = {}", c1.eval());  // output: c1.eval() = 1.2
    println!("c1.eval() = {}", c1.eval());  // output: c1.eval() = 1.2
    println!("c2.eval() = {}", c2.eval());  // output: c2.eval() = 3.4
    println!("c2.eval() = {}", c2.eval());  // output: c2.eval() = 3.4
}

Excellent. If the value stored in c1 were moved then the second invocation of println!() would cause a compilation error. It’s incredible that Rust won’t let you compile if you have memory leaks!

Adding a New Type

Let’s add the second data type in Eli’s example.

#[derive(Debug)]
struct BinaryPlus<'a, 'b, U, V>
where U: 'a,
      V: 'b,
{
    left: &'a U,
    right: &'b V,
}

Again, I am not yet confident in my Rust skills but my understanding is that the BinaryPlus type should not actually own the data stored in its left and right attributes. In particular, we want the lifetime of BinaryPlus’s left attribute to last at least as long if not longer than the BinaryPlus instance, itself. Hence, the lifetime specifications. Regardless, trying to compile this data type without lifetime parameters results in a compile error.

We now implement the Eval trait for BinaryPlus,

impl<'a, 'b, T, U, V> Eval<T> for BinaryPlus<'a, 'b, U, V>
where T: Add<Output=T>,
      U: Eval<T> + 'a,
      V: Eval<T> + 'b,
{
    fn eval(&self) -> T {
        self.left.eval() + self.right.eval()
    }
}

Note the requirements on the generic data types. Whatever type T is must be add-able with output type also T. The left and right arguments must be Eval-able; after all, we call eval() on them. What’s interesting is that these restrictions are not present in the actual definition of the BinaryPlus type, above. Only if you want to use the Eval functionality do you have to narrow down the traits of the arguments.

Here is an example usage of this new type and operation.

fn main() {
    // --snip--

    let bp1 = BinaryPlus { left: &c1, right: &c2 };
    println!("bp1 = {:?}", bp1);              // output: bp1 = BinaryPlus { left: Constant { value: 1.2 }, right: Constant { value: 3.4 } }
    println!("bp1.eval() = {}", bp1.eval());  // output: bp1.eval() = 4.6

    // ownership check: make sure bp1 doesn't now own c1 and c2
    println!("c1.eval() = {}", c1.eval());    // output: c1.eval() = 1.2
    println!("c2.eval() = {}", c2.eval());    // output: c2.eval() = 3.4

    let bp2 = BinaryPlus { left: &c1, right: &bp1 };
    println!("bp2 = {:?}", bp2);              // output: bp2 = BinaryPlus { left: Constant { value: 1.2 }, right: BinaryPlus { left: Constant { value: 1.2 }, right: Constant { value: 3.4 } } }
    println!("bp2.eval() = {}", bp2.eval());  // bp2.eval() = 5.8

Note that in adding a new type we did not have to modify and previous definitions of the Eval trait. Instead, we just specified how the Eval trait behaves with this new type. Therefore the FP version of the expression problem is resolved; we haven’t violated the open-closed principle.

Adding a New Operation

Time to add the second example operation to_string() as a method of the trait Stringify and implement it for both the Constant and BinaryPlus data types.

trait Stringify {
    fn to_string(&self) -> String;
}

use std::fmt::Display;

impl<T> Stringify for Constant<T>
where T: Display
{
    fn to_string(&self) -> String {
        format!("Constant({})", self.value)
    }
}

impl<'a, 'b, U, V> Stringify for BinaryPlus<'a, 'b, U, V>
where U: Stringify,
      V: Stringify,
{
    fn to_string(&self) -> String {
        format!("BinaryPlus({} + {})", self.left.to_string(), self.right.to_string())
    }
}

Note the type restrictions for Constant’s implementation is just that T implements the Display trait. As for BinaryPlus, we require that each constituent attribute is Stringify-able.

Let’s see this new functionality in action:

fn main() {
    println!("c1.to_string() = {}", c1.to_string());    // output: c1.to_string() = Constant(1.2)
    println!("c2.to_string() = {}", c2.to_string());    // output: c2.to_string() = Constant(3.4)
    println!("bp1.to_string() = {}", bp1.to_string());  // output: bp1.to_string() = BinaryPlus(Constant(1.2) + Constant(3.4))
    println!("bp2.to_string() = {}", bp2.to_string());  // output: bp2.to_string() = BinaryPlus(Constant(1.2) + BinaryPlus(Constant(1.2) + Constant(3.4)))
}

Nice. Again we see that adding the Stringify trait does not require modifications to the previously-written code for the Constant and BinaryPlus data types. Instead, we modify the capabilities of these types with new trait implementation code. Therefore, Rust also resolves the OOP version of the expression problem.

I suppose the caveat, here, is if you wanted to modify the definition of trait Stringify to include a new method. Here is one way to do it without having to return to the definition of Stringify,

trait StringifyExt {
    fn to_alternate_string(&self) -> String;
}

impl<T> StringifyExt for T
where T: Stringify
{
    fn to_alternate_string(&self) -> String {
        String::from("Hey!")
    }
}


fn main() {
    // --snip--

    println!("c1.to_alternate_string() = {}", c1.to_alternate_string());  // output: Hey!
}

Once again, no existing code was modified. I added the “extension trait” and implemented it for any type which implements Stringify. This is not quite the same pattern as I read in this article but, then again, Option<T> is a type (enum), not a trait. Regardless, this technique is useful if you want to extend traits that don’t belong to you.

Final Thoughts

Learning Rust has been educational. Just like when I played around with Haskell I came away looking at code design a little bit differently in other languages. (My post-Haskell Python code used more functional than iterative styles.)

Earlier I mentioned that using an Expr enum seemed unnecessary for modeling the expression problem in Rust. Strictly speaking, to accurately model the problem I should have created an enum like so,

enum Expr {
    ConstantExpr(Constant),
    BinaryPlusExpr(BinaryPlus),
}

The user could then create ConstantExpr and BinaryPlusExpr instances, both of which are of type Expr. The implementation details would be “hidden” underneath in the actual underlying structs, Constant and BinaryPlus, respectively. My thought is the use of an Expr enum does not add anything to resolving the expression problem: the only goal is to have a model where we can add data types and operations on those data types independently and easily such that the open-closed principle isn’t violated.

That being said, Rust enums cannot be extended and therefore the open-closed principle is violated. However, there is a clunky workaround.

enum MoreExpr {
    Expr(Expr),
    SomeNewExpr,
}

match my_expr_variable {
    Expr(ConstantExpr) => ...,
    Expr(BinaryPlusExpr) => ...,
    SomeNewExpr => ...
}

The role of the Expr interface in object-oriented programming languages is to establish a shared interface across all sub-types. The role of the Expr enum in functional programming languages is so that you can perform matching on various sub-types. With Rust traits the data types and operations on those data types are much more separated since you can just check if an input type implements a trait. Therefore, for the purposes of this problem I’m comfortable in omitting the Expr enum and calling the problem solved. Please prove me wrong because it seems too good to be true.