Skip to main content

Evaluate an expression without a match

This context evaluates arithmetic expressions such as 2 * (3 + 4) and converts them to Lisp, with one provider per operator and no hand-written match over the language. It is the first example in expression, an interpreter from the cgp-examples repository, built with Context-Generic Programming (CGP), which enables pluggable trait implementations, one per operator, resolved at compile time. Each later example changes one thing about this one, so every piece it introduces comes back.

tip

New to CGP?​

The Hello World tutorial introduces contexts, providers, and wiring with a smaller program. Extensible variants explains how CGP takes an enum apart for a provider, which is the idea this page puts to work. This page can be read without either.

The problem​

The task is an interpreter for a small arithmetic language, with two operations over it: evaluating an expression to a number, and converting it to Lisp. On its own, that is easy. What makes it interesting is the requirement that the interpreter stay open: new operators and new operations should be addable later, from code that cannot edit what is already written, such as a second crate.

Without CGP​

The crate keeps the ordinary Rust version in its classic module, and it is the right design for a language that will not change:

pub enum Expr {
Plus(Box<Expr>, Box<Expr>),
Times(Box<Expr>, Box<Expr>),
Literal(u64),
}

pub fn eval(expr: Expr) -> u64 {
match expr {
Expr::Plus(a, b) => eval(*a) + eval(*b),
Expr::Times(a, b) => eval(*a) * eval(*b),
Expr::Literal(value) => value,
}
}

A new operation is easy here: another function with its own match. A new operator is not. It means adding a variant to Expr and an arm to every match over it, and a crate that does not own Expr cannot do it at all. The other common Rust design, a trait with one method per operation and one impl per operator, has the opposite problem: new operators are easy, and every new operation is an edit to every impl. Keeping both directions open at once, with the compiler still checking that every case is handled, is known as the expression problem, and it is what this page's design addresses.

Run it​

From the root of the cgp-examples repository:

cargo test -p cgp-example-expression add_mult::

The context's two tests pass:

test contexts::add_mult::test::test_add_mult ... ok
test contexts::add_mult::test::test_add_mult_to_lisp ... ok

The first evaluates 2 + 3, 2 * 3, and 2 * (3 + 4) to 5, 6, and 14. The second converts the same three expressions to Lisp, so 2 * (3 + 4) becomes the tree for (* 2 (+ 3 4)).

The language is an enum of operator structs​

The context's module, add_mult.rs, defines the language and the Lisp output as two enums:

pub type Value = u64;

#[derive(Debug, CgpData)]
pub enum MathExpr {
Plus(Plus<MathExpr>),
Times(Times<MathExpr>),
Literal(Literal<Value>),
}

#[derive(Eq, PartialEq, Debug, CgpData)]
pub enum LispExpr {
List(List<LispExpr>),
Literal(Literal<Value>),
Ident(Ident),
}

Each variant wraps an operator struct defined elsewhere in the crate, such as Plus<Expr> with its left and right fields, instantiated here at MathExpr itself. So the operator structs, and the providers written for them, know nothing about this particular language. #[derive(CgpData)] exposes each enum's variants to generic code by name, which is what lets CGP take the enum apart without a match.

One provider per operator​

Evaluation is written as one provider per operator. This is the one for Plus, from the crate's providers/eval/add.rs:

#[cgp_impl(new EvalAdd)]
#[uses(CanCompute<Code, MathExpr, Output = Output>)]
impl<Code, MathExpr, Output> Computer<Code, Plus<MathExpr>>
where
Output: Add<Output = Output>,
{
type Output = Output;

fn compute(
&self,
code: PhantomData<Code>,
Plus { left, right }: Plus<MathExpr>,
) -> Self::Output {
let output_a = self.compute(code, *left);
let output_b = self.compute(code, *right);

output_a + output_b
}
}

EvalAdd implements Computer, CGP's interface for a computation that takes an input and returns an output, keyed by a marker type called the Code. Inside the impl, self is the context, the type that stands for this interpreter and holds its choices. #[uses] declares what EvalAdd needs from it: the ability to evaluate each operand. So EvalAdd adds two evaluated operands without knowing what kind of expression they are, or which enum MathExpr is. EvalMultiply is the same with *, and EvalLiteral returns a literal's value.

The context wires each operator to its provider​

Interpreter is the context. It has no fields, because every choice it makes is in its wiring:

pub struct Interpreter;

delegate_components! {
Interpreter {
open { ComputerComponent, ComputerRefComponent };

MathExprTypeProviderComponent:
UseType<MathExpr>,
LispExprTypeProviderComponent:
UseType<LispExpr>,

@ComputerComponent.<Code> Code.MathExpr: DispatchEval,
@ComputerComponent.<Code> Code.Plus<MathExpr>: EvalAdd,
@ComputerComponent.<Code> Code.Times<MathExpr>: EvalMultiply,
@ComputerComponent.<Code> Code.Literal<Value>: EvalLiteral,

@ComputerRefComponent.<Code> Code.MathExpr: DispatchToLisp,
@ComputerRefComponent.<Code> Code.Literal<Value>: LiteralToLisp,
@ComputerRefComponent.<Code> Code.Plus<MathExpr>: PlusToLisp,
@ComputerRefComponent.<Code> Code.Times<MathExpr>: TimesToLisp,
}
}

The open statement lets the table choose a provider by the computation's parameters, and each @ entry makes one choice. A key has two parts after the component: the Code, here the generic <Code> Code that matches any marker, and then the input type. So @ComputerComponent.<Code> Code.Plus<MathExpr>: EvalAdd reads "to compute anything on a Plus<MathExpr>, use EvalAdd". delegate_components! documents the syntax.

