Compiler Part 2: Compiling, Transpiling and Interpreting

Part 1 served as an introduction to this series.

In this second post, I want to do an overview of some definitions before we dive in to the actual steps of compiling.

Compiling

Compiling is the act of taking code written in one language and translating it into a lower level language. A C compiler doesn't usually output machine code directly. Instead, it translates the C source code into assembly. The assembler takes that output and compiles it into machine code. C# and Java are translated into bytecode. Bytecode isn't transformed into machine code until it is executed by the virtual machine.

It’s important to understand this distinction.

Compiling often consists of using an intermediate representation (IR) or intermediate language. Assembly is a common intermediate language. LLVM has an IR imaginatively called LLVM IR. C can also act as an intermediate language.

Transpiling

Transpiling, by contrast, is transforming code from one language to another language of equal or higher level. Translating Go to Javascript is an example of this.

Do not confuse this with what languages like Scala or Clojure do. Both of these languages are compiled directly to Java bytecode and use the JVM to execute their code. Neither are considered to be transpiled because Java bytecode is a lower level of abstraction. Were they translated into Java first prior to being compile to bytecode then they might be considered transpiled languages.

Translating Go or Lisp to C isn't really transpiling either, though it rides a fine line. C is a lower level language although it is certainly a higher level language than assembly.

Interpreting

Interpreters are usually associated with scripting. Rather than translating a language into another language or IR the language is, typically, interpreted directly.

In some cases this means, quite literally, scanning the code and interpreting it on the fly and halting the moment something isn't right. In other cases, it means scanning through the entire code, validating it and then executing it from the internal tree data structure holding all the information.

In a sense, an interpreter of this kind must “compile” the script or source code each time it is run, making it much slower. This is because it needs to do all the steps a compiler does each time the script is executed rather than doing that process only once.

Many modern interpreters don’t typically do this, however. You may want to investigate Just In Time (JIT) compiling if you’re interested in the details. The short and simple version is that the script is interpreted only once, just like a compiler, and is stored in some kind of intermediate form so it can be loaded faster. This process also allows the designers to incorporate optimizations to further speed up code.

Binaries, Compiling

The objective of compilers is often to create an executable binary, or at least some kind of object  the machine can read and execute.

It’s not so simple to just create machine code. Compiling is actually just the first step.

Here are the basic steps that GCC and Go might use to compile their source code:

C using GCC:

1. Translate C into assembly via GNU C Compiler (gcc);
2. Translate assembly into machine code via GNU Assembler (gas);
3. Link machine code with standard library and produce an architecture specific binary via the GNU Linker (ld).

Go using Go Compiler on x86-32:

1. Translate Go into assembly via Go compiler (8g);
2. Translate assembly into machine code via Plan 9 Assembler (8a);
3. Link machine code with standard library and produce an architecture specific binary via the Plan 9 Linker (8l).

As you can see, the compiler is just one step of the process. In these articles we’ll only be dealing with step 1. Assembling and linking are well beyond the purpose of these articles.

Don’t fret though! Our compiler will produce an executable binary!

Next

Now that we've taken care of some definitions and understand the process to making executable code we can look at a compiler in a little more detail in Part 3.

Compiler Part 1: Introduction to Writing a Compiler in Pure Go

Introduction

I've long been interested in learning how a compiler works. Cryptic compiler messages and odd behaviours have always baffled me. I’ve never quite understood how optimizations are done or how it is a compiler knows what I've done wrong.

When I first decided it was time to learn how to write a compiler I found out that there are a lot of terms and acronyms not often used outside of the discipline. What was an SLR or LALR parser? What in the heck is a lexeme or finite automata? What is recursive-descent parsing? What is an AST?

It can be pretty overwhelming at first.

The largest hurdle I found was that most online courses, tutorials and other learning materials on the Internet don’t teach you how to write a compiler or interpreter. Correction; they don’t teach you how to build one from scratch but provide you an overarching, top-down approach, relying on existing tools to help you do the job. This is because building a compiler is a pretty big job and it would be nigh impossible to cover everything in a single semester. I can’t fault anyone for that.

