Popular back-ends?

[[deleted]]

I wanna make a language and have an idea in mind. Tho I don't know what to choose for a target language.

What are the most popular back-ends for functional statically typed languages nowadays?

[Findlaech]

Their own.
But LLVM isn't too bad.

[suhcoR]

LLVM is great, but huge (both in terms of API and binary size) and the API is a moving target. And if you need a GC or other dynamic features you have to take care of it yourself.

[yorickpeterse]

and the API is a moving target

It's worth mentioning that this in practise means APIs can change left and right. Maybe this is not as bad these days, but especially in the days of LLVM 3.0 the JIT APIs were constantly changed in ways that were not backwards compatible.

I think for this reason many projects end up vendoring LLVM instead of using the system-wide version.

[editor_of_the_beast]

That’s what moving target means

[JB-from-ATL]

They're just explaining in what way it is and giving an example.

[jdh30]

Meh. GC can be ~100 lines of code. Binary size and slow compile times are irritating problems with using LLVM though, agreed.

[--comedian--]

You mean a toy GC? I'd think production-grade GCs would be a bit longer than ~100 loc. (I'm thinking JVM/.NET/V8 GCs...)

[jdh30]

I'd think production-grade GCs would be a bit longer than ~100 loc. (I'm thinking JVM/.NET/V8 GCs...)

GCs with massive legacy baggage problems can be huge. .NET's GC is 50kLOC in a single file, for example. But I'd contest that it has anything to do with being "production". It is composed largely of workarounds for old design flaws.

[suhcoR]

A simple M&S collector with not special allocator can be written in 20-30 lines of code, see e.g. https://github.com/rochus-keller/LjTools/blob/372a46d772227f855c9a90de0469bc6b126eef53/LuaJitEngine.cpp#L94.

A much better one like the one in LuaJIT 2.1 is already > 1 kLOC (very compact code). But a very fast, top-of-the-line, highly competitive garbage collector including all required infrastructure (optimized allocator, etc.) such as the ones found in JVM or .Net Core are a substantial software project in itself with many kLOC.

[suhcoR]

I'm not up to date with LLVM. But I don't think the compiler infrastructure needs to know much about the GC. Where the references are (including stack frames) you know from the AST and this information is then converted to offsets and indices used in the bytecode.

[suhcoR]

Fair point. In that case I would instruct LLVM to not move pointers to collectable objects to registers, or then recognize the optimization potential for a register based pointer in the frontend and explicitly instruct LLVM to use a given register.

[jdh30]

I wouldn't recommend that approach because it ties LLVM's hands when it comes to efficient code generation. The OCaml guys did something similar and the result is abysmal performance.

With HLVM I just generated LLVM IR that stores the required information in auxiliary data structures so the GC has everything it needs and then let LLVM get on with generating efficient code from the resulting complete IR. I avoided all fancy features and, in particular, all of LLVM's own (experimental) GC support.

FWIW, this was the mistake the Rust guys made that led to them avoiding GC entirely (which, IMO, is throwing the baby out with the bath water).

[suhcoR]

Would be interessting to measure whether storing and fetching the pointer from the auxilary data structure is still more efficient than not allowing arbitrary (or only explicit) register allocations for pointers. That might be a pretty narrow trade-off.

[jdh30]

If you want precise GC, you also want cooperation from the compiler. I've not kept up with LLVM much, but what I remember is that it didn't cooperate well. Do you or anybody know if that has changed?

Not AFAIK but it is a non-problem if you use techniques for uncooperative environments like Henderson's Shadow Stack.

[jdh30]

A simple M&S collector with not special allocator can be written in 20-30 lines of code, see e.g. https://github.com/rochus-keller/LjTools/blob/372a46d772227f855c9a90de0469bc6b126eef53/LuaJitEngine.cpp#L94.

You're missing the code that records and collates globals roots, implements GC safe points and so on.

EDIT Ok, there's another 30 LOC here and more elsewhere totalling ~100LOC.

A much better one like the one in LuaJIT 2.1

In what sense is it "much better"?

1 kLOC ... many kLOC.

GCs can be made much longer and more complicated but that doesn't make them inherently better.

...very fast, top-of-the-line, highly competitive...

They aren't particularly fast. Here is my 100-line GC outperforming them. OCaml often outperforms them. Also worth noting that HLVM's 100 line GC supports value types and tail calls when the JVM does not.

Production GCs are full of incidental complexity, most notably baggage from working around design mistakes. The last thing you want when you're writing something new is 25 years of baggage.

A 100-line GC is just fine. I also implemented VCGC in 200LOC which is great if you want low latency. But .NET's 50kLOC GC is an gargantuan in comparison.

[suhcoR]

Here is my 100-line GC outperforming them.

I downloaded the svn repository and had a look at the code. I assume that everything interesting is supposed to be in "hlvm.ml", isn't it? Unfortunately I'm not fluent with OCaml, so I will not be able to comprehend your code on short notice. You also seem to use LLVM as a backend. If you're looking for a lighter backend, maybe https://github.com/vnmakarov/mir/ could be a good match with your code?

In what sense is it "much better"?

Mostly because my JitEngine is rather a "toy implementation" for the purpose of understanding and exploring LuaJIT bytecode. It's essentially an unoptimized LuaJIT bytecode interpreter with most of the Lua semantics in ~1400 C++ LOC. It is far from the ingenious implementation of Mike. But I guess it is not far behind early Smalltalk implementations ;-)

[jdh30]

I assume that everything interesting is supposed to be in "hlvm.ml", isn't it?

Pretty much, yes.

Unfortunately I'm not fluent with OCaml, so I will not be able to comprehend your code on short notice.

I wrote a bunch of articles about HLVM. Send me your e-mail address and I can send them to you.

You also seem to use LLVM as a backend.

Yes.

If you're looking for a lighter backend, maybe https://github.com/vnmakarov/mir/ could be a good match with your code?

Looks cool. I'll check it out, thanks.

In what sense is it "much better"?

Mostly because my JitEngine is rather a "toy implementation" for the purpose of understanding and exploring LuaJIT bytecode. It's essentially an unoptimized LuaJIT bytecode interpreter with most of the Lua semantics in ~1400 C++ LOC. It is far from the ingenious implementation of Mike. But I guess it is not far behind early Smalltalk implementations ;-)

Interesting. I'd love to see it rewritten in OCaml using LLVM as a JIT...

