Common Lisp: The Untold Story, by Kent Pitman. A nice paper about the history of my favorite lightweight dynamic language.

This paper summarizes a talk given at “Lisp50@OOPSLA,” the 50th Anniversary of Lisp workshop, Monday, October 20, 2008, an event co-located with the OOPSLA’08 in Nashville, TN, in which I offered my personal, subjective account of how I came to be involved with Common Lisp and the Common Lisp standard, and of what I learned from the process.

Some of my favorite parts are:

How CL was viewed as competition to C++. (Really, what were they thinking?)
How CL was a reaction to the threat of Interlisp, and how "CLOS was the price of getting the Xerox/Interlisp community folded back into Lisp community as a whole" (link).
How individuals shaped the processes of standardization. MIT Sloan did an analysis of these processes.
How the two- to three-day roundtrip time for UUCP emails to Europe may be responsible for the creation of the separate EuLisp.

I have a soft spot for CL, so I am biased, but I think Greenspun's Tenth Rule (and Robert Morris' corollary) still holds - CL is the language that newer dynamic languages, such as Perl 6, JavaScript, and Racket are asymptotically approaching (and exceeding in some cases, which is why I view CL as a lightweight language today.)

Second response by Aram Harrow

Albert Einstein was a great observer of science, as well as doer of science. Most of his quotations as well as theories have proved their staying power over the past century. We, Dick and Ken, feel that some of them are better when understood narrowly within science rather than taken broadly as they usually are.

Today our guest poster Aram Harrow opens his second response to Gil Kalai’s conjectures of impediments to quantum computation by applying one of Einstein’s quotations in such a focused manner.

The quotation, and Einstein’s own clarification of it, are conveyed in this article on him and the mathematician Oswald Veblen, regarding the latter’s request in 1930 to inscribe the quotation on a plaque in the new Princeton mathematics building:

Einstein consented to the inscription of the phrase: “God is subtle, but he is not malicious,” even though he wrote to Veblen that he had meant to say “Nature conceals her mystery by means of her essential grandeur not by her cunning.”

The narrow meaning is that in physics and other natural sciences, solutions may be hard to find but they will not evade theory in perverse ways. Even in cases like the -body problem where closed-form solutions are unavailable and behavior may become unstable, the underlying elements are smooth enough that one’s expectations will not be wantonly deceived. This goes especially in a classical geometric theory like relativity—whether Einstein thought this of quantum we don’t know.

By contrast, those who work in number theory must cope with having expectations deceived all the time. For instance, the Mertens conjecture is true for the first zillions of cases but known be false, though a concrete counterexample is yet to be constructed. (See also this about expectations.) Nastiness may be as Platonic and existential as niceness—in math. If Max Tegmark is right that “all structures that exist mathematically also exist physically,” then Nature must get arbitrarily nasty somewhere. So Einstein and Tegmark cannot both be right, though we could live in a nice “pocket” of Tegmark’s cosmos.

Anyway Gil and Aram are talking about our world, and we give the matter back to Aram. This is Part 2 of his three-part response, and addresses Gil’s contention that quantum errors are subject to correlations that defeat the independence assumptions of fault-tolerant quantum computation (FTQC). There will be a Part 3 by Aram and then (at least) a longer rebuttal by Gil.

Second Response by Aram Harrow: Nature is Subtle, But Not Malicious

The possibility of a high rate of correlated errors seems reasonable in many ways. Claire Mathieu points out that independence of random events is the sort of thing that often gets blithely assumed, when actually it’s a major assumption. Independence is attractive because it lets us extrapolate from easily observable probabilities to infinitesimally small probabilities, but for this reason it is also dangerous.

Analyzing FTQC is more complicated than analyzing error correction, but the big picture is similar. If an error-correcting code on qubits corrects errors, then independent error rate will be transformed into an error rate that looks like . If this is an improvement, then we can iterate this process via concatenation and drive the effective error rate down. In all cases, our goal is to apply Chernoff-type bounds that guarantee an overall low error rate.

But what if errors are not independent? Then the answer still depends on how likely we are to encounter clusters of simultaneous errors. Gil points out (e.g. Lemma 1 of this 2008 arXiv paper) that if errors are pairwise correlated, then the probability of errors can be significantly higher. But Chernoff-type bounds still hold. Indeed mere pairwise, or -wise, correlation of errors is not enough to derail FTQC. Gil mentions that one of his models of correlations corresponds to the Curie-Weiss model, which describes classical magnets. But here too, the chance of errors decays exponentially with (see Lemma 1 of these notes).

