C as an intermediate language (2012)

https://yosefk.com/blog/c-as-an-intermediate-language.html

by yinso • 9 years ago

133 60 9 years ago

jokoon• 9 years ago

I'm still learning how to build a language, and compiling to c seems like the easiest thing to do, but I'm curious if it's more difficult or not.

If my language is close to c (functions, scope, variable, types), can I take advantage of it so it's less work in my compiler to let the c compiler catch errors, or must I rewrite a full parser?

All I want to do is add pythonic indenting, range loops, maps, and geometric types with their operators (a little similar to shader languages).

tyingq• 9 years ago

Sounds somewhat like nim. https://nim-lang.org

qznc4• 9 years ago

Using LLVM is a little bit harder but gives you advantages like better debugging. Long term that pays off.

If you only play around, using C is fine.

MaxBarraclough4• 9 years ago

Vala seems to be doing ok targeting C. I'd hardly say it's just for toys.

dom96• 9 years ago

I've never had any trouble debugging Nim, which compiles to C. The Nim compiler adds #line directives so you can just use gdb/lldb[1]. Can you elaborate on what debugging advantages LLVM brings?

1 - https://nim-lang.org/blog/2017/10/02/documenting-profiling-a...

exDM69• 9 years ago

I would say that emiting LLVM IR is easier than C. I have done a few toy compiler projects with LLVM and it is very nice. I've never done a compiler that emits C, but I can't imagine it being any easier. At least you'd have to write more boilerplate code.

You also can't create JIT compiled REPL using C as easily.

RX14• 9 years ago

The thing about llvm ir is you get a code builder "for free" from llvm, where you're just calling functions to build your ir. However, when emitting C you have to build that yourself and take care to always emit valid code. Not sure how much difference that actually makes though.

lucozade2• 9 years ago

As described, you’ll almost definitely need to write a parser. However, if your type system is very similar to C’s you may be able to just lower from the AST to C and let it worry about semantic analysis and code generation.

The biggest loss is that a lot of error and debug info will be relative to the C rather than your language. This means the user will be exposed to the internals.

Probably the biggest win, is that it’s almost trivial to integrate C, and potentially C++ libraries into your language. This has been hugely beneficial to Nim, for example. They have written a full front end though so they don’t have the error issue above.

Like most things it’s a trade off.

humanrebar2• 9 years ago

Not mentioned in that list of downsides is that you need to at least embrace the calling conventions, threading models, and memory models that C supports, at least for the flavors you target.

The biggest loss is that a lot of error and debug info will be relative to the C rather than your language. This means the user will be exposed to the internals.

In other words, sometimes the end user has to debug a bunch of code they didn't write. I wouldn't underestimate how much a pain this can be.

Probably the biggest win, is that it’s almost trivial to integrate C, and potentially C++ libraries into your language.

Again, subject to adhering to threading models, etc. If you're writing a language as a hobby, this may not be a big concern, but at scale, someone will be using memcpy or memory barriers or thread-local memory somewhere. It is certainly possible to support those use cases, but I'd be careful about overstating how trivial that is.

dtech• 9 years ago

let the c compiler catch errors, or must I rewrite a full parser?

In the long run you always want to do it specifically for your language, because otherwise giving usable error messages and debugging information becomes impossible.

dfox• 9 years ago