That said, I felt these tools skipped over what I think are valuable lessons and information. I wanted more.

So, I want to take you on a tour of my personal journey through learning how to write a compiler.

Bare in mind, I’m not a professional programmer nor am I finished figuring everything out. That said, I've discovered so many wonderful things that I can’t help but want to share them in the hopes they’ll help you discover your own path. After all, it’s why you’re here, isn't it?

Credit Where Credit is Due

Calc is an original work and while all the code for this project has been hand written there can be no denying parallels and similarities to Go and Go parser package in the standard library. In learning to write a compiler I have often referenced those works when I got stuck. Any and all credit must go to the Go developers for any code that resembles any of their collective works. You can find the source code for the Go compiler at golang.org.

Prerequisites

As much as I’d like it to be, this series is not really intended for novice programmers. It assumes you have some programming experience and are already familiar with the Go programming language. Therefore, it is targeted at more of an intermediate programmer.

While I think a more novice programmer might be able to follow the articles I will make no attempt to explain Go or any code not directly related to compiling. There are several utility functions which I will point out but since they aren't explicitly about compiling I won’t explain them.

Tools

Compiler design is a component, or perhaps companion, to language design. It’s a massive topic and each step of the compiler is a lesson in of itself.

There are a couple tools out there that people use to simplify or expedite the process of building a compiler. Each tool tends to focus on one particular step of the process. I am telling you about these tools so that you know that they exist but they are not relevant to this blog series. There are, however, many articles and classes that will teach you compiler design by using these tools.

Flex and Bison are probably the most common open source options available. Flex is based on a program called Lex, short for Lexical analysis, which is the first step of compiling. Bison is based on a program called YACC, an acronym for Yet Another Compiler Compiler, which does parsing and builds something called an abstract syntax tree.

I don't expect you to understand any of that, so don't worry. I will caution you that trying to use either of those tools without comprehending how a compiler works will be difficult in the extreme. You should prepare for some hurt.

I have actually found it more useful to skip these tools and learn the basics, first. I think building the entire compiler stack by hand provides a better solution in the long term anyway but that’s just my opinion. Take it for what you will.

The problem, for me, is that there ends up being a very serious disconnect and loss of control between each stage of compiling. It also begs the question of: “how does it actually work?”

The Solution

That’s why in this series I’m going to cover each individual component and we’re going to write code from scratch. It might take longer but I think you’ll have a stronger understanding in the end. If, after we’re done, you decide you want to use the aforementioned tools you’ll be able to do so much easier and make a more informed decision.

Stay tuned for Part 2 to start getting our feet wet!

[Edit: Updated the tools section to be more clear in its intent]

A Quick Interlude

I have vowed to be a more prolific writer this year. Indeed, I have been but not that anyone reading this blog would be able to tell!

I am currently in the midst of writing a multi-part series of articles on writing compilers. I can't really say how complete this work is because I'm honestly not sure how long it will take. I have gone back and refined what I've done so far and would say I have the first four posts in good shape. Those four posts barely crack the surface of the drafts being worked on and I have some attending code to write for the articles, too.

Regardless, good progress is being made!

I also have a much shorter series in the works on memory. In them, I talk about stack and heap memory and how they're used in Go. The ultimate purpose is to help new programmers understand how the garbage collector works and how they could possibly improve their own code to maximize efficiency.

There are a few other pieces in the works in varying degrees of completeness. It's likely I'll release one or more of them sooner rather than later since they're much smaller works.

Thanks for reading and all the shares and likes you guys have given over the years!

Changes Coming in Goncurses 0.3

*Updated  for more content*

I've been doing some more work in the month since I tagged 0.2 that, unfortunately, will introduce more breakage. I really hate to continue changing the API in backwards incompatible ways but I feel these changes are pretty necessary.

Before I get into that, though, let me introduce the most exciting change to Goncurses. So, without further adieu!

Windows Support!

 Yes, you read correctly. PDCurses support! Windows users may rejoice! ;)

I had a lot of reservations about adding PDCurses support since there seemed to be some surprisingly major incompatibilities with ncurses. I had attempted to add support almost a year ago but quickly became frustrated and decided to discard my efforts to focus on ncurses support alone. However, due to a personal need, I decided to revisit integrating PDCurses and finally met with success.