Fundamentally this is because the basic interactions in physics involve two or three particles, for instance when a photon bounces off an electron. Here is the standard model describing all known interactions. To get interactions with more particles, you need to go to higher levels of perturbation theory, but as you do so, amplitudes go down exponentially. This is also what we observe in experiments, when we entangle 7 atomic nuclei in NMR or 14 electronic states in trapped ions. Of course, one can imagine dangerously correlated noise models. One such model is that with probability nothing happens, and with probability , the user trips over the power cord, and all bits simultaneously fail. But are these more likely in quantum computers? Let’s look at the two ways that Gil claims these are more likely.

Does Entanglement Cause Correlated Errors?

Quantum computing (probably) requires producing large entangled states to be interesting. Gil suggests that this entanglement may be self-limiting, by increasing the rate at which correlated errors occur. This is one of the routes he proposes for generating highly correlated errors in quantum computers.

The key reason I regard this as unlikely is that quantum mechanics is linear, in the same way that stochastic maps act linearly on probability distributions. This means that there is no physical process that can distinguish an arbitrary entangled state from an arbitrary non-entangled state, just as no test can determine whether a probability distribution is correlated, given only a single sample. Specific states can be distinguished, but there is no “entanglement” or “correlation” observable that can be measured. In particular, when “noise” is modeled in the usual manner as a trace-preserving completely-positive linear map, then linearity forbids noise depending on whether the host system is entangled.

More generally, error processes are defined in terms of Kraus operators that do not depend on the state being acted on. The way this works is that the state is a vector, and the Kraus operators are matrices that act on this vector. Each matrix-vector product is a possible outcome, with probability given by its squared length.

For example, suppose our qubit is stored in the electronic state of a trapped ion. Spontaneously emission is a type of error with two Kraus operators: one that sends the excited state to the ground state, and one that merely reduces the amplitude of the excited state. These can be represented by 2×2 matrices. These act as a physical process on any state, entangled or otherwise. For the Kraus operators to change as a function of entanglement, quantum mechanics would have to become nonlinear, which would mean utter catastrophe, comparable to what would result from being able to act nonlinearly on the probability distribution of the universe.

How Classical Synchrony Emerges Linearly

But don’t we observe synchronization in real-world systems? Gil gives an example of metronomes: if you have a bunch of mechanical metronomes sitting on a table, then the weak coupling they experience via the common tabletop will cause them to eventually synchronize. There are also quantum analogues in which spin qubits interact with a common bath of bosonic modes. But for the metronomes, what we are really observing is the result of pairwise interactions together with dissipation.

In fact, the process is similar to the error-correction procedure for a repetition code. The differential equation has the form

These dynamics will synchronize the metronomes, and thus will generate correlations. But this process has nothing to do with the question of whether the metronomes were correlated in the first place. No physical process will make the term larger if the state is correlated/entangled.

Moreover, these types of correlations can be handled by FTQC. What it means for the error rate to be, say, , is that our control is 1000 times faster/stronger than the error processes. So even if the system would synchronize if left alone, sufficiently fast control can still prevent this by acting before multi-qubit correlations can build up. This argument is developed in detail in a paper by Aharonov, Kitaev and Preskill.

One subtlety concerns the semi-classical approximation. For example, suppose we apply a laser to the trapped ion. If it is the right frequency, the laser will cause X rotations. This can be viewed as applying a controllable Kraus operator. But now the Kraus operator still depends on the state of something; namely, the classical system controlling the laser. This appears nonlinear, but really the true Kraus operators involve two-body interactions between the ion and individual photons in the laser. Each such interaction is very weak, and when we add up the many photons comprising the laser beam, we get what looks like a Kraus operator acting only on the ion, but with parameters that depend on the settings of the laser. There is fundamentally no nonlinearity, and more important, nothing that is even approximately nonlinear in the state of the ion, which is what is relevant to the quantum computer.

Does Computation Cause Correlated Errors?

Another route to correlated errors is by piggy-backing on our computation. For example, suppose that we control our ion-trap quantum computer by blasting it with lasers. The lasers are macroscopic objects, and if there were other ions, or systems that behaved like ions, lurking near the ions we use for qubits, then these would be similarly affected by the lasers. If we were unlucky, these “shadow qubits” might interact with our computational qubits in ways that caused errors, and now these errors would exhibit complicated correlation patterns that would depend on the history of laser pulses we have used. Thus, even though there is no[…]

