13 ms·

Go 1.3+ Compiler Overhaul

210 points by geetarista 13y ago

frou_dh 13y ago
Noice. Business case aside, that sounds like a fun exercise for those with the chops to tackle it.
- noselasd 13y ago
  Step 1. Write a tool that translates the C code to go.
  - DRAGONERO 13y ago
    In C or in Go?
    - noselasd 13y ago
      Presumably in go, though that's not explicitly stated.
    - lbarrow 13y ago
      In Go.
    - mwsherman 13y ago
      It’s interesting that it’s not mentioned. I might suspect it’ll be C, as otherwise they’d need to build a new C parser in Go to even get started. Why not use a mature one, and add the Go transformation? Edit: to be more precise, they’d need to get the C syntax tree in some representation first. Then pass it over to a transformer. The latter could be in Go, but it seems foolhardy to reinvent the former.
      - hrjet 13y ago
        By the time I reached this post, the number of translation tiers managed to confuse me. To help others, here's a breakdown. Notation: T[A,B] : Translates from A to B The OP wants to develop T[C, Go]. The question is which language should T[C,Go] be written in? Option #1: If T[C,Go] is written in C, then it can use an existing C parsing library to parse C and then emit Go. Here parsing will be easier, but emitting Go will be laborious to write in C (since C is very low level). Option #2: If T[C,Go] is written in Go, then the parent claims that C parsing will have to be freshly developed in Go. This will be a pain but the Go emitting code will be easier to write in Go. However, I think the problem with option #2 (parsing) can be avoided if one uses the parsing library that is assumed to be already available in C. Since Go can interface with C code[1], the parser need not be reinvented. [1] : http://golang.org/cmd/cgo/ http://golang.org/cmd/cgo/
        amboar 13y ago
        Clearly the sane route would be write T in C then once complete run T through T to emit a C to go translator in go.
        lucian1900 13y ago
        Even if written in C, generating source code is trivial compared to parsing. The translator doesn't have to output the prettiest code either, since there's gofmt/fix.
      - rsc 13y ago
        The parser is the only part I've written so far. It took me an evening (Go has yacc).
    - U2EF1 13y ago
      In C, then translate that to Go of course ;)
    - angersock 13y ago
      Perl.
  - deleted 13y ago
    [deleted]
Locke1689 13y ago
This seems like definitely the right decision. If the C# compiler had been written in C# from nearly the beginning I think it would have heavily influenced language and infrastructure development going forward. It's much better to be in the position now, when the language is barely used, than to have to support it later.
- jmcqk6 13y ago
  The mono C# compiler has been written in C# from the start, and this proved to be very helpful. I remember at the conference where Anders Hejlsberg first discussed Roslyn (which encompasses rewriting the microsoft C# compiler in C#), Miguel de Icaza was able to show some of the same ideas he was discussing actually already running on Mono. I don't think Miguel even knew ahead of time; it was just something the mono people had done.
  - pjmlp 13y ago
    I remember Anders saying that they just started with C++, because of the existing toolchain. If it was today they would have done otherwise, based on current experience. Well, at least Rosylin is going to be available in an upcoming .NET version.
conroy 13y ago
Anyone have a non-Google Docs link? It isn't loading on my end.
- asperous 13y ago
  http://pastebin.com/raw.php?i=fv9swGBf http://pastebin.com/raw.php?i=fv9swGBf
  - conroy 13y ago
    Thanks!
- deleted 13y ago
  [deleted]
puppetmaster3 13y ago
This is the best argument to go D. The D compiler is waaaaay better, written by a compiler expert.
melling 13y ago
"The Go compilers are also significantly larger than anything we’ve converted: over 60,000 lines of C." Couldn't the compiler translation just be crowd sourced by a small group of people? It wouldn't be the best result but if people just stuck to the original C design, it would work as a first implementation.
- aray 13y ago
  Not continuously. The compiler will continue to be improved, and with a working translator developers never need to worry about the bootstrapping problem while developing the Go compiler in Go.
- thinkpad20 13y ago
  I'm inclined to agree. It seems that it would be tough to be confident in the correctness of the generated code, let alone the performance. In the end, getting a team on it would seem to be the most likely to produce correct, readable, idiomatic code. But what do I know.
- qznc 13y ago
  The D community chose the same route. Currently [0] it seems to work in Win32 already. Meanwhile, development on the C++ implementation continued. This is probably the biggest advantage, as the porting does not slow down language evolution. [0] http://forum.dlang.org/post/l8uccc$1qkr$1@digitalmars.com http://forum.dlang.org/post/l8uccc$1qkr$1@digitalmars.com
gress 13y ago
The mention of porting the rest of the plan 9 system to Go is the most interesting part of this document. Is this just academic, or does Google actually want a complete new system (kernel and all) implemented in Go?
- nteon 13y ago
  they're not talking about the plan 9 OS. Go ships with forked copy of several plan9 libs (lib9, libbio, libmach) & the plan9 c compiler. The plan is to obsolete the use of all of that code.
- zerohp 13y ago
  In this context, Russ is referencing the plan 9 libraries and compiler that is currently part of the Go source distribution.
dysoco 13y ago
Is translating seriously the best option? Are the translators accurate enough?
- enneff 13y ago
  The translator written for this specific task will be accurate enough to perform the task. The compiler already has a ton of test cases, and we will likely add more in the process.
fidotron 13y ago
While I agree with the end goal here, isn't 60k lines of C actually a rather small program to attempt to port in a one shot effort? There will also be an inevitable clean up phase since the Go generated is less than likely to be idiomatic. For me the really fun bit is getting to having the whole runtime in Go, which would be a situation not dissimilar from classic Smalltalk environments - especially writing the GC in the target language.
- seanmcdirmid 13y ago
  > which would be a situation not dissimilar from classic Smalltalk environments - especially writing the GC in the target language. Like the Jikes RVM? IBM Research did some really cool stuff. Anyways, anything is possible when you go meta.
  - pjmlp 13y ago
    I am looking forward to see Hotspot replaced by Graal, post Java 8. Lets see if it really happens.
- dsymonds 13y ago
  60k of very subtle, complex, intertwined C code is actually quite a lot. Porting the runtime to Go is also on the drawing board, but later. Right now the compiler complexity makes it harder to work on, hence porting it first is going to pay off quicker.
