zydeco-lang / zydeco

a proof-of-concept programming language based on Call-by-push-value
Other
49 stars 3 forks source link

Use `tailcall` crate to avoid stack overflow in type checker #37

Closed LighghtEeloo closed 1 year ago

LighghtEeloo commented 1 year ago

Currently our type checker is having stack overflow when handling larger test cases in debug mode. A feasible solution is to change our implementation to adopt tail-call optimization. Since LLVM has supported TCO last year, Rust is going to have it in the near future. Nevertheless, we shouldn't count on that.

As presented on the dynamics, we can use trampoline to turn tail calls into loops. However, this requires extra effort and labor. Thus, we can try to use an external crate tailcall first.

LighghtEeloo commented 1 year ago

It turns out that the crate at the moment is not sufficient for our use case. We need mutual recursions and tail-calls in traits, which is beyond the reach of the crate; to adopt the current code base to use requires more work than manual trampoline. Therefore it seems to be a better idea to do trampoline by ourselves - or defer it until we actually need to.

LighghtEeloo commented 1 year ago

We are now manually doing trampoline. It turns out to be a small amount of work with Rust traits.

maxsnew commented 1 year ago

Can you link to where this is used in the code?

LighghtEeloo commented 1 year ago

Sure. It's used in the type checker and the evaluator.

maxsnew commented 1 year ago

Is there an observable performance difference?

LighghtEeloo commented 1 year ago

Since our test cases are too small, no; but we can pass bigmac.zy right now. The only stack-overflowing test is deterministic-pushdown-automaton.zydeco.