A MIT class about advanced data structures

Ed is the standard text editor!

How I boosted my Vim
Published: September 14, 2010

A few weeks ago, I felt inspired by articles from Jeff
Kreeftmeijer and Armin
Ronacher. I took some
time to configure and fine-tune my Vim environment. A lot of new stuff made it
into my .vimrc file and my .vim directory. This blog post is a summary
describing what I’ve added and how I use it in my daily work.

Before doing anything else, make sure you have the following line in your
.vimrc file:

" This must be first, because it changes other options as side effect
set nocompatible
Step 0: make the customization process easier
Before starting configuring, it’s useful to install
pathogen. Plugins in
Vim are files that you drop in subdirectories of your .vim/ directory. Many
plugins exist of only a single file that should be dropped in .vim/plugin,
but some exist of multiple files. For example, they come with documentation,
or ship syntax files. In those cases, files need to be dropped into
.vim/doc and .vim/syntax. This makes it difficult to remove the plugin
afterwards. After installing pathogen, you can simply unzip a plugin
distribution into .vim/bundle/myplugin, under which the required
subdirectories are created. Removing the plugin, then, is as simple as
removing the myplugin directory.

So, download pathogen.vim, move it into the .vim/autoload directory (create
it if necessary) and add the following lines to your .vimrc, to activate it:

" Use pathogen to easily modify the runtime path to include all
" plugins under the ~/.vim/bundle directory
call pathogen#helptags()
call pathogen#runtime_append_all_bundles()
Besides that, this is a little tweak that is a time-saver while you’re building
up your .vimrc:

" Quickly edit/reload the vimrc file
nmap <silent> <leader>ev :e $MYVIMRC<CR>
nmap <silent> <leader>sv :so $MYVIMRC<CR>
This maps the ,ev and ,sv keys to edit/reload .vimrc. (I got this from
Derek Wyatt’s .vimrc file.)

Notice that I’ve remapped the leader key to , (comma) instead of the default
\ (backslash), just because I like it better. Since in Vim’s default
configuration, almost every key is already mapped to a command, there needs to
be some sort of standard “free” key where you can place custom mappings under.
This is called the “mapleader”, and can be defined like this:

" change the mapleader from \ to ,
let mapleader=","
Change Vim behaviour
One particularly useful setting is hidden. Its name isn’t too descriptive,
though. It hides buffers instead of closing them. This means that you can
have unwritten changes to a file and open a new file using :e, without being
forced to write or undo your changes first. Also, undo buffers and marks are
preserved while the buffer is open. This is an absolute must-have.

set hidden
These are some of the most basic settings that you probably want to enable,
too:

set nowrap " don't wrap lines
set tabstop=4 " a tab is four spaces
set backspace=indent,eol,start
" allow backspacing over everything in insert mode
set autoindent " always set autoindenting on
set copyindent " copy the previous indentation on autoindenting
set number " always show line numbers
set shiftwidth=4 " number of spaces to use for autoindenting
set shiftround " use multiple of shiftwidth when indenting with '<' and '>'
set showmatch " set show matching parenthesis
set ignorecase " ignore case when searching
set smartcase " ignore case if search pattern is all lowercase,
" case-sensitive otherwise
set smarttab " insert tabs on the start of a line according to
" shiftwidth, not tabstop
set hlsearch " highlight search terms
set incsearch " show search matches as you type
There is a lot more goodness in my
.vimrc file, which is put in
there with a lot of love. I’ve commented most of it, too. Feel free to poke
around in it.

Also, I like Vim to have a large undo buffer, a large history of commands,
ignore some file extensions when completing names by pressing Tab, and be
silent about invalid cursor moves and other errors.

set history=1000 " remember more commands and search history
set undolevels=1000 " use many muchos levels of undo
set wildignore=*.swp,*.bak,*.pyc,*.class
set title " change the terminal's title
set visualbell " don't beep
set noerrorbells " don't beep
Oh, and man… never ever let Vim write a backup file! They did that in the
70’s. Use modern ways for tracking your changes, for
God’s sake.

set nobackup
set noswapfile
Use file type plugins
Vim can detect file types (by their extension, or by peeking inside the file).
This enabled Vim to load plugins, settings or key mappings that are only useful
in the context of specific file types. For example, a Python syntax checker
plugin only makes sense in a Python file. Finally, indenting intelligence is
enabled based on the syntax rules for the file type.

" set filetype stuff to on
filetype on
filetype plugin on
filetype indent on
To set some file type specific settings, you can now use the following:

