[ChadNauseam]

Writing efficient interpreters in a functional style is not easy. I write interpreters in OCaml for a living and we had to switch to a mutation-heavy style for performance and memory usage reasons. It can be done though.

When you think about it, any dependently typed language has to have an interpreter inside it, because you can put function applications inside a type and the typechecker will probably need to evaluate the application at some point. The go-to technique is to use Normalization by Evaluation [0], where you convert the AST version of a function in the interpreted language to an actual function in the host language, and piggyback off the host language's (presumably very fast) function application.

[0]: https://en.wikipedia.org/wiki/Normalisation_by_evaluation

[Quekid5]

I suspect you already know this, but other readers might be interested to know that in Haskell you can also use the ST monad which can do local (actual) mutation which is guaranteed to not escape the function's scope.

(Of course you can only access the actual local state and not do I/O or anything like that.)

[vnorilo]

Sure, but there are many kinds of interpreters!

I was involved with one that wasn't really demanding in terms of computation, but was distributed in a way that required a lot of speculation and rollbacks. The functional approach was pretty sweet.

Highest speed bytecode interpreter is actually one of the few loops where I prefer assembly to C, as the instruction mix, branch prediction and even the use of stack can be weird from the PoV of a modern optimizing compiler.

[agumonkey]

Isn't there a way to derive efficient/in-place interpretation from pure total recursive functions ?

reading lisp in small pieces, the author migrates interpreters from naive recursive eval to bytecode. It felt there was an underlying model to extract.

[mbrodersen]

I am also in the compiler/interpreter business. Can you tell me more about what you are working on? It sounds interesting.