- tolmasky 13y ago
  Not saying this is all that matters, but if you have a verifiable c->go translator (that is to say, a well understood and tested translator known ("proven") to give you an output program that behaves identically to the input program), then you may be able to skip (or more likely alleviate) the awkward phase of bug introduction when translating a program. I think a problem like this is one of the cases where its easier to reason about in the abstract ("Clearly all arrays should be converted in this fashion"), vs the concrete ("in this part of the code we should do this with the array"), and also avoids the inevitable temptation of "fixing" or "cleaning things up" during the translation. Also of course there is a huge incentive for a good c->go translator to exist for the go community.
jhawk28 13y ago
This is really exciting. I can't wait to port some legacy C code using it. It should make it a lot easier than doing it by hand.
Cort3z 13y ago
Why not start from scratch in go? C and go are different programming languages with different standards etc. Why rely on shoehorning the C version into go?
- shurcooL 13y ago
  Yes, this is indeed one of the questions that the article addresses in the "Alternatives" section.
  - largote 13y ago
    That is not an article, it's a design document.
- heydenberk 13y ago
  From the document itself: "Despite Go’s simplicity, there are many subtle cases in the optimizations and other rewrites performed by the compilers, and it would be foolish to throw away the 10 or so man-years of effort that have gone into them."
  - twic 13y ago
    This strikes me as dubious. Rewriting from scratch would throw away the C code, but it would not have to throw away the lessons learned from and recorded in the C code.
- jesstaa 13y ago
  There is a large communication overhead to this. You have to start a new project, which could take months to develop. In the meantime you still need to maintain the current compilers, fix bugs and make improvements but all that effort becomes wasted. People stop working on the old code base because your new code base is more fun so it suffers and eventually you end up with a not-yet working new project and a broken buggy old project. With a translator work doesn't have to stop on the current compiler code base while the new version is developed, all that effort is saved and bugs are automatically fixed in both places so you don't have to maintain and synchronise two bug trackers.
