Porting the Go compiler from C to Go

http://gophercon.sourcegraph.com/post/83820197495/russ-cox-porting-the-go-compiler-from-c-to-go

by sqs • 12 years ago

212 93 12 years ago

gophercon.sourcegraph.com

stcredzero3• 12 years ago

Automated rewrite FTW! This can help you avoid freezing a project while it is being ported. Also, if you have a code base with its own idioms, then those idioms can be matched and translated, which can produce cleaner target code.

adient2• 12 years ago

Go 1.0 spec is already frozen and will not change any time soon.

szabba• 12 years ago

I believe he referred mostyl to freezing the efforts on impoving the implementation.

ANTSANTS• 12 years ago

  >A Union is like a struct, but you’re only supposed to use one value
  >(they all occupy the same space in memory). It’s up to the programmer to know which variable to use.
  >  There’s a joke in some of the original C code:
  >      #define struct union /* Great space saver */
  >  This inspired a solution:
  >      #define union struct /* keeps code correct, just wastes some space */

Somewhere in Scotland, a sum type sheds a single tear.

piokuc2• 12 years ago

  >      #define union struct /* keeps code correct, just wastes some space */

Not always, though...

rsc2• 12 years ago

Yes, always. And if you don't believe me, it's not my trick. I learned it from Dennis Ritchie (he was thinking about a C to Limbo converter).

Shamanmuni2• 12 years ago

It's great that they are aiming for an automated conversion from C to Go. It's clear they aspire to convert their code which was written in a certain way. But I think it would be a huge boost in Go usage if they could eventually aim to transpile any C code into Go code.

A little dream of mine would be if in the future when Rust is stable Mozilla developed a transpiler from C++ to Rust. That would be brilliant.

By the way, all the other talks at GopherCon seem pretty interesting, I hope someone uploads videos of them soon.

NateDad• 12 years ago

It has been stated that there will be videos available, but I'd not expect them until next week sometime (when the organizers get home and have recuperated).

jerf• 12 years ago

It is unclear how one would compile arbitrary C code into useful Go. The stereotyped conventions of well-written compiler code allows for a more idiomatic translation than a general translator could ever aspire to.

C++ to Rust would be even crazier.