The two operations use two components. Evaluation goes through ComputerComponent, which takes its input by value, and conversion goes through ComputerRefComponent, which borrows it. Calling compute evaluates and calling compute_ref converts, whatever Code the caller passes. The two UseType entries set the context's two abstract types, type names the context fills in so that providers can use them without knowing the concrete type. The conversion providers below read the Lisp one, and the next example's provider reads the other.

A small wrapper takes the enum apart​

The MathExpr entries go to a provider the module writes for itself:

#[cgp_impl(new DispatchEval)]
impl<Code> Computer<Code, MathExpr> for Interpreter {
type Output = Value;

fn compute(context: &Interpreter, code: PhantomData<Code>, expr: MathExpr) -> Self::Output {
<MatchWithValueHandlers>::compute(context, code, expr)
}
}

MatchWithValueHandlers is CGP's generic dispatcher. It finds which variant the enum holds and hands the operator struct inside back to the context, whose table sends it to EvalAdd, EvalMultiply, or EvalLiteral. That replaces the match a plain interpreter would write, and the compiler still checks that every variant has a provider.

The wrapper is there because wiring MatchWithValueHandlers as the MathExpr entry directly sends the compiler round a loop it cannot finish: evaluating a MathExpr needs evaluating its operands, which are MathExpr again. A wrapper written for one concrete context breaks the loop. Dispatch layers explains why, and every context in the crate has its own.

Conversion builds a type it does not name​

The conversion providers produce a LispExpr, but they are written without naming the enum. This is the one for Plus, from providers/to_lisp/add.rs:

#[derive(CgpData)]
enum LispSubExpr<Expr> {
List(List<Expr>),
Ident(Ident),
}

#[cgp_impl(new PlusToLisp)]
#[use_type(HasLispExprType.LispExpr)]
#[uses(CanComputeRef<Code, MathExpr, Output = LispExpr>)]
impl<Code, MathExpr> ComputerRef<Code, Plus<MathExpr>>
where
LispSubExpr<LispExpr>: CanUpcast<LispExpr>,
{
type Output = LispExpr;

fn compute_ref(
&self,
code: PhantomData<Code>,
Plus { left, right }: &Plus<MathExpr>,
) -> Self::Output {
let expr_a = self.compute_ref(code, left);
let expr_b = self.compute_ref(code, right);
let ident = LispSubExpr::Ident(Ident("+".to_owned())).upcast(PhantomData);

LispSubExpr::List(List(vec![ident.into(), expr_a.into(), expr_b.into()]))
.upcast(PhantomData)
}
}

#[use_type] brings in LispExpr as an abstract type the context defines, which the UseType<LispExpr> entry above sets. The provider builds only the two variants it needs, in a small local enum, and upcast turns that into the full LispExpr, which works because every variant of LispSubExpr is also a variant of LispExpr. So PlusToLisp serves any Lisp type that has a list and an identifier.

The checks cover every input​

The module asserts its wiring with check_components!, listing each operation and input pair:

check_components! {
Interpreter {
ComputerComponent: [
(Eval, MathExpr),
(Eval, Literal<Value>),
(Eval, Plus<MathExpr>),
(Eval, Times<MathExpr>),
],
ComputerRefComponent: [
(ToLisp, MathExpr),
(ToLisp, Literal<Value>),
(ToLisp, Plus<MathExpr>),
(ToLisp, Times<MathExpr>),
]
}
}

Eval and ToLisp are empty marker structs the crate defines as its codes. Listing each operator, not only MathExpr, is what makes a missing operator entry fail at the check, as the change below shows.

Try a change​

Remove the evaluation entry for Times, the line @ComputerComponent.<Code> Code.Times<MathExpr>: EvalMultiply, and run cargo cgp check. The check names the missing entry:

error[E0277]: [CGP-E001] missing wiring for `@ComputerComponent.Eval.Times<…>` on `…`
= note: root cause: [CGP-E113] missing wiring for `@ComputerComponent.Eval.Times<…>` on `…`
this is required through the dependency chain:
[CGP-E101] consumer trait impl `CanCompute<Eval, Times<…>>` for context `…`
└─ [CGP-E103] redirect lookup to `@ComputerComponent` in `…`
= help: wire `@ComputerComponent.Eval.Times<…>` to a provider in the wiring of `…`

A second, longer error, [CGP-E002], points at the wrapper's call to MatchWithValueHandlers, because the dispatcher's chain cannot provide a Times operand either. The first error is the one to read, and the block elides the module paths, which name the context's module. Removing the entry leaves EvalMultiply unused, so the output carries a warning about that import. cargo cgp check leads with the root cause for the classes it recognizes, and the tool does not yet reshape every class. Put the line back, and the check passes.

The pattern​

This context shows the extensible visitor pattern: an operation over an enum written as one provider per variant, with a generic dispatcher in place of the match. Each provider handles one operator and asks the context about the rest, so it serves every language that contains that operator, and a new operator is a new provider and a new entry rather than an edit to every operation. Extensible variants explains the representation that makes this possible, and Dispatching explains the dispatchers.

The cost is the machinery. Where the plain interpreter has an enum and a match, this one has operator structs, a provider per operator per operation, a wiring table, and a wrapper per context, and a mistake is a compile error with a long chain behind it. For a language that will not grow, the match is simpler and better.

Where to go next​


An AI agent wrote this page using the CGP knowledge base. Its content was verified against the project's source. See How AI is used in this project.