heydenberk 13y ago
Besides the immediate appeal of bootstrapped compilers, we're also going to have a tool to turn C code into Go code when this is done. I imagine this might breathe some new life into some stagnant projects.
- cpeterso 13y ago
  The C-to-Go transmogrifier (my phone's autocorrection of "translator" :) well be an interesting artifact, but what other C programs are good candidates for Go? Does a Python-to-Go translator exist? Now that could be a very interesting tipping point for Go.
  - pcwalton 13y ago
    The fact that Python is dynamically typed would hurt. I suspect you'd end up with a lot of `interface{}` everywhere.
  - ghshephard 13y ago
    Well, given that there is a Python-to-C translator (As long as your Python code is of the Cython variant).....
- dsymonds 13y ago
  It might be useful, but I suspect it will still be a lot of work to expand the translator to be generally applicable. It's a fair amount of work just to get such a translator to operate on a specific code base.
aabalkan 13y ago
This explains why there is "goto" keyword in Go spec. Nobody uses it, except state machines and reducers for compilers. They probably thought they'll rewrite compiler in Go and didn't drop that keyword?
- srl 13y ago
  I've used it. It's uncommon, but occasionally useful.
- tptacek 13y ago
  Am I misunderstanding this comment? Golang has a "goto" like many other languages. There's a goto in my source tree (in a lexer, to handle the newline terminating a line comment); there are also plenty of gotos in the go standard library. "goto" can be useful.
- rsc 13y ago
  That's not why goto is there. Goto is there because sometimes you want to go somewhere and goto is the best way to get there.
  - RBerenguel 13y ago
    I wonder why this is not a more wideread notion. Goto is useful, in all languages where it is defined. Can be misused? Sure, just like you can write switches with ifs or use while in all loops (talking of C here, not Go... I'm kind of glad I only write for or ranges now.) It's just that goto has bad fame, and ifs and whiles don't
    - enneff 13y ago
      It's because "goto considered harmful" is a catchy meme, and also many older programmers have had understandably bad experiences with code that abuses goto.
      - beagle3 13y ago
        I suspect the percentage of programmers who actually had bad experience with goto is now vanishingly small. I'm not downplaying the harm that goto can cause - but to have experienced it, you have had to experience old basic, fortran 77 or COBOL before learning C or Java. That probably describes 0.1% of people doing programming. Maybe less. The averse reaction to goto is conditioned response, not learned experience.
cpeterso 13y ago
For comparison, the original Rust compiler was written in OCaml. AIUI, the Rust compiler build now has three stages: a blessed binary snapshot of Rust+LLVM (stage0) compiles and tests a new build (stage1) from source, then (as a bootstrap sanity check) the stage1 compiles and tests a new build (stage2) from the same sources. Needless to say, this is a time-consuming process. :)
- jzelinskie 13y ago
  Is there a place where I can read the source of the OCaml Rust compiler?
  - pcwalton 13y ago
    It's in the boot/ directory here if you go back far enough in time: https://github.com/mozilla/rust https://github.com/mozilla/rust Sadly the GitHub Web UI seems to cap viewable history at 100 pages' worth of commits.
  - dbaupp 13y ago
    All 38k lines were deleted in https://github.com/mozilla/rust/commit/6997adf76342b7a6fe03c4bc370ce5fc5082a869 https://github.com/mozilla/rust/commit/6997adf76342b7a6fe03c... , so the most recent revision is https://github.com/mozilla/rust/tree/ef75860a0a72f79f97216f8aaa5b388d98da6480/src/boot https://github.com/mozilla/rust/tree/ef75860a0a72f79f97216f8... (The "Rust" that the OCaml compiler handled is very very different to modern Rust, fwiw.)
- acqq 13y ago
  Does it mean that you have to change ocaml sources to change the language? Why don't you develop Rust in Rust? That would be the real eat your own dogfood?
  - dbaupp 13y ago
    It is now purely in Rust (with a few thousand lines of C, mostly external libraries or tiny wrappers to interact with the OS, where the API is defined in terms of C macros) + the LLVM optimiser. The OCaml compiler was just written to get an implementation of the language that was good enough in which to write a compiler. The OCaml source was deleted more than 2.5 years ago and Rust has been properly bootstrapping/dogfooding for that long.
blt 13y ago
> There are many corners of C that have no direct translation into Go; macros, unions, and bit fields are probably highest on the list. Fortunately (but not coincidentally), those features are rarely used, if at all, in the code being translated. Sounds like they had this idea in the back of their minds from the beginning, and wrote the C code accordingly.
- deleted 13y ago
  [deleted]
- thinkpad20 13y ago
  A compiler with no unions is surprising. At least for parsing, I've found unions to be almost indispensable.
  - pjmlp 13y ago
    Really?! Last time I used unions was probably in MS-DOS.
- deleted 13y ago
  [deleted]
- rsc 13y ago
  That's an interesting causality. It implies that in 1990 when Ken started writing the compiler he knew it was going to be converted to Go. I doubt it. The more likely explanation is that the same people wrote the compiler in C and designed Go. The subset of C they found most useful is the one they used in the compiler and the same one whose semantics ended up in Go.
  - EdiX 13y ago
    Plan 9's userspace was originally written mostly in Alef, a predecessor of Go, then translated to C. I wonder if the original version of the C toolchain was in Alef, too. Unfortunately I don't think there is a easy way to check.
    - 13y ago
jmspring 13y ago
Interesting development, but to be a bit crusty, statements like: "It is easier to write correct Go code than to write correct C code." and "It is easier to debug incorrect Go code than to debug incorrect C code." and "Go is much more fun to use than C." Really are very subjective and don't add much beyond setting a POV for reading the article.
- tptacek 13y ago
  I've been a C programmer since '93-94, and it is my absolute favorite language, and I'm not sure how anyone could suggest that any of those 3 statements are false. Large-scale correct C code is very difficult to build and debug. Subjective or not, since the whole project is about eliminating C from the codebase, they seem very relevant as well.
  - shadowmint 13y ago
    You mean the first 2 I take it. It's pretty obvious fun-level is blatantly subjective.
    - xkarga00 13y ago
      I have a good knowledge of C off last years and recently started programming in Go. I find the later to be much more fun doing.
  - jmspring 13y ago
    In the last three years, for the day job, I've written code in C, C++, Objective C, Java, NodeJS, and C#. A recent project that was back to C was really a breath of fresh air. Simple syntax, sure you have to pay attention to memory, but you have full control and need to pay attention, at the same time very little is hidden from you. Personal projects, I prefer Python but dabble in other things as needed. I evaluate the task and the language options. If I needed to prototype out a web service where the server was up to my control, I'd likely shy away from C/C++. In cases where I was writing a module, it would depend on the architecture/framework. Anything low-level or system related, C is my goto well above C++. Stakeholders, external components, and team factor in. I do love how simple and straight forward C is. Calling it hard to debug or write code correctly for is wholly based on the person making such statements.
charlieflowers 13y ago
(Update: TLDR --> Modifying the Dick Sites quote from the original article: "I would rather write programs to help me refactor/transform programs than refactor/transform programs." So, a programming language highly amenable to that would be very powerful). I just had an insight while reading this. It's a powerful insight. (I am surely not the first person to have this insight, but it's WAY ahead of being mainstream). A programming language that could be PROGRAMMATICALLY REFACTORED would be a HUGE home run. I know Lispers will jump in here. But I know Lisp (somewhat), and it does not have what I'm talking about. (Hell, maybe Go does ... if so, I finally get what the fuss is about). The idea is that you could develop a huge codebase in this language, and then you could write code (probably in some other language) that REFACTORS the original codebase. Of course, you CAN write translators, as the original article mentions. But I want a whole new programming language that is designed from the GROUND UP to be amenable to programmatic transformation. NOT just Lisp with its AST's and macros. The "transformation language" should be able to understand the following aspects of the original code: its modularity, its test coverage, which parts are functionally pure/impure, which parts are parallel/not, and the full compiler-level semantics of every piece of text in the code (in other words, what JetBrains knows ... this is a local variable name, this is a function name, etc.) In other words, the original language has to capture more of the programmers intent (probably by inferring most of it). The intent-information is mostly or completely unneeded at runtime, but it is VITAL at automated translation time. Imagine having such a codebase, and being able to pull up a REPL and interactively start changing the modularity of the code by issuing commands. Or telling the transformation system to parallelize some portion of code that wasn't parallelized previously. Or saying something like, "Take all the code snippets that instantiate the xyz data structure, and change them to call this function instead." Don't miss my point -- we have features like this here and there. Some IDE's more than others, some languages more than others. Nothing new there. But I'm talking about a new programming language designed from the ground up to be highly amenable to this kind of interactive, automated transformation. In other words, I think this might be the killer feature that allows one programming language to outcompete most others. This might be the one programming language feature that we should focus on now, more than any other.
- charlieflowers 13y ago
  Alright, looks like I may be downvoted to oblivion. I still believe I'm on to something. Would any downvoters care to take a minute to share what you think I'm missing? Seems like the polite thing to do. I know you're busy, so make it short and sweet if you have to, but if I'm wrong/naive/ignorant, please, help me out.
bluesnowmonkey 13y ago
I don't really get the motivation behind this effort. I'm not very familiar with the Go compiler, but it seems like make-work. > It is easier to write correct Go code than to write correct C code. But the correct C code is already written. > It is easier to debug incorrect Go code than to debug incorrect C code. Is the C code incorrect? How much debugging is left to be done? > Work on a Go compiler necessarily requires a good understanding of Go. Implementing the compiler in C adds an unnecessary second requirement. The compiler is already implemented in C. > Go makes parallel execution trivial compared to C. Is it not trivial to run multiple C compilers in different processes?
- mcpherrinm 13y ago
  The compiler certainly has bugs. It has features yet to be added. It could be faster, use less memory, and be friendlier. Your arguments would hold a little weight maybe if there were no plans to continue Go development, but I doubt that is the case.
- pcwalton 13y ago
  > Is it not trivial to run multiple C compilers in different processes? I think the design doc is talking about using shared-memory concurrency to do parallel codegen on a per-function basis (like some LLVM patches are experimenting with doing). In this regard it's easier to set up the infrastructure needed to farm out concurrent tasks in Go, because C has neither built-in channels nor the generics to conveniently build them.
