Exploring the "expression problem" in Rust

Let's explore some interesting papers in Rust!

• "Data types à la carte", Wouter Swierstra.
• "Compositional data types", Patrick Bahr, Tom Hvitved.

These papers all discuss the "expression problem", as described by Phil Wadler:

The goal is to define a data type by cases, where one can add new cases to the data type and new functions over the data type, without recompiling existing code, and while retaining static type safety.

Since these are FP papers, they all present solutions in Haskell. I'd like to explore the problem in Rust! Unlike some other "lets implement some papers in language X" explorations, my goal here is not to translate the Haskell solutions into Rust; instead, I want to see what a Rust solution would look like. Partly that's because (at least as of right now) we don't have some of the same building blocks available in Rust (e.g., functors, higher-kinded types). But my hunch is that we have different building blocks that let us produce solutions with the same properties. Let's see if that's true!

Since a big part of the expression problem talks about what you can do without editing existing code, I'm going to implement this is a bunch of different Rust modules. That will help enforce that we're building new capabilities by only writing new code, and not by editing any existing code.

Data types à la carte

§1: Introduction

• ch01a_before: We create a toy language and an AST for it, and write some evaluation rules.

• ch01b_new_method: We add a new method that operates on our AST.

• ch01c_sad_face: We try to add a new kind of term to the language, and get pretty far before running into a brick wall.

§2: Fixing the expression problem

• ch02_open_sum: Create separate types for each kind of term, instead of force-glomming them into a single enum type. Define a generic Sum type to be able to pick and choose which ones to include.

§3: Evaluation

• ch03_evaluation: Define evaluation using a trait, with an impl of that trait for each of our terms.

§4: Automating injections

• ch04_smart_constructors: Make it not so hideously ugly to create instances of our new types.

§5: Examples

• ch05a_multiplication: It's pretty easy to add a new kind of term!

• ch05b_display: It's also pretty easy to add a new function that operates on all of the terms we've defined so far!

§6: Monads for free

• ch06_calculator_monad: In Rust, the monads are even more free? Since we don't really need them?

Compositional data types

§2.1 Evaluating expressions

• ch07a_pairs: Let's add a new type of value to our language.

• ch07b_generic_evaluation: How could we have done a better job of defining our evaluation rules from ch03_evaluation — so that we could reuse them as-is with our new pair-equipped language?

• ch07c_pair_evaluation: And now we can add evaluation rules for pairs too! And we can reuse the existing evaluation rules for integers, even though we now have a more complicated value type.

§3.2 Monadic computations

• ch07d_safer_pair_evaluation: Let's evaluate pairs again, without panicking when we encounter a type error. No changes needed to the evaluation rules — we just need to use a value type that can encode errors!

Eliminating boilerplate

• ch08a_expressions: This was all very fun, but it required more boilerplate than we needed on the Haskell side. Can we get rid of it? First let's create a Rust trait that lines up with the Expr type family. This will let us talk about expressions in any of our mini-languages generically.

• ch08b_open_recursion_evaluation: Blammo! With a little tweak to how we do the recursion, we can update the evaluation rules from ch07b_generic_evaluation so that they work out of the box for any type that implements Expression.