We are going to be taking chunks of source code, translating them to machine code (directly or indirectly) and executing them. If we do it all in one pass, it is ahead of time execution. If we do it in chunks interleaved with execution, it is just in time.
What do you call interpreted? My guess is that you mean compiling just time, except you forget the chunks you already translated, instead of reusing them and composing them into bigger chunks.
It's particularly difficult to compile ahead of time, to native machine code, a dynamically typed language like Python.
Yes. Not impossible.
Largely as a result of the above, the implementation of these languages is often interpreted.
Yes. Well, depends on what you call interpreted. However, just in time, yes.
Let us break it down...
As you already know, you need to know the target machine. Which means that you either compile your code for multiple target machines before deployment, or you do it on deployment (the installer does the ahead of time compilation).
Now, Let me talk to you about type erasure. The true type erasure, not the Java brand, however I will not go there.
If the compiler knows all the types ahead of time, that is during static analysis, which is easy with static types...
Then it knows exactly how each routine/method/function will be called, and thus it knows the exact memory layout and how to perform operations on it. Thus, it can emit optimized native code for that, and there would be no need to do type checks in runtime.
Thanks to that, the compiler can write native code that does not need type information. Which means that type information can be erased from the runtime. Hence type erasure.
You can see where I am going, however there are a couple stations I want to visit on the way. First stop: generics.
When we have a generic type, we have type parameters that might or might not be known ahead of time. For an application, the compiler can look at every place the type is used, and emit optimized code for each variant. That also means that compiling libraries with open generic types ahead of time will only be possible along side the final application.
By the way, to use libraries in any shape or form, they must have some level of type information anyway. Thus, not full type erasure.
Second stop: reflection and emission.
Let us say we want to create a new type on runtime. Well, the information of that type would only be available on runtime in particular if it depends on external input.
Furthermore, if you have something like monkey patching (where a type can change in runtime) or "eval" it is all worse.
Destination: dynamic types.
If we do not know the types of variables and parameters, we cannot emit optimized code for them. It is possible to do static analysis on a dynamically typed language and get type information. This is a huge task, because the source does not mark types... the static analysis would have to follow the values in the code... and you know what? It is easier to execute the code and see where the values go (which would be just in time compilation). In essence the compiler would have to do that, except following every possible branch.
Just in time compilation still emits native machine code, except it does it on demand.
When a routine/method/function is being called, the JIT will see if it has already been compiled for the particular combination of types it takes, if so, it can execute that machine code. Otherwise, now that we know the types, it can be compiled and executed. There are also tiered JIT systems that emit native code quickly the first time (reducing start up time), and then on the background work on more optimized code to replace it with.
Alright, there is a twist: what if we settle for sub-optimal code? Above I was saying optimized code. However, we could handle dynamic types on machine code with sub-optimal code. In particular, we can use a variant type for primitive types, and something like an Entity-Component-System for compound types.
It would be full native code from a dynamically typed language. However, it will might have worse performance than JIT.
No, this does not solve generics, it solves dynamic types.
So, yes dynamically typed languages are hard to compile to native code ahead of time. However, they are often compiled just in time.
I also want to mention that there are solutions that will compile ahead of time what they can, and use JIT for everything else.
I suspect complexity theory (and more specifically the halting problem itself when it comes to the problem name binding / dispatching) is really to be blamed here
I suppose there is an analogy in trying to figure out type information, and that it is sometimes undecidable.
However, it is not really the halting problem. Most compilers are happy to produce machine code that will never halt (just try an infinite loop in your favorite language). They do not care. They do not try to proof the program will halt.
There are languages that do proof automation, they will try to check if the program will halt, and give you one of three: a) we know it will halt. b) we are not sure, proceed on your own risk. c) we know it will not halt. Those languages are not dynamically typed.
But I'd like to know if this has been formally studied, for either any of these languages in particular, or a larger class of languages.
Perhaps also to help with the above, what are some notable examples of dynamically-typed languages with AoT-compilers to native machine code?
Since you ask for Python, I had a look. There seem to be a few options: Nukita, mypyc, Numba. I do not know much of them.
Any language that can run on .NET or Java, for which there already are ahead of time compilation solutions, could be compiled ahead of time. Those are a lot of languages. And there is already ahead of time compilation for a few. First to come to mind is Ruby. Yes, it has “eval” and monkey patch, I know. It will not be possible for every program to be compiled ahead of time, because sometimes the program will depend on user input.
That is the thing. Not every valid program in a dynamically typed language can be compiled ahead of time. If a program creates or modifies types on runtime, there is no way to have that type information ahead of time. The same goes for any library with open generic types. Not because language complexity or the halting problem, but because of the space time continuum. We haven't figured out time travel to get the type information of types that are yet to exist.
Yet, as I was saying above, you could have sub-optimal code. Have you seen .NET Dynamic Language Runtime? .NET is statically typed, with reflection. Using the .NET Dynamic Language Runtime (which is full .NET code), it can have objects statically typed as dynamic. This was developed to port Python and Ruby to .NET, which was done successfully, and was followed by other languages (note that these ports are behind the main version of those languages).
Yeah, the real problem for ahead of time compilation is not the dynamic types part, the problem are code emission, open generics and similar forms of metaprogramming.