I’m attempting to write a parser combinator library (yes, another one), and i’d like to be able to exploit static dispatch as much as possible by building expression trees at the type level.
I’ve got a (slightly) reduced example in https://is.gd/1izJC4 , which is a trivial arithmetic interpreter. The inner function
main::prg is supposed to represent a function that will never terminate. Ideally, I’d like to specify a type such as:
type X = Then<Literal<u64>, Fn(u64) -> X>
But presently, rust doesn’t allow types to be self referential in quite that way. I’m trying to work around it with this approach:
type X = Then<Literal<u64>, Fn(64) -> Box<Eval<Out=u64>>>
So here we encode the recursion by casting it to a boxed trait object. However, this doesn’t work so well, with:
note: 'Eval<Out=u64>' does not have a constant size known at compile-time
Which in itself is fine, but at the time I create the box; the concrete type is known. Hence I’m a bit confused.
I know that libraries like
combine will encode recursive rules as free functions that just return a
Result type, rather than an AST, but they also seem to use boxed functions quite a lot, thus requiring pervasive dynamic dispatch.
if anyone could either point out what I’m missing about creating a boxed trait object (The Trait Objects section in the book seems to imply this is doable), or suggest another way to tie these knots, I’d be very happy.