- enneff 13y ago
  The compiler is still in a relatively early stage of its development. At this point we feel we can make faster progress and attract more contributors if it is written in Go. (Go programmers like to write Go code, who'd have thought? :-)
  - thomasahle 13y ago
    Good point about attracting developers. I guess Ken and Rob will eventually want to seek other challenges and leave Go to the youngsters and free software community.
twotwotwo 13y ago
Fascinating and fun. I really hope perf doesn't regress much from this: the zippy edit-compile-run loop is part of why Go's fun to use.
- enneff 13y ago
  On the contrary, these changes will allow us to more easily parallelise parts of the compiler which should yield compilation time improvements.
Scaevolus 13y ago
I'm most excited about Phase 4b. The Go compiler currently leaves a lot of performance on the table with its weak optimization capabilities. Having an intermediate representation and a few optimization passes will recover the majority of that performance.
xiaq 13y ago
Alas, that means "Plan 9" bits in go is going to vanish. Luckily some of Plan 9's legacies (saner stdio, simpler socket interface, channels) are embodied in go itself and hopefully getting into mainstream. 9P was not so lucky (it's more of an OS thing than a language thing), but I wish it could take off somewhere.
pjmlp 13y ago
This are great news. I always defend bootstrapping is the proper way to write compilers for general purpose languages. Looking forward to the day Go's runtime is free from C code.
- dubcanada 13y ago
  Go will never be "free from C code" it will always use C code as the bootstrapping compiler will be C. All their doing is making the new compiler in Go and using the old C one to compile the new Go one. And I'm not sure Go qualifies as a "general purpose language".
  - pjmlp 13y ago
    I guess you haven't read the document properly. They plan to keep around the C based compiler for the time being until the whole process is finished. Afterwards there is the option to have a backed that generates C code as target, although other approaches can be taken as well. They just need to replace that backend by other one that cross compiles. C is nothing special, I already wrote a few compilers without a single line of C.
  - enneff 13y ago
    > And I'm not sure Go qualifies as a "general purpose language". I feel somewhat foolish for asking, but how do you define a "general purpose language"? I've seen Go used for building internet servers, command-line tools, games, scientific computing, mass data processing, and more. Sure, there are some things Go is not well-suited to, but I think it does enough (and well) to qualify as "general purpose".
laureny 13y ago
> But I want a whole new programming language that is designed from the GROUND UP to be amenable to programmatic transformation. Pretty much any modern statically typed language can easily be refactored. The problem is not the refactoring, it's deciding when to refactor and to what (e.g. renaming). This is much more of a human than a computer problem, and as such, it will probably be intractable for a very long time.
- lmm 13y ago
  I wonder. We have automated tools that can notice when a method is too complicated, or when two types are frequently used next to each other. There's a cool program that converts Haskell expressions to pointfree style. Would it be too hard to have a system that could suggest when several parameters should be grouped into a container object, or when a common piece of logic can be factored out of several methods? I think it's worth looking at.
  - mseepgood 13y ago
    And it can come up with good method names?
laureny 13y ago
> But I want a whole new programming language that is designed from the GROUND UP to be amenable to programmatic transformation. Pretty much any modern statically typed language can easily be refactored. The problem is not the refactoring, it's deciding when to refactor and to what (e.g. renaming). This is much more of a human than a computer problem, and as such, it will probably be intractable for a very long time.
laureny 13y ago
Go is already extremely fast to compile, I'm puzzled that they choose to improve this aspect of the compiler, which nobody really complains about, while ignoring elephants in the room such as generics and a proper exception mechanism. It's almost as if they choose to tackle the easy problems instead of the hard ones.
- pjmlp 13y ago
  I used to have long discussions here about generics and other stuff with uriel. However, I fully support this decision. Bootstrapping is the best way to develop a language, as it allows the language designers to experience the language in first hand, while making it independent of other tooling. Plus it is one argument less for C zealots against Go, in the sense of "my compiler compiles yours".
- redbad 13y ago
  I'm not sure why you classify "a proper exception mechanism" as an "elephant in the room". Go will never have exceptions for control flow, and it's one of the best properties of the language.
- enneff 13y ago
  The language is not seeing significant development since Go 1 (deliberately). The libraries and tools are now the focus. Generics might happen in Go 1 at some point. Exceptions will never happen. Explicit error handling was a design choice.
- samnardoni 13y ago
  If they wanted every language feature, they'd use C++
RamiK 13y ago
How would this affect the Plan9 and Dragonfly ports?
swah 13y ago
A related article from a few weeks ago: http://tratt.net/laurie/blog/entries/the_bootstrapped_compiler_and_the_damage_done http://tratt.net/laurie/blog/entries/the_bootstrapped_compil...
swah 13y ago
So, can Go channels be implemented using channels?
seunosewa 13y ago
I don't think the tool to automagically convert C code to Go will work. At the very least it will take much longer than expected to get it right. And when it's finally ready, he resulting Go code will be very slow, so they won't be able to use it without serious manual modification. Meanwhile, the C compiler will continue to add new features, and each one will have to be converted to Go and then refactored for performance. It won't work.
- RamiK 13y ago
  There's nothing magical about a compiler. If the Go team decides to build a C compiler using Go that targets Go instead of machine code, they will. Worse case scenario the resulting code will be a GOTO littered state-machine with 'import "unsafe"' on every source file. Though I like to think the Go team would fare better then that.
- howeman 13y ago
  They aren't writing a general tool from C to Go. They are writing a specific tool to convert the compiler from C to Go. They will then make major modifications, but it's much easier to do that from working Go code than from scratch.
tehwalrus 13y ago
Very interesting. The cat-and-mouse problem mentioned a couple of times - finding a solution that allows development on the old to continue while still working on the new - is very similar to a problem I had in a previous job. We had an Actionscript 2 application that was under constant development and use on the web, and we needed/wanted to port it to Actionscript 3 to make use of new language features. I would write a tool that would attempt to translate between the two automatically, and then any more complex transformations could be hand coded and/or added to the translation engine. Of course, the project did not succeed during my time at the company, mostly because the scope of the translator was so limited; there were too many concepts in AS2 (the borrowed javascript setInterval, for example) that had no equivalent line-for-line in AS3 (where you had to use the new Timer class to delay/loop execution) and therefore couldn't be simply substituted. Perhaps if the parser had tried to represent higher order concepts than files and lines of code (e.g. classes, instance data, methods) the project would have got further - but we simply didn't have the resource to spend on it, nor the ability to freeze features on the AS2 codebase. As it was, the AS3 version of the app never quite reached feature parity with the AS2 version, which raced ahead too quickly for the new features to be added by hand in AS3 (and too many changes had already been made by hand to make re-running the parser viable.) If Go is indeed simple enough to translate into from (a specific subset of) C, and if Google can afford more than one engineer for a week to write the tool, then this sounds like it's off to a better start than my project was.
abjorn 13y ago
Now if only they'd do something about that garbage collector.

210 points by geetarista 13y ago

frou_dh 13y ago

Noice. Business case aside, that sounds like a fun exercise for those with the chops to tackle it.

noselasd 13y ago
Step 1. Write a tool that translates the C code to go.
- DRAGONERO 13y ago
  In C or in Go?
  - noselasd 13y ago
    Presumably in go, though that's not explicitly stated.
  - lbarrow 13y ago
    In Go.
  - mwsherman 13y ago
    It’s interesting that it’s not mentioned. I might suspect it’ll be C, as otherwise they’d need to build a new C parser in Go to even get started. Why not use a mature one, and add the Go transformation? Edit: to be more precise, they’d need to get the C syntax tree in some representation first. Then pass it over to a transformer. The latter could be in Go, but it seems foolhardy to reinvent the former.
    - hrjet 13y ago
      By the time I reached this post, the number of translation tiers managed to confuse me. To help others, here's a breakdown. Notation: T[A,B] : Translates from A to B The OP wants to develop T[C, Go]. The question is which language should T[C,Go] be written in? Option #1: If T[C,Go] is written in C, then it can use an existing C parsing library to parse C and then emit Go. Here parsing will be easier, but emitting Go will be laborious to write in C (since C is very low level). Option #2: If T[C,Go] is written in Go, then the parent claims that C parsing will have to be freshly developed in Go. This will be a pain but the Go emitting code will be easier to write in Go. However, I think the problem with option #2 (parsing) can be avoided if one uses the parsing library that is assumed to be already available in C. Since Go can interface with C code[1], the parser need not be reinvented. [1] : http://golang.org/cmd/cgo/ http://golang.org/cmd/cgo/
      - amboar 13y ago
        Clearly the sane route would be write T in C then once complete run T through T to emit a C to go translator in go.
      - lucian1900 13y ago
        Even if written in C, generating source code is trivial compared to parsing. The translator doesn't have to output the prettiest code either, since there's gofmt/fix.
    - rsc 13y ago
      The parser is the only part I've written so far. It took me an evening (Go has yacc).
  - U2EF1 13y ago
    In C, then translate that to Go of course ;)
  - angersock 13y ago
    Perl.
- deleted 13y ago
  [deleted]

Locke1689 13y ago

This seems like definitely the right decision. If the C# compiler had been written in C# from nearly the beginning I think it would have heavily influenced language and infrastructure development going forward. It's much better to be in the position now, when the language is barely used, than to have to support it later.

jmcqk6 13y ago
The mono C# compiler has been written in C# from the start, and this proved to be very helpful. I remember at the conference where Anders Hejlsberg first discussed Roslyn (which encompasses rewriting the microsoft C# compiler in C#), Miguel de Icaza was able to show some of the same ideas he was discussing actually already running on Mono. I don't think Miguel even knew ahead of time; it was just something the mono people had done.
- pjmlp 13y ago
  I remember Anders saying that they just started with C++, because of the existing toolchain. If it was today they would have done otherwise, based on current experience. Well, at least Rosylin is going to be available in an upcoming .NET version.

conroy 13y ago

Anyone have a non-Google Docs link? It isn't loading on my end.

asperous 13y ago
http://pastebin.com/raw.php?i=fv9swGBf http://pastebin.com/raw.php?i=fv9swGBf
- conroy 13y ago
  Thanks!
deleted 13y ago
[deleted]

puppetmaster3 13y ago

This is the best argument to go D. The D compiler is waaaaay better, written by a compiler expert.

melling 13y ago

"The Go compilers are also significantly larger than anything we’ve converted: over 60,000 lines of C." Couldn't the compiler translation just be crowd sourced by a small group of people? It wouldn't be the best result but if people just stuck to the original C design, it would work as a first implementation.

aray 13y ago
Not continuously. The compiler will continue to be improved, and with a working translator developers never need to worry about the bootstrapping problem while developing the Go compiler in Go.
thinkpad20 13y ago
I'm inclined to agree. It seems that it would be tough to be confident in the correctness of the generated code, let alone the performance. In the end, getting a team on it would seem to be the most likely to produce correct, readable, idiomatic code. But what do I know.
qznc 13y ago
The D community chose the same route. Currently [0] it seems to work in Win32 already. Meanwhile, development on the C++ implementation continued. This is probably the biggest advantage, as the porting does not slow down language evolution. [0] http://forum.dlang.org/post/l8uccc$1qkr$1@digitalmars.com http://forum.dlang.org/post/l8uccc$1qkr$1@digitalmars.com

gress 13y ago

The mention of porting the rest of the plan 9 system to Go is the most interesting part of this document. Is this just academic, or does Google actually want a complete new system (kernel and all) implemented in Go?

nteon 13y ago
they're not talking about the plan 9 OS. Go ships with forked copy of several plan9 libs (lib9, libbio, libmach) & the plan9 c compiler. The plan is to obsolete the use of all of that code.
zerohp 13y ago
In this context, Russ is referencing the plan 9 libraries and compiler that is currently part of the Go source distribution.

dysoco 13y ago

Is translating seriously the best option? Are the translators accurate enough?

enneff 13y ago
The translator written for this specific task will be accurate enough to perform the task. The compiler already has a ton of test cases, and we will likely add more in the process.

fidotron 13y ago

While I agree with the end goal here, isn't 60k lines of C actually a rather small program to attempt to port in a one shot effort? There will also be an inevitable clean up phase since the Go generated is less than likely to be idiomatic. For me the really fun bit is getting to having the whole runtime in Go, which would be a situation not dissimilar from classic Smalltalk environments - especially writing the GC in the target language.

seanmcdirmid 13y ago
> which would be a situation not dissimilar from classic Smalltalk environments - especially writing the GC in the target language. Like the Jikes RVM? IBM Research did some really cool stuff. Anyways, anything is possible when you go meta.
- pjmlp 13y ago
  I am looking forward to see Hotspot replaced by Graal, post Java 8. Lets see if it really happens.
dsymonds 13y ago
60k of very subtle, complex, intertwined C code is actually quite a lot. Porting the runtime to Go is also on the drawing board, but later. Right now the compiler complexity makes it harder to work on, hence porting it first is going to pay off quicker.
tolmasky 13y ago
Not saying this is all that matters, but if you have a verifiable c->go translator (that is to say, a well understood and tested translator known ("proven") to give you an output program that behaves identically to the input program), then you may be able to skip (or more likely alleviate) the awkward phase of bug introduction when translating a program. I think a problem like this is one of the cases where its easier to reason about in the abstract ("Clearly all arrays should be converted in this fashion"), vs the concrete ("in this part of the code we should do this with the array"), and also avoids the inevitable temptation of "fixing" or "cleaning things up" during the translation. Also of course there is a huge incentive for a good c->go translator to exist for the go community.

jhawk28 13y ago

This is really exciting. I can't wait to port some legacy C code using it. It should make it a lot easier than doing it by hand.

Cort3z 13y ago

Why not start from scratch in go? C and go are different programming languages with different standards etc. Why rely on shoehorning the C version into go?

shurcooL 13y ago
Yes, this is indeed one of the questions that the article addresses in the "Alternatives" section.
- largote 13y ago
  That is not an article, it's a design document.
heydenberk 13y ago
From the document itself: "Despite Go’s simplicity, there are many subtle cases in the optimizations and other rewrites performed by the compilers, and it would be foolish to throw away the 10 or so man-years of effort that have gone into them."
- twic 13y ago
  This strikes me as dubious. Rewriting from scratch would throw away the C code, but it would not have to throw away the lessons learned from and recorded in the C code.
jesstaa 13y ago
There is a large communication overhead to this. You have to start a new project, which could take months to develop. In the meantime you still need to maintain the current compilers, fix bugs and make improvements but all that effort becomes wasted. People stop working on the old code base because your new code base is more fun so it suffers and eventually you end up with a not-yet working new project and a broken buggy old project. With a translator work doesn't have to stop on the current compiler code base while the new version is developed, all that effort is saved and bugs are automatically fixed in both places so you don't have to maintain and synchronise two bug trackers.

heydenberk 13y ago

Besides the immediate appeal of bootstrapped compilers, we're also going to have a tool to turn C code into Go code when this is done. I imagine this might breathe some new life into some stagnant projects.

