8 ms·

Implementing Interactive Languages

80 points by luu 3y ago

zabzonk 3y ago
Forth?
- fjfaase 3y ago
  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.
  - zabzonk 3y ago
    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.
noelwelsh 3y ago
The answer is Graal or RPython, which for not very good reasons they "immediately discard".
- noelwelsh 3y ago
  Following up on this, this paper was recently posted to HN: https://stefan-marr.de/downloads/oopsla23-larose-et-al-ast-vs-bytecode-interpreters-in-the-age-of-meta-compilation.pdf https://stefan-marr.de/downloads/oopsla23-larose-et-al-ast-v... It shows performance approximately equal to V8 if you write an interpreter + a few optimizations and feed it to Graal.
- chubot 3y ago
  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 - https://www.pypy.org/posts/2018/09/the-first-15-years-of-pypy-3412615975376972020.html 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.
lispm 3y ago
SBCL has an interactive/incremental/in-memory native code compiler and a file compiler. https://www.sbcl.org/ https://www.sbcl.org/
- nerdponx 3y ago
  Lisp seems like the most incredibly obvious choice here.
- tester89 3y ago
  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.
- chubot 3y ago
  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. (copy of lobste.rs comment)
  - lispm 3y ago
    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?
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.
vector_spaces 3y ago
> 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 [1] https://en.m.wikipedia.org/wiki/Interactive_programming https://en.m.wikipedia.org/wiki/Interactive_programming
samsquire 3y ago
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. https://GitHub.com/samsquire/compiler 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.
gumby 3y ago
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.
- chubot 3y ago
  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'm doing a similar experiment right now, as sort of an offshoot of https://www.oilshell.org/ 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 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 https://news.ycombinator.com/item?id=35045520 )
  - gumby 3y ago
    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. But let them do all the hard work.
mpweiher 3y ago
Objective-S is aiming right into that sweet spot. https://objective.st 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-objective-smalltalk.html 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.
- andsoitis 3y ago
  Intriguing claim: “Objective-S is the first general purpose programming language.” — https://objective.st/About https://objective.st/About
  - mpweiher 3y ago
    Because what we call "general purpose" programming languages are really domain-specific languages for the domain of algorithms. See also: ALGOL, the ALGOrithmic Language.
eatonphil 3y ago
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).
- tadkar 3y ago
  I came here to say exactly the same thing. There are also a couple of other options: the MIR project from RedHat [1], libjit [2], lightning [3] and Dynasm [4] 1. https://github.com/vnmakarov/mir https://github.com/vnmakarov/mir 2. https://www.gnu.org/software/libjit/ https://www.gnu.org/software/libjit/ 3. https://www.gnu.org/software/lightning/manual/lightning.html https://www.gnu.org/software/lightning/manual/lightning.html 4. https://corsix.github.io/dynasm-doc/tutorial.html https://corsix.github.io/dynasm-doc/tutorial.html 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
transfire 3y ago
Crystal (https://crystal-lang.org/ https://crystal-lang.org/) has both a compiler and an interpreter.
owlstuffing 3y ago
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. 1. https://github.com/manifold-systems/manifold#what-can-you-do-with-manifold https://github.com/manifold-systems/manifold#what-can-you-do...
danielvaughn 3y ago
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: https://tylr.fun/ https://tylr.fun/
suyash 3y ago
"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?
w10-1 3y ago
I'm not getting it. 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...
- chubot 3y ago
  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)
simondanisch 3y ago
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 :)
lhames 3y ago
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.)
nsm 3y ago
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.
talismanick 3y ago
> Futumura projections (eg truffle, rpython) 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-pypy-3412615975376972020.html#why-did-we-abandon-partial-evaluation https://www.pypy.org/posts/2018/09/the-first-15-years-of-pyp...

80 points by luu 3y ago

zabzonk 3y ago

Forth?

fjfaase 3y ago
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.
- zabzonk 3y ago
  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.

noelwelsh 3y ago

The answer is Graal or RPython, which for not very good reasons they "immediately discard".

noelwelsh 3y ago
Following up on this, this paper was recently posted to HN: https://stefan-marr.de/downloads/oopsla23-larose-et-al-ast-vs-bytecode-interpreters-in-the-age-of-meta-compilation.pdf https://stefan-marr.de/downloads/oopsla23-larose-et-al-ast-v... It shows performance approximately equal to V8 if you write an interpreter + a few optimizations and feed it to Graal.
chubot 3y ago
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 - https://www.pypy.org/posts/2018/09/the-first-15-years-of-pypy-3412615975376972020.html 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.

lispm 3y ago

SBCL has an interactive/incremental/in-memory native code compiler and a file compiler. https://www.sbcl.org/ https://www.sbcl.org/

nerdponx 3y ago
Lisp seems like the most incredibly obvious choice here.
tester89 3y ago
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.
chubot 3y ago
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. (copy of lobste.rs comment)
- lispm 3y ago
  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?

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.

vector_spaces 3y ago

> 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 [1] https://en.m.wikipedia.org/wiki/Interactive_programming https://en.m.wikipedia.org/wiki/Interactive_programming

samsquire 3y ago

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. https://GitHub.com/samsquire/compiler 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.

gumby 3y ago

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.

chubot 3y ago
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'm doing a similar experiment right now, as sort of an offshoot of https://www.oilshell.org/ 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 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 https://news.ycombinator.com/item?id=35045520 )
- gumby 3y ago
  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. But let them do all the hard work.

mpweiher 3y ago

Objective-S is aiming right into that sweet spot. https://objective.st 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-objective-smalltalk.html 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.

andsoitis 3y ago
Intriguing claim: “Objective-S is the first general purpose programming language.” — https://objective.st/About https://objective.st/About
- mpweiher 3y ago
  Because what we call "general purpose" programming languages are really domain-specific languages for the domain of algorithms. See also: ALGOL, the ALGOrithmic Language.

eatonphil 3y ago

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).

tadkar 3y ago
I came here to say exactly the same thing. There are also a couple of other options: the MIR project from RedHat [1], libjit [2], lightning [3] and Dynasm [4] 1. https://github.com/vnmakarov/mir https://github.com/vnmakarov/mir 2. https://www.gnu.org/software/libjit/ https://www.gnu.org/software/libjit/ 3. https://www.gnu.org/software/lightning/manual/lightning.html https://www.gnu.org/software/lightning/manual/lightning.html 4. https://corsix.github.io/dynasm-doc/tutorial.html https://corsix.github.io/dynasm-doc/tutorial.html 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

transfire 3y ago

Crystal (https://crystal-lang.org/ https://crystal-lang.org/) has both a compiler and an interpreter.

owlstuffing 3y ago

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. 1. https://github.com/manifold-systems/manifold#what-can-you-do-with-manifold https://github.com/manifold-systems/manifold#what-can-you-do...

danielvaughn 3y ago

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: https://tylr.fun/ https://tylr.fun/

suyash 3y ago

"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?

w10-1 3y ago

I'm not getting it. 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...

chubot 3y ago
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)

simondanisch 3y ago

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 :)

lhames 3y ago

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.)

nsm 3y ago

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.

talismanick 3y ago

> Futumura projections (eg truffle, rpython) 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-pypy-3412615975376972020.html#why-did-we-abandon-partial-evaluation https://www.pypy.org/posts/2018/09/the-first-15-years-of-pyp...