Go experience report: the append function

When the Go language was first publicly released it contained a package named container/vector.  The type vector.Vector was a name for the type []interface{}.  Vector supported methods like Len, Cap, At, Set, Insert, Delete, Push, Pop, and several more.  You can see the source code at on Github.  An interesting aspect of the package is that string and int versions of Vector were automatically generated by copying the file vector.go with edits applied by gofmt -r.

The container/vector package was deleted in October, 2011, before the Go 1 release, because by that time it added nothing that was not available more simply using slices.  But it was useful once; in October, 2010, it was used by 18 packages in the standard library.  By the time it was deleted one year later, it was not used by any.  This change occurred because of a key feature added to the language: the built-in append function.

The append function was first proposed by Robert Griesemer in an internal e-mail sent in November, 2009, during a discussion of whether to add the built-in copy function (as a result of that discussion copy was added to the language in CL 156089).  At that time I replied about both copy and append saying “It seems to me that these functions are not useful if we figure out a way to implement generics. Not necessarily a strong argument against them, I suppose, but do we want to introduce new builtin functions if we may not need them?”

In 2009 we added copy but not append.  In October, 2010, David Symonds proposed append independently, saying “It’s been getting tiresome having to write the same old boilerplate to grow a slice on demand. container/vector would be suitable if it were generic, but cluttering code with type assertions is worse than the expansion.”  Robert picked this up and outlined the function we know today, adding “Should we ever have some form of genericity, this could even become a library function. For now, the implementation would be a built-in.”  I replied to the thread, essentially repeating myself from a year before: “I’m not really opposed to a builtin append function but I want to make the obvious comment that, like copy, this is a function we are only considering because we don’t have generics.”  The result of this discussion was to add append as we know it today to the Go language (CL 2627043).

The point I want to make here is that because we had no way to write a generic Vector type with an Append method, we wound up adding a special purpose language feature to implement it.  A language that supported parameterized types with methods would not have required a special built-in function that only works with slices.  An append operation makes sense for other sorts of data structures, such as various kinds of linked lists.  The built-in append function can not be used for them.

I am writing this note as a user experience report to add to the Go wiki.  To fit the format there, what we wanted to do was to add a generally useful mechanism for extending a slice.  What we had to do was extend the language.  That wasn’t great because it made the language more complex by adding a special purpose, non-generalizable, non-orthogonal, feature.

Comments (1)

The 2016 Election

Although I haven’t written in this blog in years, like many people I’ve been thinking about the recent U.S. presidential election. What I find most interesting is the continuing evolution of effect of the Internet on life in the U.S.

The Internet is destroying the truth.

By this I don’t mean the recently much-discussed issue of fake news, and I don’t mean the way the Internet facilitates the spread of conspiracy theories. These aspects of our lives are not new. We have old phrases to describe them, such as “yellow journalism” and “the paranoid style.” The Internet permits falsehoods to spread faster and live forever, but it does the same for their rebuttals.

What the Internet is doing is something deeper.

The U.S. used to have a set of core truths, taught in schools and promulgated by the media. The U.S. was the land of the free and the home of the brave, the country of manifest destiny and huddled masses yearning to breathe free, the leader of the free world, the place where paths are beaten to the door of the inventor of the better mousetrap. Few people wholly believed these truths, but it was the shared idea that people reacted against.

When people argued that the U.S. was an example for the world, they did so in agreement with these core truths. When they argued that the U.S. was a racist country, or a country with a history of terrible interference in other countries, they did so in explicit opposition to these core truths. During the Cold War Communism was bad because it was not the American way.

People tried to change the country with reference to these core truths. They did not say “we have a different vision for the U.S..” They said “the U.S. is not living up to its ideals.” Both sides of the culture wars in the decades after World War II argued in terms of who was more American. They drew different conclusions about what it means to live in “the land of the free,” but they agreed on that basic idea.

These core truths were maintained by a set of intermediaries between the world at large and individual citizens. Journalists and politicians described the world to most people. There were a limited number of them and they formed a professional class which sought to maintain mutual respect. People who strayed too far from the shared ideas lost access to the platforms that gave them wide audiences.

The changing nature of journalism is well known. Walter Cronkite, the CBS news journalist, once won an opinion poll as “the most trusted man in America.” In a recent opinion poll by Reader’s Digest for the 100 most trusted people in America, the top four people were movie stars; the highest ranked journalist, at number 12, was Robin Roberts, the anchor of a morning show. The main network’s news broadcasts on radio and TV used to reach over 50% of households. They now reach less than 20% of an increasingly aging audience.

While there are several causes for the decline of journalism, the Internet is a large factor. The Internet has displaced the primary revenue source for print journalism, but, more than that, the Internet has profoundly changed society’s intermediaries. The new intermediaries are platforms like Facebook or Twitter which connect people directly to each other. These companies try to fade into the background as much as possible, and make no attempt to present a coherent worldview or to separate truth from falsehood.

I’m not trying to claim that the world before the Internet was a prelapsarian time of truth and fairness. It wasn’t. Especially for people who are not part of the (white, male, straight) majority, the country today is more truthful and more fair than before. What I am claiming is that we no longer have a shared idea of what the country is. We can no longer stand in support of or opposition to the country, because we don’t agree on what it is.

The U.S. is the only major country founded on an idea, rather than being simply a collection of people who happen to live in one place. We must not forget the truth that this way of founding a country led to the near genocide and forced migration of the Native Americans who did happen to live in this place. But what I want to focus on is that basing a country on an idea makes the country uniquely vulnerable: if people no longer believe the idea, then the country has no foundation.

Now let’s talk about the election.

Trump as a presidential candidate was unacceptable to the traditional maintainers of the core truths. Journalists and politicians were mostly united against him. He was rejected by left- and right-wing alike. His victory demonstrates that those people no longer matter. The truth they have been maintaining is no longer shared.

Trump himself is likely to be a terrible president. I say this not because of how he won, and not because he is a racist megalomaniac–many presidents have been that–but because he appears to be profoundly uninterested in the world outside himself. Trump aspires to be a tin-pot dictator, and he would probably be a good one: entertaining and, as dictators go, among the less evil. As the U.S. president many are rightly concerned about his authoritarian aspirations, but those very concerns, and his lack of broad-based support, make his wishes unlikely to be realized. We are forewarned and will resist.

Trump can’t take over the country, but he can destroy it. As a candidate he encouraged divisions: against immigrants, against Muslims, against people who voted for other candidates. All our presidents in living memory have sought to unite the country, to speak to all the people. Trump has shown no signs of that. He is likely to accelerate the process, already well under way, of destroying the shared vision of the country. He is likely to encourage the ongoing process of some people viewing others as being not merely in profound disagreement, but as being actually un-American.

When we no longer agree on what the U.S. means, how long can the U.S. survive? What would a failure of the U.S. look like?

Great civilizations like the Roman Republic or Tang China fell primarily due to internal strife. The U.S. does not employ foreign mercenaries, but it does have what is in essence a military caste of families who serve in the armed forces. Some 80% of the current military come from a family in which a parent or sibling is also in the military. Nearly half the current military comes from just five states. The last president with real military service was George H.W. Bush, who left office more than 20 years ago. The members of the current Congress have the lowest rate of military service ever. (I personally never served; my grandfather and father-in-law did, in a different time.)

This military caste is large and does not have uniform views, but they do tend to share a version of the truth about the country.

The U.S. military has a very strong tradition of civilian control, but the same was true in Rome and Tang China: Julius Caesar crossed the Rubicon, An Lushan defied the Mandate of Heaven. In the U.S., the military will reject civilian control if they have a strong leader and if enough of the military perceive the government as no longer representing the ideals and traditions of the U.S. Since those ideals and traditions are what I am claiming are falling into disagreement, we are now closer than ever to a military coup.

The most likely scenario would be a demagogic leader with ties to the military who wins a closely contested election with strong military support. Overreaching by the new president causes strong opposition from the professional intermediaries, leading to lawsuits and eventually to impeachment and conviction. The president rejects the conviction and refuses to vacate the office, arguing that the opposition is un-American and that the country can not change leadership while facing significant external threats from the enemy du jour. The military, whose members have lived through many years of severe disagreement about what the country really means, supports him. Chaos ensures, ending in a military dictatorship and the dissolution of the country.

Trump is not that leader, but he is giving us a template for our future collapse. He is increasing the problems that make it more likely.

This probably sounds hyperbolic, and I hope that it is. But don’t fool yourself too much. History has not ended. The future will not be like the past. At nearly 250 years the U.S. has already had a good run as countries go. If we want it to continue, a majority of citizens must actively work to prevent it from failing.

What can we do?

We must spread an understanding of how potentially perilous the situation is. Nothing motivates people like fear. Other than millenarians, people fear the dissolution of society. One of our early great leaders, Benjamin Franklin, put it perfectly: “we must all hang together, or most assuredly we shall all hang separately.”

Our political class is required by elections to respond to the popular view. We must press them to remember that we are all in this together. This is unfortunately a long shot with our modern variant of rotten boroughs, safely held by a single party. California has introduced what I believe are steps toward addressing this: a politically balanced redistricting commission, and top-two primaries that help save candidates in single-party districts from being “primaried”. People who still believe in democracy should support these changes for all states.

The extremely wealthy have enormous influence over our political system. It would be nice to reduce that influence, and I wholeheartedly support efforts to get money out of politics, but that is very difficult. More realistic is to remind the wealthy that their interests will be harmed if society collapses. They do not live in a completely separate world. The country still matters, and they should care about maintaining it.

We must reduce the isolation of the military caste. While mass conscription is not appropriate for today’s world, service is not. We should have a mandatory year of national service, in the military or in programs like the Peace Corps or AmeriCorps, for all healthy young people. This is not a new idea, and other countries have tried similar systems. It would be expensive but worth it.

Can these ideas be implemented in the face of opposition?

I think they can. These are incremental changes. While many politicians these days are engaged in a zero-sum game in which the only thing that matters is beating the other side, that is not true of most voters. It doesn’t take a major shift to get people to vote for sensible reforms.

Will these ideas solve the problem?

Of course not. The Internet will still be here, still disintermediating the world and giving each person their own individual truth. We can’t stop that or avoid it. All we can do is set up countervailing forces. The Internet is splitting us apart. We have to keep reminding ourselves and everyone that we have to live together even with those with whom we disagree. Our country is fragile. If we don’t care for it, we will lose it.


Piece of PIE

Modern ELF systems can randomize the address at which shared libraries are loaded. This is generally referred to as Address Space Layout Randomization, or ASLR. Shared libraries are always position independent, which means that they can be loaded at any address. Randomizing the load address makes it slightly harder for attackers of a running program to exploit buffer overflows or similar problems, because they have no fixed addresses that they can rely on. ASLR is part of defense in depth: it does not by itself prevent any attacks, but it makes it slightly more difficult for attackers to exploit certain kinds of programming errors in a useful way beyond simply crashing the program.

Although it is straightforward to randomize the load address of a shared library, an ELF executable is normally linked to run at a fixed address that can not be changed. This means that attackers have a set of fixed addresses they can rely on. Permitting the kernel to randomize the address of the executable itself is done by generating a Position Independent Executable, or PIE.

It turns out to be quite simple to create a PIE: a PIE is simply an executable shared library. To make a shared library executable you just need to give it a PT_INTERP segment and appropriate startup code. The startup code can be the same as the usual executable startup code, though of course it must be compiled to be position independent.

When compiling code to go into a shared library, you use the -fpic option. When compiling code to go into a PIE, you use the -fpie option. Since a PIE is just a shared library, these options are almost exactly the same. The only difference is that since -fpie implies that you are building the main executable, there is no need to support symbol interposition for defined symbols. In a shared library, if function f1 calls f2, and f2 is globally visible, the code has to consider the possibility that f2 will be interposed. Thus, the call must go through the PLT. In a PIE, f2 can not be interposed, so the call may be made directly, though of course still in a position independent manner. Similarly, if the processor can do PC-relative loads and stores, all global variables can be accessed directly rather than going through the GOT.

Other than that ability to avoid the PLT and GOT in some cases, a PIE is really just a shared library. The dynamic linker will ask the kernel to map it at a random address and will then relocate it as usual.

This does imply that a PIE must be dynamically linked, in the sense of using the dynamic linker. Since the dynamic linker and the C library are closely intertwined, linking the PIE statically with the C library is unlikely to work in general. It is possible to design a statically linked PIE, in which the program relocates itself at startup time. The dynamic linker itself does this. However, there is no general mechanism for this at present.

Comments (2)

Non-free Services

As both of my faithful readers can see, my blog postings have dropped significantly. I’ve been posting my random little comments on Google+ instead.

Which leads me to the following. There is a hard-core group of people who only use free software. I’m not quite that hard-core, but in practice I do use only free software, except perhaps for some binary drivers in the kernel (I don’t actually know whether the systems I’m running use binary drivers or not, and I’m not hard-core enough to find out).

I’ve seen some people argue that if you are serious about using free software, you should also only use Internet services which are themselves free software. For example, you should not use Facebook or Google+, because the software used to run those services is not free.

I don’t agree with that argument. The key goal of free software is that I always have the right to change the software that I am running. When I use an Internet service like Google+, I am not running the software. Even if I had a copy of the software, I would not be able to run it, because I don’t have enough servers. And even if I had enough servers, it would be useless for me to run the software, because I don’t have the data. And there is no way to grant me access to the data, because that would violate the reasonable privacy choices of everybody else using the service.

When it comes to a service like Google+, whether the software is free is not important. Releasing the software would not give me any more freedom than I already have. Google+ is only interesting when many people are operating out of a single shared data base, and that data base must have privacy safeguards to ensure that it is not copied.

What matters with Google+ is not the software, but the data. It is important that I be able to retrieve all my data associated with Google+, and that I be able to retrieve it in a way that makes it possible to use with other software. That is, I should be able to retrieve my posts, my comments on other people’s posts, my list of followers, my photos, etc. And I should be able to plug them into some other software service if I so choose.

In fact Google+ does have a set of APIs which permit me to retrieve my data. I haven’t verified that all Google+ data is available via the APIs, but all the obvious stuff seems to be available. Given those APIs, it should be possible for me to move all my data to some other service which provides te required APIs itself.

So I personally don’t see any reason why even a hard-core free software supporter should avoid using a service like Google+. This isn’t to say that it wouldn’t be nice if Google freed up the software and accepted patches from outside users. It’s just that that is not a critical part of freedom to use software.

Comments (5)


There is no chance that Edward de Vere, the Earl of Oxford, wrote the plays attributed to William Shakespeare.

That said, I found the movie Anonymous to be reasonably watchable, although I thought many of Vanessa Redgrave’s scenes as the older Queen Elizabeth were ridiculous. But since the movie claims (perhaps as a joke) to be seriously advocating the position that Oxford wrote the plays, I was surprised that they did such a poor job of supporting the theory.

Oxford was shown as being tutored at length on topics other than poetry. He traveled abroad, he intrigued at court. When would he have had time to write the plays and the sonnets? The movie essentially presents Oxford as being mysterious gifted by the ability to write; he speaks of continual voices in his head. That could happen to anybody, and perhaps describes the real Shakespeare–if anybody could have written Shakespeare’s plays, then why not Shakespeare himself?

Oxford is shown as using the plays to support his court intrigues. Is it possible to imagine Shakespeare, with his clear vision of humanity, thinking that he could achieve such ends through his plays? One of the strongest examples of that in the movie was the suggestion that it was odd that Shakespeare portrayed Richard III as a hunchback, but even I know that Richard III was popularly (and probably falsely) considered to be a hunchback long before Shakespeare’s time.

Of course it’s conceivable if unlikely that somebody else wrote Shakepeare’s plays. But the undercurrent of the Oxford theory has always been that a member of the nobility would be more likely as the playwright than a commoner. But this reverses reality. The nobility were highly trained from birth in their roles in society. They were busy people with lots to do. It was far less likely that an earl could write the plays than a member of the middle class. As far as I know only one member of the English nobility ever achieved any note as an author: Lord Dunsany, who lived much later.

The movie did have a couple of nice (non-Shakespearean) lines, one of which, by the Ben Jonson character, was simply the truth: the only reason future ages remember the people who lived then was because they were alive when Shakespeare was writing.


« Previous entries Next Page » Next Page »