(Transpile is a silly word. It's "compile". Compiling already trans-es.)

stcredzero3• 12 years ago

Good automated translations involve matching and translating the project idioms. This results in code that fits the target language's language-idioms. Automated translation only at the level of language constructs results in odd looking generated code.

Shamanmuni2• 12 years ago

I know it's crazy difficult to do it, that's why I was talking about dreams.

But maybe a set of guidelines about translatable C code plus a translator which is good enough for a variety of cases would make refactoring the resulting code such a manageable task that many projects could consider switching to Go directly.

You are technically correct in that compile already implicates a translation, but we usually use that term refering to a translation into a lower level language and not another language at the same level. You can say transpiler or source-to-source compiler for those cases and I think it's clearer and more accurate for the reader.

mwsherman• 12 years ago

The use case is to bootstrap the conversion from C to Go, if one has made a decision to do so. You pick a cutoff time, and say “now were going to do our work in Go”.

What comes out the other end, as Russ phrases it, is a C program in Go syntax. The next phase of work is to turn it into “Go” as a human might write it.

The translated program is not meant for deployment, really. It’s to give the humans a starting point.

kodablah• 12 years ago

"a transpiler from C++ to Rust"

I think the best approach for something like this is a disassembler for LLVM IR. I am not extremely familiar with the LLVM IR, but I figure there are common patterns or debug symbols clang produces that could let you get a decent idea of what the higher level gave you. If not targeted to clang output too much, you can then transpile any LLVM-able language to Rust.

I think, but am not sure, that the problem with Rust being a target for these other languages (my pipe dream is to write a JVM in it w/ a JIT using the bootstrapped rustc lib) is that you have to use unsafe code all the time (unless there's 0 performance penalty for ARC) because the original code is not written with ownership/borrowing semantics.

sanderjd• 12 years ago

I think there are probably lots of chunks of code that would be perfectly valid under Rust's ownership semantics and could therefore be transpiled safely. Figuring out which chunks are and aren't would probably be quite difficult though.

Someone2• 12 years ago

Reading https://docs.google.com/document/d/1P3BLR31VA8cvLJLfMibSuTdw..., I don't see that they are aiming for an automated conversion; they are aiming for an automation-assisted conversion.

They want to go quite a step up from doing some global regex replaces, but in the end, step 3 has "cleaning up and documenting the code, and adding unit tests as appropriate.". I don't think they aim to automate anything there.

SixSigma2• 12 years ago

Russ' paper on the subject from Dec 2013

https://docs.google.com/document/d/1P3BLR31VA8cvLJLfMibSuTdw...

thinkpad20• 12 years ago

There are currently 1032 goto statements in the Go compiler jumping to 241 labels.

Wow, that's really striking. I know that goto statements have their uses but for something written in the last couple of years to have over a thousand of them is very surprising (it might not be surprising at all for those who write C code all the time). I guess they're mostly just for error handlers?

azernik• 12 years ago

Yeah, there are a lot of them in e.g. Linux kernel code for jumping to end-of-function cleanup. I suspect that in the process of translation to Go most will be replaced by the defer keyword.

jgrahamc• 12 years ago

For example: http://golang.org/src/cmd/6g/gsubr.c

Some are for single error return, but others are just to make a nice structure for the code.

raverbashing4• 12 years ago

Ah the old C style of function types in a different line.

This smells of very old code (as the header testifies)

saucetenuto• 12 years ago

I dunno, a few of them seem hard to justify. The one on line 475 could just be an "else" branch, frex, and the ones in the loop on 327 could as easily be continues.

simias3• 12 years ago

I would be curious to hear the justification behind the implementation of angryrealloc, the "goto ok" is strictly equivalent to a "continue" as far as I know. Maybe it triggers an optimization with a certain compiler.

daeken• 12 years ago

I'm not surprised to see them in a compiler. When you're parsing and want to treat it as a big state machine, gotos are your best friend.

bakul• 12 years ago

Except in languages with tail recursion such as Scheme! A state ends with a call to the next state instead of a goto next state.

clarry3• 12 years ago

Encoding state implicitly in control flow tends to give you nicer and more natural code. A big state machine implemented with gotos can be tough to read if it's also a parser (which may need to build a tree, recurse, etc.). A small hand-rolled lexer might be reasonable to implement with goto. Although I would prefer to enumerate the states and use a switch.

If you're writing a recursive descent parser for C while keeping minimal lookahead, I can think of a place or two where goto might really help. One is to deal with casts, compound literals and subexpressions. They all begin with a left-parenthesis, so you can't tell what you're dealing with until a bit further. Since these all appear in the parsing of simple expressions (identifiers, constants, unary operators), the code can go in one function and you can jump to the right place with goto as soon as you know what you are dealing with.

I did not look in the Go code but C programmers mostly use goto for error paths.

awda2• 12 years ago

As others have pointed out, this is actually idiomatic C. You have a portion of your function below a label which is "clean up everything and return this variable (usually error status)." Then at any point where you have an error, you goto that label and everything is released and the error gets returned. It's sort of a manual 'defer' pattern.

"goto considered harmful" is taken out of context and bemoaned mostly by people unfamiliar with idiomatic C, I think. (Edit: sorry, I mean just for C. For other languages, e.g. Go, there may be more appropriate patterns like the 'defer' keyword.)

im3w1l• 12 years ago

I saw one goto that could cleanly be replaced with an else (goto fp).

I don't think the authors were very goto-averse.

coldtea3• 12 years ago

but for something written in the last couple of years to have over a thousand of them is very surprising

Hardly surprising. Gotos will be found by the hundrends or thousands in C projects like compilers, kernels etc.

It's used for localized consolidated error handling, but also for stuff like parsing code (bison generates tons of gotos IIRC), state machines, etc.

If anything it's the old "Goto statement considered harmful" that's a little too naive.

copergi3• 12 years ago

If anything it's the old "Goto statement considered harmful" that's a little too naive.

No, people who didn't read it and just repeat the title without knowing what he was talking about may be too naive, but the original point was not.

beliu• 12 years ago

Author of the post here. Happy to answer any questions I can, and FYI, we (Sourcegraph) are liveblogging all of GopherCon at http://gophercon.sourcegraph.com. Let us know if you have any questions or find it useful!

nfoz• 12 years ago

Are you at all concerned about the possibility of the Trusting Trust[1] problem manifesting in any of your Go compilers?

[1] http://cm.bell-labs.com/who/ken/trust.html

0xdeadbeefbabe• 12 years ago

Since this is an exercise divorced from reality, the usual vehicle was FORTRAN.

Dang it I cheated and looked up Rus's quine. For anyone not wanting to cheat a good hint would be "tail recursion"

zellyn• 12 years ago

It was suggested long ago that having multiple compilers would make it incredibly difficult to play Trusting Trust games.

codezero• 12 years ago

You might want to clarify that you aren't Russ Cox and that this post is a summary of a presentation he gave.

sqs2• 12 years ago

Thanks for mentioning this. I initially included "(unofficial liveblog post)" in the HN title, but it apparently was edited out by a moderator. So, I added a clarification to the top of the post itself.

AYBABTME2• 12 years ago

I'm really thankful for the liveblogging, as I couldn't manage to get my body to the conference.

I understand the desire to promote the Sourcegraph app by doing the blogging, and I think its effective. However, the blog is real annoying to browse, as every (prominent?) link points to Sourcegraph the app instead of the blog.

AYBABTME2• 12 years ago

Just to clarify, because I think my original comment is disbalanced.

I'm REALLY thankful for sourcegraph's liveblogging. The above comment was a suggestion as I thought they might want to know that (at least for me), the navigation of the blog was confusing.

sqs2• 12 years ago

Thanks! We are having a fun time liveblogging and are glad you're finding it useful. We got complaints when the blog image did NOT link to Sourcegraph, too. :) It's almost the end of this conference, but next time we liveblog, we'll have 2 separate header images, or try something else to make it less confusing.

hrjet• 12 years ago

This might become a nice benchmark for the Go language; the same code base implemented in C and Go! It may not be fine-tuned for optimisation, neither in C nor in Go, but may still give a good ball-park estimate.

lazyjones• 12 years ago

Indeed, but it would be much more useful and impressive if they rewrote the compiler in Go by hand. I'm disappointed that they are aiming for an automatic translation instead - some people are going to ask themselves whether Go actually isn't that much fun to program in. An independent reimplementation is better for correctness too, they can compare outputs and find bugs in both implementations instead of porting over old bugs and adding new bugs where the translation goes wrong.

micro_cam• 12 years ago

I'm reminded of the fortran to c compiler f2c that was used to produce pure c implementations of lots of libraries like LAPACK.

I'm curious how they will handle things like pointer arithmetic and memory safety in C vs Go. If they mange to do so in a performant way I could see translating lots of numerical or computationally intensive code to Go so that it could be run in a shared cloud environment without worries about memory safety and without having to resort to vms for separation.

mjcohen• 12 years ago

If you took arbitrary fortran, especially with i/o, the results were an unreadable mess - but they compiled and ran.

For a project I had (in the early 90s iirc), I had to extensively modify the fortran and make multiple versions before the generated C was readable. Still, much easier than a rewrite.

kristianp• 12 years ago

"They’re deciding to automatically convert the Go compiler written in C to Go, because writing from scratch would be too much hassle."

When transcribing a talk, there isn't any need to write "They're". Just use the same pronoun the presenter used, otherwise it stands out like a sore thumb.

rdc12• 12 years ago

"Note: There’s a book written about converting goto code to code without goto in general, but this is a sledgehammer and not necessary here."

Anyone have any idea what the title of that book is?

pohl2• 12 years ago

3) Go has turned out to be a nice general purpose language and the compiler won’t be an outsize influence on the language design.

In what sort of ways does self-hosting early influence a language design? Were they hoping to avoid something in particular by delaying self-hosting?

gizmo686• 12 years ago

The general way that self hosting influences language design is that the compiler is often one of the first major projects to be built using a language. This does not give it more influence then other major projects, but if your goal is to have a language designed for use case X, it is generally best to have your early projects with it be for X. Additionally, self hosting may encourage a language design that makes bootstrapping easier (such as a stricter divide between the state-1 language and the general language).

steveklabnik• 12 years ago

To expand a bit on your last point, self-hosting helps answer the question "can I build Real Software (tm) with this language, or is it really difficult?" earlier in the lifetime of the language.

pohl2• 12 years ago

I sort of had the general sense of that already. I guess I was hoping for something more specific about what language features are so useful when writing a compiler but get in the way for general problems.

The part I quoted above almost sounds like wiping sweat from one's brow after having dodged a bullet: "phew, the language is safe from influence by those gull-durn compiler-writers..."

Porting the Go compiler from C to Go

Related Stories