Implementing Interactive Languages
scattered-thoughts.net
scattered-thoughts.net
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
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?
$ time nodejs -e 'console.log("hi");'
hi
real 0m0.111s
$ deno run hi.ts
hi
real 0m0.030s
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 :)
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?
// layout.h
struct MyRecord { ... }
#define N 1024*1024
MyRecord myarray[N];
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
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).
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...
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.
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...
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.)
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
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.
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”.
>>> import socket
>>> socket.socket()
<socket.socket fd=3, family=2, type=1, proto=0, laddr=('0.0.0.0', 0)>
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.
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:
class Weekday(int): pass
Monday = Weekday(1)
...
> 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:
type Weekday int
const (
Monday = Weekday(1)
...
)
func (w Weekday) Name() string {
switch w {
case Weekday(1):
return "Monday"
...
default:
panic("?")
}
}
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.
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.
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?
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: