Airs – Ian Lance Taylor

Around 1997 I had did quite a bit of programming in the Tcl language, as part of an IDE project at Cygnus. The project failed, for several reasons, but here I’m going to write about Tcl.

I don’t hear much about Tcl these days, although it was fairly popular in its day. Tcl is a highly dynamic interpreted language. It is easy to embed the Tcl interpreter into a C program. The Tk system, which is written in Tcl but is logically independent of it, is a very clever way to easily write a GUI program. Unfortunately, despite these advantages, Tcl is a mess of a language.

In Tcl, everything is a string. Tcl has list and associative array operations, but they all operate on strings with a specific syntax. The program itself is a string: you could construct new procedures on the fly, and annotate variables. This makes the language very powerful. It also makes it very confusing.

When everything is a string, type checking is completely impossible. It’s very easy to have a list and accidentally use a string operator on it. Everything will work fine, except you won’t be able to pull out the list values as expected. You might think that is not so bad–after all, in Lisp everything is a list, and that works well. But in Lisp, atoms are not lists, and atoms have a type: you can’t apply a string operator to a number. In Tcl the atomic unit is the character, and that doesn’t have a type. Applying a string operator to a number works fine, because a number is just a string of characters which happen to be digits. So when I say that type checking is impossible, I don’t just mean the ordinary lack of static type checking for a dynamic language. I mean that even at runtime there is no type checking.

Because everything is a string, quoting becomes essential. Tcl has various quoting mechanisms: double quotes create a simple string, square brackets create a string formatted as a list which is then normally executed as code, curly braces create a string formatted as a list which is not executed. Within a string, square bracketed lists are executed and variables with a leading dollar sign are interpolated. I’m sure I’m forgetting some aspects. Within such an environment, a detailed understanding of quoting becomes essential. Unfortunately, the only comprehensible way to quote actually involves using square brackets to invoke the list function. In other words, although everything is a string and it should be very easy to stick things together when that is what you want to do, in any scenario which is even slightly complex you have to start writing list operations in order to build your strings. Even then I recently wrote some Tcl code with seven consecutive backslashes, admittedly in a complex use case. That’s too much for easy reasoning, and in practice requires trial and error to get right.

I believe that Tcl has namespaces these days, but when I used it did not. That made it a poor choice for programming in the large, because all functions and variables lived in the same namespace. Because everything is fully dynamic, redefining a procedure causes no error. You don’t discover a namespace collision when you load the program, you only discover it when trying to figure out what went wrong.

The Tk system, as I mentioned, is a very clever way to write a GUI. it lets you write very simple code with windows and buttons and text input and so forth. These days most people would write some HTML and run it in a web browser, but Tk is a more powerful environment, and you can write everything in the same language, unlike the browser’s mix of HTML, Javascript, and server-side PHP or whatever. Tk is cross-platform.

Unfortunately, Tk too has a fatal flaw: because your GUI is produced by a simple program, your programmers have to change your GUI. When a UI designer wants to move a button, the only way to do it is to change the program. And Tk’s layout procedure does a lot for you automatically, which in practice means that it’s a pain to do anything else. The effect is that a Tk program always looks OK but never looks good. This effect is exacerbated by the fact that a Tk program looks kind of the same on any platform, which means that it looks unusual on any platform. For our IDE work we spent a fair amount of time building Tk interfaces to standard Windows objects, so that the programs would look sort of OK on Windows. In other words, Tk winds up being a great prototyping system, but a terrible system to use for your final program.

Despite all these awful characteristics, I have to say that the actual Tcl implementation is great. It’s platform independent, has a nice event loop, the code is easy to read and easy to modify. The core library provides system independent facilities which are well designed and well implemented. Unfortunately a good implementation can not overcome a poorly designed language.

So there you have it: a brief overview of language design gone wrong.

GCC fully supports cross-compilation: building a program on one machine in order to run it another. However, it’s quite painful to actually build a full cross-toolchain with compiler, tools, and libraries. Many people new to the process have the same reaction: it simply can’t be this hard. But it is.

The basic problem is that a cross-toolchain has several different components, and those components are different projects with different release cycles, different maintainers, and different goals. Similar issues arise on a much larger scale with a complete operating system. There, the operating system, or distro, is run as a separate project, one which doesn’t actually do anything except coordinate many different projects and ensures that they work together. No such coordinating project exists for cross-toolchains. (I should say that you can purchase them from various companies, but there are no free projects.)

That’s the first thing to understand if you want to build a cross-toolchain: it really is painful and ugly. Normally when things fail to fit together in a reasonable way, you assume you’re on the wrong path. That’s a false indicator in the cross-toolchain world. Of course, you might still be on the wrong path. But don’t assume that because nothing quite works that you are doing the wrong thing.

The second thing to understand is terminology. The host system is the one where the compiler and other tools run. The target system is the one where the program that you build runs. For extra-advanced use, the build system is the one where you actually build the compiler. For GCC and friends, you specify these systems using the --host, --target, and --build options to the configure script. When the host and target system are the same, you have a native system.

There are many different kinds of target systems. They all require some sort of system library, commonly called a libc. GCC does not provide a system library. You have to figure out what libc is appropriate for your target system.

• If your target runs GNU/Linux, you probably want glibc or uClibc, though Android systems use bionic, and there are other variants. glibc is used on most normal native systems; uClibc is designed for embedded systems, and has better documentation for cross-building.
• If your target runs Windows, you want Mingw or Cygwin. These are fairly easy to cross-build.
• If your target runs some other full-featured operating system, such as Solaris, you will have to copy the libc and all header files from an existing system.
• If your target runs an embedded system such as RTEMS or eCos they will usually provide some documentation on how to build the system.
• Finally, for a barebones embedded system, GCC is often used in conjunction with newlib. Newlib requires some sort of board support package, which handles I/O specific the the system. Some examples are in the libgloss directory.

Different choices here imply different approaches to building, and I’m not going to provide a complete recipe for any of them. Any complete recipe changes over time anyhow.

There are two different basic approaches: the one-tree build and the separate-tree build The one-tree build was developed at Cygnus by people like K. Richard Pixley and David Zuhn. The idea there is to mix all the source code together in a single directory. You can combine gcc, the GNU binutils, gdb, newlib, and/or cygwin/mingw into a single directory by simply merging the source trees. They all share the same top-level configure script and Makefile. However, in order to do this you must use sources from the same date, as there are various shared directories (include, libiberty), and they have to be the same. If you try to mix source trees from different dates, such as from different official releases, you have to be prepared to address complex failures. I can not recommend doing that.

The one-tree build does not work to build glibc. For that you need a separate-tree build. Although I was the release manager at Cygnus for a time nearly 20 years ago, these days I normally do a separate-tree build. For a separate-tree build, you just build the different projects separately. When doing this it’s essential to provide exactly the same configure options for each project. The usual procedure is this:

1. Configure, build and install the GNU binutils.
2. Configure GCC. Run “make all-gcc”. This builds just the compiler, not the supporting libraries. Install it using “make install-gcc”.
3. Configure, build and install the library.
   • If you are copying the library from an existing system, then there is nothing to do there. Instead, copy the library and header files into some directory and use --with-sysroot to point to that directory when configuring the other tools.
   • Building newlib or the cygwin library is fairly straightforward here, as they expect to be built by a cross-compiler.
   • If building glibc, you have to be careful about the configure script checks, as you are using a compiler which can not build a complete program. I am unfortunately not very familiar with the problems that can arise here. Look at the crosstool-ng project for more issues and helpful scripts.
4. Now build and install the rest of GCC, namely the supporting libraries.

At this point you probably think it’s not so bad. Here’s the catch. For any specific tools you are trying to build for a specific host and target, there’s a small but real chance that you are first person to try that specific combination. There is a very good chance that none of maintainers of any of these projects have tried the specific combination you are trying. What this means is that you are likely to encounter some bizarre problem somewhere along the way: some project will fail to build.

When I was the release manager at Cygnus we built a set of new releases every three months. My full-time job was fixing all the bizarre problems that occurred. It was good training in working with these tools. You might think that it would have gotten better over time, but it just hasn’t, because there is still no project dedicated to making it work better. Projects regularly change in incompatible ways that cause obscure combinations to break, and nobody notices.

This is an area that is ripe for somebody to come in and clean up, but it’s hard. It means continual testing and continual patching. It means finding problems fast and harassing maintainers regularly until they get fixed. It means working across releases, or figure out a way to reliably use unreleased code. It means understanding all of these different programs, understanding their goals and their internals. It’s not a completely thankless job, but after all most programmers do not do cross-development, and most programmers who do cross-development get complete cross-toolchains from some vendor, so there aren’t really all that many people who will thank you. Still, it would be good for the GCC world if somebody took this on.

It’s interesting that the U.S. economy has moved away from manufacturing at the same time as computers have made it very easy to copy digital goods. We see the U.S. pushing China hard to enforce their copyright laws, because much of what the U.S. has to sell is easily copied. The U.S. has developed great skill at creating complex software. That skill itself is not easily copied, based as it is on many years of experience, but the end result of applying that skill is is difficult to control. Similarly, the U.S. leads the world in developing entertaining movies, but those too can not be controlled once they have been distributed. You can enforce all the copyright laws you want, but if a digital product is both expensive and desirable, it will inevitably be copied.

Software developers have reacted by increasingly tying software to some sort of service. That is a significant business advantage for offering cloud computing: your software works without requiring distribution, which means that nobody can easily copy it. If you’re going to sell virtual goods rather than manufactured ones, it’s important to not distribute them as part of using them. In other words, you have to sell a service.

Right now the U.S. is trying to push other countries to honor the agreements it needs to sell virtual goods. I don’t see how that can work in the long run. Better to focus on selling real goods or selling services. A simple service is vulnerable to competition, but there is plenty of space for selling complex services which are difficult to develop. That seems to be the likeliest trend for successful software companies going forward. It’s even if a possible path for entertainment companies if you think in terms of games.

The Go language is generally safe, in that errors in your program do not lead to unpredictable crashes (unless you use the facilities in the unsafe package). There is one classic cause of problems, however, which Go does not protect you from: race conditions. A race condition occurs when one goroutine modifies a variable and another reads it or modifies it without any synchronization.

Go makes correct synchronization easy, following the slogan of “do not communicate by sharing memory; instead, share memory by communicating.” Race conditions only occur when sharing memory. However, although correct synchronization is easy, the language does not enforce it. Race conditions are possible and I have seen them in real Go programs.

Is it possible for a language to be safe with regard to race conditions? In a language that supports multiple threads of execution, it’s always going to be possible to construct race conditions by doing things like having multiple threads write to the same offset in the file. Let’s rule out that somewhat exotic variety and concentrate on race conditions which don’t involve external constructs. Let’s also not worry about other threading problems like deadlock or starvation; they are real problems, but they are usually easier to understand and avoid.

Race conditions in memory always involve global variables, in which I include memory which can be accessed via a pointer. When more than one thread can access a global variable, the variable can become a nonlocal side effect: something which can affect program behaviour while changing in a way that is not obvious from reading the program code. When that variable can change without any synchronization, you may have a race condition.

One approach, then, is to prohibit variable modifications. When no variables can be modified, no race conditions are possible. This may sound odd to programmers used to conventional imperative languages like C++, Java, or Go, but this is the approach used by strict functional languages. There are few truly strict functional languages outside of academia, but languages like Haskell approach the goal by clearly delineating the non-strict set of operations. Functional languages generally do not have explicit threading models, but the lack of side effects makes it possible to automatically parallelize them. E.g., when a function is called with two arguments, both arguments can be evaluated in parallel; since there are no global variables, there is no way that the evaluation of one argument can affect the evaluation of the other.

While functional languages have some clear benefits, I think they face a problem of history. They’ve been around for a long time, but they are not widely used. It’s possible that this is merely a matter of education, but I think it’s a more fundamental issue. The real world is full of global state and non-local side effects. I think it’s hard for programmers to adapt to languages which don’t support them. Operations that are conceptually very simple, like sorting a list of numbers, become harder to understand in a functional language. Functional languages will always have adherents and will always have good uses in specific domains, but I think widespread adoption is unlikely. Go is obviously not a functional language.

A somewhat less strict approach for avoiding race conditions is for different threads of execution to not share memory. Without shared memory, all thread communication must use a limited set of communication operations which can avoid races. The Erlang language follows this model. Erlang is a functional language, though somewhat less strict than Haskell. Erlang has an explicit thread model. However, threads do not share memory, and can only communicate via message passing. In effect this enforces Go’s slogan: all sharing must be done by communication. This model also has a nice advantage in that threads can run on the same machine or a different one with no change in the program, but only a change in efficiency.

Go did not adopt this model because of efficiency considerations. Threads communicating in shared memory are far more efficient that threads communicating via message passing. In shared memory you can pass around pointers to large data structures. Without shared memory, large data structures must be sent as a whole. Real implementations of Erlang have a variety of implementation optimizations to reduce the cost of sending large data structures, but that means that programmers have to be aware of the available optimizations when writing programs.

One could argue that correct program behaviour is always more important than efficiency, and that the efficiency advantages of shared memory should be disregarded in the name of correctness. However, that argument does not hold up in the real world, where efficiency does matter. Erlang made the right choice for an environment in which threads can run on different machines and can even move from one machine to another. Go may not be the right choice for that environment. Of course, it is also not the environment in which most programs run.

I don’t know of any other approaches to avoiding race conditions in a programming language, though I’m sure there are some. One possibility would be for the language to maintain a global synchronization state. Each operation on a global variable would then be annotated with the current state. If two operations were done using an incompatible state, meaning operations done by different threads with no explicit synchronization, you would get an error.

If this were done purely dynamically, the result would be similar to Thread Sanitizer or helgrind. With language support, it could be constructed to avoid all race conditions. However, since race conditions would only be detected dynamically, it would mean that your program could still crash occasionally at runtime. This would be much better than the current situation, in which your program can behave unpredictably at runtime. The dynamic information would also provide a lot of the information required to debug the problem.

This approach could also be used statically, but I suspect it would require fairly extensive annotations on functions to indicate their synchronization status. It might be possible to deduce some of that statically using whole program analysis, but in a language like Go with channels I think that would be difficult in practice and impossible in theory (i.e., some programs would provably require annotations, and most programs would in practice require annotations).

So what would the dynamic approach look like? It would basically mean instantiating the Go memory model in each operation, tracking the happens before relationships. For example, give every goroutine a ticker. When a goroutine sends a value on a channel or acquires or releases a lock, increment the ticker. When sending a value on a channel or releasing a lock, attach the current goroutine and its tick. When receiving a value on a channel or acquiring a lock, record a happens-before relationship from the attached goroutine/ticker to the current goroutine/ticker. When modifying any global variable, including any shared memory, annotate the variable with the goroutine and its ticker. When reading any global variable, look at the current annotation, and require that there be a happens-before relationship between that annotation and the executing goroutine.

What’s nice about this approach is that it doesn’t require any change to the language or to your program. What’s not nice is that you have to pay a heavy execution cost, and you only catch all actual race conditions, you don’t catch all possible race conditions. It would be nice if the heavy execution cost could be mitigated by static analysis, but in general I don’t think it can. Escape analysis can prove that some variable reads don’t require checking annotations, but I think that even simple programs will defy such analysis for most reads.

On the other hand, with some caching, perhaps the execution cost would not be prohibitive. Most reads are going to be of values written by the current goroutine. That requires an extra read and comparison for each memory read, which would be bad but perhaps supportable. Since one would presumably want to track individual memory words, memory usage would double. Alternatively, since the Go memory model is written in terms of variables, one could instead have an extra word per variable. Then pointer accesses would require identifying the appropriate variable, even if the pointer were to the middle of the variable.

I doubt this could ever be the default way to run Go, but it would certainly be interesting to try an implementation and find the real performance effects.

When I started using networked computers, I had two inboxes: e-mail and Usenet. I read every e-mail message I received. I read most Usenet postings in the groups I followed, but it was no big deal if I missed some. Those are the two main types of inboxes: the ones where you pay attention to every message, and the ones where you read the interesting ones and skip the others. Other examples of the first kind of inbox, at least for me, are voice mail and the original inbox: personal letters. An example of the second kind of inbox is the daily news, whether on paper or on radio or television.

I didn’t realize it when I was younger, but there is another kind of inbox: what the people you see frequently are talking about. In one sense this is gossip, in another it is society. This is a kind of inbox which you don’t look for, where you don’t pay attention to every message, where information just kind of passes by you. Mostly you glance at it and forget it, although you usually remember the general gist.

In the last several years that kind of inbox has been copied online, most obviously in Facebook and Twitter and their friends. The difference between them and Usenet is organizational. Usenet was organized around specific themes. Sometimes the theme was completely random, but it meant that only people who wanted something random read that group. Facebook and Twitter are organized around social groups or followers, just like gossip.

Because it’s a pain to have to check lots of inboxes, there are lots of tools these days to copy information from one inbox to another, and, conversely, to let you send information to other people’s inboxes in various different ways. These tools all work differently and have various degrees of effectiveness. At the same time, all popular inboxes struggle with a problem of spam: messages that you don’t really want that are mostly trying to part you from your money in some way.

It would be nice if inboxes were easier to consolidate, if I could look at some master control panel and say “I’d like his blog posts to come to this box in my e-mail, and I’d like her most recent photo to my desktop background” and then change all of it again tomorrow. But in real life anybody who created such a panel would get so bogged down in issues of authenticity and spam that the next big thing would never bother to interoperate with the panel, in fact would probably try to actively avoid it so that they could in fact become the next big thing, rather than being just another inbox.

Meanwhile we’ll all just keep juggling our proliferation of inboxes, which mostly means getting better and better at ignoring them, at accepting that we will never catch up with all of them, and that that’s maybe not perfect, but it’s OK, it’s as good as it gets.