autocmd filetype python set expandtab
To remain compatible with older versions of Vim that do not have the autocmd
functions, always wrap those functions inside a block like this:

if has('autocmd')
...
endif
Enable syntax highlighting
Somewhat related to the file type plugins is the syntax highlighting of
different types of source files. Vim uses syntax definitions to highlight
source code. Syntax definitions simply declare where a function name starts,
which pieces are commented out and what are keywords. To color them, Vim uses
colorschemes. You can load custom color schemes by placing them in
.vim/colors, then load them using the colorscheme command. You have to try
what you like most. I like
mustang a
lot.

if &t_Co >= 256 || has("gui_running")
colorscheme mustang
endif

if &t_Co > 2 || has("gui_running")
" switch syntax highlighting on, when the terminal has colors
syntax on
endif
In this case, mustang is only loaded if the terminal emulator Vim runs in
supports at least 256 colors (or if you use the GUI version of Vim).

Hint: if you’re using a terminal emulator that can show 256 colors, try
setting TERM=xterm-256color in your terminal configuration or in your shell’s
.rc file.

Change editing behaviour
When you write a lot of code, you probably want to obey certain style rules.
In some programming languages (like Python), whitespace is important, so you
may not just swap tabs for spaces and even the number of spaces is important.

Vim can highlight whitespaces for you in a convenient way:

set list
set listchars=tab:>.,trail:.,extends:#,nbsp:.
This line will make Vim set out tab characters, trailing whitespace and
invisible spaces visually, and additionally use the # sign at the end of
lines to mark lines that extend off-screen. For more info, see :h listchars.

In some files, like HTML and XML files, tabs are fine and showing them is
really annoying, you can disable them easily using an autocmd declaration:

autocmd filetype html,xml set listchars-=tab:>.
One caveat when setting listchars: if nothing happens, you have probably not
enabled list, so try :set list, too.

Pasting large amounts of text into Vim
Every Vim user likes to enable auto-indenting of source code, so Vim can
intelligently position you cursor on the next line as you type. This has one
big ugly consequence however: when you paste text into your terminal-based Vim,
Vim cannot know it is coming from a paste. To Vim, it looks like text entered
by someone who can type incredibly fast :) Since Vim thinks this is regular
key strokes, it applies all auto-indenting and auto-expansion of defined
abbreviations to the input, resulting in often cascading indents of paragraphs.

There is an easy option to prevent this, however. You can temporarily switch
to “paste mode”, simply by setting the following option:

set pastetoggle=<F2>
Then, when in insert mode, ready to paste, if you press <F2>, Vim will switch
to paste mode, disabling all kinds of smartness and just pasting a whole buffer
of text. Then, you can disable paste mode again with another press of <F2>.
Nice and simple. Compare paste mode disabled vs enabled:

Enable the mouse
While using the mouse is considered a deadly sin among Vim users, there are a
few features about the mouse that can really come to your advantage. Most
notably—scrolling. In fact, it’s the only thing I use it for.

Also, if you are a rookie Vim user, setting this value will make your Vim
experience definitively feel more natural.

To enable the mouse, use:

set mouse=a
However, this comes at one big disadvantage: when you run Vim inside a
terminal, the terminal itself cannot control your mouse anymore. Therefore,
you cannot select text anymore with the terminal (to copy it to the system
clipboard, for example).

To be able to have the best of both worlds, I wrote this simple Vim plugin:
vim-togglemouse. It maps <F12> to
toggle your mouse “focus” between Vim and the terminal.

Small plugins like these are really useful, yet have the additional benefit of
lowering the barrier of learning the Vim scripting language. At the core, this
plugin exists of only one simple function:

fun! s:ToggleMouse()
if !exists("s:old_mouse")
let s:old_mouse = "a"
endif

if &mouse == ""
let &mouse = s:old_mouse
echo "Mouse is for Vim (" . &mouse . ")"
else
let s:old_mouse = &mouse
let &mouse=""
echo "Mouse is for terminal"
endif
endfunction
Get efficient: shortcut mappings
The following trick is a really small one, but a super-efficient one, since it
strips off two full keystrokes from almost every Vim command:

nnoremap ; :
For example, to save a file, you type :w normally, which means:

Press and hold Shift
Press ;

Release the Shift key
Press w

Press Return
This trick strips off steps[…]

The contributions to the original binary search thread continue to trickle in, and now stand at an astonishing tally of 679 comments, most of them containing code.  Thanks once more to all of you who’ve attempted this challenge, and to everyone who’s commented.

In one of the more interesting comments, Darius Bacon tested a sample of 20 of the Python submissions, and found that exactly 10% of them both passed the functional test and appeared to run in O(log n) time — which of course is exactly in line with Jon Bentley’s original statistic, that 10% of the professional programmers he’d examined were able to write correct binary search code (albeit under rather different conditions).  It subsequently became apparent, though, that Darius’s testing code was overly strict, and that a further two of the sampled routines did run correctly (though not necessarily in O(log n) time).  Still — it’s a surprisingly low hit-rate, especially when you bear in mind that, contrary to the rules, many of the programmers did use testing to help them develop the code. (You should read the second linked comment, as it has plenty of other interesting observations, too.)

[Update, an hour or two later: as Darius Bacon points out in a comment below, I misinterpreted his results.  Once the testing code had been fixed, his sample of 21 routines found 9 that passed all test, of which 6 were O(log n).]

“It’s dumb not to test”
By far the most common comment on this challenge was that it’s dumb to try to write correct code without testing.  Many, many people made this point, not only here but especially on Reddit.  For example, someone calling him/herself K wrote: “ I don’t really see a point in this exercise – are you (or the author of the book) implying that if a programmer can’t implement this on first try, without testing, he’s not as good as one who can?  IMO, it’s not a good metric for the ability of the programmer.”

First of all, let me be very clear what I wasn’t saying: I was not saying that it’s a bad thing to test your code.  I am very much in favour of testing.  So is Jon Bentley.  That’s because neither of us is insane.

The point is this: testing is only one of the weapons in our armoury, and it’s one that has recently become so fashionable that a lot of programmers are in danger of forgetting the others.  Although testing is valuable, even indispensible, it is also limited in important ways, and we need to have facility with other techniques as well.

Here are three limitations of testing:

Tests can only show the presence of bugs, not their absence
Tests can be buggy, just like tested code
Tests increase confidence, not understanding

I’ll expand on each of these below.  Before I do that, let me say one more time that testing is good.  Please do not respond in the comments saying “Mike is a doofus because he says testing is bad.”  Testing is very good.  But like so many very good things — Doctor Who, sushi, Wi-Fi, Gold Miner ale — it turns out that it’s not the only very good thing you need.

So the purpose of the write-your-code-without testing exercise was not to discard testing because it’s useless; but, precisely because testing is useful, it’s important that we sometimes force ourselves to walk without that particular crutch … and perhaps we’ll find out how atrophied our muscles have become.  Then we can discover what other areas we need to concentrate on, what techniques we need to bone up on, what tools we need to relearn and what exercises we need to do.

(I’m assuming here that we aspire to be excellent, rather than merely adequate, programmers.)

Tests can only show the presence of bugs, not their absence
I wrote this heading off the top of my head, then looked at it and thought it sounded a bit familiar.  When I grepped around, I found that it was, almost word for word, a quote from an old friend:

Testing can show the presence of bugs, but not their absence.
– Edsgar W. Dijkstra, University of Texas

So I guess I am in good company in making this point.  To say the same thing in more general terms, as Tom Holtz is fond of saying, “Absence of evidence is not evidence of absence”.  (He’s usually talking about fossils in a particular rock formation, but the principle is good more widely.  And to be fair, absence of evidence is indeed evidence of absence, but it’s not proof of absence.)

You can test all you want; but all you have shown at any given point is that you have not yet found any bugs.  We can see this principle at work in several of the posted solutions — I don’t want to pick on individuals, so I won’t name names, but I’ve seen submissions tagged with statements like “Mine works”, “works for me” and “no errors at the first try”, which have been subsequently shown to be buggy — presumably because the author’s own tests didn’t test all the edge cases.

Again, this is not to say that testing is useless: each passed test can legitimately increase confidence in the tested code.  But it can never get you all the way.  For that, you need something different.

Tests can be buggy, just like tested code
“Quis custodiet ipsos custodes?”, asks Juvenal (and let us not forget that quidquid latine dictum sit, altum viditur).  ”Who will watch the watchmen?” replies Alan Moore.  ”Who will test the tests?”, say I.

This is another problem that cropped up several times in the comments.  For example:

“My code worked the first time, but my test had a bug.” — nicholas.
“Worked at first try though I did test it before submitting here, which took some time before I realized that while the binary search was working, my small test code was faulty.” — Robert Leffmann.
“I felt my heart sink when it threw an exception on first run, but it turned out the error was forgetting to sort the test arrays in the test code, so all was ok.” — Paddy.
“Had some bugs in the harness itself, but didn’t catch any in the binary search method.” — Dan Carroll.