By default Goncurses will always use ncurses on Linux and MacOS X but I imagine you could also use PDCurses on those platforms as well with minimal changes. Built-in support for doing so will likely never be introduced into the library.

A New Demo/Game

I also have added a new, fun example program which features a much more complete working example of using Goncurses. It is a side-scrolling shoot-em-up called Starfield where you blast asteroids. Rather than use Go's concurrency model to handle input and drawing separately I instead used Go's time library to simulate "heartbeats" using Tickers for different timings. Updating of the background, user input (ship position) and active sprites all happen at different intervals which I can finely control. In order to achieve this I used a select statement to poll whether a 'tick' or 'heartbeat' has happened and, if not, handle any input. It was pretty fun to whip together but don't expect anything magical!

I am also in the progress of writing a feature demo but it's in a poor state right now and I don't recommend using it, yet.

Breaking Changes

• Changed NapMilliseconds to simply Nap
• Changed NL to NewLines for clarity
• Changed Getyx to CursorYX to make it clear exactly what you were getting; see below for the new YX function
• Changed Maxyx to MaxYX to match YX and CursorYX
•  DelChar was split into DelChar and MoveDelChar to make the interface more idiomatic Go and inline with the rest of the library.
• (Update) Window creation functions like Init, NewWindow, Sub and Duplicate now return pointers. Any functions which take pointers like Sub does you no longer need to take the address of the Window you are passing which may break some code. Thankfully it's a simple, if not annoying, fix.
• (Update) GetMouse now returns a MouseEvent to make it more idiomatic and sane.
• (Update) Mouse has been renamed to MouseOk
• (Update) Form and Menu functions now take the Char type as parameters to match the rest of the library.

Other Changes

• NewPad now returns a pointer and all pad related methods use a pointer receiver. This should not break/change existing code unless you needed to address a pad for some reason.
• Several Window methods had their godoc strings improved.
• The Parent Window method was fixed to work properly. Previously it always returned a Window object whether it was valid or not. Now it correctly returns nil if the window has no parent.
• (Update) Made fixes to almost all examples including: a vastly improved Window example, and the Mouse example much improved and should now work properly on all platforms.

Pending Changes

• Finish the feature demo
• (Update) Change functions/methods that return a Window to return pointers. This will help with several functions which expect to receive a Window pointer and other implementation difficulties when writing Goncurses apps. In most cases old code should not need to be updated but there will be some exceptions to that rule.

Upcoming Changes in Goncurses 0.2

I wrote and maintain an ncurses wrapper library for the Go programming language. Much like this blog, it went through a long dormancy with a few minor spurts of action while I was wrapped up in my regular job and my family. Back in June I finally tagged version 0.1.

Since that time I've implemented a fair number of changes and, as I warned at the time, a couple are somewhat breaking. The library is quite young as far as implementation goes and I want to avoid any API breaking changes if I can but I felt these were necessary.

Here is a list of changes coming up in 0.2:

Breaking Changes

• As I announced in the 0.1 release, the Print statement has now been broken up into separate Print and MovePrint functions to be more ncurses-like and each has been further separated to be more Go-like: Print,  Println, Printf, MovePrint, MovePrintln, and MovePrintf. A regex replacement ought to fix most instances but some manual editing will probably be required.
• The Character type has been changed to the shorter Char type. A simple gofmt or sed regex will easily fix any existing code.
• Several functions now use the Char type like: AttrOn, AttrOff, Box, Border,ColorPair,  etc
• Color related functions now take an int16 rather than an int (32bit) type. This is to mirror the C short type to protect against any type conversion errors.

Non-Breaking Changes

• Implemented the slk soft-keys functions.
• Added screen functions (newterm, set_term, etc).
• Implemented a StdScr function which returns the underlying stdscr window object. This was mainly a requirement to using the screen functions because there was no other way to get the stdscr but it may be useful for other situations.
• Implemented AttrSet, Standend and Standout text attribute functions.
• Implemented Timeout for input on Windows

Version Control for Go

When I first heard of version control, the most popular ones at the time were probably CVS and subversion. It seemed like every open source project used one. I understood their value for collaboration but not as a sole developer so I steered clear of them for a long while. However, they kept coming up and eventually there were some new kids on the block which were vying for attention: Git, Mercurial and Bazaar. Now, this isn't a history lesson of any kind or some kind of detailed comparison of them all. There’s plenty of that already out there. Instead, this is a short explanation of which one I chose to use when programming in Go and why.

I recall reading a book on C programming which had a section on Subversion. I tried it out. I didn't understand it. There were a lot of do’s and don’ts and I found it very intimidating. I understood the value but hated using it. Why did I have to keep track of changes anyway if I wasn't sharing the code? As time went on and I wanted to finally work on my first major project, however, I knew I was going to need a method of tracking my changes even if I didn't share my code. Too many times I'd get part way through working through a feature, realize I didn't like it or it didn't work, and realize it was too late to go back (or would take a lot to revert the changes. This left me little choice but to look at version control, again.

Fast forward a few years and I finally installed a GNU/Linux distribution that really clicked with me: Ubuntu. Long story short, I discovered Ubuntu used a version control system called Bazaar and after reading a few articles telling me how easy it was to use I decided to give it a try. A lot of mistakes later I finally figured out how to use it and I loved it. Bazaar was simple and easy to use. I really liked that the commands were clear in their purpose and the defaults felt natural. I could clone a repository into a new directory with a specific name, make changes (like a hot-fix or new feature), then merge that directory back into the main repo. and the name stuck with it! Forever I would know that a series of commits belonged to a fix or feature with that name. Loved it!

As time went on, I began to discover that Bazaar was the least favoured of the 'big three' distributed version control systems. At first this didn't matter to me but it started to make me wonder if I'd made the right choice. Indeed, Git and Mercurial both had much larger share of the market, as it were. But, Git scared the hell out of me. It had so many commands and features that it still made me feel truly lost, even after using Bazaar for close to a year.

I had just discovered Go and, perhaps naively, I thought that if I were to create a Go library I should use Google Code hosting, just like Go did! The problem being: no support for Bazaar. This was a problem I found everywhere except Launchpad and Sourceforge. No other popular code hosting site supported Bazaar. But, many of them did support Mercurial and guess what? Mercurial was just like Bazaar but, perhaps, even better.

Mercurial welcomed me with open arms! It supported the same workflow and the commands were all almost identical. Now I had a wider choice in code hosting too.

Again, as I stated already, I was discovering Go. And one thing that Go doesn't like is when sub-directories change. Let me give an example. Lets say you’re using Google Code to host your project. Let’s call the project an imaginative name. Let’s call it: foo. So you’d import that library from “code.google.com/p/foo”. Maybe I want to make a fix. What I would typically do is clone my project into a new directory called foo-name-of-fix. Now, let’s say I want to run the test framework to make sure it passes and I didn't mess something up. If I just run ‘go test’ it will import from “code.google.com/p/foo” NOT from the repo. I just created, which would be “code.google.com/p/foo-name-of-fix”. That meant, every time I made a new directory I’d need to change everything. And, make sure you change it all back before merging! A headache to be sure!

Now, this isn't the only way to do it in Mercurial. You can used named branches or tags. There are ways to overcome this problem. But again, these were workarounds and it was like “a splinter in my mind” driving me crazy. I was also aware that the most popular version control was Git.

So, I tried it. And this time I’d accumulated enough experience that I wasn't completely overwhelmed. Yes, Git has a shit-ton of features. But, you don’t need to use them. You don’t even have to know they’re there. You just need to know the basic commands and ask questions (most questions have already been asked on Stack Overflow so a quick search is usually the best thing to do) when you get stuck or if something bothers you. Because in Git, there’s almost always an answer.

I didn't immediately like Git but one thing I really liked was that named, in-directory branches were the natural way to do things. It made working with Go brutally easy. I didn't like that the name is discarded once you merge and delete said branch. I really liked that Git doesn't assume that just because you made a change to a file you want to commit it. This is a feature I didn't like at first but that I've grown to like. You can use a shortcut when committing to get the same behaviour as Mercurial and Bazaar but otherwise it will force you to manually add those files you want to commit. Very nice for cherry picking changes.

There are things I don’t like about Git. Many of it's features are reserved for corner cases and it’s still a bit overwhelming at first even though the Git community has done a tremendous job alleviating that particular problem. There are a million and one ways to do the same thing with their own pros and cons making it sometimes difficult to know which is the right solution for you. I’m not overly fond that branch names aren't attached to a commit series after merging, either.

Conclusion

I don’t want to mislead you. I still like, and use, Mercurial. As a matter of fact, my main project goncurses uses it still and I have no plans to change that. The Go project itself also uses it. I do, though, find myself missing Git sometimes and the reverse is not true when using other version control systems. I can’t really say why I find myself liking Git better but its just a feeling I get that I can’t put my finger on. Were I to make a recommendation it would be Git because it plays nicely with Go within its 'default' workflow but to be perfectly honest very similar behaviour can be done in Mercurial so you can't really go wrong with it either. It's a very close second. You just need to be aware about the issue with using cloned branches.

Depending on your workflow and habits, you may need to be flexible when using a VCS like Mercurial with Go. My needs are simple and the adjustment wasn't hard. Depending on what you’re used to, no adjustment at all may be necessary.

Proposal for a GUI Toolkit for Go

The Situation

This isn't a unique topic. It's come up in the mailing list before.

Let’s face it, while Go is a general purpose programming language it is ultimately a systems language. It was designed to be concurrent. It was designed to write servers. It was designed to provide a back-end to other services. It does those things pretty well. There is, therefore, an area where Go is lacking and that’s as an application programming language.

This isn't because Go as a language isn't suited it to but that it's standard library doesn't include a crucial component: a UI toolkit. A few people have blamed Google (which makes no sense because Go is not actually a Google project) and the Go developers for this but honestly, it's not their problem. It's not what Go was designed to do nor are the current devs experts in UI design.

Who’s responsible then?

Us.

To be honest, there have been a few attempts already, each with their own merits, but I think all these solutions still fall short of an ideal GUI for Go. So, let me tell you why I think this.


What We Have and Why They Don’t Work

1. GTK+ or another UI Toolkit Wrapper

The easiest, most obvious choice is to create a wrapper for an existing UI Toolkit because of cgo and SWIG. GTK+ fits the bill and mattn has begun this work already. However, there's a problem. For one, GTK+ is C-based. No matter how well the wrapper is designed I don't think it will every feel very Go-like. The toolkit itself is a beast, too. It has thousands of function signatures in it’s API and will take a fairly large concerted effort to completely implement it. More importantly, however, I don’t think this is the right choice and I'll tell you why.

Using GTK+ means that users will need to install it if they don’t have it already. For Linux users, this usually isn't a problem but what about Windows and Mac users? Now we have a problem. I’m a firm believer that you shouldn't force users to install things onto their computer just to run your application unless it's absolutely necessary; and, it makes the installation process more complicated. There is, of course, a solution by including the GTK+ source into the dev tree but we're not talking something like sqlite3 where this can be done easily. GTK+ is massive and I just don't see this as being a feasible solution.

2. GoWut or another HTML Server

I think GoWut is a great idea with what I think is one glaring flaw: it’s a web server. For a single user application, it doesn't feel right. For one, the server doesn't shut down after you’re done using it. Yes, this could be considered a feature because it would reduce load-time of future invocations and you can have user sessions but to me it’s a problem. As an end-user, I don’t want a terminal hanging open with a server running in it. I certainly don’t want all my applications each running it’s own server hogging up my resources, just waiting to be accessed again. I'm sure you could have a 'quit' button to shut down the server but that just doesn't feel right.

3. Go UIK

A native UI Toolkit designed to work like an idiomatic Go library from the start? Sounds awesome! The problem? It’s not done, yet. It’s still in the early design stages but certainly something I’m going to watch for. I think this project has a lot of promise and I look forward to seeing how it turns out. Another issue might that it is going to use a custom widget design rather than a look and feel native to the OS. If, however, it looks pretty enough I’m sure I can overlook that.

4. GoWebkit

Now we’re talking. This to me feels like a more natural solution than a wrapper for another Toolkit. Open a basic application window with webkit embedded in it? Fantastic! This solution comes very close to the mark with one glaring issue: it uses GTK+ as a back-end. The other issue is that it's not a UI. You will have to have some HTML and CSS skills to actually create anything with it and I don't think that provides a very unified solution.


The Solution

Webkit + Native UI Backend + HTML + CSS + (YA/X)ML

Existing technologies mixed together to provide a hybrid result. I think we need a UI Toolkit that uses the OS’s native windowing mechanism (Win API for Windows, Cocoa for Mac, X, GTK+ or Qt for Linux), maybe using John’s WDE library, an embedded webkit renderer, with an API akin to any traditional UI Toolkit complete with event handling. It should allow for customizable CSS elements and, the icing on top, a markup language UI layout design utilizing something like XML. Hrm...it feels like I've just described Android’s UI toolkit...

Of course, this needs some rationale.

1. Native UI Backend - Go is multi-platform. A UI toolkit should be as multi-platform as possible and not require end-users install additional toolkits onto their system. Many application designers will want to control window sizing and else-wise have control over them, like having modal windows. Javascript could provide some of this behavior as well.

2. Webkit - Creating a custom toolkit from scratch, including widgets and all the rest is a colossal undertaking. Qt, GTK+, Win API and Cocoa took an incredible, collective effort to create. Webkit would allow us to circumvent this effort by using a UI that already exists: HTML5 and Javascript. Is this an ideal solution? Maybe not but it’s a reasonable solution that wouldn't require the herculean effort to create a full UI from scratch.

3. HTML + CSS - I think GoWut has a good idea here. Default widgets and creation mechanism so devs don’t have to write HTML and CSS if they aren't skilled in those areas. There is a request in another toolkit's issue tracker requesting ‘nicer’ CSS style to be used by default which I think is a good idea. All a dev would have to do to make their UI unique or make some minor alterations is edit the existing CSS. Or better yet, have an override system in place so that the built-in CSS wouldn't need to be altered. I think adding a custom CSS file shouldn't require injecting an html string with a link element as it does with GoWut but rather a simple API call of SetCSSFile() for a much more elegant and less error prone solution.

4. XML or some other markup language - Android uses this mechanism and so does GTK with GtkBuilder/Glade. I think the reason for this is twofold: a) a UI can be quickly generated by hand without cluttering up the application itself with hordes of API calls for creating widgets; and b) it allows for the use of visual GUI creation tools for building UI’s, akin to Qt’s QtCreater or GTK+’s aforementioned Glade. Like Qt and GTK+, I’m not sure this should be the sole method of building an application UI but rather a complementary one to a standard API. I suggest XML only because I know it's used in existing solutions like Glade/GtkBuilder and Android.

Is this the best solution? Good question!

Conventional languages for writing applications seem to rely on either an existing native toolkit (Tk for TCL, Swing/JavaFX for Java, GTK+ for C or Qt for C++) or a language wrapper for a non-native toolkit. However, most of those tools are either language specific (Swing/JavaFX) or are encumbered by methods for handling situations native to their own languages that don’t play nice with Go (concurrency/threading). There might be ways to overcome these limitations but there you have it.

There are a lot of existing resources for HTML and CSS. I think it would be far easier to find someone proficient in these technologies to help in such an endeavor than it would be to work on some of the other solutions. As a further plus, most of the groundwork has already been done. By combining something like wde for a backend and webkit to render pages then we already have the canvas on which we can paint. By adding in elements of gowut on top, minus the server aspect of it, we essentially have the end product. Add in a dash of CSS to pretty things up, XML for widget creation and layout and we’re done. Sounds easy huh?

Probably isn’t but I think it’s easier than the other solutions with a better end result. It would feel more idiomatic to Go, build on existing technologies, and make for an easy transition for a wide audience (those who are already familiar with HTML, XML and CSS).

I'd love to see some input.