Beating Coppersmith-Winograd

Virginia Vassilevska Williams is a theoretical computer scientist who has worked on a number of problems, including a very neat question about cheating in the setup of tournaments, and a bunch of novel papers exemplified by this one on graph and matrix problems with runtime exponents of that have long been begging to be improved.

Today Ken and I want to discuss her latest breakthrough in improving our understanding of the matrix multiplication problem.

Of course Volker Strassen first showed in his famous paper in 1969 that the obvious cubic algorithm was suboptimal. Ever since then progress has been measured with one parameter : if your algorithm runs in time , then you are known by this one number. Strassen got , and the race was off. A long series of improvements started to happen, which for a while seemed to be stuck above . Then, Don Coppersmith and Shmuel Winograd (CW) got and everything changed. After a contribution by Strassen himself, CW finally obtained in 1987, with full details here. This has been the best known for decades.

This has all changed now. Virginia has proved that she can beat the “barrier” of CW and get a new lower value for . Currently her paper gives , an improvement of “only” , but there is promise of more. This is also another case of proofs coming in twos, as a theorem in PhD thesis work by Andrew Stothers was circulated to some in June 2010 but not very widely. All this is extremely exciting, and is one of the best results proved in years in all of theory. While these algorithms are unlikely to be usable in practice, they help shed light on one of the basic questions of complexity theory: how fast can we multiply matrices? What could be more fundamental than that?

The Basic Idea

Matrix multiplication is bi-linear: the formula for the entry of is . The first step in simplifying the problem is to make it more complicated: Let us have indicator variables and compute instead the tri-linear form

This is a special case of a general tri-linear form

where and we have re-mapped the indices. It looks like we have made order-of work for ourselves. The key, however, is to try to fit a representation of the form:

where . The point is, suppose we can compute these products in total time . Then we can compute (the coefficients for) all the desired entries

in steps. Thus what we have are separate handles on the time for the products and the time for the . The way to manage and balance these times involves recursion.

The Basis Idea

The recursion idea is nice to picture for matrices, though its implementation for the way we have unrolled matrices into vectors is not so nice. Picture and as each being matrices. We can regard instead as a matrix of four matrices , and do the same for . Then the product can be written via products , and we can picture ourselves recursing on these products.

The reason why the vector case does not look so nice is that the tri-linear form is so general—indeed we cannot expect to fit a general tri-linear form into a small number of products . What CW did, building on work by Arnold Schönhage, is relax the tri-linear form by introducing more than -many variables, supplying appropriate coefficients to set up the recursion, and most of all framing a strategy for setting variables to zero so that three goals are met: the recursion is furthered, the values of “” at each level stay relatively small, and the matrix product can be extracted from the variables left over. This involved a hashing scheme which used subsets of integers that are free of arithmetical progressions.

The final step by CW was to choose a starting algorithm for the basis case of the recursion. They devised one and got . Then they noticed that if they bumped up the base case by manually expanding their algorithm to an handling the next-higher case, they got a better analysis and their famous result . By their way of thinking, bumping the basis up once more to was the way to do better, but they left analyzing this as a problem. Others attempted the analysis and…found it gave worse not better results. So , actually , stood.

The insight for breaking through was to make a bigger jump in the basis. Vassilevska Williams was actually anticipated in this without her knowledge by Andrew Stothers, in his 2010 PhD thesis at the University of Edinburgh. Stothers used and showed this method capable of achieving , though there has been some doubt in whether all details were worked out. Vassilevska Williams, however, used and brought some powerful computing software to bear on a more-extensive framework for the plan. It is not clear whether there is anything necessary about jumping by a power of —in any event her program and framework work for any exponent.

The Proof

We cannot yet really give a good summary of the proof—further details are in her paper. One quick observation about her work is in order. She used the CW method, but extended it into a general schema can be used to find good matrix product algorithms, perhaps even better than the one in the paper. The algorithms themselves can be generated and examined, but as usual the task of analyzing them is very hard. The brilliant insight that she has is this task can be laid out automatically by a certain computer program. This allows her to do the analysis where previous others failed.

For example here is a sample of the overview of her main program, in pseudo-code:

The details are not as important as the fact that this program allows one to work on much larger schemas than anyone could previously.

What Does the Bound Mean?

Note that she has improved the bound of Stothers by . For what threshold value of does an additive improvement of in the exponent halve the running time? The answer is , which in this case is . This value is far above the Bekenstein Bound for the number of particles that could be fit into a volume the size of the observable universe without collapsing it into a black hole. In this sense the algorithm itself is even beyond galactic.

The meaning instead comes from this question: Is there a fundamental reason why could settle at a value strictly greater than ? Note that is not taken to mean the existence of a quadratic-time algorithm, but rather that for all there are algorithms that achieve time . There was some reason to think could be a natural barrier, but it was breached. Perhaps , since this is connected to the golden ratio? Her paper notes a recent draft by Noga Alon, Amir Shpilka, and Christopher Umans that speaks somewhat against the optimism shared by many that .

Open Problems

Can the current bounds be improved by more computer computations? Are we about to see the solution to this classic question? Or will it be struggling over increments of ?

In any event congratulate Virginia—and Andrew—for their brilliant work.

Update: Markus Bläser, who externally reviewed Stothers’ thesis, has contributed an important comment on the blog of Scott Aaronson here. It evaluates the significance of the work in-context, and also removes the doubt going back to 2010 that was expressed here.

Steve Jobs and Dennis Ritchie both died within a few days of each other.

In my mind, there are four most important people in the story of computer software. The story begins with Ken Thompson and Dennis Ritchie, who figured out how to write an operating system (Unix). With this, we got the first powerful beasts.

The third person in the story is Bill Joy, who got the beasts to talk to each other (BSD). This gave us the Internet.

The fourth person in the story is Steve Jobs, who gave the networked beasts a pretty face, who got mere mortals to command the beasts.

Today, the wonders of the world of computing are: iPad, iPhone, Android, Kindle, Macbook Air. Every single one these is derived from the work of these four people. Wow.

(iPad, iPhone, Macbook Air run variants of Mac OS X, which is derived from NextOS which is a child of BSD. Android is derived from Linux, which is a ground-up rewrite of BSD. Some kindles run Linux, the others a forked Android).

This is my contribution to Ada Lovelace Day

Ada Lovelace is, perhaps, the world’s first programmer of an actual computer. Others wrote about algorithms much earlier—think Euclid and the famous GCD algorithm—but she wrote a program for a specific computing machine. The machine was Charles Babbage’s Analytic Engine, and her notes look like a program to most.

Today I plan on joining over a million other bloggers in discussing women in science, and more specifically computing. The event is named after Ada Lovelace, and is happening all over the web.

Okay, I exaggerated about the number of bloggers, it is closer to 100,000 than a million—actually it is closer to 1,700. The number is not important; what is important is: we need more women administrators, educators, and researchers in all areas of computing. Further, more women who already have done great work in computing need to be recognized and given the awards and accolades they deserve. This has not always happened.

I am honored to be a tiny part of this special day, and I hope I can help in some way to make the event a success.

What To Do?

I am honestly unsure what I should do. For starters I am not a woman, and cannot really understand their issues. But, I have been in the computing field for over thirty years and perhaps I can add some small insights. I will try.

When I was first at Princeton we worked very hard to hire Andrea LaPaugh from MIT, where she got her Ph.D. We were successful, and for quite a while she was the only woman in all of engineering at Princeton. Later, she been the first tenured woman in engineering at Princeton. The balance is not perfect now, but I am happy to say today she is not the only tenured professor in engineering.

One day I was talking with a colleague from another engineering department. He asked me, “How many women did we have in Computer Science?” I immediately answered one—Andrea. Then, I asked the obvious question, “How many do you have in your department?” My colleague thought a long time—I guessed he must be adding up women faculty. Finally he said, “None.”

I am telling this story to show how subtle the issues can be concerning women in science. I gave him a very hard time: I said, you can take a long time to add up the cardinality of a big set, but you cannot take any time to figure out the cardinality of the empty-set. What was he thinking?

The Two Rule

One rule is the two rule. I learned this rule from my wife, Judith Norback, who is a Ph.D in psychology from Princeton. Often in an attempt to create balance—especially in academia—one woman will be placed on each committee. A woman. One. It is good to have women on committees, but putting one on does not usually work well.

