2 ms·
This is called the Expression Problem because, as you allude to in your example, it comes up all the time in compilers and interpreters when dealing with expres
by couchand 5y ago
This is called the Expression Problem because, as you allude to in your example, it comes up all the time in compilers and interpreters when dealing with expressions.
If you're looking for an elegant solution (the first I've ever seen), check out the work by Kiselyov on tagless final encodings.
The core idea is to invert the interface. Instead of the expression types being objects that implement an interface consist ing of operations, or the expression types being enum values and the operations being total functions of those enums, the interface is the abstract logic of the operation, and the interface methods are the expression types.
Adding new operations is easy, it's a new interface implementation. Adding new expression types is easy, too. You create a new interface for the new type, and implement that interface for each compatible operation.
It does require typeclasses or traits or something like that, and if you want the full power you need language support for higher-kinded types. Look at the papers for full examples, but here's a teaser in pseudocode:
interface BoolLogic {
fn bool(bool) -> Self;
fn if(Self, Self, Self) -> Self;
}
struct Eval {
value: Anything
}
implement BoolLogic for Eval {
fn bool(value) -> Eval {
Eval { value }
}
fn if(condition, consequent, alternate) -> Eval {
if (conditon.value)
consequent
else
alternate
}
}
struct Print {
text: String
}
implement BoolLogic for Print {
fn bool(value) -> Print {
let text = value.toString()
Print { text }
}
fn if(condition, consequent, alternate) Print {
let text = "if (" +
condition.text +
") {" +
consequent.text +
"} else {" +
alternate.text +
"}"
Print { text }
}
}
interface NumLogic {
fn num(int) -> Self
fn add(Self, Self) -> Self
fn eq(Self, Self) -> Self
}
implement NumLogic for Eval {
fn num(value) -> {
Eval { value }
}
fn add(left, right) -> Self {
let value = left.value + right.value
Eval { value }
}
fn eq(left, right) -> Self {
let value = left.value == right.value
Eval { value }
}
}
fn munge<T: BoolLogic + NumLogic>() -> T {
T.if(T.eq(T.add(T.nu.(2), T.num(2)), T.num(4)), T.num(42), T.num(0))
}
If you're curious I'd highly recommend reading and implementing the papers yourself. Have fun writing a typechecker, it's surprisingly easy! (with HKTs...)