Is it possible to make a compiler for any dynamic/script/interpreter language

Question

Logically, not based on how cost we will spend or how much we will hire programmers to do it.

Can we (Is it possible to) make a compiler for any dynamic/script/interpreter language, like Lua, Python, JavaScript etc, to compile it to native machine code, as like the result that come from C/C++ , without need to modify the syntax/dialect/subset of that language, and accepts it as it without any needs to modify the code (code of project used that language JS for example)?

Or there is a special case/feature make it impossible to write compiler for it?

Answer 1

Can we (Is it possible to) make a compiler for any dynamic/script/interpreter language,

Yes, it is.

Note that there is no such thing as an "interpreter" language. An interpreter is a strategy for implementing a language, it is not a property of the language itself. It is a property of … well … the interpreter.

Also note that the Second Futamura Projection actually gives a way of automatically deriving a compiler from an interpreter, so in a theoretical sense, once you have an interpreter, you also have a compiler as well.

In a practical sense, both the Truffle language implementation framework and the RPython language implementation framework have already successfully demonstrated automatically creating compilers from interpreters, e.g. Truffle has interpreters for Ruby, Python, JavaScript, R, Smalltalk, Newspeak, and even LLVM bitcode, and RPython has implementations for Python and Monte, and used to have working implementations of Smalltalk, Prolog, and many others.

like Lua, Python, JavaScript etc,

Yes. In fact, all of those languages have compilers. There is not a single mainstream implementation of Lua, Python, or JavaScript that does not have a compiler.

For example,