The difficulty is a lone person on any committee is hard pressed to speak out and really make a difference. A lone person of any minority—the principle is the same for other minorities—is not in general the right choice. There are exceptions to this rule, but studies show one person, from a minority, is not nearly as effective as two. This is the rule of two. If possible always place two women on a group or a committee. They will be immensely more effective, if there are two.

Of course in order to make this happen the academic organization needs to have at least two women—another argument for more diversity. I do not claim to completely understand the reason the “two rule” works, but it does. Try it.

The Out Rule

Another rule is the out rule. This I learned from long experience watching fellow computer scientists operate—especially in academia. In the old days when wagon trains were attacked, they were taught to “circle the wagons.” In computer science we still do this, as do most other areas of science and academia.

However, in computer science the joke—unfortunately all too true—is we shoot the wrong way. We shoot in, not out. Hence, the rule of out: when attacked remember to shoot out, not in toward each other.

With all due respect, I have long noticed women on various committees often ignore this simple rule. They shoot in toward their fellow women. I have been on many committees of all kinds—award, hiring, program, and other types—and have noticed the women on the committee are often the hardest on women candidates. I have often argued for a women candidate for something, and noticed the other faculty were generally supportive. However, the women faculty in the room would frequently agree with me on the big points, yet attack the candidate on some minor points. Do not shoot in, shoot out.

I am not arguing for a decrease in standards. Never. I am arguing for both male and female faculty to be sure they are as objective as possible. I certainly am far from perfect, but I do think more attention should be paid to being aware of the out rule.

The Zero Rule

I am trying to be constructive and not writing a “moral with a tale,” but one last rule is critical in my mind. The zero rule is just this: there must be zero—no—tolerance for any jokes, comments, stories, of any kind that put down women. I have heard many of them over the years, and have always immediately complained about them. I believe such statements cause many women to go into other areas of science. We must be intolerant of any comments of this kind.

Ada As The First Programmer

It seems to me clear Lady Lovelace was more than the first programmer: she had great insight into what a computing device could or could not do. Here is a direct quote from her—it could have been written the other day. It would be interesting to see what she would think about computing today—she wrote this in 1842.

It is desirable to guard against the possibility of exaggerated ideas that might arise as to the powers of the Analytical Engine. In considering any new subject, there is frequently a tendency, first, to overrate what we find to be already interesting or remarkable; and, secondly, by a sort of natural reaction, to undervalue the true state of the case, when we do discover that our notions have surpassed those that were really tenable.

The Analytical Engine has no pretensions whatever to originate anything. It can do whatever we know how to order it to perform. It can follow analysis; but it has no power of anticipating any analytical relations or truths. Its province is to assist us in making available what we are already acquainted with. This it is calculated to effect primarily and chiefly of course, through its executive faculties; but it is likely to exert an indirect and reciprocal influence on science itself in another manner. For, in so distributing and combining the truths and the formula of analysis, that they may become most easily and rapidly amenable to the mechanical combinations of the engine, the relations and the nature of many subjects in that science are necessarily thrown into new lights, and more profoundly investigated. This is a decidedly indirect, and a somewhat speculative, consequence of such an invention. It is however pretty evident, on general principles, that in devising for mathematical truths a new form in which to record and throw themselves out for actual use, views are likely to be induced, which should again react on the more theoretical phase of the subject. There are in all extensions of human power, or additions to human knowledge, various collateral influences, besides the main and primary object attained.

To really appreciate her brilliant mind, read all her comments here. This is the front piece to the document:

Open Problems

The main open problem is continue to try and increase the number of women in all aspects of science, especially computing. I think there are already many good ideas on how to do this—perhaps what we need is to execute the best of these ideas. In any event have a happy Ada Lovelace Day. It would have been a great privilege to have met her.

How an NFL quarterback taught complex analysis

Frank Ryan is not just a theorist, but is also a mathematician who specialized in complex analysis. He got his Ph.D from Rice University on “A Characterization of the Set of Asymptotic Values of a Function Holomorphic in the Unit Disc,” in 1965.

Today I would like to talk about how we learn, and how we teach.

I have a story to tell about Ryan—I just shared it the other day with Alan Kay—and he insisted I had to post on it. Right away. So here it is Alan.