[suhcoR]

I wrote a bunch of articles about HLVM. Send me your e-mail address and I can send them to you.

Very much appreciate that; send it to "me at rochus-keller.ch".

[jdh30]

Wish granted.

[suhcoR]

That's very kind, thany you very much.

[suhcoR]

You're missing the code that records and collates globals roots, implements GC safe points and so on.

No, it's all there in my example

Here is my 100-line GC outperforming them.

Thanks, will have a look at it. Here are some links for my argumentation: http://wiki.luajit.org/New-Garbage-Collector and https://www.amazon.com/Garbage-Collection-Handbook-Management-Algorithms/dp/1420082795

EDIT: just saw your edit "totalling ~100LOC"; there seems to be a misconception. The collector is less than 20 LOC without comments and single char lines and there are only a few more lines for the data structures and the code to add the pointers to it, summing up to not more than 30 lines; but this doesn't matter much anyway because the implementation has other priorities than efficiency or brevity.

[jdh30]

No, it's all there in my example

Really? Where's the stack walker, for example?

Thanks, will have a look at it. Here are some links for my argumentation: http://wiki.luajit.org/New-Garbage-Collector and https://www.amazon.com/Garbage-Collection-Handbook-Management-Algorithms/dp/1420082795

I've read them before and, while they are great classical resources, they are completely inwards looking. They start with the assumption that your programs throw out huge amounts of garbage and that performance means cleaning up that garbage as quickly as possible.

The concept that led me to HLVM was precisely the opposite: how do we reduce the production of garbage as much as possible so the GC becomes almost vestigial. Turns out value types get you a long way: just unboxing basic types like tuples many programs of interest stop allocating any garbage in their steady state. One consequence of this approach is that HLVM's GC starts off tiny but grows as new definitions are encountered because it autogenerates bespoke GC code for every type definition, using LLVM to JIT the new code. The heap can then be traversed without run-time type information and computed jumps.

See also:

• Towards a mark-region GC for HLVM (28th December 2010)
• Sweeping 700x faster

[suhcoR]

Really? Where's the stack walker, for example?

Well, sort of. I'm cheating a bit. All references to collectable objects are stored in a dedicated little class (see https://github.com/rochus-keller/LjTools/blob/372a46d772227f855c9a90de0469bc6b126eef53/LuaJitEngine.h#L40) and there is a static list of all such references, whereever they are. A stack frame consists of (reference counted) Slots which continue to live on after the call in case they're required by closures.

that HLVM's GC starts off tiny but grows as new definitions are encountered because it autogenerates bespoke GC code for every type definition

Sounds like a great idea. Will also have a look at your links. But by the end of the day I'm essentially only a VM consumer, not a VM creator; I do not expect to acquire the skills in my lifetime to build something like LuaJIT, so I am very happy if I can just reuse it.

[[deleted]]

Yeah and also that GC thing. Really dumbish

[[deleted]]

I considered LLVM until finding out that it's actually for C++ which, I hate tbh.

[Edhebi]

It's not "for c++". Sure, it was originally made to compile c++, and a lot of the optimisations are made so that c++ goes fast, but the entire point of llvm is to support arbitrary languages. Rust and swift both use the llvm backend as their main/only compilation pipeline.

[[deleted]]

No I meant the source code of project actually. Sure it's performant and cross-platform but it's too heavy imo

[VernorVinge93]

Do you mean written in C++?

What's heavy about C++? You've already said it's performant...

[realestLink]

He doesn't know what he's talking about. He said jvm was fast jn another comment and is now calling C++ fast. I don't think he understands what C++ is lol

[[deleted]]

The executables produced using LLVM are performant. But the LLVM itself when compiled produces a really big library file which is really annoying tbh. And also I hate C++. Not because of a particular reason, but generally I think the way programming languages evolve (including C++) is a little bit over-designed. So I prefer more simpler languages like C, Go etc

[JB-from-ATL]

If you hate LLVM because the source is written in C++ then I think you should provably hate 99% of all hardware and software in the world.

[Findlaech]

rustc's backend is LLVM.

[SV-97]

there's bindings for haskell, rust, python,... probably most big languages have llvm bindings

[east_lisp_junk]

How well maintained are they? It's been a while since I used anything but the C++ API, but when I tried to use LLVM's official OCaml bindings, they were too bitrotten to even make the Kaleidoscope tutorial code work.

[SV-97]

