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 Rust Playground , 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.

Thanks,