Ryan was not only a professor at Case Western Reserve, where I was an undergraduate in the ’60’s, but he was at the same time the starting quarterback for the Cleveland Browns. The starting quarterback for a NFL football team, and a professor with a full teaching load. During the football season he taught his class early in the week, and then on Sundays he was behind the center taking the ball. Handing it off, throwing passes, and getting sacked—like any other quarterback in the league. He was one of the best quarterbacks of his day, and had great successes. For example, he appeared in three straight Pro Bowls.

I still remember listening to him explain a fine point in complex analysis on Tuesday, and then watching him on TV getting tackled, on Sunday. It was hard to believe, even though I knew it was the same person, the player being taken hard to the ground was my professor. The player being tackled knew how to throw a perfect spiral 40 yards, and also could go to the board and prove Picard’s Little Theorem. Amazing.

Today, I believe there is no chance a quarterback—or any player—on an NFL team would want to or be allowed to be a full time professor during the season. The game has gotten very technical, the pay is too great, and the stakes are too high for any team to allow this to happen. But, back when I was taking complex analysis it happened. Really.

I still recall wincing when he got sacked during one tough game. Then, a few days later I saw him in class, with his arm in a sling and his speech slightly slurred. I assumed the slurring came from pain killers he was taking for the shoulder injury. Sling or not we pushed on, deeper into the beautiful structure of complex analysis.

Ryan’s Seminar

As an undergraduate I took a seminar with Ryan on complex analysis. This was one of strangest classes I ever had in mathematics, and probably one of the best. It was a small group, about eight of us, taking his class on advanced topics in complex analysis. The course was based on a thin monograph, but Ryan did zero lecturing. Instead, at the beginning of each class he ran the following protocol:

He would shuffle up a deck of playing cards, and we all would gather around a table.
He then would deal out the cards one at a time face up on the table: we each got the cards landing in front of us.
There were two bad cards: the Queen of Spades and the Queen of Diamonds.

Once these two cards were dealt, the class really began. The player who was “lucky” enough to get the Queen of Spades went to the blackboard and was expected to start explaining from exactly where we stopped at the end of the last class. You were allowed to use the book or notes and you typically explained the proof of some theorem.

After half the class was over, it was the other “lucky” person—who got the Queen of Diamonds—to take over from the first student.

Sounds not too hard, but it was a killer. The main problem was the thin book’s concept of a proof was not a detailed proof, but at best a high level sketch. Proofs were filled with phrases like: “it is easy to see that is continuous,” or “it clearly follows that is never in the unit disk.” The person at the board would say these phrases, but Ryan would usually jump in with a simple “why?” Why indeed was continuous? Why indeed was never ?

Sometimes the student at the board could answer and we moved on to the next point, but often they got stuck. The rest of us could help and make suggestions—of course we were usually lost too. The class might stay on a single question for the entire first half of class. If this happened, then the next student would have to get up and try to convince Ryan why it was true.

The student who was up second had an interesting prediction problem. They had 45 minutes to prepare for their turn, but they had no idea where the first student would get to in their 45 minutes. I remember being in this position—half listening to the class while trying to guess where I would have to start explaining.

The cards, the Queen of Spades and the Queen of Diamonds, were picked as the “bad” cards for a reason. The first is, of course, the worst card to get in the game of hearts: the player who is stuck with this card gets 13 points. The second is based on the original movie “The Manchurian Candidate”. In the movie this card is used to trigger Laurence Harvey to follow orders without question. One of the great movies, in my opinion

Learning Methods

I sometimes wonder how we learn and how we should teach. A while ago I posted on EEE and still think about this—the Educational Extinct Event.

I hated Ryan’s class. One consequence of the way the class was organized was I learned relatively little material. In a more conventional class I think I would have learned more theorems, more proofs, more concrete facts from complex analysis.

I loved Ryan’s class. The class taught me to think on my feet—literally. I learned how to read a proof and find the “gaps” I needed to fill in myself. I may have learned relatively little complex analysis, but I learned a great deal about mathematics in general.

By the way Picard’s Little Theorem, named for Charles Picard, is:

Theorem: Suppose is an entire function. Then, the range of is either the whole complex plane or the plane minus a single point.

The function shows the theorem is best. A very beautiful theorem.

Open Problems

The main open problem is this: what is the best way to present mathematical material? I am especially interested in hearing what you think about Ryan’s method. Did you have some similar experience? Should we teach more classes in this way? Or is it better to cover lots of material?