cpeterso 13y ago
The C-to-Go transmogrifier (my phone's autocorrection of "translator" :) well be an interesting artifact, but what other C programs are good candidates for Go? Does a Python-to-Go translator exist? Now that could be a very interesting tipping point for Go.
- pcwalton 13y ago
  The fact that Python is dynamically typed would hurt. I suspect you'd end up with a lot of `interface{}` everywhere.
- ghshephard 13y ago
  Well, given that there is a Python-to-C translator (As long as your Python code is of the Cython variant).....
dsymonds 13y ago
It might be useful, but I suspect it will still be a lot of work to expand the translator to be generally applicable. It's a fair amount of work just to get such a translator to operate on a specific code base.

aabalkan 13y ago

This explains why there is "goto" keyword in Go spec. Nobody uses it, except state machines and reducers for compilers. They probably thought they'll rewrite compiler in Go and didn't drop that keyword?

srl 13y ago
I've used it. It's uncommon, but occasionally useful.
tptacek 13y ago
Am I misunderstanding this comment? Golang has a "goto" like many other languages. There's a goto in my source tree (in a lexer, to handle the newline terminating a line comment); there are also plenty of gotos in the go standard library. "goto" can be useful.
rsc 13y ago
That's not why goto is there. Goto is there because sometimes you want to go somewhere and goto is the best way to get there.
- RBerenguel 13y ago
  I wonder why this is not a more wideread notion. Goto is useful, in all languages where it is defined. Can be misused? Sure, just like you can write switches with ifs or use while in all loops (talking of C here, not Go... I'm kind of glad I only write for or ranges now.) It's just that goto has bad fame, and ifs and whiles don't
  - enneff 13y ago
    It's because "goto considered harmful" is a catchy meme, and also many older programmers have had understandably bad experiences with code that abuses goto.
    - beagle3 13y ago
      I suspect the percentage of programmers who actually had bad experience with goto is now vanishingly small. I'm not downplaying the harm that goto can cause - but to have experienced it, you have had to experience old basic, fortran 77 or COBOL before learning C or Java. That probably describes 0.1% of people doing programming. Maybe less. The averse reaction to goto is conditioned response, not learned experience.

cpeterso 13y ago

For comparison, the original Rust compiler was written in OCaml. AIUI, the Rust compiler build now has three stages: a blessed binary snapshot of Rust+LLVM (stage0) compiles and tests a new build (stage1) from source, then (as a bootstrap sanity check) the stage1 compiles and tests a new build (stage2) from the same sources. Needless to say, this is a time-consuming process. :)

jzelinskie 13y ago
Is there a place where I can read the source of the OCaml Rust compiler?
- pcwalton 13y ago
  It's in the boot/ directory here if you go back far enough in time: https://github.com/mozilla/rust https://github.com/mozilla/rust Sadly the GitHub Web UI seems to cap viewable history at 100 pages' worth of commits.
- dbaupp 13y ago
  All 38k lines were deleted in https://github.com/mozilla/rust/commit/6997adf76342b7a6fe03c4bc370ce5fc5082a869 https://github.com/mozilla/rust/commit/6997adf76342b7a6fe03c... , so the most recent revision is https://github.com/mozilla/rust/tree/ef75860a0a72f79f97216f8aaa5b388d98da6480/src/boot https://github.com/mozilla/rust/tree/ef75860a0a72f79f97216f8... (The "Rust" that the OCaml compiler handled is very very different to modern Rust, fwiw.)
acqq 13y ago
Does it mean that you have to change ocaml sources to change the language? Why don't you develop Rust in Rust? That would be the real eat your own dogfood?
- dbaupp 13y ago
  It is now purely in Rust (with a few thousand lines of C, mostly external libraries or tiny wrappers to interact with the OS, where the API is defined in terms of C macros) + the LLVM optimiser. The OCaml compiler was just written to get an implementation of the language that was good enough in which to write a compiler. The OCaml source was deleted more than 2.5 years ago and Rust has been properly bootstrapping/dogfooding for that long.

blt 13y ago

> There are many corners of C that have no direct translation into Go; macros, unions, and bit fields are probably highest on the list. Fortunately (but not coincidentally), those features are rarely used, if at all, in the code being translated. Sounds like they had this idea in the back of their minds from the beginning, and wrote the C code accordingly.

deleted 13y ago
[deleted]
thinkpad20 13y ago
A compiler with no unions is surprising. At least for parsing, I've found unions to be almost indispensable.
- pjmlp 13y ago
  Really?! Last time I used unions was probably in MS-DOS.
deleted 13y ago
[deleted]
rsc 13y ago
That's an interesting causality. It implies that in 1990 when Ken started writing the compiler he knew it was going to be converted to Go. I doubt it. The more likely explanation is that the same people wrote the compiler in C and designed Go. The subset of C they found most useful is the one they used in the compiler and the same one whose semantics ended up in Go.
- EdiX 13y ago
  Plan 9's userspace was originally written mostly in Alef, a predecessor of Go, then translated to C. I wonder if the original version of the C toolchain was in Alef, too. Unfortunately I don't think there is a easy way to check.
  - 13y ago

jmspring 13y ago

Interesting development, but to be a bit crusty, statements like: "It is easier to write correct Go code than to write correct C code." and "It is easier to debug incorrect Go code than to debug incorrect C code." and "Go is much more fun to use than C." Really are very subjective and don't add much beyond setting a POV for reading the article.

tptacek 13y ago
I've been a C programmer since '93-94, and it is my absolute favorite language, and I'm not sure how anyone could suggest that any of those 3 statements are false. Large-scale correct C code is very difficult to build and debug. Subjective or not, since the whole project is about eliminating C from the codebase, they seem very relevant as well.
- shadowmint 13y ago
  You mean the first 2 I take it. It's pretty obvious fun-level is blatantly subjective.
  - xkarga00 13y ago
    I have a good knowledge of C off last years and recently started programming in Go. I find the later to be much more fun doing.
- jmspring 13y ago
  In the last three years, for the day job, I've written code in C, C++, Objective C, Java, NodeJS, and C#. A recent project that was back to C was really a breath of fresh air. Simple syntax, sure you have to pay attention to memory, but you have full control and need to pay attention, at the same time very little is hidden from you. Personal projects, I prefer Python but dabble in other things as needed. I evaluate the task and the language options. If I needed to prototype out a web service where the server was up to my control, I'd likely shy away from C/C++. In cases where I was writing a module, it would depend on the architecture/framework. Anything low-level or system related, C is my goto well above C++. Stakeholders, external components, and team factor in. I do love how simple and straight forward C is. Calling it hard to debug or write code correctly for is wholly based on the person making such statements.

charlieflowers 13y ago

(Update: TLDR --> Modifying the Dick Sites quote from the original article: "I would rather write programs to help me refactor/transform programs than refactor/transform programs." So, a programming language highly amenable to that would be very powerful). I just had an insight while reading this. It's a powerful insight. (I am surely not the first person to have this insight, but it's WAY ahead of being mainstream). A programming language that could be PROGRAMMATICALLY REFACTORED would be a HUGE home run. I know Lispers will jump in here. But I know Lisp (somewhat), and it does not have what I'm talking about. (Hell, maybe Go does ... if so, I finally get what the fuss is about). The idea is that you could develop a huge codebase in this language, and then you could write code (probably in some other language) that REFACTORS the original codebase. Of course, you CAN write translators, as the original article mentions. But I want a whole new programming language that is designed from the GROUND UP to be amenable to programmatic transformation. NOT just Lisp with its AST's and macros. The "transformation language" should be able to understand the following aspects of the original code: its modularity, its test coverage, which parts are functionally pure/impure, which parts are parallel/not, and the full compiler-level semantics of every piece of text in the code (in other words, what JetBrains knows ... this is a local variable name, this is a function name, etc.) In other words, the original language has to capture more of the programmers intent (probably by inferring most of it). The intent-information is mostly or completely unneeded at runtime, but it is VITAL at automated translation time. Imagine having such a codebase, and being able to pull up a REPL and interactively start changing the modularity of the code by issuing commands. Or telling the transformation system to parallelize some portion of code that wasn't parallelized previously. Or saying something like, "Take all the code snippets that instantiate the xyz data structure, and change them to call this function instead." Don't miss my point -- we have features like this here and there. Some IDE's more than others, some languages more than others. Nothing new there. But I'm talking about a new programming language designed from the ground up to be highly amenable to this kind of interactive, automated transformation. In other words, I think this might be the killer feature that allows one programming language to outcompete most others. This might be the one programming language feature that we should focus on now, more than any other.

charlieflowers 13y ago
Alright, looks like I may be downvoted to oblivion. I still believe I'm on to something. Would any downvoters care to take a minute to share what you think I'm missing? Seems like the polite thing to do. I know you're busy, so make it short and sweet if you have to, but if I'm wrong/naive/ignorant, please, help me out.

bluesnowmonkey 13y ago

I don't really get the motivation behind this effort. I'm not very familiar with the Go compiler, but it seems like make-work. > It is easier to write correct Go code than to write correct C code. But the correct C code is already written. > It is easier to debug incorrect Go code than to debug incorrect C code. Is the C code incorrect? How much debugging is left to be done? > Work on a Go compiler necessarily requires a good understanding of Go. Implementing the compiler in C adds an unnecessary second requirement. The compiler is already implemented in C. > Go makes parallel execution trivial compared to C. Is it not trivial to run multiple C compilers in different processes?