We’ve all been there, I’m sure.  As it happen, this very afternoon I spent an unpleasant hour or so trying to debug the test suite of a Perl module that I was building a Debian package for.  We fall too easily into talking as though code and tests are two different things, but tests are code.  We know that we’re not clever enough to write correct code all the time, so why would we think that we can reliably write correct tests?

Actually, there are two reason why this argument isn’t as strong as it sounds.  One is that the code that makes up test suites is often — not always, but often — much simpler than the code being tested.  In which case it’s more likely to be correct.  I’ve been in situations where that’s not true, where the testing code is itself a major piece of work; but I admit those cases are the exception.  The second reason why this argument is not super-strong is this: writing tests lets you triangulate.  You’re looking at the same problem from two different directions, and if your tests are broken there’s a fair chance that your correct code will help you spot that fact and fix it.  (If you’re really unlucky, your code and your test will both be broken but in such a way that the deficiencies of one patch over the mistakes in the other; but that seems to be rare.)

I’m not going to labour the tests-can-be-wrong point too much, just as I skimmed quickly over tests-can’t-show-the-absence-of-bugs, because I want to get on to the meat: the real reason why testing is in desperate danger of being overhyped.  These two points have just been a prelude; now on to the fugue.

Tests increase confidence, not understanding
Here we reach my core point.  It’s this.  If you had to boil down the whole programming skill-set to a single core skill — a completely general one that applies across all that we do — what would you choose?  I can imagine various different answers, but for me the answer would be: thinking clearly.  I’d argue that the essence of good programming is thinking clearly about the problem; understanding; grokking.

Testing a piece of code is essentially a black-box process.  If you hack together a binary search routine, you can and will write tests for it that are not based on how the code works, but only on what it claims to do.  This is right and good — it’s proper separation of concerns.  But what it means is that writing and running tests does not in itself increase your understanding of the code being tested.

And we need to understand.

In the case of binary search (and let’s all remember that this was chosen because it’s a particularly straightforward algorithm), we’ve seen posted code that does all sorts of horrible things — some of them kind of harmless; some of them with performance implications (like all those array-slicing Python implementations that run in O(n) time, and so are no better than a trivial linear search); and some positively detrimental.  The point is this: no amount of testing will, in itself, give you any insight into these coding mistakes.

(Aaaaand I am going to say it yet again, in the desperate hope of not being misunderstood: this does not mean that I think testing is bad; it means that I think it serves some purposes but not all.)

If you’re not convinced, consider this pair of comments.  From Jonathan Deutsch: “Writing code without testing is akin to doing math without a calculator”; and from Matthias Goergens: “Arithmetic without a calculator borders on nonsense.  But for analysis, algebra or proofs in general, you’d need a very advanced calculator.”  Unit tests are great for verifying your arithmetic; but they don’t help you to think through your calculus.  For that, you need to think.  There’s no way out of it.  Sometimes, no amount of agile, pattern-oriented, test-driven, refac[…]

Hugh Pickens writes "The Register reports that experts from some 30 organizations worldwide have compiled 2010's list of the 25 most dangerous programming errors along with a novel way to prevent them: by drafting contracts that hold developers responsible when bugs creep into applications. The 25 flaws are the cause of almost every major cyber attack in recent history, including the ones that recently struck Google and 33 other large companies, as well as breaches suffered by military systems and millions of small business and home users. The top 25 entries are prioritized using inputs from over 20 different organizations, who evaluated each weakness based on prevalence and importance. Interestingly enough the classic buffer overflow ranked 3rd in the list while Cross-site Scripting and SQL Injection are considered the 1-2 punch of security weaknesses in 2010. Security experts say business customers have the means to foster safer products by demanding that vendors follow common-sense safety measures such as verifying that all team members successfully clear a background investigation and be trained in secure programming techniques. 'As a customer, you have the power to influence vendors to provide more secure products by letting them know that security is important to you,' the introduction to the list states and includes a draft contract with the terms customers should request to enable buyers of custom software to make code writers responsible for checking the code and for fixing security flaws before software is delivered."
Read more of this story at Slashdot.

bgweber writes "The 2010 conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE 2010) will be hosting a StarCraft AI competition as part of the conference program. This competition enables academic researchers to evaluate their AI systems in a robust, commercial RTS environment. The competition will be held in the weeks leading up to the conference. The final matches will be held live at the conference with commentary. Exhibition matches will also be held between skilled human players and the top-performing bots."
Read more of this story at Slashdot.