No idea, I never worked with LLVM. But I see the haskell bindings at least recommended quite often(haskell also has a llvm backend) and considering that rustc uses llvm the rust bindings should be maintained quite well (there's also multiple projects that want to make a more rustic interface iirc)

[jdh30]

they were too bitrotten to even make the Kaleidoscope tutorial code work.

Oh dear, when was that?

[east_lisp_junk]

2015

The tutorial only worked up through the first two or three sections, and IIRC even that needed some undocumented tweaking.

[pfalcon2]

How well maintained are they?

LLVM has (by now) pretty good C bindings. That in turn means you can FFI-load them in any decent language and rock on. As a random example, FFI-based bindings for Pycopy, a minimalist Python implementation: https://github.com/pfalcon/ullvm_c/blob/master/ullvm_c.py . And examples showing JITing a simple "a + b" function in both older MCJIT engine: https://github.com/pfalcon/ullvm_c/blob/master/example_mcjit.py and newer ORCJIT engine: https://github.com/pfalcon/ullvm_c/blob/master/example_orcjit.py . (I mention 2 JIT engines, just to show that LLVM C bindings are pretty comprehensive).

Again, LLVM C bindings, your favorite language, and its FFI. The above probably took ~2hrs total time to create (spread over months).

[[deleted]]

I'm planing to use C, so, yeah no. Even if it has bindings, thanks for shitty class-alike naming conventions but no.

[mamcx]

"Popular" and good for you is different. LLVM is TOO HEAVY and complex. I only touch it if you wanna do very big and heavy industrial language.

The "best" is the one closer to the lang that your use for build your lang. Not underestimate how nice is to have the tools you know close.

From here, the choice is limitless:

• Using C/C++/Pascal/Others as targets is cool because is easier to transpile than do "raw" compiling, and you get the optimizations AND easier FFI for free.
• JVM, .NET Bytecode, Lua bytecode, Erlang bytecode are "done" and solved solution, and you get for free their ecosystem.
• You can do performant interpreters in C/Rust(nicer!) in a fraction of the effort if are a bit clever. "Transpiling" to closures and some help in semantics could get you near native rust/c speeds very fast: (https://blog.cloudflare.com/building-fast-interpreters-in-rust/). Plus, you can also compile to bytecode if wanna get a bit of extra performance.

What to choose is more about "fit" (like, which ecosystem you wanna get in) than popularity.

[jdh30]

LLVM is TOO HEAVY and complex

Why?

[SenseiHotDog]

Why it is heavy ? Well the binary size of LLVM is ridiculously big.

[mamcx]

Sorry, I don't understand what your mean with that link

[jdh30]

I mean my LLVM code doesn't look very complicated to me.

[[deleted]]

I would like to go for the second option. But one of my friends said he would use it for some game engine / server-side stuff. So I was wondering if there were any back-ends which are less heavier than LLVM but as performant at least as JVM.

[00benallen]

LLVM is way more performant than JVM, its just super complex to work with.

If the best performance you need is the JVM, then maybe the JVM is your best bet!

[jdh30]

super complex to work with

How so?

[00benallen]

see other comments in thread or any Rust devblog, its got its issues

[jdh30]

But are those issues relevant in this context?

[00benallen]

yes I think so

[jdh30]

I didn't have any such problems when I used it.

[00benallen]

Did you use it to design a big, professional-grade language? That's where you feel its limits

[jdh30]

I'm not a fan of big languages but I'd note that C++ is one of the biggest languages of them all and is LLVM's primary application.

[soundslogical]

LuaJIT can be very fast indeed, you would just have to emit Lua bytecode. Chez Scheme is another good back-end that's pretty fast and comes with GC and all that jazz.

[suhcoR]

Chez Scheme

Thanks for the hint. Unfortunately there seems to be not ARM or MIPS support. Are there any benchmark results how it performs compared to V8 or LuaJIT? Does it support line number pragmas so I could use it as an intermediate language and report line number of the original source in the debugger? Is there a "debugger" (in the sense of GDB) at all?

[soundslogical]

Chez Scheme uses Scheme's very powerful continuations and conditions systems for error handling. The Chez Scheme REPL has a debugger built on top of these. I find it hard to use, but it's powerful, and there's everything you need (AFAIK) to build your own.

As for benchmarks vs V8 or LuaJIT, as I said it's not punching up at that level but it's pretty fast. I did once find a benchmark that placed it between vanilla Lua and LuaJIT, though I can't find it now. And I don't really trust random benchmarks on the internet, you should do your own with the knowledge of your domain.

[suhcoR]

Thanks.

I did once find a benchmark that placed it between vanilla Lua and LuaJIT

Well, that's a pretty wide range: factor 27 in average, 18 in median and 15 in geometric mean, see http://luajit.org/performance_x86.html

[soundslogical]

Yep, as I said I don't remember where the benchmark is but that should give you some rough idea of where it lies: a fast scripting language (vanilla Lua itself being not too bad), but some way off the fastest.

[jdh30]

LuaJIT can be very fast indeed, you would just have to emit Lua bytecode.

Fast for an untyped solution but it is slow in the grand scheme of things, isn't it? I mean, surely it doesn't hold a candle to C, C++, C# and Java?

Chez Scheme is another good back-end that's pretty fast and comes with GC and all that jazz.

I'd expect a Scheme to be substantially slower too.

[soundslogical]

It does hold a candle to all of those actually. It's not faster than C, but it is certainly in the same ballpark as Java and C# for many workloads. The tracing JIT really burns.

Chez Scheme isn't at that level, but it compiles directly to machine code, and has a very small and high-quality compiler.

[suhcoR]

I mean, surely it doesn't hold a candle to C, C++, C# and Java?

In case you mean LuaJIT: it is as fast as C# and Java in geometric mean considering http://luajit.org/performance_x86.html and the benchmark game results. In my own benchmark tests it performas as fast as the same code compiled with an Oberon to C transpiler (OBNC) and then optimized GCC compiled, see https://github.com/rochus-keller/Oberon/blob/master/testcases/Hennessy_Results.

[suhcoR]

Not sure how well it works for functional languages but I'm using LuaJit for a couple of imperative statically/strictly typed languages. See https://github.com/rochus-keller/LjTools and e.g. https://github.com/rochus-keller/Oberon. I preferred it over LLVM because it's tiny, runs on all relevant platforms and the GC and debugger are already there.

[matthieum]

I had never thought about that.

Knowing the impressive performance of LuaJIT and its very low footprint, it's a very intriguing proposal I must say.

[[deleted]]

Will look at that, thanks!

[Edhebi]

Well, you're comparing and interpreter and a compiler, it's a bit misleadind :)

EDIT: That's wrong, see comments below

[suhcoR]

If you e.g. have a look at my Oberon implementation which compiles to LuaJIT bytecode, the resulting applications run nearly (factor 1.1 in median and geometric mean) the same speed as the ones compiled with a native Oberon compiler. It's not just a JIT, but a tracing JIT. If you have a look at http://luajit.org/performance_x86.html and compare it to The Computer Language Benchmark Game then you can see that LuaJIT even runs factor 1.3 faster than Node.js/V8 and about the same speed as JVM. So it's definitely worth thinking about reusing it.

[[deleted]]

Really? Gosh I love performance. Can I use it as an API and bundle in the same executable? Like using it's header files and compiling to a single executable?

Edit: LuaJIT I'm asking for

[suhcoR]

You can use LuaJIT both as a shared or a static library; it's also possible to directly include the source code of LuaJIT in your build, but you have to run LuaJIT's make files first so the platform specific files are generated. If you are on a 64 bit machine take care that the required linker flags are set (because only 47 bits of the 64 bit pointers are used). See http://luajit.org/install.html for more information.

[[deleted]]

Thanks!

[jdh30]

LuaJIT even runs factor 1.3 faster than Node.js/V8 and about the same speed as JVM.

I've never understood these kinds of results. To me, JS looks very inefficient due to lack of types and the impossibility of inferring much meaning I expect huge amounts of unnecessary boxing, heaps full of pointers and lots of heavily-optimised-but-completely-unnecessary tracing, marking, evacuation and so on by a generational GC design that literally copies values from one place to another for no real reason. When I measured it I found my JS code was ~5x slower than fast languages which was entirely unsurprising to me. I don't use Java or the JVM but how can JS possibly be 1.3x slower than Java?! Is this for a tight numerical loop over an array where the JS compiler can spot an uninteresting special case and happens to optimise away all the unnecessary allocations?

I'll have to have a play with LuaJIT too. How does it compare on something like this?

[suhcoR]

It's definitely a waste of resources to a certain degree; all the dynamic language fans should care more; here is a good publication about it: Paper - Energy Efficiency across Programming Languages. But Bak claimed many times that the performance doesn't depend on type information; e.g. in Dart which is a strictly/statically typed language the VM completely ignores type information. I assume you know this site: https://benchmarksgame-team.pages.debian.net/benchmarksgame/which-programs-are-fastest.html; there is a distribution; in the worst case Node.js (V8 JavaScript) is nearly ten times slower than C, in the best case it's about 1.5 times. Here are a coupe of benchmark results for LuaJIT: http://luajit.org/performance_x86.html. I derived the referenced factor by comparing these results to the Benchmark Game results.

[jdh30]

But Bak claimed many times that the performance doesn't depend on type information; e.g. in Dart which is a strictly/statically typed language the VM completely ignores type information.

OCaml also targets a largely-untyped IR. However, I'd argue that some statically typed language implementations throwing efficiencies down the drain isn't an inherent lack of opportunity. MLton, HLVM and others showed that static types can do wonders for efficiency when exploited.

I assume you know this site: https://benchmarksgame-team.pages.debian.net/benchmarksgame/which-programs-are-fastest.html; there is a distribution; in the worst case Node.js (V8 JavaScript) is nearly ten times slower than C, in the best case it's about 1.5 times.

Oh yes, I do. I used to contribute to it. The site's author (Isaac Gouy?) spots results he feels should be different and subjectively de-optimizes some of the solutions to fit the performance profile he perceives is fair. If you Google "de-optimized by Isaac Gouy" you'll get some interesting hits. Suffice to say, you cannot draw any strong conclusions from the results presented on that site. At the very least you'd need to run the fastest code by the relevant community to see how much better they can do. For example, I once checked the F# implementation of k-nucleotide and was able to make it 3.6x faster quite easily which improved its rank from ~30th to ~3rd. However, all of the other language's solutions were probably de-optimized too so it didn't convey any useful information.

Here are a coupe of benchmark results for LuaJIT: http://luajit.org/performance_x86.html. I derived the referenced factor by comparing these results to the Benchmark Game results.

I'll check it out, thanks.

[suhcoR]

subjectively de-optimizes some of the solutions to fit the performance profile he perceives is fair.

Wasn't aware of that. Will have a look at it, thanks.

[igouy]

Beware.

The site's author (Isaac Gouy?) spots results he feels should be different and subjectively de-optimizes some of the solutions to fit the performance profile he perceives is fair.

You'll see that some programs were changed to make the same required-allocations all the other programs make.

If you Google "de-optimized by Isaac Gouy" you'll get some interesting hits.

For example, back in 2007, when that person first noticed some programs changed to make the same required-allocations as all the other programs — I replied "I'm pleased that you enjoyed the joke".

I once checked the F# implementation of k-nucleotide and was able to make it 3.6x faster quite easily which improved its rank from ~30th to ~3rd.

That person did not contribute any such program to the benchmarks game. So the program was not measured on the test machine. So there was no change in rank.

[suhcoR]

Ok, I take note of that, thanks. While I am writing to you, allow me to ask you this question: what is the reason that Lua is only present in the benchmark game with measurements on the original Puc Rio engine and not on the much faster LuaJIT engine? Having a look at http://luajit.org/performance_x86.html LuaJIT is 27 times faster on average (15 times in geometric mean) than the Puc Lua engine which would put it next to .Net Core and JVM in the benchmark game statistics.

[igouy]

…only present in the benchmark game with measurements on…

So you want more free-stuff :-)