I am currently at the major meeting of the ASL—the Association of Symbolic Logic. I will give you an update on what it is like at a logic meeting. The reason I am here is to chair a session held in honor of the Gödel lecturer, who this year is our own Sasha Razborov.

I love working in the shell. Mastery of shell lets you get things done in seconds, rather than minutes or hours, if you chose to write a program instead.

In this article I’d like to explain the top one-liners from the commandlinefu.com. It’s a user-driven website where people get to choose the best and most useful shell one-liners.

But before I do that, I want to take the opportunity and link to a few of my articles that I wrote some time ago on working efficiently in the command line:

Working Efficiently in Bash (Part I).
Working Efficiently in Bash (Part II).
The Definitive Guide to Bash Command Line History.
A fun article on Set Operations in the Shell.
Another fun article on Solving Google Treasure Hunt in the Shell.

And now the explanation of top one-liners from commandlinefu.

Update: Russian translation available.

#1. Run the last command as root
$ sudo !!
We all know what the sudo command does - it runs the command as another user, in this case, it runs the command as superuser because no other user was specified. But what’s really interesting is the bang-bang !! part of the command. It’s called the event designator. An event designator references a command in shell’s history. In this case the event designator references the previous command. Writing !! is the same as writing !-1. The -1 refers to the last command. You can generalize it, and write !-n to refer to the n-th previous command. To view all your previous commands, type history.

This one-liner is actually really bash-specific, as event designators are a feature of bash.

I wrote about event designators in much more detail in my article “The Definitive Guide to Bash Command Line History.” The article also comes with a printable cheat sheet for working with the history.

#2. Serve the current directory at http://localhost:8000/
$ python -m SimpleHTTPServer
This one-liner starts a web server on port 8000 with the contents of current directory on all the interfaces (address 0.0.0.0), not just localhost. If you have “index.html” or “index.htm” files, it will serve those, otherwise it will list the contents of the currently working directory.

It works because python comes with a standard module called SimpleHTTPServer. The -m argument makes python to search for a module named SimpleHTTPServer.py in all the possible system locations (listed in sys.path and $PYTHONPATH shell variable). Once found, it executes it as a script. If you look at the source code of this module, you’ll find that this module tests if it’s run as a script if __name__ == '__main__', and if it is, it runs the test() method that makes it run a web server in the current directory.

To use a different port, specify it as the next argument:

$ python -m SimpleHTTPServer 8080
This command runs a HTTP server on all local interfaces on port 8080.

#3. Save a file you edited in vim without the needed permissions
:w !sudo tee %
This happens to me way too often. I open a system config file in vim and edit it just to find out that I don’t have permissions to save it. This one-liner saves the day. Instead of writing the while to a temporary file :w /tmp/foobar and then moving the temporary file to the right destination mv /tmp/foobar /etc/service.conf, you now just type the one-liner above in vim and it will save the file.

Here is how it works, if you look at the vim documentation (by typing :he :w in vim), you’ll find the reference to the command :w !{cmd} that says that vim runs {cmd} and passes it the contents of the file as standard input. In this one-liner the {cmd} part is the sudo tee % command. It runs tee % as superuser. But wait, what is %? Well, it’s a read-only register in vim that contains the filename of the current file! Therefore the command that vim executes becomes tee current_filename, with the current directory being whatever the current_file is in. Now what does tee do? The tee command takes standard input and write it to a file! Rephrasing, it takes the contents of the file edited in vim, and writes it to the file (while being root)! All done!

#4. Change to the previous working directory
$ cd -
Everyone knows this, right? The dash “-” is short for “previous working directory.” The previous working directory is defined by $OLDPWD shell variable. After you use the cd command, it sets the $OLDPWD environment variable, and then, if you type the short version cd -, it effectively becomes cd $OLDPWD and changes to the previous directory.

To change to a directory named “-“, you have to either cd to the parent directory and then do cd ./- or do cd /full/path/to/-.

#5. Run the previous shell command but replace string “foo” with “bar”
$ ^foo^bar^
This is another event designator. This one is for quick substitution. It replaces foo with bar and repeats the last command. It’s actually a shortcut for !!:s/foo/bar/. This one-liner applies the s modifier to the !! event designator. As we learned from one-liner #1, the !! event designator stands for the previous command. Now the s modifier stands for substitute (greetings to sed) and it substitutes the first word with the second word.

Note that this one-liner replaces just the first word in the previous command. To replace all words, add the g modifer (g for global):

