> You did not describe your approach to a problem yet. How would you implement an optimising BNF-based eDSL without macros?
Let's get more concrete. What does the business requirement look like? Do you mean "a language that happens to be expressed in BNF", or are you asking for a DSL for expressing languages which itself looks like BNF?
> Let's imagine you want to embed parsers into your language. Choose any parsing algorithm you like, but parsers must be defined in a BNF-like syntax.
Doesn't sound hard to do in (macroless) scala. Just create objects and methods with appropriate names - and for the optimization part just ensure everything is lazy and preserves the structure so you have the AST available in the language and can do your optimizations at that level (which doesn't have to mean interpreting - we can use the type system to perform these computations at compile time[1]). The syntax will probably end up being slightly differently punctuated from actual BNF, which is a tradeoff for having syntax that follows the ordinary rules of the language and is accessible to e.g. an IDE.
I can agree that languages need to be able to perform complex transformations at compile time. But this doesn't have to be exactly the same kind as the compiler does itself, and as long as the language provides a sufficiently lightweight way of constructing an AST "in" the language, I think it's worthwhile making an explicit distinction between such ASTs and the AST of the language itself.
[1] I can imagine you objecting that this is just a macro system by another name, but it isn't (except in the trivial sense of turing equivalence). It has a different grain: it's more natural to create companion trees that mirror the structure of the AST exactly, and less natural to transform the AST by moving nodes around. And any such companions are explicitly distinct from the "original" tree, and the structure naturally lets you see both.
No, it's not easy, it's a barely usable hack. Coding anything on a type system level is like coding in Brainfuck or Unlambda, while with macros I can use whatever fancy DSLs I already have implemented for nice, declarative compiler construction.
Can you stop in the middle of your translation from BNF to low level code and dump a bunch of nice .dot files plus a tex documentation for the grammar? No. Your type system cannot do it, and you certainly do not want to do it in runtime, it's something to be done exclusively in compile time.
Let's get more concrete. What does the business requirement look like? Do you mean "a language that happens to be expressed in BNF", or are you asking for a DSL for expressing languages which itself looks like BNF?