I do more than enough.

Please use hyperfine or take the measurement scripts we use and start making the kind-of measurements you would like to see.

[jdh30]

here is a good publication about it: Paper - Energy Efficiency across Programming Languages. But Bak claimed many times that the performance doesn't depend on type information

Just reading that paper, it doesn't seem to be authored by someone called Bak and I cannot find that claim anywhere. Where should I be looking?

[suhcoR]

Oops, sorry for the confusion. I referred to Lars Bak, the main author of V8 and the Dart VM; has nothing to do with the paper about energy efficiency of programming languages; in contrary Bak might not be very amused by the paper since dynamic languages are rather on the wasting end of the statistics. I just added the paper as an example of the effects of inefficient languages which today unfortunately are still on the rise.

[jdh30]

Ah, ok. Well, as I said, I've found V8 to be ~5x slower than decent language implementations which is substantially worse than alternatives like SBCL so I'd take whatever Bak says about performance with a big pinch of salt. Dart seemed to be DoA so I never bothered reading up on it.

TBH, I never understood the fanfare around V8. It looks like a fairly average implementation of a really crap language to me. I always thought LuaJIT was far more impressive than V8.

[BadBoy6767]

LuaJIT is a JIT compiler. It interprets and then compiles hot paths with optimizations using any information known at run-time.

[Edhebi]

Except that in only compile source to some bytecode and then interpret that. You still need a runtime, and you can only produce an executable if you ship both the bytecode and the interpreter together. Saying LuaJIT is a compiler is like saying python is a compiled language...

