Ah right, those are going to make things fun. :-) I think in your position I'd write a compiler, but keep the AST associated with the byte code and back off to an interpreter if the AST is modified, maybe recompile after enough calls without further change. The call-by-need arguments don't sound too bad, but could take some thought on the memoisation strategy, I think I'd do it at the caller and pass those structures through, but I'd want to think about it.

I'd hardly count myself as an expert, but I think the best win we've had is in thinking carefully about callsite caching strategies and having a eureka moment about just how insanely powerful MethodHandles.exactInvoker can be.