3 ms·
It's an interesting article. Has some oversights but still a good design space to think about. I like the Futamura projections approach. The associated descrip
by JonChesterfield 3y ago
It's an interesting article. Has some oversights but still a good design space to think about.
I like the Futamura projections approach. The associated description of write a partial evaluator and you get a compiler for free is starting to look like an inside joke - compilers are easier to write than partial evaluators - but the Graal/RPython approach where someone else has already written the partial evaluator and you strap on your own interpreter has definite merit.
There's also this community wisdom, echoed in the article, that python can't be made fast because the runtime extensible language semantics get in the way. Somehow that is known to be true despite javascript having the same properties and very fast implementations, and people are still holding onto it as truth after Mojo starts talking about statically compiling the static parts of the program. Also the self and lisp implementations that came before.
--------
For what it's worth, my current thinking on this goes:
0/ Representation. Define a static single assignment form bytecode
1/ Front end. Translate source semantics into that bytecode as simply as possible
2/ Runtime. Write a machine code implementation of each opcode used by 1/
3/ Back end. Compile the bytecode to a series of (machine code) calls to said opcodes
That's the baseline compiler. No baseline interpreter involved. Main design goal of each step is to do the absolute bare minimum work possible. An argument could be made that the above describes a template jit if you do the translation at runtime, or a naive ahead of time compiler if you do it before running the program. They're the same thing really.
Going from there to non-baseline compiler involves increasingly heroic optimisations on the SSA form and adding operations to the bytecode that correspond to things like memory operations on the target machine.
--------
The compiler runtime is worth a mention as it's something which doesn't get much love in compiler implementation discussion. I didn't realise it existed before I started working on these things. A compiler is a translator from language A to B. Wherever something in A doesn't have an obvious counterpart in B - maybe A has hash tables and B is x86 machine code - either the compiler emits code that makes the thing happen anyway, or it emits a call to a pre-written function.
This might be integer division written as a loop for hardware that doesn't have integer divide, or it might be an openmp offloading construct parametrised on a function pointer. You can essentially move complexity out of the compiler and into the supporting library, and functionality can move between the two at will. If the runtime library is written in (or compiled to) the compiler intermediate representation instead of machine code, you can get the same performance and semantics as having the compiler build the same code on the fly.
- noelwelsh 3y agoJavascript has different runtime properties where it counts. You can't subclass numbers or inspect the stack in JS, which you can do in Python. These (bad, IMO) design decisions make Python harder to optimize than JS.
- tonyg 3y agoThis doesn't follow. Both Self and Smalltalk allow you to do those things. (You still need to specialise code for plain small ints vs oops either way for the subclassing one, and stack inspection can be done on a slow path, see the dynamic deoptimization stuff)
- noelwelsh 3y agoIt's not impossible, just more work. V8 would be something like 100 man years of work, and that's with a language that is somewhat easier to optimize.
- tonyg 3y agoI don't think it's even more work. (V8 has the dynamic deopt stuff already...) But at this point I guess we're dueling reckons. Python is hard to optimize in a semantics-preserving way, of course, because the semantics are so bonkers. I just don't think it's stuff like subclassing int or inspecting the stack that makes it difficult.
- noelwelsh 3y agoI can agree with this take. What about Python do think makes it hard to optimize?
- tonyg 3y agoHmm. Off the top of my head, mind, but: - The bad API to foreign code that all the extensions depend on. - The nuts scoping rules, though I suppose throw enough static analysis at it and you might be OK. - Reference counting, which people depend upon. - locals(), globals(), though you could do some tricks with deoptimization there too I suppose. - Its metaclass system is pretty wacky. In general, just the overall ugliness of the design. It'd be jolly difficult to get beyond a toy operational model of the language, for example. There are so many corner cases to get right. Compare, say, Smalltalk, where there's an actual aesthetic to the metasystem (in all its 80s glory), and a full implementation can be remarkably small and simple; or anything else where you could plausibly capture an operational semantics without too much fuss.