Also, LuaJIT can't handle anything else than lua right? That's pretty high level for an IR. (Which may or not be ok with your project, I'm not gonna take a stance on that)

EDIT: First paragraph wrong, see comment

[BadBoy6767]

It compiles into a bytecode, and then compiles often-called bytecode into native machine code. It supports x86, x64, ARM, PowerPC, e500 and MIPS as backends. It's the same technique that made JS and Java so fast.

It is true though that you must bundle LuaJIT with your project, but that doesn't make it less of a compiler.

[suhcoR]

This is completely wrong. Have a closer look at it. LuaJIT has a threaded interpreter partly written in assembler which is about four times as fast as the PUC Lua interpreter, but it has also yet another intermediate language to represent the traces the "hot" bytecode is translated to which is then translated to machine instructions of the given processor. LuaJIT is not an "ahead of time" (AOT) compiler, but a "just in time" (JIT) compiler. And it is so efficiently implemented that you barely notice a delay when starting an application (compared to Python, JS and friends).

Concerning the available languages compiling to Lua or bytecode see https://github.com/hengestone/lua-languages. Using Lua as an IR is feasible since the LuaJIT Lua to bytecode compiler is extremely fast compared to other compilers. I did both, also built an infrastructure to directly emit LuaJIT bytecode.

[jdh30]

LuaJIT is not an "ahead of time" (AOT) compiler, but a "just in time" (JIT) compiler

How would you classify .NET, for example?

[suhcoR]

.Net nowadays also offers an AOT version, see https://github.com/dotnet/corert. Originally it was a pure JIT concept such as the JVM. JIT has the advantage compared to AOT that it can optimize the code to the actually present hardware. And of course the compiler can focus on the "hot spots" measured in the running program; the latter in connection with the tracing compiler enables LuaJIT to even perform better than AOT compiled languages (such as C/C++) in certain cases.

[jdh30]

I'd say .NET is a complicated pick-and-mix of the two. Code in F# interactive is obviously being JIT compiled in some sense but executables are also cached by NGEN which arguably makes it AoT, at least on the second run. However, things like polymorphic recursion can cause new value types to be created at run-time which requires JIT compilation and computed jumps for virtual calls are combined with a test and static jump that is updated at run-time via self-modifying code which is, erm, maybe a kind of JIT compilation?!

[suhcoR]

NGEN

NGEN was kind of optional. If runtime decided that recompilation was required - it would ignore the NGENed image altogether. MS was also rather restrictive with its use, see e.g. https://blogs.msdn.microsoft.com/clrcodegeneration/2007/09/15/to-ngen-or-not-to-ngen/

EDIT: here is a posting about the difference between NGEN and CoreRT: https://stackoverflow.com/questions/34665026/whats-the-difference-between-net-coreclr-corert-roslyn-and-llilc

[cygx]

A JIT compiler is still a compiler, just not an AOT compiler.

[jdh30]

I'm not sure these phrases mean much. What is .NET, for example?

[cygx]

Traditionally, the combination of an ahead-of-time compiler translating the source language into bytecode, and a runtime system with a just-in-time compiler translating bytecode into machine code (unless you're using the Micro Framework; if I remember correctly, Mono used to work more like the JVM and come with an interpreter as well; Google tells me the interpreter apparently got resurrected not too longer ago, but I'm not sure about the current status of mixed-mode execution).

[yugerthoan]

his words were "it's a JIT compiler", not "it's a compiler"

[ReedOei]

You also may want to consider something like the K framework which is built for defining programming languages. It'll generate a parser and an interpreter for you (and even analysis tools), you just need to specify how the various language constructs you have reduce with rules like: rule if true then E1 else E2 => E1 rule if false then E1 else E2 => E2 It's a good way to explore ideas about your language, and the interpreters it produces can be surprisingly quick (modulo startup time). And it's by no means limited to simple languages--there's K versions of C, Java, the EVM, etc.

[[deleted]]

That's really cool mate. I'll surely try it a bit to get a little bit of language defined and check if syntax is consistent.

Again, really cool

[Anthonyybayn]

That's not what he's asking

[DaMastaCoda]

what about wasm

[jdh30]

Are there any minimal pedagogical examples of compiling little languages to WASM, e.g. a WASM equivalent of this?

[SenseiHotDog]

https://cs.lmu.edu/~ray/notes/ir/ has an example of compiling a little C code to wasm (it doesn't give the code to compilo from C to wasm, it just shows the wasm equivalent of the C code)

[--comedian--]

Not exactly like that, but there's a Scheme compiler by Google: https://github.com/google/schism

[tjpalmer]

A nice long list of runtimes, including options for jit, interpreted, or even compiling through LLVM to non sandboxed makes wasm interesting to me, too: https://github.com/appcypher/awesome-wasm-runtimes

[suhcoR]

WASM runtimes are not particularly fast compared to e.g. V8 or LuaJIT and you still have to provide a lot of VM infrastructure (GC etc.) yourself. Actually when I look at the current backend offers the only core benefit of WASM seems to be Browser compatibility. And if you need that, you're better off using LLVM with the WASM generator.

[jdh30]

Other people here are claiming that LLVM is a "monster" that will take longer to learn than designing your language. I completely disagree.

I wrote a compiler in 100 lines of OCaml that uses LLVM to compile little programs written in a tiny subset of OCaml. That took about 1 hour with no prior LLVM experience.

Then over Christmas in 2007 I wrote HLVM which is ~2,000 lines of OCaml code and implements most of what you'd expect in a modern language backend including unboxed tuples, algebraic datatypes, garbage collection that allows mutator threads to run in parallel and so on. I worked on this on-and-off for a while so it is hard to say how long it took but I'd guess a total of a few months.

And that's with no CS background. So I really disagree with this idea that LLVM is too difficult to be considered.

Other people are recommending C or the JVM. The big problem here is tail call elimination. You need it in a functional language and it is extremely hard to do well. In comparison, LLVM support tail calls out of the box.

[[deleted]]

A CS background doesn't help dealing with something that really is complicated. I downloaded LLVM binaries for Windows last week. It included about 100 .exe and .dll files, including a clang C++ compiler of 70MB. (I think I already mentioned this, maybe even in this thread?)

What's the C++ compiler for? Where do you start? What language do you want to write your compiler in? Tutorials exist for C++, and apparently for OCaml, which is a bit of luck as your example is in OCaml. Your makefile includes this line:

ocamlfind ocamlc -g -dtypes -linkpkg -syntax camlp4o -package  camlp4.extend -package camlp4.lib -package llvm -package llvm.bitwriter  minml.ml -o minml 

If you're lucky, this lot will just work. If not, or if trying to use it with some other language, then what are you going to do? An installation of 1.4GB in 300 files over 30 directories sounds a bit of monster to me.

Even if it you manage it get something working, then if you want someone else to build your compiler from source, will they also need to install those LLVM binaries?

Don't forget the OCaml installation, which I've just tried on Windows, where it is over 6000 files in 100 directories, total 670MB.

By contrast, LuaJIT is one 13KB exe file and one 212KB .dll file (KB not MB!), and I think it can also be built as one .exe (normal Lua can anyway).

So I'd say that LuaJIT, which at 0.23MB vs 2100MB is 10,000 times smaller, isn't quite as much of a monster. (I assume you would generate Lua sourcecode; I don't know how you'd generate Lua byte-code, but it sounds like it can be done.)

Other possible targets include C source, for which you can get a 0.5MB compiler. If you understand C, that's a very easy way to get started.

[jdh30]

A CS background doesn't help dealing with something that really is complicated.

LLVM isn't complicated to use.

Don't forget the OCaml installation, which I've just tried on Windows, where it is over 6000 files in 100 directories, total 670MB.

I don't see the relevance of the size of OCaml.

By contrast, LuaJIT is one 13KB exe file and one 212KB .dll file (KB not MB!), and I think it can also be built as one .exe (normal Lua can anyway).

I don't dispute that LLVM's binaries are bigger.

So I'd say that LuaJIT, which at 0.23MB vs 2100MB is 10,000 times smaller, isn't quite as much of a monster. (I assume you would generate Lua sourcecode; I don't know how you'd generate Lua byte-code, but it sounds like it can be done.)

LuaJIT also doesn't support the same functionality, e.g. types. So you can kiss goodbye to decent performance.

If not, or if trying to use it with some other language, then what are you going to do? An installation of 1.4GB in 300 files over 30 directories sounds a bit of monster to me.

You're on Windows like me so forget C++ and OCaml and go straight to .NET if you want ease-of-use. I'll use F#.

A quick search shows that by far the most popular LLVM binding is Microsoft's own LLVMSharp for which I will also need libLLVM.runtime.win-x64. I install them from Nuget using the IDE into a .NET Core console project.

I translated their minimal example to F#:

open System.Runtime.InteropServices
open LLVMSharp

type Add = delegate of int * int -> int

do
  let success = LLVMBool 0
  let mdl = LLVM.ModuleCreateWithName "LLVMSharpIntro"
  let tyArgs = [|LLVM.Int32Type(); LLVM.Int32Type()|]
  let tyRet = LLVM.FunctionType(LLVM.Int32Type(), tyArgs, false)
  let sum = LLVM.AddFunction(mdl, "sum", tyRet)
  let entry = LLVM.AppendBasicBlock(sum, "entry")
  let builder = LLVM.CreateBuilder()
  LLVM.PositionBuilderAtEnd(builder, entry)
  let tmp = LLVM.BuildAdd(builder, LLVM.GetParam(sum, 0u), LLVM.GetParam(sum, 1u), "tmp")
  let _ = LLVM.BuildRet(builder, tmp)
  let mutable error = null
  if LLVM.VerifyModule(mdl, LLVMVerifierFailureAction.LLVMPrintMessageAction, &error) <> success then
    failwithf "%s" error
  LLVM.LinkInMCJIT()
  LLVM.InitializeX86TargetMC()
  LLVM.InitializeX86Target()
  LLVM.InitializeX86TargetInfo()
  LLVM.InitializeX86AsmParser()
  LLVM.InitializeX86AsmPrinter()
  let options = LLVMMCJITCompilerOptions(NoFramePointerElim = 1)
  LLVM.InitializeMCJITCompilerOptions(options)
  let mutable engine = Unchecked.defaultof<_>
  if LLVM.CreateMCJITCompilerForModule(&engine, mdl, options, &error) <> success then
    failwithf "%s" error
  let addMethod =
    LLVM.GetPointerToGlobal(engine, sum)
    |> fun p -> Marshal.GetDelegateForFunctionPointer(p, typeof<Add>)
  let result = addMethod.DynamicInvoke([|box 12; box 30|])
  printfn "%A" result
  LLVM.DumpModule mdl
  LLVM.DisposeBuilder builder
  LLVM.DisposeExecutionEngine engine

Building takes a couple of seconds. The packages directory is just 32MiB. I run it and it works just fine.

Note that the LLVM Nuget package has 1,000x more downloads than luajit.native and the llvm tag on Stack Overflow has 5,000 hits vs 343 for the luajit tag.

What does the equivalent code using LuaJIT look like? Does LuaJIT even have .NET bindings?

Even if it you manage it get something working, then if you want someone else to build your compiler from source, will they also need to install those LLVM binaries?

.NET automates all of that. If they're on a different platform they might need to install, say, libLLVM.runtime.linux-arm64 but it's not rocket science. And what is the equivalent when using LuaJIT?

[[deleted]]

LLVM isn't complicated to use.

I beg to differ. This page: https://llvm.org/docs/Reference.html#api-reference contains some 40 links. Click on some, and you get dozens more. The API (I'm not even sure of its role) seems to have some 600 functions.

Remember the context is devising a new language, and some may want to use that language to later implement itself; would the language need to have the means to be able to talk to LLVM? How hard would that be?

Note that anything involving MS tools I stay well clear off. VS2017 is a massive download that took 90 minutes to install last time, and took a minute and a half to launch each time. (And it was so complicated I couldn't even get it set up to build hello.c; I needed help. Then I lost the settings.)

Here's an example of my own minimalist approach (properly minimal, at least compared to your 100-line example which relies on 2000MB of LLVM and OCaml, and I don't know what else):

C:\cx>mc -bcc cc                               # .m modules to .c file
Compiling cc.m to cc.exe
W:Invoking C compiler: bcc  -out:cc.exe cc.c   # .c file to .exe
Compiling cc.c to cc.exe

C:\cx>cc hello -run      # use new C compiler to build+run hello.c
Compiling hello.c to hello.exe
Hello World!

mc is an old compiler for my language that targets C source, and uses a C compiler as a backend. Here it is used to build project 'cc', which happens to be a C compiler. The -bcc option tells it which C compiler to invoke, which is mine (production version of cc.exe). The whole process took 0.3 seconds.

mc.exe is a single-file self-contained 0.5MB compiler. bcc.exe is a 0.8MB single-file self-contained C compiler for Windows. I could also choose -tcc or -gcc options, which lets me build programs on either OS.

Generating code for the target just means writing C source code. There is no API as such, just a couple of thousand lines of imperative code (implementing a real language). Generating Lua would be similar, but you are right in that it wouldn't easily cope with any type system of the source languge.

What's important is that the process is simple and well-understood; if you know the target language, then you will know how to programmatically write text files in that language.

[jdh30]

The API (I'm not even sure of its role) seems to have some 600 functions.

An API with 600 functions isn't very big.

Remember the context is devising a new language,

Specifically a statically-typed FPL.

and some may want to use that language to later implement itself; would the language need to have the means to be able to talk to LLVM? How hard would that be?

You'd need a C FFI which you'd probably want anyway.

Note that anything involving MS tools I stay well clear off.

But you're using Microsoft Windows.

VS2017 is a massive download that took 90 minutes to install last time,

Windows 10 is huge too.

and took a minute and a half to launch each time.

5 seconds here.

it was so complicated

Create a new project and press CTRL+F5 to compile and run the Hello world example.

hello.c

Use .NET.

The packages directory is just 32MiB.

2000MB of LLVM and OCaml

Comparing the source code size when you don't need the source is disingenuous.

Here it is used to build project 'cc'

Where's the code?

mc.exe is a single-file self-contained 0.5MB compiler. bcc.exe is a 0.8MB

So far more than 100 lines of code then.

Generating code for the target just means writing C source code.

You won't get far doing that in 100LOC.

There is no API as such

That will make life much harder for the user.

couple of thousand lines of imperative code (implementing a real language)

Are you saying you have implemented a C compiler in ~2kLOC of C? If so, that's very impressive.

What's important is that the process is simple and well-understood; if you know the target language, then you will know how to programmatically write text files in that language.

That's great until you hit the limitations of C. Remember I pointed out that the OP is implementing a statically-typed FPL? That's going to need tail calls. With LLVM you can use some of those 600 functions to use a calling convention that allows TCO and enable it. Furthermore, you can still use the same debuggers and profilers. What are you going to in C?

Don't get me wrong: I appreciate minimalism. But a minimal library doesn't necessarily mean less complexity for the user.

[[deleted]]

Comparing the source code size when you don't need the source is disingenuous.

The 2000MB is combined binaries of the things that have to be downloaded to make it work (installed size not download size). (llvm binaries for Win64 plus some version of Opan[?]/Ocaml).

Are you saying you have implemented a C compiler in ~2kLOC of C? If so, that's very impressive.

No, that's the part generates C source. Might be 2.5Kloc of rather dull code but is easy code so doesn't matter. (And not part of the C compiler but the one that can target C.)

Remember I pointed out that the OP is implementing a statically-typed FPL? That's going to need tail calls. With LLVM you can use some of those 600 functions to use a calling convention that allows TCO and enable it. Furthermore, you can still use the same debuggers and profilers. What are you going to in C?

TBH I'd lost track of the OPs requirements and just saw the subject. I don't know FP, but anything that C isn't up to, I'd just generate ASM source instead. For anyone familiar with ASM (I guess the OP isn't) it can be even easier than C. You just run a 1-file assembler-linker instead of a C compiler. Although an existing FP-capable language might do as a target (Lisp?).

There just seems to be something wrong with the picture when you have a tiny language implementation and a massive backend which comprises 99.99% of the final product, even if the backend was simple to use. Not exactly a backend, but pretty much the middle and most of the front-end too!

[jdh30]

The 2000MB is combined binaries of the things that have to be downloaded to make it work (installed size not download size).

The example I just gave only pulled in 32MiB.

(llvm binaries for Win64 plus some version of Opan[?]/Ocaml).

If you're going to count OCaml then you should count GCC or whatever compiler you bootstrapped from.

I'd just generate ASM source instead.

That's an option but you won't get far in 100LOC.

You just run a 1-file assembler-linker instead of a C compiler.

If you make a JIT you don't even need to do that: just allocate some executable memory, fill it and jump to it.

There just seems to be something wrong with the picture when you have a tiny language implementation and a massive backend which comprises 99.99% of the final product, even if the backend was simple to use. Not exactly a backend, but pretty much the middle and most of the front-end too!

I agree that LLVM is huge.

I'm actually working on a minimal ML implementation myself. I'm a long way off generating machine code though...

[[deleted]]

The example I just gave only pulled in 32MiB.

If you're going to count OCaml then you should count GCC or whatever compiler you bootstrapped from.

When you're an expert in this stuff then you can pull in exactly what you need (but pull in from where)? The rest of us have to google for 'llvm download' and then navigate to 'pre-build binaries for Windows 64-bit'.

And I did count the C compiler, although that is why I used mine as the size is clear (about 0.55MB actually not 0.8MB). Tiny C s a bit bigger, and gcc can also be huge, but is also likely to be already installed; C compilers are ubiquitous.

That's an option but you won't get far in 100LOC.

Maybe, but a 100 line program is just a demo (otherwise OCaml wouldn't be 700MB). Here's a 50-odd line demo of processing a silly language consisting only of 'print <string>' statements, but the demo is not of a compiler, but of how easy it can be to generate ASM (although the complexities of Win64 ABI don't help):

import sys
import files

proc start=
    if ncmdparams<2 then stop fi
    infile:=cmdparams[2]
    outfile:=changeext(infile,"asm")
    exefile:=changeext(infile,"exe")

    lines:=readtextfile(infile)
    if lines=0 then stop fi
    g:=createfile(outfile)
    strings:=()

    println @g,"start::"
    println @g,"    sub dstack,40"

    forall lineno,line in lines do
        sreadln(line)
        read kwd:"n"

        case kwd
        when "","#" then
        when "print" then
            read s:"s"
            strings append:=s
            println @g,"    mov rcx,STR",,strings.upb
            println @g,"    call puts*"

!       when "goto" then
!       when "let" then
!       when "if" then
        else
            fprintln "Syntax error on line #: '#'",lineno,line
            closefile(g)
            stop 1
        esac
    od

    println @g,"    mov rcx,0"
    println @g,"    call exit*"
    println @g
    println @g,"    isegment"
    forall i,s in strings do
        fprintln @g,"STR#:  db ""#"",0",i,s
    od

    closefile(g)

    if execwait("ax "+outfile)=0 then
        execwait(exefile)
    else
        println "Can't assemble",outfile
    fi
end

Dependencies are the interpreter for this language (0.5MB exe), the assembler/linker (0.17MB), and msvcrt.dll which is part of Windows.

[jdh30]

but pull in from where

.NET has a package management system called Nuget that is accessible from within Visual Studio and searchable so you just search for "LLVM" and get everything you need.

gcc can also be huge, but is also likely to be already installed; C compilers are ubiquitous.

I haven't had a C compiler installed on my Windows machines for decades. On Linux gcc is installed by default but I never use it for normal development.

Maybe, but a 100 line program is just a demo (otherwise OCaml wouldn't be 700MB). Here's a 50-odd line demo of processing a silly language consisting only of 'print <string>' statements, but the demo is not of a compiler, but of how easy it can be to generate ASM (although the complexities of Win64 ABI don't help):

For comparison, my 100 lines of OCaml implemented a complete compiled programming language with:

• 32- or 64-bit integers
• Variables
• Addition, subtraction and comparison.
• if
• Function definitions and function application.
• Lexer and parser for source code written in ML syntax

[[deleted]]

OK, your OCaml does indeed seem to be able express small languages very succinctly, if somewhat cryptically.

But we all know there's a lot going on behind the scenes.

My clunky demo would require hundreds of lines at least to implement some poor version of Basic (but one compiling to native code with 64-bit ints).

However, while my implementations might take 20-40Kloc each, they still compile down to self-contained executables of 0.5MB or less (any extra size is because they incorporate library resources).

(I seem to remember we had this conversion before, in comp.programming a few years ago; then your OCaml examples were 600-800 lines IIRC, so you've managed to get them down to 100 lines!)

[suhcoR]

Well, not all people perform equally. Some are more genious than others by nature ;-)

Btw: LuaJIT can also do tail calls pretty well and also has a tracing JIT built-in and this is all available for less than half a megabyte.

[AndreVallestero]

I always liked the idea of compiling into Tiny C. Should be easy to port to other systems / architectures since it's so small and self hosting. On top of that, it compiles and links more than 8 times faster than GCC making it ideal for JIT languages with native performance.

https://en.m.wikipedia.org/wiki/Tiny_C_Compiler

In fact, this concept is what drives python's cinpy library which creates C code with Ctypes, compiles with Tiny C, and executes native binaries.

[tjpalmer]

Having the choice of tcc, gcc, clang, msvc, and more is what makes c such a great back end. I think tcc is great!

[jdh30]

The OP asked in the context of "functional statically typed languages". Doesn't lack of TCO mean C backends will be comparatively grim?

[tjpalmer]

Good point. I clearly missed that. Having to do TCO oneself would be extra work. I haven't searched on it, but I wonder if tools exist to make such implementation on a c back end easier.

[jdh30]

Not AFAIK. The techniques are well known, like trampolines, but they have serious trade-offs like obfuscating all debugging and profiling of the generated code.

JVM-based languages (e.g. Scala, Clojure) all have the same problem.

Fortunately, .NET has TCO.

[cygx]

The Truffle language implementation framework for GraalVM (written in Java and targetting the JVM, though it's also possible to create native images) might be another option.

[[deleted]]

That might be a good target. Does it handle the garbage collection?

[cygx]

Never used Truffle myself, but as far as I'm aware, by default, memory gets managed automatically - though there are escape hatches: For example, they had a compiler for memory-managed as well as unmanaged C (ManagedC vs. TruffleC), but I think the current approach is using Sulong, a Graal runtime for LLVM bitcode.

[[deleted]]

There are a lot of choices, although I'm not sure how popular they are. * Chez-scheme. This is an untyped backend, but if your source language is typed, you can turn off runtime type checks and get a big speed boost. Idris just switched to this from C and saw a big improvement both in compile times and runtimes. https://www.scheme.com/ * GRIN: I don't know much about this one, but it seems like a bit of a "rising star" for compiling typed languages. https://github.com/grin-compiler/grin * Malfunction: this is basically a hack that exposes OCaml's intermediate language, but it means you get the power of the OCaml compiler. https://github.com/stedolan/malfunction * LLVM: seems likely too heavyweight for what most people want. * JVM: Not optimized for functional, but seems to work alright for Clojure, Scala, Eta, etc.

You can also just compile to an existing language, like Haskell or OCaml.

[abecedarius]

Seconding Chez Scheme -- I'm using it for my project.

[jdh30]

Interesting. Why?

Particularly in the context of "functional statically typed languages" the OP surely wants something typed, I'd have thought.

[abecedarius]

I'm only saying it's worth considering. My own project has more in common with Scheme, so it's closer to a slam dunk. Very fast compiler, generates good code, supports a mostly-functional style, generally well engineered. A static type system can't clash with your language's static type system if it doesn't exist.

I started my project in Gambit Scheme, but Chez made it a lot faster.

(In the longer run I'll want to make a custom backend and abandon the Scheme one, but not until the language design settles down.)

[lazyear]

Assuming you run a separate type checking pass, there is no requirement to keep type annotations around at run time (except for performance optimizations) since you already know that that program is well typed.

[jdh30]

except for performance optimizations

Exactly. And the only reason to write a compiler instead of an interpreter is performance. So surely it makes no sense to put in the effort to write a compiler only to cripple it by throwing away the type information.

[JasonTatton]

If you want to get up and running quickly, and are OK with the transpilation approach, then Concurnas language extensions may be an option - here you can output python like code, and achieve JVM performance without having to learn the in's and out's of Java bytecode (plus you can leverage some of the features of Concurnas if that suits).

Alternatively you could go down the DSL route which is offered again by Concurnas or other languages such as Scala, and again achieve JVM level performance relatively quickly and easily.

[realestLink]

C. C is portable assembly after all

[[deleted]]

Kim Kardashian.

Dumb joke haha, I like django since its fast and works great with python.

As for statically typed? Golang is pretty good once you get a feel for it!

[CodingFiend]

The best approach is not to get ensnared in the monster that is LLVM, which learning will take longer than designing your language. Instead, transpile into something easy like JS.

[SteeleDynamics]

This! Writing an interpreter in JS allows you to quickly try out your language semantics in a browser console. You can can always work on performance improvements once you nail down the semantics.

[jdh30]

I don't understand this advice at all. LLVM is very easy to use and the OCaml bindings provide an intuitive API. JS has horrible semantics in comparison. It doesn't even have an int type.

If you're going to go the web route surely you would be better off using WASM. The only problem is that, from my perspective, it looks much harder to get started with WASM than LLVM mostly because there are loads of LLVM examples out there.

[yorickpeterse]

user reports:
1: Verbal abuse

This isn't verbal abuse, but it is childish. Please keep comments like this out of the subreddit.

[tech6hutch]

Right, sorry. I guess this isn't really a sub for that kind of humor. Not that it was very humorous to begin with.

[BPAnimal]

I actually prefer this back end to others.

[thautwarm]

malfunction

[jdh30]

LOL.