Forth is a language that is simple to parse and executed by a virtual machine with a stack, possibly using byte code. However, this is not the type of compilation that the article is talking about. Performing operations on a stack (that can grow deep) is often not as efficient as assembly code that can use several registers to store immediate results.
i have written a couple of forth-like languages (which were pretty fast) but i can imagine extending a forth to use registers, if they were available.
Also, no virtual machine, at least for a machine code implementation. I wrote a forth like in c++ to implement adventure games, but the first I wrote was in z80 assembler, no vm.
Judging by the example of Babashka, Graal apparently does give you a "huge opaque runtime", and also there seem to be severe limitations on loading code. I think it basically has to include all the Clojure code up front, which makes it arguably NOT interactive.
RPython and PyPy are great engineering and great projects, but I think RPython has not quite "escaped" into the real of general purpose language implementation -
Looking at the list of requirements:
0. Only 1-2 years of dev effort to implement.
1. Predictable, explainable performance.
2. A small, embedabble runtime.
3. Support for repl / incremental programming (ie adding one function shouldn't require stopping the process and re-compiling the entire project).
4. Support for debugging and profiling.
Lisp satisfies 1, 3 and 4 I’m pretty sure, and maybe 2 depending on your definition of small. Idk about 1 though.
I glossed over this the first time around, and it seems like others did too, but once you add the following constraint, it takes many languages off the table -- Java, basically all Lisps, Julia, OCaml, etc.
> Ability to use static dispatch, static field offsets and stack allocation.
> Control over memory layout - at minimum being able to express arrays-of-structs without pointer soup.
---
So reading between the lines a bit, I believe the author is asking for an REPL'd, interpreted, and fast running Go, Swift, Rust, C++, or Zig. (which to me is an interesting problem -- I basically use shell as my REPL for C++)
OCaml with new value types would qualify, and Java with value types would qualify, but they're not there yet AFAIK.
I think Julia/Clasp can get that kind of performance in some cases, but it's not predictable performance, with language control.
How much of these things make an interactive language difficult? Many languages can be used interactively, but only in very simple ways of being interactive. To be truly interactive one also needs dynamic behavior. Let's say we define a struct with fixed fields (which Lisp can) and we want to interactively redefine the thing. If we want to stay in our interactive flow the runtime needs additional changes. It needs to deal with existing and future allocated structures. It needs to deal with inlined accessors etc. One of the simple ways to deal with that is to kill the program and start over. But that is not 'interactive'. Static types also get in the way of dynamic behavior.
That's why the interactive versions of languages like C, Rust, Haskell typically are not very interactive and come with a lot of compromises. Often compromises at the boundary of compiled and 'interpreted' code.
What does 'interpreted' mean and why would we actually need it? Lisp as its bases has a radical interpreter: it interprets source code in the form of s-expressions. Most people think of interpreted code "byte code interpreters" - that's an entirely different form. The source code gets compiled to a byte code interpreter. In Lisp its quite often that one uses incremental native code compilers. These achieve much faster running code, in a spectrum of possible optimizations: optional type declarations, reduced runtime safety, code inlining, stack allocation, type specialized code generation and more. Many of these optimizations make the code harder to write. SBCL by default always uses the native code compiler. If we want "byte code" interpreted code, there is no way to make it fast without either some form of native code compilation (typically a JIT compiler) or writing the code in some other language (Python + C). The alternative is to get rid of byte code and having a native code compiler, with the drawbacks: one or more hardware architectures to support.
> Control over memory layout - at minimum being able to express arrays-of-structs without pointer soup.
That's a problem. Lisp needs to deal with it when interfacing 'foreign' memory. Thus it typically has a foreign-function interface.
> I believe the author is asking for an REPL'd, interpreted, and fast running Go, Swift, Rust, C++, or Zig. (which to me is an interesting problem -- I basically use shell as my REPL for C++)
There are compromises to make. "Interpreted" already is vague, see above. "Fast running" - is it always "fast running"? Is that possible? While being "interactive" / "interpreted"?
"REPL" is another concept with a range of possible meanings. Is a Read Eval Print Loop like in Lisp integrated into the language (read, print, eval, loop are primitives in the language) and is it the base for interactive programming. Is it a glorified command line interpreter which basically can call functions on data?
I agree with you, the language design implications are just as interesting / important. What I imagine the problem statement as is to make a definition like this:
And then suppose you have 1000 translation units that #include layout.h
So whenever you change N, you have to recompile a lot of code.
And then you want to compile myprog quickly, and run the following quickly:
cat 2gigs.txt | ./myprog
It's an interesting problem, but I think from the perspective of an interactive language, it does make sense to have some kind of fast mode and slow mode ... the classic debug/release build split is precisely that. I would settle for an interactive C++/Rust, with a good incremental build system, where you can choose the build variant!
C++ build systems suck, and Rust often has to interface with them. And both C++ and Rust are not designed for fast interactive use. They have a lot of syntax that allows the control over memory, and that's perhaps a bigger problem.
I also don't really like typing code into a REPL -- I use an editor and a shell (and Ninja, which turns out to be crucial for fast C++ dev).
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.
Javascript 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.
This 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)
I 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.
- 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.
Oh! Neat: Shriram's group wrote a 2013 paper on semantics for Python. It's roughly what I would have expected it to be. It doesn't look like it addresses mutation of module bindings, for example, but perhaps the paper just doesn't show enough of the full model they built, or I'm misunderstanding the desugaring they are using. https://cs.brown.edu/~sk/Publications/Papers/Published/pmmwp...
While I can't argue about Python's design decisions impacting the ability to optimise it (not my area of expertise), I'd like to defend these decisions.
Subclassing numbers (or other primitive types) is one way to achieve the goal of having type-safe enumerations. In Python, I can do:
class Weekday(int): pass
Monday = Weekday(1)
...
The value x=1 will not pass the test of isinstance(x, Weekday); mypy won't let you accidentally pass April as a Weekday; etc. There definitely are many ways to make this prettier, or easier for an optimising compiler, but I would like to echo DJB's talk referenced by the original article:
> Programmers waste enormous amounts of time thinking about, or worrying about, the speed
of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered.
Likewise, the ability to inspect the stack enables creation of useful tools, that would be difficult or impossible otherwise. When working with pytest, I can write "assert my_array == [1, 2, 3]"; when my_array contains an extra element at the end, my test fails with a pretty-printed diff of the two sides.
You don't need to perform aggressive whole-program optimisation passes when running a test suite, and you shouldn't need to inspect the stack at runtime while executing performance-critical sections in production. I save time and energy by not having to add "print(my_array)", re-running the tests, and copy-pasting the pretty-printed values for diffing. I save time and energy when my program has less bugs, because I had the tools to make it more correct.
I agree those are useful tools, but I think the same goals can be achieved with different tools that don't make optimization hard. For example, type safe enums are one use of so-called algebraic data types found in Rust / Scala / Swift etc. (The language feature is called an enum in these languages, but it can represent a lot more than what people usually think of as an enumeration.)
100% agree on everything you said. However it's easy to judge Python's mistakes through the lens of where we are right now - nobody even considered tracing JITs for dynamic languages before V8 showed up, and without this perspective, subclassing int could look like the more ergonomic choice.
Python could have had ADTs as a core language feature 20+ years ago (rather than sloppily grafting them on in a recent release), just like it could have had unicode strings as the default text type since before 2.x (1.6 was 2000; unicode was early 1990s). But it also had a much smaller community back then, and who knows how making these choices back then would've impacted its development? Maybe it'd end up being as relatively obscure as say Tcl.
Also I think you could still achieve reasonable optimisations even if you do go that route; Go has type aliases (including on primitive types) that you can define custom methods on:
type Weekday int
const (
Monday = Weekday(1)
...
)
func (w Weekday) Name() string {
switch w {
case Weekday(1):
return "Monday"
...
default:
panic("?")
}
}
If your compiler could prove nothing crazier than that is happening with your int subclass, I don't see why similarly written Python code should have a lower performance ceiling; but yes, that's more work for the compiler.
IMO SSA is not useful for bytecode formats; it is rather for doing optimizations in a compiler. When designing Wasm, several team members work working on PNaCl (LLVM bitcode) and others were working on Web VMs. The fact that SSA requires deconstruction would have made baseline compilation and interpretation more complex and we gravitated towards a stack machine without SSA.
Don't underestimate how much extra startup time it adds to do even one pass over the code. For really big applications (think 100MB or more of code), you want to avoid touching the code at all. You certainly don't want to compile anything that executes just once.
SSA doesn't require deconstruction. Keep it all the way to the machine code.
When bytecode is designed for ease of interpretation you get a compact form which is easy to interpret. When you're going to translate it to machine code before it runs, that benefit is much reduced.
Stack vs register machine might be a preference. I find forth very difficult to reason with and don't particularly mind allocating registers to machine stack slots.
I like the idea of interpreting code directly as one walks the ascii file. What example do you have in mind? Most "interpreters" I can think of do a compilation to bytecode and then feed that to a bytecode interpreter. Some walk an AST instead but I'm not aware of any which lazily instantiate that tree from the source code.
> SSA doesn't require deconstruction. Keep it all the way to the machine code.
At some point you need to insert moves, either before or after register allocation. If you do it after register allocation (i.e. regalloc on SSA form), then there are certain benefits to the regalloc algorithm (a slew of papers from 2005-2015 or so), but there are missed opportunities to reschedule the moves.
It's possible to directly interpret SSA form. I am doing that now in my Virgil compiler.
But I don't think it's good for a bytecode, because that forces producers to do the transform and requires more locals (because you can only assign to them once).
> interpreting code directly as one walks the ascii file.
I'm mostly thinking of binary code, e.g. Wasm. I wrote two of the papers referenced in the article.
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.
Python and JavaScript DO NOT have the same properties. It's harder to make Python run faster than to make JavaScript run faster, in general.
This is a VERY common misconception. Reasons here:
You can make Python A LOT faster if you change the semantics so it's not Python, but instead a language that looks like Python with different behavior.
It's faster than v8, SpiderMonkey, and basically any Python compiler. Because you just cheat and change the semantics so they're fast. We run exactly 1 program.
The real problem is running arbitrary code, and that's again harder for Python than JavaScript, and it takes closer to 1M lines of code, not 4000.
---
This is sort of what Mojo has done, which is another thing that seems to be widely misunderstood. They did NOT write a compiler for arbitrary Python code.
They stated they WOULD achieve full compatibility with Python, but that hasn't been done yet.
They wrote a fast compiler for a language with Python-like syntax, but different semantics. (But not even that, because it's fn and struct rather than def and class).
And then they made a runtime bridge from that language to the stock CPython interpreter, similar to how Swift has some CPython integration for machine learning. It's better to think of static Mojo as a Swift-like language with Python syntax.
It's NOT Python -- the syntax is not what matters; the semantics are what matter.
---
My initial impressions, based on knowledge of Python, but before Mojo was released:
The most common belief is that python is intrinsically very hard to execute efficiently. Which seems valid. However there's a conclusion drawn that it must therefore always be slow. Your link has some of the usual points but seems to miss the global interpreter lock which usually attracts blame.
Nevertheless, I maintain that python and javascript are semantically the same thing in terms of the properties that make ahead of time compilation hard. Basically that stuff changes on you at runtime and the type system can express things that static ones cannot. So you have to do the assume + jit + rollback game for either of them, at which point python might have a longer list of stuff that is assumed constant in the prelude.
But then I'm not going to write a proof of this - I'm not confident I have enough life left to clone v8 for python, nor do I have motivation to do so. I expect mojo will end up serving that role. It doesn't have the same semantics yet, but that's the stated goal and I think they'll get there.
I maintain that python and javascript are semantically the same thing in terms of the properties that make ahead of time compilation
With respect, this attitude goes back at least 15 years, and usually comes from compiler people who don't understand Python very well, and the way people use it to solve problems in context.
The problem is very well studied, and your comments indicate that you haven't studied the prior art -- PyPy, Unladen Swallow, Jython/IronPython, Pyston, more recently Cinder and Skybison -- which are DIRECTLY from the v8 lineage.
---
To be clear, what I'm saying is that it's certainly possible to make a v8-like implementation for a Python-like language.
But the "like" is doing a lot of work there, and is the difference between the language being practical, and not practical.
So I think you're a compiler person who has an image of "Python" in his head, which is not Python.
That's not really a knock, because everybody who has tried to optimize Python starts from that position. I think even the Mojo team is, and they know way more about compilers than me -- but less about Python.
My guess is that they will succeed at producing something very interesting and useful in 5-10 years, but either renege on the Python compatibility promises, rewrite NumPy/Pandas themselves, or maintain a bridge to stock CPython forever.
Although I also think your comments indicate a fairly big misunderstanding of what Mojo is.
One of the flaws of the comment format is brevity mixed with a tendency to write conclusions without the reasoning behind them.
Mojo is an extension of python. In addition to the existing syntax, there are new keywords to opt into a more static set of semantics, chosen to compile directly to efficient code. You can have a machine integer instead of an arbitrary size python one, but they have different names. This gives you a path to writing code which doesn't opt into pythons compilation challenges. Or you can compile raw python as-is, but you get whatever type inference it manages, and some things aren't implemented yet. It also has calls into cpython for some stuff, but that's not inherent to the implementation strategy and I hope will not last forever.
This is personally interesting because it takes the python + C extension model, and the adjacent C++ that shows up nearby, and reassembles the semantics under a single compiler stack which has a credible path to optimising across the combination.
This is perilously close to what I want a programming language to be, possibly to the extent that I'm assuming they're going to do the obviously correct things in the future, so I would be interested to hear if any of the above is disjoint from your understanding. It may mean I need to recheck that they've built what I think they have.
> an interactive language - one where code is often run immediately after writing
Sorry if I'm ignorant, but I thought the term interactive language usually referred to languages where the code was run and modified in real time, while it is running, as in Smalltalk or Self, using something akin to Erlang's hot reload capabilities?[1] I think the viewpoint in that paradigm is to "cut out the middleman" of having a UI altogether, and to treat code as the UI, effectively
It feels like the author is describing interactive languages in the sense of IPython or REPL based programming, unless I pretty badly misunderstood. I was interested because I am in the process of writing a baby Smalltalk, although nowhere near as sophisticated as what the author seems to be building, I'm just starting with learning this stuff. I still enjoyed reading though
I am a beginner in this space but I have some thoughts.
The JVM is slow to startup but when it starts it is fast. I think it's slow due to how classes are arranged and lookup for classes. I think Graal or CDS works to speed this up.
I like the idea of a process that is fast to startup or is ran in the background such as php-fpm.
My JIT compiler is an incomplete toy but I only compile a function when it is called.
I have written about the idea of supercompilation which is the idea that we can apply lots of resources to compilation to create the most performant execution. But it requires you to be upfront and more detailed about your program semantics for safe reordering.
I think this stuff is sufficiently complicated that it is hard to read the code for without an explanation of what is going on.
Just do both. You could easily do it with the lisp machines of the late 70s and it’s even easier today.
Use an interpreter to execute code interactively. That’s what the user wants anyway.
Compile code in a background thread or process. When it’s ready map it into memory, and swap your interpreted references for the compiled version. Make the GOT writable and update it as necessary — sort of like the UUO mechanism in ITS or CP/M syscall table.
Yes, that was my initial reaction to this post. I like the framing a lot, and the references to copy-and-patch, Umbra, and so forth are great.
But my suspicion is that rather than trying to make the hard tradeoff, it may be less effort to implement the slow simple interpreter (I actually like tree interpreters), and also the compiler which can take a long time.
I don't know how easy it is to develop the interpreter and compiler in lock step, but I think it's worth exploring. I think you can probably reduce the effort with simple code organization, and by making the interpreter slower to run, and the compiler slower to compile.
It's indeed very easy to design a language with an interpreter, and then find out it can't be compiled to fast code. So IMO it's worth some design up front to avoid that fate.
---
I also think OCaml (mentioned in the post) proves the strategy: they had a bytecode compiler first, then a native compiler. (Though TBH I don't know how it plays out in practice for users)
And WASM also proves it -- there are multiple implementations of the same spec with different tradeoffs.
I think it's almost more of a UX / DX issue of how to put these things together. I noticed node.js starts too slowly for my taste, but deno starts faster?
$ time nodejs -e 'console.log("hi");'
hi
real 0m0.111s
$ deno run hi.ts
hi
real 0m0.030s
I guess node.js is doing a bunch of stuff that isn't v8 starting up? But I guess this doesn't prove the point, because deno still has the unpredictable v8 code generator. (Related comment on "failure of JITs" for certain problems: https://news.ycombinator.com/item?id=35045520 )
My recommendation is not to develop a compiler at all!
Well, not really, but just emit C or C++ structured the same as your hand-built library routines -- do the least amount of work possible -- and just call gcc. You may not be able to persuade the normal runtime linker to do what you want but the mods should be relatively straightforward.
However the usual counter-argument is that you're inheriting horrible C/C++ semantics, which often but not always true.
That was for the implementation language of Oils, not the shell language we're exposing. So I'd say it's a very useful and fast technique for tools, but not for future-facing languages that you want people to use :)
The dichotomy between "interactive, but slow" and "fast, but extremely slow to compile" is a false one. Similar to the one we had of "easy-to-use but crashy client operating systems (Windows, MacOS)" vs. "solid but user hostile server OSes". Now my watch runs Unix.
For Objective-S, this is a side-quest, but an important one.
I made 3 false starts with LLVM, but each time got discouraged by the crazy binary sizes, compile times and sheer conceptual overhead, all for (mostly) a slew of optimisations that yield extremely diminishing returns in the first place, and mostly aren't applicable anyway.
I now have a tiny (and still incomplete) AOT native compiler for aarch64 in addition to the AST-walker and couldn't be happier. Produces .o files, can JIT in principle, now looking at getting sufficient linker functionality in there to directly create executable and dylibs/frameworks. Oh, and ELF support.
While he mentions the slowness of LLVM, it would have been cool to see Jamie's thoughts on tinycc and qbe as well. I've been looking into the fastest options for generating and executing machine code (without me doing it all myself; generating and compiling C feels like a happy medium).
Check out project manifold[1]. It integrates languages at the type system level using a technique the project labels “type manifold”, which is described as JIT *static* code generation.
This project targets the JVM, but the general model could be adopted with any static type system / compiler.
Not directly related, but this made me think of something I've been interested in recently - structured editors. Instead of tokenizing text and then parsing to an AST, you effectively edit the AST directly.
Since the thrust of the post seems to be about the sum of compilation + run time, it's a potentially more efficient alternative to traditional code editing. Here's an example of one in action:
"an interactive language - one where code is often run immediately after writing"
I believe you need some kind of server that is listening to the code changes and executing the program really quickly, all that will happen so quick that it will feel it's all in real time, similar to how 'live coding' works on web browser. Does that help?
How is this different from REPL mode in python, swift, or java? (There was even a REPL for Java 1.1.) Both the javac and eclipse compilers have incremental compilation, so they save state and do only the necessary updates -- and provide effective feedback at each step. One interesting project would be to use an incremental linker with clang/swift.
For human-interactive programming, the key feature is not speed of execution (or really compilation/build), but the clarity of the feedback and code-assist. IDE's are growng by leaps and bounds in content-assist features, and shell languages have blossomed of late by supporting type-completion almost as well as IDE's.
For interactive use, type-inference in the language would seem to be a key requirement, and that means a robust type system, likely reduced to a constraint solving algorithm. (Has anyone has made one of those work in an incremental mode?)
Finally, for ground-up or semantic prototyping, I would think a good way to try a new language/compiler combination would be Haskell, where people are starting to support incremental compilation. Here pandoc could be an interesting code base because it interprets multiple (markup and document) languages with the same AST. (Which itself suggests the investigating implementations for DSL's...)
So the article would seem to ignore longstanding work streams in this space, to focus on the wrong features, and not to consider some relevant alternatives.
So... it's easy to miss the forest for the trees? I must be missing something...
I'm not the author, but my impression is that he wanted a single compiler that both compiles fast and generates fast code.
I think it's a good goal, although if you take into account total engineering effort, my suspicion is that having a separate interpreter and a compiler is an accepted (if not common) solution for that reason.
I think you're saying you don't need to compile fast to be interactive, because you can just use a slow compiler on tiny snippets of code, and patch them in. That seems like a fair point.
(Python doesn't count, because it doesn't run fast, but Swift probably does. As far as I know the Swift playgrounds use the compiler at runtime. Java doesn't fit the requirements based on "predictable, explainable performance". You can of course quibble with that requirement)
I do wish every language had a REPL and a compiler. And the interaction with language design is definitely worth exploring. I think Java and Swift have the tech, but I never really hear about people using them interactively, maybe because the languages themselves aren't great for typing in. (as opposed to R or shell or Lisp; Python could do better here too)
Neither Python nor Java have REPL, or can have it in principle. The "L" in REPL stands for "loop". I.e. what you print, you should be able to feed back into R (read). This is the whole point of this concept, and that's what this acronym means.
The term you are looking for is "interactive shell". There's no need to modify existing terminology -- you are only confusing yourself and others.
> Neither Python nor Java have REPL, or can have it in principle
Python certainly can have it in principle; its true that there are structures that where __repr__() doesn't feed back — that’s true in most Lisps for certain things, like recursive structures, too — but, too the extent that is worse than Lisp, that’s not an “in principle” limit.
Now, its true that the default Python interactive shell does not make it easy to distinguish between side effect printing and evaluation results, and worse yet (for use as a REPL) swallows rather than displaying None when it is a result, but “the default interactive shell is not a REPL” is very different than “Python cannot have a REPL in principle”.
Again, Python cannot have REPL in principle because like half of the language isn't even printable... you don't have anything to attach your __repr__() to. Most Python code either doesn't produce any values worth evaluating further (i.e. None) or produces values that are impossible to convert back to executable code (a lot of the stuff in the "standard" library produces non-actionable "decoration" style renderings, eg.:
You'd have to rewrite over half of the "standard" library to make it print something reasonable, and why would you at that point call the resulting language "Python"?
improving Julia's interpreter and code caching should get you pretty close to that dream language! and it's already a great, existing language with a nice ecosystem :)
Regarding LLVM's JIT infrastructure: You can plug your own compiler into it if LLVM is not fast enough. You can also mix and match multiple compilers within a single JIT'd program.
The LLVM JIT APIs operate in terms of abstract "materialization", and provide an in-memory, just-in-time linker to link object files into the process. You just have to write a materializer that calls your compiler, then hands the object back to the LLVM JIT APIs to be linked.
The advantage you get from using LLVM's JIT APIs to wrap your compiler are:
1) It can manage compilation requests from multiple threads of JIT'd code, and it can dispatch compilation work to multiple threads (or other processes).
2) It has built in support for lazy compilation, so you don't need to write this part yourself.
3) It can JIT across process boundaries (and architecture, object format and OS boundaries).
4) It supports many object format features (e.g. exceptions, general dynamic TLS, static initializers, etc.)
One option is to write your language as a transpile to Racket and then leverage the existing ChezScheme implementation for performance. Racket is usually faster than Python although initial process startup is slightly slower than CPython.
54 comments
[ 0.28 ms ] story [ 118 ms ] threadAlso, no virtual machine, at least for a machine code implementation. I wrote a forth like in c++ to implement adventure games, but the first I wrote was in z80 assembler, no vm.
It shows performance approximately equal to V8 if you write an interpreter + a few optimizations and feed it to Graal.
RPython and PyPy are great engineering and great projects, but I think RPython has not quite "escaped" into the real of general purpose language implementation -
https://www.pypy.org/posts/2018/09/the-first-15-years-of-pyp...
I think it taught a lot of valuable lessons in this space, but it's not really an answer to the stated problem.
https://www.sbcl.org/
Lisp satisfies 1, 3 and 4 I’m pretty sure, and maybe 2 depending on your definition of small. Idk about 1 though.
> Ability to use static dispatch, static field offsets and stack allocation.
> Control over memory layout - at minimum being able to express arrays-of-structs without pointer soup.
---
So reading between the lines a bit, I believe the author is asking for an REPL'd, interpreted, and fast running Go, Swift, Rust, C++, or Zig. (which to me is an interesting problem -- I basically use shell as my REPL for C++)
OCaml with new value types would qualify, and Java with value types would qualify, but they're not there yet AFAIK.
I think Julia/Clasp can get that kind of performance in some cases, but it's not predictable performance, with language control.
(copy of lobste.rs comment)
That's why the interactive versions of languages like C, Rust, Haskell typically are not very interactive and come with a lot of compromises. Often compromises at the boundary of compiled and 'interpreted' code.
What does 'interpreted' mean and why would we actually need it? Lisp as its bases has a radical interpreter: it interprets source code in the form of s-expressions. Most people think of interpreted code "byte code interpreters" - that's an entirely different form. The source code gets compiled to a byte code interpreter. In Lisp its quite often that one uses incremental native code compilers. These achieve much faster running code, in a spectrum of possible optimizations: optional type declarations, reduced runtime safety, code inlining, stack allocation, type specialized code generation and more. Many of these optimizations make the code harder to write. SBCL by default always uses the native code compiler. If we want "byte code" interpreted code, there is no way to make it fast without either some form of native code compilation (typically a JIT compiler) or writing the code in some other language (Python + C). The alternative is to get rid of byte code and having a native code compiler, with the drawbacks: one or more hardware architectures to support.
> Control over memory layout - at minimum being able to express arrays-of-structs without pointer soup.
That's a problem. Lisp needs to deal with it when interfacing 'foreign' memory. Thus it typically has a foreign-function interface.
> I believe the author is asking for an REPL'd, interpreted, and fast running Go, Swift, Rust, C++, or Zig. (which to me is an interesting problem -- I basically use shell as my REPL for C++)
There are compromises to make. "Interpreted" already is vague, see above. "Fast running" - is it always "fast running"? Is that possible? While being "interactive" / "interpreted"?
"REPL" is another concept with a range of possible meanings. Is a Read Eval Print Loop like in Lisp integrated into the language (read, print, eval, loop are primitives in the language) and is it the base for interactive programming. Is it a glorified command line interpreter which basically can call functions on data?
So whenever you change N, you have to recompile a lot of code.
And then you want to compile myprog quickly, and run the following quickly:
It's an interesting problem, but I think from the perspective of an interactive language, it does make sense to have some kind of fast mode and slow mode ... the classic debug/release build split is precisely that. I would settle for an interactive C++/Rust, with a good incremental build system, where you can choose the build variant!C++ build systems suck, and Rust often has to interface with them. And both C++ and Rust are not designed for fast interactive use. They have a lot of syntax that allows the control over memory, and that's perhaps a bigger problem.
I also don't really like typing code into a REPL -- I use an editor and a shell (and Ninja, which turns out to be crucial for fast C++ dev).
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.
- 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.
Subclassing numbers (or other primitive types) is one way to achieve the goal of having type-safe enumerations. In Python, I can do:
The value x=1 will not pass the test of isinstance(x, Weekday); mypy won't let you accidentally pass April as a Weekday; etc. There definitely are many ways to make this prettier, or easier for an optimising compiler, but I would like to echo DJB's talk referenced by the original article:> Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered.
Likewise, the ability to inspect the stack enables creation of useful tools, that would be difficult or impossible otherwise. When working with pytest, I can write "assert my_array == [1, 2, 3]"; when my_array contains an extra element at the end, my test fails with a pretty-printed diff of the two sides.
You don't need to perform aggressive whole-program optimisation passes when running a test suite, and you shouldn't need to inspect the stack at runtime while executing performance-critical sections in production. I save time and energy by not having to add "print(my_array)", re-running the tests, and copy-pasting the pretty-printed values for diffing. I save time and energy when my program has less bugs, because I had the tools to make it more correct.
Python could have had ADTs as a core language feature 20+ years ago (rather than sloppily grafting them on in a recent release), just like it could have had unicode strings as the default text type since before 2.x (1.6 was 2000; unicode was early 1990s). But it also had a much smaller community back then, and who knows how making these choices back then would've impacted its development? Maybe it'd end up being as relatively obscure as say Tcl.
Also I think you could still achieve reasonable optimisations even if you do go that route; Go has type aliases (including on primitive types) that you can define custom methods on:
If your compiler could prove nothing crazier than that is happening with your int subclass, I don't see why similarly written Python code should have a lower performance ceiling; but yes, that's more work for the compiler.Don't underestimate how much extra startup time it adds to do even one pass over the code. For really big applications (think 100MB or more of code), you want to avoid touching the code at all. You certainly don't want to compile anything that executes just once.
When bytecode is designed for ease of interpretation you get a compact form which is easy to interpret. When you're going to translate it to machine code before it runs, that benefit is much reduced.
Stack vs register machine might be a preference. I find forth very difficult to reason with and don't particularly mind allocating registers to machine stack slots.
I like the idea of interpreting code directly as one walks the ascii file. What example do you have in mind? Most "interpreters" I can think of do a compilation to bytecode and then feed that to a bytecode interpreter. Some walk an AST instead but I'm not aware of any which lazily instantiate that tree from the source code.
At some point you need to insert moves, either before or after register allocation. If you do it after register allocation (i.e. regalloc on SSA form), then there are certain benefits to the regalloc algorithm (a slew of papers from 2005-2015 or so), but there are missed opportunities to reschedule the moves.
It's possible to directly interpret SSA form. I am doing that now in my Virgil compiler.
But I don't think it's good for a bytecode, because that forces producers to do the transform and requires more locals (because you can only assign to them once).
> interpreting code directly as one walks the ascii file.
I'm mostly thinking of binary code, e.g. Wasm. I wrote two of the papers referenced in the article.
Python and JavaScript DO NOT have the same properties. It's harder to make Python run faster than to make JavaScript run faster, in general.
This is a VERY common misconception. Reasons here:
https://news.ycombinator.com/item?id=20953221
You can make Python A LOT faster if you change the semantics so it's not Python, but instead a language that looks like Python with different behavior.
I did that with 4000 lines of code on top of MyPy's typed AST, in Oils: https://www.oilshell.org/blog/2022/05/mycpp.html
It's faster than v8, SpiderMonkey, and basically any Python compiler. Because you just cheat and change the semantics so they're fast. We run exactly 1 program.
The real problem is running arbitrary code, and that's again harder for Python than JavaScript, and it takes closer to 1M lines of code, not 4000.
---
This is sort of what Mojo has done, which is another thing that seems to be widely misunderstood. They did NOT write a compiler for arbitrary Python code.
They stated they WOULD achieve full compatibility with Python, but that hasn't been done yet.
They wrote a fast compiler for a language with Python-like syntax, but different semantics. (But not even that, because it's fn and struct rather than def and class).
And then they made a runtime bridge from that language to the stock CPython interpreter, similar to how Swift has some CPython integration for machine learning. It's better to think of static Mojo as a Swift-like language with Python syntax.
It's NOT Python -- the syntax is not what matters; the semantics are what matter.
---
My initial impressions, based on knowledge of Python, but before Mojo was released:
https://lobste.rs/s/nppf8y/mojo_is_much_better_objective_c_w...
https://lobste.rs/s/qbcjsl/mojo_future_ai_programming#c_a5vg...
Nevertheless, I maintain that python and javascript are semantically the same thing in terms of the properties that make ahead of time compilation hard. Basically that stuff changes on you at runtime and the type system can express things that static ones cannot. So you have to do the assume + jit + rollback game for either of them, at which point python might have a longer list of stuff that is assumed constant in the prelude.
But then I'm not going to write a proof of this - I'm not confident I have enough life left to clone v8 for python, nor do I have motivation to do so. I expect mojo will end up serving that role. It doesn't have the same semantics yet, but that's the stated goal and I think they'll get there.
With respect, this attitude goes back at least 15 years, and usually comes from compiler people who don't understand Python very well, and the way people use it to solve problems in context.
The problem is very well studied, and your comments indicate that you haven't studied the prior art -- PyPy, Unladen Swallow, Jython/IronPython, Pyston, more recently Cinder and Skybison -- which are DIRECTLY from the v8 lineage.
---
To be clear, what I'm saying is that it's certainly possible to make a v8-like implementation for a Python-like language.
But the "like" is doing a lot of work there, and is the difference between the language being practical, and not practical.
So I think you're a compiler person who has an image of "Python" in his head, which is not Python.
That's not really a knock, because everybody who has tried to optimize Python starts from that position. I think even the Mojo team is, and they know way more about compilers than me -- but less about Python.
My guess is that they will succeed at producing something very interesting and useful in 5-10 years, but either renege on the Python compatibility promises, rewrite NumPy/Pandas themselves, or maintain a bridge to stock CPython forever.
Although I also think your comments indicate a fairly big misunderstanding of what Mojo is.
Mojo is an extension of python. In addition to the existing syntax, there are new keywords to opt into a more static set of semantics, chosen to compile directly to efficient code. You can have a machine integer instead of an arbitrary size python one, but they have different names. This gives you a path to writing code which doesn't opt into pythons compilation challenges. Or you can compile raw python as-is, but you get whatever type inference it manages, and some things aren't implemented yet. It also has calls into cpython for some stuff, but that's not inherent to the implementation strategy and I hope will not last forever.
This is personally interesting because it takes the python + C extension model, and the adjacent C++ that shows up nearby, and reassembles the semantics under a single compiler stack which has a credible path to optimising across the combination.
This is perilously close to what I want a programming language to be, possibly to the extent that I'm assuming they're going to do the obviously correct things in the future, so I would be interested to hear if any of the above is disjoint from your understanding. It may mean I need to recheck that they've built what I think they have.
Sorry if I'm ignorant, but I thought the term interactive language usually referred to languages where the code was run and modified in real time, while it is running, as in Smalltalk or Self, using something akin to Erlang's hot reload capabilities?[1] I think the viewpoint in that paradigm is to "cut out the middleman" of having a UI altogether, and to treat code as the UI, effectively
It feels like the author is describing interactive languages in the sense of IPython or REPL based programming, unless I pretty badly misunderstood. I was interested because I am in the process of writing a baby Smalltalk, although nowhere near as sophisticated as what the author seems to be building, I'm just starting with learning this stuff. I still enjoyed reading though
[1] https://en.m.wikipedia.org/wiki/Interactive_programming
The JVM is slow to startup but when it starts it is fast. I think it's slow due to how classes are arranged and lookup for classes. I think Graal or CDS works to speed this up.
I like the idea of a process that is fast to startup or is ran in the background such as php-fpm.
My JIT compiler is an incomplete toy but I only compile a function when it is called.
https://GitHub.com/samsquire/compiler
I have written about the idea of supercompilation which is the idea that we can apply lots of resources to compilation to create the most performant execution. But it requires you to be upfront and more detailed about your program semantics for safe reordering.
I think this stuff is sufficiently complicated that it is hard to read the code for without an explanation of what is going on.
Use an interpreter to execute code interactively. That’s what the user wants anyway.
Compile code in a background thread or process. When it’s ready map it into memory, and swap your interpreted references for the compiled version. Make the GOT writable and update it as necessary — sort of like the UUO mechanism in ITS or CP/M syscall table.
But my suspicion is that rather than trying to make the hard tradeoff, it may be less effort to implement the slow simple interpreter (I actually like tree interpreters), and also the compiler which can take a long time.
I'm doing a similar experiment right now, as sort of an offshoot of https://www.oilshell.org/
I don't know how easy it is to develop the interpreter and compiler in lock step, but I think it's worth exploring. I think you can probably reduce the effort with simple code organization, and by making the interpreter slower to run, and the compiler slower to compile.
It's indeed very easy to design a language with an interpreter, and then find out it can't be compiled to fast code. So IMO it's worth some design up front to avoid that fate.
---
I also think OCaml (mentioned in the post) proves the strategy: they had a bytecode compiler first, then a native compiler. (Though TBH I don't know how it plays out in practice for users)
And WASM also proves it -- there are multiple implementations of the same spec with different tradeoffs.
I think it's almost more of a UX / DX issue of how to put these things together. I noticed node.js starts too slowly for my taste, but deno starts faster?
I guess node.js is doing a bunch of stuff that isn't v8 starting up? But I guess this doesn't prove the point, because deno still has the unpredictable v8 code generator. (Related comment on "failure of JITs" for certain problems: https://news.ycombinator.com/item?id=35045520 )Well, not really, but just emit C or C++ structured the same as your hand-built library routines -- do the least amount of work possible -- and just call gcc. You may not be able to persuade the normal runtime linker to do what you want but the mods should be relatively straightforward.
But let them do all the hard work.
However the usual counter-argument is that you're inheriting horrible C/C++ semantics, which often but not always true.
That was for the implementation language of Oils, not the shell language we're exposing. So I'd say it's a very useful and fast technique for tools, but not for future-facing languages that you want people to use :)
https://objective.st
The dichotomy between "interactive, but slow" and "fast, but extremely slow to compile" is a false one. Similar to the one we had of "easy-to-use but crashy client operating systems (Windows, MacOS)" vs. "solid but user hostile server OSes". Now my watch runs Unix.
For Objective-S, this is a side-quest, but an important one.
https://blog.metaobject.com/2019/12/the-4-stages-of-objectiv...
I made 3 false starts with LLVM, but each time got discouraged by the crazy binary sizes, compile times and sheer conceptual overhead, all for (mostly) a slew of optimisations that yield extremely diminishing returns in the first place, and mostly aren't applicable anyway.
I now have a tiny (and still incomplete) AOT native compiler for aarch64 in addition to the AST-walker and couldn't be happier. Produces .o files, can JIT in principle, now looking at getting sufficient linker functionality in there to directly create executable and dylibs/frameworks. Oh, and ELF support.
See also: ALGOL, the ALGOrithmic Language.
But in general it seems to be very hard to beat the bang for buck from generating C and compiling that - even with something simple like tcc
This project targets the JVM, but the general model could be adopted with any static type system / compiler.
1. https://github.com/manifold-systems/manifold#what-can-you-do...
Since the thrust of the post seems to be about the sum of compilation + run time, it's a potentially more efficient alternative to traditional code editing. Here's an example of one in action:
https://tylr.fun/
I believe you need some kind of server that is listening to the code changes and executing the program really quickly, all that will happen so quick that it will feel it's all in real time, similar to how 'live coding' works on web browser. Does that help?
How is this different from REPL mode in python, swift, or java? (There was even a REPL for Java 1.1.) Both the javac and eclipse compilers have incremental compilation, so they save state and do only the necessary updates -- and provide effective feedback at each step. One interesting project would be to use an incremental linker with clang/swift.
For human-interactive programming, the key feature is not speed of execution (or really compilation/build), but the clarity of the feedback and code-assist. IDE's are growng by leaps and bounds in content-assist features, and shell languages have blossomed of late by supporting type-completion almost as well as IDE's.
For interactive use, type-inference in the language would seem to be a key requirement, and that means a robust type system, likely reduced to a constraint solving algorithm. (Has anyone has made one of those work in an incremental mode?)
Finally, for ground-up or semantic prototyping, I would think a good way to try a new language/compiler combination would be Haskell, where people are starting to support incremental compilation. Here pandoc could be an interesting code base because it interprets multiple (markup and document) languages with the same AST. (Which itself suggests the investigating implementations for DSL's...)
So the article would seem to ignore longstanding work streams in this space, to focus on the wrong features, and not to consider some relevant alternatives.
So... it's easy to miss the forest for the trees? I must be missing something...
I think it's a good goal, although if you take into account total engineering effort, my suspicion is that having a separate interpreter and a compiler is an accepted (if not common) solution for that reason.
I think you're saying you don't need to compile fast to be interactive, because you can just use a slow compiler on tiny snippets of code, and patch them in. That seems like a fair point.
(Python doesn't count, because it doesn't run fast, but Swift probably does. As far as I know the Swift playgrounds use the compiler at runtime. Java doesn't fit the requirements based on "predictable, explainable performance". You can of course quibble with that requirement)
I do wish every language had a REPL and a compiler. And the interaction with language design is definitely worth exploring. I think Java and Swift have the tech, but I never really hear about people using them interactively, maybe because the languages themselves aren't great for typing in. (as opposed to R or shell or Lisp; Python could do better here too)
The term you are looking for is "interactive shell". There's no need to modify existing terminology -- you are only confusing yourself and others.
Python certainly can have it in principle; its true that there are structures that where __repr__() doesn't feed back — that’s true in most Lisps for certain things, like recursive structures, too — but, too the extent that is worse than Lisp, that’s not an “in principle” limit.
Now, its true that the default Python interactive shell does not make it easy to distinguish between side effect printing and evaluation results, and worse yet (for use as a REPL) swallows rather than displaying None when it is a result, but “the default interactive shell is not a REPL” is very different than “Python cannot have a REPL in principle”.
The LLVM JIT APIs operate in terms of abstract "materialization", and provide an in-memory, just-in-time linker to link object files into the process. You just have to write a materializer that calls your compiler, then hands the object back to the LLVM JIT APIs to be linked.
The advantage you get from using LLVM's JIT APIs to wrap your compiler are: 1) It can manage compilation requests from multiple threads of JIT'd code, and it can dispatch compilation work to multiple threads (or other processes). 2) It has built in support for lazy compilation, so you don't need to write this part yourself. 3) It can JIT across process boundaries (and architecture, object format and OS boundaries). 4) It supports many object format features (e.g. exceptions, general dynamic TLS, static initializers, etc.)
Pretty sure RPython/PyPy dropped partial evaluation in favor of a metatracing JIT: https://www.pypy.org/posts/2018/09/the-first-15-years-of-pyp...