mcpherrinm 13y ago
The compiler certainly has bugs. It has features yet to be added. It could be faster, use less memory, and be friendlier. Your arguments would hold a little weight maybe if there were no plans to continue Go development, but I doubt that is the case.
pcwalton 13y ago
> Is it not trivial to run multiple C compilers in different processes? I think the design doc is talking about using shared-memory concurrency to do parallel codegen on a per-function basis (like some LLVM patches are experimenting with doing). In this regard it's easier to set up the infrastructure needed to farm out concurrent tasks in Go, because C has neither built-in channels nor the generics to conveniently build them.
enneff 13y ago
The compiler is still in a relatively early stage of its development. At this point we feel we can make faster progress and attract more contributors if it is written in Go. (Go programmers like to write Go code, who'd have thought? :-)
- thomasahle 13y ago
  Good point about attracting developers. I guess Ken and Rob will eventually want to seek other challenges and leave Go to the youngsters and free software community.

twotwotwo 13y ago

Fascinating and fun. I really hope perf doesn't regress much from this: the zippy edit-compile-run loop is part of why Go's fun to use.

enneff 13y ago
On the contrary, these changes will allow us to more easily parallelise parts of the compiler which should yield compilation time improvements.

Scaevolus 13y ago

I'm most excited about Phase 4b. The Go compiler currently leaves a lot of performance on the table with its weak optimization capabilities. Having an intermediate representation and a few optimization passes will recover the majority of that performance.

xiaq 13y ago

Alas, that means "Plan 9" bits in go is going to vanish. Luckily some of Plan 9's legacies (saner stdio, simpler socket interface, channels) are embodied in go itself and hopefully getting into mainstream. 9P was not so lucky (it's more of an OS thing than a language thing), but I wish it could take off somewhere.

pjmlp 13y ago

This are great news. I always defend bootstrapping is the proper way to write compilers for general purpose languages. Looking forward to the day Go's runtime is free from C code.

dubcanada 13y ago
Go will never be "free from C code" it will always use C code as the bootstrapping compiler will be C. All their doing is making the new compiler in Go and using the old C one to compile the new Go one. And I'm not sure Go qualifies as a "general purpose language".
- pjmlp 13y ago
  I guess you haven't read the document properly. They plan to keep around the C based compiler for the time being until the whole process is finished. Afterwards there is the option to have a backed that generates C code as target, although other approaches can be taken as well. They just need to replace that backend by other one that cross compiles. C is nothing special, I already wrote a few compilers without a single line of C.
- enneff 13y ago
  > And I'm not sure Go qualifies as a "general purpose language". I feel somewhat foolish for asking, but how do you define a "general purpose language"? I've seen Go used for building internet servers, command-line tools, games, scientific computing, mass data processing, and more. Sure, there are some things Go is not well-suited to, but I think it does enough (and well) to qualify as "general purpose".

laureny 13y ago

> But I want a whole new programming language that is designed from the GROUND UP to be amenable to programmatic transformation. Pretty much any modern statically typed language can easily be refactored. The problem is not the refactoring, it's deciding when to refactor and to what (e.g. renaming). This is much more of a human than a computer problem, and as such, it will probably be intractable for a very long time.

lmm 13y ago
I wonder. We have automated tools that can notice when a method is too complicated, or when two types are frequently used next to each other. There's a cool program that converts Haskell expressions to pointfree style. Would it be too hard to have a system that could suggest when several parameters should be grouped into a container object, or when a common piece of logic can be factored out of several methods? I think it's worth looking at.
- mseepgood 13y ago
  And it can come up with good method names?

laureny 13y ago

Go is already extremely fast to compile, I'm puzzled that they choose to improve this aspect of the compiler, which nobody really complains about, while ignoring elephants in the room such as generics and a proper exception mechanism. It's almost as if they choose to tackle the easy problems instead of the hard ones.

pjmlp 13y ago
I used to have long discussions here about generics and other stuff with uriel. However, I fully support this decision. Bootstrapping is the best way to develop a language, as it allows the language designers to experience the language in first hand, while making it independent of other tooling. Plus it is one argument less for C zealots against Go, in the sense of "my compiler compiles yours".
redbad 13y ago
I'm not sure why you classify "a proper exception mechanism" as an "elephant in the room". Go will never have exceptions for control flow, and it's one of the best properties of the language.
enneff 13y ago
The language is not seeing significant development since Go 1 (deliberately). The libraries and tools are now the focus. Generics might happen in Go 1 at some point. Exceptions will never happen. Explicit error handling was a design choice.
samnardoni 13y ago
If they wanted every language feature, they'd use C++

RamiK 13y ago

How would this affect the Plan9 and Dragonfly ports?

swah 13y ago

A related article from a few weeks ago: http://tratt.net/laurie/blog/entries/the_bootstrapped_compiler_and_the_damage_done http://tratt.net/laurie/blog/entries/the_bootstrapped_compil...

swah 13y ago

So, can Go channels be implemented using channels?

seunosewa 13y ago

I don't think the tool to automagically convert C code to Go will work. At the very least it will take much longer than expected to get it right. And when it's finally ready, he resulting Go code will be very slow, so they won't be able to use it without serious manual modification. Meanwhile, the C compiler will continue to add new features, and each one will have to be converted to Go and then refactored for performance. It won't work.

RamiK 13y ago
There's nothing magical about a compiler. If the Go team decides to build a C compiler using Go that targets Go instead of machine code, they will. Worse case scenario the resulting code will be a GOTO littered state-machine with 'import "unsafe"' on every source file. Though I like to think the Go team would fare better then that.
howeman 13y ago
They aren't writing a general tool from C to Go. They are writing a specific tool to convert the compiler from C to Go. They will then make major modifications, but it's much easier to do that from working Go code than from scratch.

tehwalrus 13y ago

Very interesting. The cat-and-mouse problem mentioned a couple of times - finding a solution that allows development on the old to continue while still working on the new - is very similar to a problem I had in a previous job. We had an Actionscript 2 application that was under constant development and use on the web, and we needed/wanted to port it to Actionscript 3 to make use of new language features. I would write a tool that would attempt to translate between the two automatically, and then any more complex transformations could be hand coded and/or added to the translation engine. Of course, the project did not succeed during my time at the company, mostly because the scope of the translator was so limited; there were too many concepts in AS2 (the borrowed javascript setInterval, for example) that had no equivalent line-for-line in AS3 (where you had to use the new Timer class to delay/loop execution) and therefore couldn't be simply substituted. Perhaps if the parser had tried to represent higher order concepts than files and lines of code (e.g. classes, instance data, methods) the project would have got further - but we simply didn't have the resource to spend on it, nor the ability to freeze features on the AS2 codebase. As it was, the AS3 version of the app never quite reached feature parity with the AS2 version, which raced ahead too quickly for the new features to be added by hand in AS3 (and too many changes had already been made by hand to make re-running the parser viable.) If Go is indeed simple enough to translate into from (a specific subset of) C, and if Google can afford more than one engineer for a week to write the tool, then this sounds like it's off to a better start than my project was.

abjorn 13y ago

Now if only they'd do something about that garbage collector.