Tying knots in the type system


Hi all,

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.


impl<X: ?Sized + Eval> Eval for Rc<X>

You were demanding that X was Sized, which is what the error message was telling you: it Eval<Out=u64> had to be Sized because of impl Eval for Rc<X>.


Ah, that’s because *self on a &self gives you a Self which is an Rc<X>, not an X. You need to explicitly trigger Rc's Deref by using **self.


That was exactly it. I knew i’d seen the ?Sized constraint used somewhere, but it didn’t quite sink in.