You can implemement reasonably C-like languages (eg. Objective C and various C-derived DSLs in many Lisp implementations) by a simple text transforming preprocessor and get reasonable error messages from the C backend (#file is your friend for achieving that).

But for anything more complex you are better off implementing complete parser with your own error handling and reporting.

Edit: one of the clearest signs of language implemented in this way is use of '@' character as part of syntax extensions as it is the only printable ascii character that has no syntactic meaning in C (the other such "unused character" is '$', but its meaning is implementation-defined, for example gcc has option that causes it to be accepted as part of identifiers, which is quite obviously the default on VMS)

quicklime• 9 years ago

The Mercury compiler has a backend which compiles to C. This is currently described as "high-level" C, because the generated code sort-of (relatively speaking) looks like code that a C programmer might write. But back in the early days (mid 90s?) it emitted "low-level" GNU (not ANSI/ISO) C, which basically looked like assembly code for an abstract machine. Kind of like the "compilation strategy" described in TFA, taken a number of steps further.

One of the nice things about GNU C is that various GCC-specific extensions can be taken advantage of. For example ISO C does not require a compiler to optimise tail recursive calls, which are heavily used in functional (and logic) programming languages, where recursion is used instead of loops. It also lets you access CPU registers directly, and write inline assembly code.

d33• 9 years ago

I heard that GCC supports more architectures than LLVM. Perhaps Rust having a C backend would make sense? On the other hand, I have no idea how tightly coupled to LLVM it is.

adrianN• 9 years ago

LLVM is used for optimizations in Rust. LLVM is more than just a nice way to target multiple backends, it's a very sophisticated set of building blocks for compilers.

Rusky2• 9 years ago

The language itself isn't coupled to LLVM outside of some underspecified details around things like unsafe and the memory model, which will eventually be better-defined.

The compiler has historically been fairly strongly tied to LLVM. This is changing for several reasons as the compiler is refactored, which should enable alternative backends like directly generating C or even plugging directly into GCC.

There is also an LLVM backend for generating C, at various levels of maintenance, that might be made to work.

pjmlp5• 9 years ago

A very long term project could be to eventually make the Rust compiler full Rust based.

However that would not make much sense from engineering point of view, too many years of optimization algorithms, tooling and supported architectures have been spent into gcc and LLVM backends just to thrown them away in name of purity.

__s• 9 years ago

Rust has tried to not couple its design to LLVM

For awhile LLVM could target C

cpeterso• 9 years ago

There is some discussion of supporting Mozilla's experimental Cretonne compiler (initially designed to be a new Firefox wasm JIT) as an alternative backend for rustc. Cretonne could be handy for developers wanting faster compile times during development with the cost of less code optimization.

https://internals.rust-lang.org/t/possible-alternative-compi...

pjmlp5• 9 years ago

Another language that famously took this route is Eiffel.

EiffelStudio uses a VM like environment for the develop-compile-debug cycle, and then compilation to native code via the platform's system C compiler for deployment.

jmiserez• 9 years ago

I remember compilation being rather slow though, and deleting the EIFGENS folder frequently when something stopped working. This meant all the C code had to be regenerated and then recompiled, which took a while.

I still think it was a great language for learning programming.

vram22• 9 years ago

Eiffel seemed like a really good language. I wish it had succeeded more and become mainstream. I've tried it out some with EiffelStudio earlier. Their support for developing GUI apps, at least on Windows, also seemed good, based on what I tried of it.

The book "Object-Oriented Software Construction" by Bertrand Meyer, Eiffel creator, is also very good. I had read most of it some years ago.

mpweiher• 9 years ago

This becomes difficult when you want to do something that C doesn't really handle (well), for example the processor flags or for example passing control to another function, leaving the stack intact (objc_msgSend).

If you can then insert some asm, that's good, otherwise you hit a brick wall.

See: https://cr.yp.to/qhasm/20050129-portable.txt

lisper• 9 years ago

This. C is a great intermediate language for languages that have semantics close to C. Otherwise, not so much.

pankajdoharey• 9 years ago

I have always asked this question why C as IL and not something like C-- which is more portable and less system call specific. I think that LLVM IR already serves a good purpose at doing this and is really easy to hand program in.

cordite• 9 years ago

One I knew of was Vala. I’ve not used it, but the elementary-os devs seem to like it. https://wiki.gnome.org/Projects/Vala

ktpsns2• 9 years ago

Vala is interesting because it adds syntactic sugar for the GObject OOP library [1] which is a fundament in GTK+ GUI programming (but also can be used independently). All this was (is?) part of the idea that C++, Qt (with the moc) and finally KDE is bloated, broken from the roots. From my understanding, the main argument is the (in many cases unneccessary) complexity of C++ vs. the simplicity of C. In the Gnome desktop world, from my experience many devs moved on to Python based GUI programming. But I still think there are purists who prefer C/GLib due to its plain design.

[1] https://en.wikipedia.org/wiki/GObject

pjmlp5• 9 years ago

Usually in C vs C++ flamewars, even virtual calls are seen by C devs as bloated, which is ironic in a language that needs to cache the calls to strlen().

shmolyneaux• 9 years ago

In addition to the ones already mentioned here, pypy, a tracing jit for python2 and python3, is another project which gets compiled to C. It's written in RPython, which gets compiled down to C.

RPython includes a jit generator that can be used to speedup new languages written in it. Pixie [0] is an example of another language written in RPython.

[0] https://github.com/pixie-lang/pixie

throwaway7645• 9 years ago

There was a big HackerNews thread on Pixie awhile back with the author Tim Baldrige and why he eventually stopped the project. A neat idea.

tburmeister• 9 years ago

Cython is another Python-like language that gets compiled to C; it's a great tool for getting big performance bumps for very little effort.

chestervonwinch• 9 years ago

In my experience, by the time I start getting performance improvements with Cython (typing everything, removing Python function calls, etc.), I seem to end up with code that's bigger and messier than if I had just written a C extension or used f2py.

frankpf• 9 years ago

[...] pypy, a tracing jit for python2 and python3, is another project which gets compiled to C.

That's interesting. How does it work? I think most JIT compilers emit assembly directly and then execute it. Does PyPy generate C code while your program is running?

widdma• 9 years ago

PyPy is written in RPython, which can be compiled to C. PyPy itself emits machine instructions like a regular JIT interpreter.

sinistersnare• 9 years ago

To add to the other answer, PyPy is a "Meta-JIT compiler", because it generates JITs, it isnt itself a JIT.

ufo• 9 years ago

You might want to read the PyPy's documentation wiki[1] and the Tracing the Meta-Level paper from the PyPy authors[2].

Pypy consists of a Python interpreter written in the RPython language. RPython is a statically typed language that is easy for an opimizing compilation framework to work with. It also happens to be a valid subset of Python but that isn't actually that important.

The RPython translation framework has three ways to run RPython code:

* The first way is by using an ahead-of-time compiler to convert the RPython to C and then passing that to a C compiler (gcc or clang).

* The second way is by compiling the RPython down to RPython bytecode and running that through an RPython bytecode interpreter. (The RPython bytecode interpreter is written in C)

* The third way is the trace compiler. It takes in a linearized trace of the program execution (as observed by the RPython bytecode interpreter) and generates optimized machine code for this trace.

So, going back to PyPy as a concrete example, this is what is going on:

PyPy is a Python interpreter written in RPython. The pypy executable contains two versions of this python interpreter, both created by the RPython translation framework. The first version is the one where the rpython code for the python interpreter gets compiled to C. The second version is one where the rpython code for the python interpreter is converted to rpython bytecode (which is stored in the data section of the pypy binary) and where this bytecode is in turn executed by the rpython bytecode interpreter.

When you run a python program with pypy, it starts being executed by the first interpreter. When this interpreter detects a hot loop in the python program, it transfers control to the RPython bytecode interpreter. This bytecode interpreter executes for one iteration of the loop, and records a trace of what rpython bytecode instructions were executed in this iteration. Then, it uses the jit-compiler to directly generate machine code for this trace, and transfers execution to that.

If it goes according to plan, the base C interpreter will have speed comparable to CPython (or slightly slower), the tracing interpreter will be very slow (but for just one iteration) and the machine code for the traces will be very fast.

-------

You might be wondering: why bother with so many different steps?

1) Why write a python interpreter in rpython and then run that on an rpython jit compiler instead of just writing a JIT compiler for Python?

