rfw.name

Move Over Classes, Hello Algebraic Data Types, Traits and Implementations!

Posted on

Discretionary warning: I may have gotten some of the sigils wrong in Rust, and please correct me if I have. I also apologize for the lack of Rust highlighting, GitHub’s Pygments doesn’t support it yet.

Let’s look at an example of a singly-linked list in everyone’s favorite language, Java:

class Cons<T> {
    private T head;
    private Cons<T> tail;

    public Cons(T x, Cons<T> xs) {
        head = x;
        tail = xs;
    }

    // Let's be super pedantic and implement getters.
    public T getHead() {
        return head;
    }

    public Cons<T> getTail() {
        return tail;
    }
}

Cons<int> xs = new Cons<int>(1, new Cons<int>(2, new Cons<int>(3, null)));

As all of you probably know, a singly-linked list fulfills these properties:

With some amount of intuition, that Java code is a singly-linked list. Let’s look at a singly-linked list in Rust 0.4:

enum List<a> {
    Cons(a, @List<a>),
    Nil
}

// Just to make it fair.

// head is a function that takes a variable xs of type List<a> and returns a
// value of type a (the head).
pure fn head<a: Copy>(xs: List<a>) -> a {
    match xs {
        Cons(x, @_) => x,
        Nil => fail ~"empty list"
    }
}

// tail is a function that takes a variable xs of type List<a> and returns a
// value of type List<a> (the tail).
pure fn tail<a: Copy>(xs: List<a>) -> List<a> {
    match xs {
        Cons(_, @xs) => xs,
        Nil => fail ~"empty list"
    }
}

let xs: List<int> = Cons(1, @Cons(2, @Cons(3, @Nil)));

We notice some interesting things in the Rust example:

However, if you’re an esteemed Java developer, you’re probably thinking “dear god, this looks like someone puked on Java.” But with some abstract thinking, you can probably see that the algebraic data type List<a> in Rust is much more closely aligned to the definition of a linked list than the class Cons<T> in Java — the compiler enforces more type-safety for us, and also infers types from the recursive type of List<a>!

You haven’t explained what an algebraic data type is yet!

There are two aspects of algebraic data types:

Rust calls algebraic data types enumerated types but they serve the exact same purpose.

We can look at the definition of a binary tree in Java (constructors omitted):

class BinaryTreeNode<T> {
    private T value;
    private BinaryTreeNode<T> left;
    private BinaryTreeNode<T> right;
}

… and compare it to Rust:

enum BinaryTree<a> {
    BinaryTreeNode(a, @BinaryTree<a>, @BinaryTree<a>),
    Nil
}

The Rust version is more expressive — it states that something of BinaryTree<a> is either a BinaryTreeNode containing a value and two children, or Nil, whereas the Java code doesn’t say anything about what the children are.

We can have even more fun and look at how we might go about implementing a simple scene graph in Java (constructors omitted):

interface SceneGraphNode {
    public void render(ThreeDContext ctx);
}

class TransformNode implements SceneGraphNode {
    private Matrix transform;
    private SceneGraphNode[] children;

    public void render(ThreeDContext ctx) {
        ctx.pushMatrix(transform);
        for (SceneGraphNode c : children) {
            c.render(ctx);
        }
        ctx.popMatrix();
    }
}

class CameraNode implements SceneGraphNode {
    public void render(ThreeDContext ctx) {
        ctx.setView(ctx.currentMatrix().inverse());
    }
}

class MeshNode implements SceneGraphNode {
    private Mesh mesh;

    public void render(ThreeDContext ctx) {
        ctx.draw(mesh);
    }
}

… and, of course, in Rust:

enum SceneGraph {
    TransformNode(@Matrix, &[@SceneGraph]),
    CameraNode,
    MeshNode(@Mesh)
}

Clear, succinct and straightforward — we can easily see what kinds of things our scene graph would support, all grouped together.

We can then use pattern matching to perform different actions depending on which case of the sum type we’re using, decoupling the algorithm from the definition of our type — no visitor pattern needed! For instance, with our SceneGraph:

fn render(ctx: ThreeDContext, g: @SceneGraph) -> () {
    match g {
        TransformNode(@m, &[@children]) => {
            pushMatrix(ctx, m);
            for children.each |child| {
                render(ctx, child);
            }
            popMatrix(ctx);
        },

        CameraNode => {
            setView(ctx, inverse(currentMatrix(ctx)));
        },

        MeshNode(@mesh) => {
            draw(ctx, mesh);
        }
    }
}

There is an issue with this, though…

What about polymorphism? Checkmate, functional programmers.

Never fear, we have polymorphism in Rust land too, which comes in the form of traits and implementations. For instance, we can define a trait that looks like:

trait Renderable {
    fn render(&self, ctx: ThreeDContext) -> ();
}

Then, we can separate out our SceneGraph sum types into Rust’s struct record types:

struct TransformNode {
    transform: @Matrix;
    children: &[@Renderable]
}

struct CameraNode { }

struct MeshNode {
    mesh: @Mesh
}

Then we can implement the traits for our node types!

impl TransformNode : Renderable {
    fn render(&self, ctx: ThreeDContext) -> () {
        pushMatrix(ctx, self.transform);
        for self.children.each |child| {
            render(ctx, child);
        }
        popMatrix(ctx);
    }
}

impl CameraNode : Renderable {
    fn render(&self, ctx: ThreeDContext) -> () {
        setView(ctx, inverse(currentMatrix(ctx)));
    }
}

impl MeshNode : Renderable {
    fn render(&self, ctx: ThreeDContext) -> () {
        draw(ctx, self.mesh);
    }
}

Again, we gain the advantage of separating the implementation of our algorithms from the specification of them, and we also get the added bonus of being able to add new graph nodes!

Conclusion

Rust’s type system is a breath of fresh air compared to the old, classical object-oriented way of thinking about data. It cleanly separates the ideas of data aggregation and algorithms to perform on data, adopting much from functional programming languages like Haskell and ML and bringing them into an imperative programming world that sorely misses them.

Whether or not you enjoy Rust’s way of doing things is up to you, of course.

comments powered by Disqus