• LuaVM compiles Lua to LuaVM byte code,
• LuaJIT compiles LuaVM byte code to native machine code,
• CPython compiles Python to CPython byte code,
• Jython compiles Python to JVM byte code,
• IronPython compiles Python to DLR Trees,
• GraalPython is a strange one, it parses Python into Truffle ASTs, and then interprets the Truffle ASTs with a specializing interpreter, which is essentially equivalent to compiling the Truffle ASTs (it's related to Partial Evaluation and Abstract Interpretation (aka Supercompilation)),
• PyPy is another strange one, it compiles Python to RPython byte code, interprets that RPython byte code, and uses a tracing compiler to compile a specialized version of the interpreter which can only interpret that one program, which is essentially equivalent to compiling the RPython byte code (it's related to Partial Evaluation and Abstract Interpretation (aka Supercompilation)),
• the original version of Google's V8 JavaScript engine compiled JavaScript straight to native machine code, later versions added a second compiler, so that there was a fast compiler that produced less optimized native machine code, and a slow compiler that produced more optimized native machine code; current versions only have one compiler but also an interpreter,
• SpiderMonkey compiles JavaScript to SpiderMonkey byte code, then interprets part of that byte code, and compiles other parts to native machine code,
• SquirrelFish Extreme compiles JavaScript to SquirrelFish Extreme byte code, then interprets part of that byte code, and compiles other parts to native machine code,
• Nashorn compiles JavaScript to JVM byte code,
• dyn.js compiles JavaScript to JVM byte code,
• IronJS compiles JavaScript to DLR Trees,
• …

As you can see, every Lua implementation, Python implementation, and JavaScript implementation in widespread use, has at least one compiler – some even have more than one.

to compile it to native machine code,

That is an extremely narrow definition of "compile". Compilation only means translating from one language to another language while preserving the meaning of the program. There is no requirement that the target language be native machine code.

And what does "native machine code" mean, anyway? I am writing this on a MacBook Air M1 with an ARM processor, running the AMD64 version of my browser in the Rosetta 2 emulator. So, is the AMD64 code of the browser native machine code or not? What if you run Linux in an x86 emulator on a Java Virtual Machine running on a MIPS emulator running on a SPARC workstation? What if you run Linux in an x86 emulator running on a Java Virtual Machine running natively on a Java CPU?

However, as you can see in my list above, there are indeed several implementations that will actually compile to "native machine code" (e.g. AMD64, ARM, POWER, MIPS, …), for example LuaJIT, Jython when running on e.g. HotSpot, GraalVM, or J9, IronPython when running on Mono, CoreCLR, or CLR, all JavaScript implementations in all major browsers will compile JavaScript to native machine code; I believe V8 even compiles Regexes to native machine code.

Or there is a special case/feature make it impossible to write compiler for it?

No. Some people say that a feature like eval makes it impossible, but that is not true: you could write an interpreter, and compile calls to eval into calls to that interpreter. Or, much simpler, since you already have a compiler anyway: compile calls to eval into a call to the compiler followed by a call to the output of the compiler.

Other people say that macros make it impossible, but that is not true either. In fact, it is just the dual to the problem with eval: instead of making the compiler a part of the program, you make the program a part of the compiler.

In fact, problems like these are not unique to dynamic languages. C++ Templates are Turing-complete, which means that compiling them is equivalent to running a potentially infinite program. Similarly, some extensions to Haskell's type system are Turing-complete, as is Scala 2's type system. Overload resolution in C# is famously NP-complete, so while it is guaranteed that compiling a C# program always terminates, I can easily write a program that takes longer than the heat death of the universe to compile.

Does the fact that compiling some legal C++ programs takes an infinite amount of time mean that you can't have a compiler for C++? Does the fact that compiling some legal C# programs takes longer than the lifetime of the universe mean that you can't have a compiler for C#?

Answer 2

Yes, it is possible to create a “compiler” for any language, no matter how dynamic. But this isn't necessarily a useful thing to do.

1. Many languages like Ruby, Python, and JavaScript are extremely dynamic. Quite fundamental things can be changed on the fly. For examples, the available methods on an object may change during the lifetime of the object. So it is not possible to generate machine code that would be as efficient as machine code generated from C/C++. There must be data structures to allow things to be changed at run time, and there must be extra checks in the machine code to retrieve the current configuration. Optimizations like inlining are only possible speculatively.

2. Another difficulty is a feature like eval(), i.e. the ability to take a string of source code and to execute it. This requires that the resulting program also contains a compiler/interpreter.

As a result of these difficulties, ahead-of-time compilation of dynamic languages is basically non-existent. However, not all is lost. The following strategies are reasonably common.

• A just-in-time compiler (JIT) might generate machine code at runtime. The compiler is aware of what is happening at runtime, and might therefore be able to elide unnecessary checks.
• Speculative optimization creates two code paths: one path that assumes that certain assumptions hold (e.g. that a variable x holds an integer), and a slow fallback path that allows for full dynamic features. The fallback path won't be noticeably faster than an interpreter, but the other path can be very good. At the start of the code section, the program will verify that all necessary assumptions still hold.
  • this is a common feature of JIT compilers, such as the V8 JavaScript engine
  • in Python, the Numba module provides JIT for individual functions, but generates fallback code paths by default
• Not all parts of the code use all dynamic features. For example, a function that doesn't use highly dynamic features like eval() or the JavaScript with statement are much easier to compile. So a compiler can generate more efficient code when it detects suitable subsets of the language.
• In a lot of cases, generating machine code isn't worth the effort. However, bundling an application into a single executable file can be quite convenient. For example, PyInstaller creates an executable that contains the Python interpreter and all Python source code files.

Answer 3

No, it is not, due to possible runtime insertion of code of which the behavior depends on runtime results. This is a common, powerful and arguably horrible feature of script languages: their logic is not necessarily static or pre-determined. "You should not do this!" Maybe not. "This is not common practice!" That depends on the era and the system. In the old days the script languages themselves weren't particularly powerful so people got creative. And add-ons were created: other script languages serving a particular purpose to enhance the performance of the original script language. Code for these add-on script languages would be dynamically generated and subsequently interpreted. Pretty trivial stuff in a script environment, practically impossible to deal with using compiler technology.

Theoretically you could compile generated code on the fly, in runtime, but that would be stretching the definition of a compiled language.