The PyPy devs had already tried that with the Psyco JIT compiler.

2) Why generate C code for the first interpreter if you already have a JIT compiler that can generate machine code?

The JIT compiler can only compile linear traces, and can't compile whole functions.

3) Why not use C as an intermediate language for the JIT compiler as well?

While C is a workable intermediate language for method-at-a-time compilation, it is less suited for trace compilers.

Scarbutt• 9 years ago

Pixie was abandoned by the author mostly because he realized he couldn't achieve the performance that Clojure has on the JVM.

1wd• 9 years ago

Chicken Scheme does this. https://www.call-cc.org/

And Bigloo Scheme. http://www-sop.inria.fr/indes/fp/Bigloo/doc/bigloo-3.html

And Gambit Scheme. http://gambitscheme.org/

There seems to be a theme here...

WalterBright4• 9 years ago

I considered compiling D to C. The trouble is when you need to do things like exception handling, adjustor thunks, define things that are implementation defined or undefined in C, etc. I figured I'd spend too much time struggling with that, and besides, it would make compilation slow.

Without doubt, today the answer is C++ and Objective-C – languages whose first compilers emitted C code.

I wrote the first native C++ compiler for the PC. It was a huge win over the cfront based PC compilers, which were nearly unworkable.

stingraycharles• 9 years ago

I figured I'd spend too much time struggling with that, and besides, it would make compilation slow.

Is that only because of the extra compilation step, or are there other things making this more slow ?

WalterBright4• 9 years ago

Things that make it slow:

1. Compile the code 2. Generate strings for C code (C is much larger than intermediate code). Translating things like integers to strings is slow. 3. Writing the file out, as opposed to just keeping the data in memory.

C compilers are already slow (due to the preprocessor and phases of translation), so add your compiler on top of that, and you're going to have an unfixably slow solution.

WalterBright4• 9 years ago

Another problem I failed to mention is you don't have control over the C compiler the customer is using. It may behave differently, have bugs in it, etc., and the customer will blame you. Being unable to fix the C compiler means you'll be fixing the problem in the wrong place, making things pretty hard on you.

I run into these sorts of problems with D's C++ interface. In particular, how "long long" and "long" are mangled when they are the same size, and when "long long" is used vs when "long" is used. It's an endless whack-a-mole problem.

zzzcpan• 9 years ago

Well, you don't have to generate raw C code and deal with all the compilers. It might be possible if your language doesn't have machine types, but if it does you have to do what C software usually does: test the compiler for various things and generate a header to rely on. Maybe even supply a ./configure script.

rdc12• 9 years ago

If you were writing D from scratch today, would you go for a full back end solution or would you target the LLVM?

WalterBright4• 9 years ago

There's already LDC, a D compiler using the LLVM. The 3 D compilers (DMD, GDC, LDC) nicely complement each other.

C as an intermediate language (2012)

Related Stories