$ !!:gs/foo/bar
This one-liner is also bash-specific, as event designators are a feature of bash.

Again, see my article “The Definitive Guide to Bash Command Line History.” I explain all this stuff in great detail.

#6. Quickly backup or copy a file
$ cp filename{,.bak}
This one-liner copies the file named filename to a file named filename.bak. Here is how it works. It uses brace expansion to construct a list of arguments for the cp command. Brace expansion is a mechanism by which arbitrary strings may be generated. In this one-liner filename{,.bak} gets brace expanded to filename filename.bak and puts in place of the brace expression. The command becomes cp filename filename.bak and file gets copied.

Talking more about brace expansion, you can do all kinds of combinatorics with it. Here is a fun application:

$ echo {a,b,c}{a,b,c}{a,b,c}
It generates all the possible strings 3-letter from the set {a, b, c}:

aaa aab aac aba abb abc aca acb acc
baa bab bac bba bbb bbc bca bcb bcc
caa cab cac cba cbb cbc cca ccb ccc

And here is how to generate all the possible 2-letter strings from the set of {a, b, c}:

$ echo {a,b,c}{a,b,c}

It produces:

aa ab ac ba bb bc ca cb cc

If you liked this, you may also like my article where I defined a bunch of set operations (such as intersection, union, symmetry, powerset, etc) by using just shell commands. The article is called “Set Operations in the Unix Shell.” (And since I have sets in the shell, I will soon write articles on on “Combinatorics in the Shell” and “Algebra in the Shell“. Fun topics to explore. Perhaps even “Topology in the Shell” :))

#7. mtr - traceroute and ping combined
$ mtr google.com
MTR, bettern known as “Matt’s Traceroute” combines both traceroute and ping command. After each successful hop, it sends a ping request to the found machine, this way it produces output of both traceroute and ping to better understand the quality of link. If it finds out a packet took an alternative route, it displays it, and by default it keeps updating the statistics so you knew what was going on in real time.

#8. Find the last command that begins with “whatever,” but avoid running it
$ !whatever:p
Another use of event designators. The !whatever designator searches the shell history for the most recently executed command that starts with whatever. But instead of executing it, it prints it. The :p modifier makes it print instead of executing.

This one-liner is bash-specific, as event designators are a feature of bash.

Once again, see my article “The Definitive Guide to Bash Command Line History.” I explain all this stuff in great detail.

#9. Copy your public-key to remote-machine for public-key authentication
$ ssh-copy-id remote-machine
This one-liner copies your public-key, that you generated with ssh-keygen (either SSHv1 file identity.pub or SSHv2 file id_rsa.pub) to the remote-machine and places it in ~/.ssh/authorized_keys file. This ensures that the next time you try to log into that machine, public-key authentication (commonly referred to as “passwordless authentication.”) will be used instead of the regular password authentication.

If you wished to do it yourself, you’d have to take the following steps:

your-machine$ scp ~/.ssh/identity.pub remote-machine:
your-machine$ ssh remote-machine
remote-machine$ cat identity.pub >> ~/.ssh/authorized_keys

This one-liner saves a great deal of typing. Actually I just found out that there was a shorter way to do it:

your-machine$ ssh remote-machine 'cat >> .ssh/authorized_keys' < .ssh/identity.pub

#10. Capture video of a linux desktop
$ ffmpeg -f x11grab -s wxga -r 25 -i :0.0 -sameq /tmp/out.mpg
A pure coincidence, I have done so much video processing with ffmpeg that I know what most of this command does without looking much in the manual.

The ffmpeg generally can be descibed as a command that takes a bunch of options and the last option is the output file. In this case the options are -f x11grab -s wxga -r 25 -i :0.0 -sameq and the output file is /tmp/out.mpg.

Here is what the options mean:

-f x11grab makes ffmpeg to set the input video format as x11grab. The X11 framebuffer has a specific format it presents data in and it makes ffmpeg to decode it correctly.
-s wxga makes ffmpeg to set the size of the video to wxga which is shortcut for 1366×768. This is a strange resolution to use, I’d just write -s 800x600.
-r 25 sets the framerate of the video to 25fps.
-i :0.0 sets the video input file to X11 display 0.0 at localhost.
-sameq preserves the quality of input stream. It’s best to preserve the quality and post-process it later.

You can also specify ffmp[…]