Compiler Development – Best Podcasts for Learning

You oversimplified Guido's statement in phrasing your question. The problem isn't writing a compiler for a dynamically-typed language. The problem is writing one that is (criteria 1) always correct, (criteria 2) keeps dynamic typing, and (criteria 3) is noticeably faster for a significant amount of code.

It's easy to implement 90% (failing criteria 1) of Python and be consistently fast at it. Similarly, it's easy to create a faster Python variant with static typing (failing criteria 2). Implementing 100% is also easy (insofar implementing a language that complex is easy), but so far every easy way to implement it turns out to be relatively slow (failing criteria 3).

Implementing an interpreter plus JIT that's correct, implements the entire language, and is faster for some code turns out to be feasible, though significantly harder (cf. PyPy) and only so if you automate the creation of the JIT compiler (Psyco did without it, but was very limited in what code it could speed up). But note that this is explicitly out of scope, as we're talking about static (aka ahead-of-time) compilers. I only mention this to explain why its approach does not work for static compilers (or at least there's no existing counterexample): It first has to interpret and observe the program, then generate code for a specific iteration of a loop (or another linear code path), then optimize the hell out of that based on assumptions only true for that specific iteration (or at least, not for all possible iterations). The expectation is that many later executions of that code will also match the expectation and thus benefit from the optimizations. Some (relatively cheap) checks are added to assure correctness. To do all this, you need an idea of what to specialize for, and a slow but general implementation to fall back to. AOT compilers have neither. They can't specialize at all based on code they can't see (e.g. dynamically loaded code), and specializing carelessly means generating more code, which has a number of problems (icache utilization, binary size, compile time, additional branches).

Implementing an AOT compiler that correctly implements the entire language is also relatively easy: Generate code that calls into the runtime to do what the interpreter would do when fed with this code. Nuitka (mostly) does this. However, this doesn't yield much performance benefit (failing criteria 3), as you still have to do just as much unnecessary work as an interpreter, save for dispatching the bytecode to the block of C code which does what you compiled in. But that's only a rather small cost -- significant enough to be worth optimizing in an existing interpreter, but not significant enough to justify a whole new implementation with its own problems.

What would be needed to fulfill all three criteria? We have no idea. There are some static analysis schemes which can extract some information about concrete types, control flow, etc. from Python programs. The ones that yield accurate data beyond the scope of a single basic block are extremely slow and need to see the whole program, or at least most of it. Still, you can't do much with that information, other than perhaps optimize a few operations on builtin types.

Why's that? To put it bluntly, a compiler either removes the ability to execute Python code loaded at runtime (failing criteria 1), or it does not make any assumptions that can be invalidated by any Python code at all. Unfortunately, that includes pretty much everything useful for optimizing programs: Globals including functions can be rebound, classes can be mutated or replaced entirely, modules can be modified arbitrarily too, importing can be hijacked in several ways, etc. A single string passed to eval, exec, __import__, or numerous other functions, may do any of that. In effect, that means almost no big optimizations can be applied, yielding little performance benefit (failing criteria 3). Back to the above paragraph.

No. The reason why there are speed differences between languages like Python and C++ is because statically-typed languages give the compiler tons of information about the structure of the program and its data which allows it to optimize both computations and memory access. Because C++ knows that variable is of type int, it can determine the optimal way to manipulate that variable even before the program is run. In Python on the other hand, the runtime doesn't know what value is in a variable right until the line is reached by the interpreter. This is extremely important for structures, where in C++, the compiler can easily tell the size of the structure and every location of its fields within memory during compilation. This gives it huge power in predicting how the data might be used and lets it optimize according to those predictions. No such thing is possible for languages like Python.

To effectively compile languages like Python you would need to:

1. Ensure that the structure of data is static during the execution of the program. This is problematic because Python has eval and metaclasses. Both which make it possible to change the structure of the program based on the input of the program. This is one of the things that give Python such expressive power.
2. Infer the types of all variables, structures and classes from the source code itself. While it is possible to some degree, the static type system and algorithm would be so complex it would be almost impossible to implement in a usable way. You could do it for a subset of the language, but definitely not for the whole set of language features.