Update: This post got many good comments and useful answers summarized at the very end.
Or rather, are there any widely used implementations of a popular-enough language that directly interpret ASTs (or similar)? [1] Anything that doesn't compile to assembly to bytecode would do.
This post is prompted by my recent awareness of the Spry language and my own attempt at a Python direct AST interpreter written in Python.
I could only find language implementations that are compiled to assembly and language implementations compiled to bytecode. Compilation can happen at different points before execution (e.g., an explicit compilation step, caching at runtime, or JIT), but ultimately every language is compiled.
Python uses bytecode. Both CPython and PyPy. (Jython compiles to the Java VM's bytecode and I think IronPython compiles to .NET?)
Ruby apparently started out as an AST interpreter but I couldn't find any direct reference to that. It now has a bytecode. Ruby also have alternate implementations for other virtual machines' bytecode.
Perl, Javascript (different implementations compile to either bytecode or machine code) and even PHP work similarly.
Maybe the reason there are no interpreted languages is speed? But a (bytecode) interpreted language already has a speed penalty so why not just make that a bit greater and allow simpler internals? I'd be happy with a 100x slowdown (compared to, say C) to get direct AST interpretation in a dynamic language. Or maybe even a larger constant factor like 1000x if I can be sure never to exceed that.
However, if the main loop for AST interpretation in some language L is 10 times slower, then calling functions written purely in L (from L) results in a 100x slowdown. Having one more layer of pure L (calling a library which itself calls an underlying library) already brings us to 1000x. In other words, the issue is that the speed loss is the product of the speed lost at each (pure L) layer!
One way to get around this is to have the slower part written in a faster language (such a C libraries in Python). But in my mind, that's cheating a bit on the direct AST requirement. In some sense, this is manually compiling L to a faster language.
But the same argument should still apply with bytecode interpretation loop! But it seems that reducing the base exponent to the bytecode loop's slowdown and some speed hacks like the above were enough to make bytecode interpreted languages viable.
This article tries to address some of the speed issues by specializing nodes to the type of their value. That feels somewhat tangential to the above. I have not seen a widespread implementation using this method.
The most useful to myself is by thequux who pointed out the speed calculations were wrong and I agree. If the (worst) ratio between an AST-interpreted loop iteration and bytecode loop iteration is o then the maximum amount of time spent by directly interpreting everything is at most o times the time spent by running everything in bytecode! It does not matter how nested the functions are.
Depending on the value of o, maybe I didn't need to look for an example anyways.
Updates on existing languages. The question I meant to ask is if there are popular implementations of popular language that are interpreted (thank etc)
Other ways to speed up direct interpretation:
[1] If there's a better word than "interpreted languages" for this definition, feel free to make a suggestion.
AST intermediate representations in the Lambda the Ultimate forums
Posted on Feb 22, 2018