Hello Debian, my old friend

I’ve been using Linux as my primary operating system since early 2000. Similarly to many Linuxers, I’ve done my share of distro hopping. Here is, as far as I can recall, some of the distributions that I’ve used seriously (where seriously means for more than 6 months at one time) in order:

  • Mandrake (yes, that was before they changed their name)
  • Slackware
  • Debian
  • Ubuntu
  • Arch Linux
  • Lubuntu

Though I had known of Linux for a couple of years, it was only when I bought an issue of Linux France magazine that came with a Mandrake 6.1 CD and clear instructions that I decided to install Linux. I was quite lost at first, but after buying O’Reilly’s “Running Red Hat Linux”, I could do most of what I wanted to do.

Later on, I decided to try Slackware, because apparently that was for more hardcore users, and I wanted to be hardcore. Then came Debian, because I had heard great things about apt-get (and boy was I impressed the first time I used it!). I used Debian for a solid 4-5 years before Ubuntu appeared on the radar and started making a solid impression on the Linux world. I decided to try it out, and I really liked that it took away some of the drudgery of Debian.

I then had a foray of a year and a half with Arch Linux before I came back to Ubuntu, but this time I used Lubuntu since the first thing I did after booting Ubuntu was to uninstall over 100 packages relating to Gnome. As time went on, I kept using Lubuntu, but I became less and less happy with it, always hoping that the next major release would solve my issues, but it became clear that it wouldn’t happen.

Among the issues I had with Ubuntu were:

  • The upgrade process never worked for me, I always had weird issues that were usually resolved by reinstalling the entire OS.
  • The release process produced distributions that were less and less stable.
  • Ubuntu quickly pushed new products that didn’t feel like they had anything to do with the Unix philosophy
  • I had some weird bugs that I reported, but went without solutions.
    • If I used lightdm and the french Canadian keyboard layout, pressing and holding certain keys (the right and down arrow keys for examples) would not repeat them; changing the login manager or the keymap fixed the issue, but this was weird.
    • plymouthd (a piece of software that I just don’t understand) constantly used 5-7% of my CPU. Uninstalling it was not an option since so many packages depend on it. Disabling it caused other weird issues with the display
  • It seems that Ubuntu is becoming less and less a Linux distribution, and more and more its own OS.

Last week, I just had enough. I want a stable and simple operating system, and I was no longer getting that from Ubuntu. Debian Wheezy had been released a few weeks earlier, and I decided that it was time to go back to my ol’ trusty distro.

I downloaded the LXDE Live DVD, booted it and less than an hour later the system was installed and ready to roll. I added some repositories to have access to Chrome and the latest Emacs snapshots, the only two programs that I want to be as up to date as possible. In less than two hours, I had a system that looked and worked exactly like my Lubuntu setup (except that the load average was closer to 0.0 than 1.0 as with Lubuntu!)

It’s been a week, and I have had no problems with Debian. The first time I used Ubuntu was because of the promise of easy hardware configuration; Debian Wheezy has that. My sound card and video card were automatically recognized and properly configured, I only had to install firmware-realtek to get my Wifi card working, my integrated webcam worked without me having to install or configure anything, so did my multiple gaming controllers.

The Debian folks have produced a truly fine operating system. For the next two years, I’ll be doing my M.Sc and I most likely won’t have the time or the inclination to fiddle and hack my OS, so I think that this stable Debian installation will suit me perfectly.

It’s good to be back!

Sorting algorithms in OCaml

We had a mini snow storm in Montreal this weekend, so instead of going to my usual Saturday afternoon chess club, I spent the day writing sorting algorithms in OCaml. It had been a while since I’d revised my notes from my algorithms class (which I finished two years ago), and I thought it’s be a nice time to do some review.

I implemented the following algorithms:

  • Bubble sort, O(n^2)
  • Selection sort, O(n^2)
  • Insertion sort, O(n^2)
  • Merge sort, O(n lg n)
  • Quick sort, O(n lg n)*

* Pivots are chosen at random.

I also wrote a small driver program to test them all on bunch of arrays. Here’s a sample run:

$ ./bench.native --iters 250 --max-elems 2500
100.00%
Algorithm                       : Total		Average
============================================================
insertion sort                  : 2.142468	0.008570
bubble sort                     : 5.517859	0.022071
selection sort                  : 2.795310	0.011181
merge sort                      : 0.115057	0.000460
merge sort + selection sort     : 0.100913	0.000404
merge sort + insertion sort     : 0.098223	0.000393
quicksort 1                     : 0.098276	0.000393
quicksort 2                     : 0.090065	0.000360
Array.sort                      : 0.106113	0.000424
Array.stable_sort               : 0.071891	0.000288

(The times are in seconds.)

A few notes: I have implemented an second merge sort function that can use an alternate sorting function when the arrays get small enough. Quicksort 1 and quicksort 2 are both implementations of an in-place Quick sort, but using different implementations. Finally, Array.sort and Array.stable_sort are OCaml’s standard library’s sorting functions.

During the implementation, I realized (again) that merge sort is my favorite sorting algorithm; the idea is simple, the implementation is easy (both with arrays and linked lists) and offers good performance. Insertion sort, which is super easy for linked lists, is a trickier than the other O(n^2) algorithms, because one of the invariants is a little unnatural; the element should be inserted not at position i, but i+1. It makes sense, but I was caught when I initially wrote the code, and ended up with an incorrect algorithm.

Notably missing from the list of algorithms are heapsort (which I’ll hopefully implement this week) and newer algorithms such as timsort and introsort, which I know little about.

I have made my code available on Github if you wish to look at it; I would also love to get some input on the quality of the code, or how to improve my code.

My quick review of Acme

A few weeks ago, Russ Cox released a tour of Acme, the Plan 9 editor written by Rob Pike. Since Acme looked so different from what I was used to, I installed Plan 9 from User Space and tried Acme out. Here are some quick thoughts on the interesting text editor. I should note that I have used Acme for maybe a week, and during that time, I was not using it exclusively, and I did not have a real mouse, only my laptop trackpad, so this certainly influenced how I perceived it.

Minimalist

If there is one adjective that comes to mind when using Acme, it’s “minimalist”. Everything about the editor is reduced to its barest minimum. The interface has no menu, no context menu, the scrollbars don’t have little arrows at both ends, the “toolbar” doesn’t use icons, but words, and the color scheme is very reminiscent of the early 1990’s. The editor is not only minimal in its interface, but also in its functionality: it has 28 commands internal commands, the rest of the functionality is provided by external programs.

From the original paper on Acme, this is by design. Rob wanted the program to be out of the programmer’s way. I don’t know if it’s my own habits using Emacs extensively, but I found that Acme was more in my way, mostly because it destroyed some of my long-held habits about editing text. The focus of the project was to make an editor, and anything else that the programmers wanted, they could write external programs and call them.

You probably won’t find anything in Acme that you don’t need, because there is so little. Also, you can probably know most of there is to know about the editor in an afternoon by reading the man page.

Absent features

I won’t call this section “missing feature”, but let’s look at some common text editor functions that Acme does without:

  • Syntax highlighting: all text in Acme is black. It won’t highlight your string literals in one color and identifiers in another. Acme’s proponents claim that the colors distract them.
  • Indenting according to mode: editors such as Emacs and vim allow for automatic indenting that is done according to the style of the languages they support. In Acme, automatic indentation simply copies the indentation of the line above. If you want to indent in a way that’s different from what the Tab key offers, you need to do it yourself.
  • Keyboard navigation: I’ll discuss this further in the interface section, but pressing the Up arrow on your keyboard does not move your cursor to the previous line as you would expect. In fact, there are only 5 keyboard shortcuts.

There are other features that Acme has, but implements in different ways. Searching is quite different, going to a specific line as well. It can’t edit a remote, it can’t spell check a document or count its words, you can’t display line numbers, etc.

Interface

I won’t go too much into details, but let me talk a little about the interface of Acme. First, it’s aqua and yellowish; all windows are separated into two parts, a tag and a body. The body contains the text of a file and has a yellowish background; the tag is a scratch space with some commands associated with that file and it’s aqua. These colors cannot be changed without editing the Acme source code. The scrollbars are brownish, and don’t work as you expect them. Left-clicking will scroll up, no matter what, and right-clicking will scroll down. If you want to go to a certain position in the file, you need to middle click on the scroll bar. The amount that left-clicking and right-clicking scroll up/down depends on how far up the bar you are. Near the top, and they scroll line-by-line; near the bottom and it’s page-by-page.

Beyond what the interface looks like, the most important thing about the Acme interface is that it’s mouse-driven. As I said before, there are only 5 “standard” keyboard shortcuts; for everything else, you must use your mouse. If you want to write something on the line above your cursor, you reach for your mouse, click on the line and start typing. You cannot use the Up arrow or Ctrl+P. Saving is done by middle clicking (I’ll get to the middle click part in a moment) the command “Put” in the tag of the file, no Ctrl+S’ing every 8 keystrokes. Of course, cutting, copying (called snarfing in Acme) and pasting are all done with the mouse, using mouse chords. Mouse chords are going to be familiar to people using the Opera web-browser or using one of the mouse gesture addons for Firefox and Chrome. Basically, but holding down one button of the mouse, and clicking another one, you can perform different actions. Here are the two most important:

  • After selecting some text by holding down the left button, keep it held down and middle click to cut the text.
  • To paste text, hold down the left button and click the right click.
  • If you combine these two actions (Select text, keep left button held down, middle click, right click), you copy text.

This way of manipulating text is certainly different from what I’m used to, and since I don’t have a three-button mouse, but only my Thinkpad trackpad, it was extremely awkward to do those chords. I’m guessing that it’s a little better, but still awkward with a 2-button mouse with a scroll wheel that you can click. It really looks like you need a 3-button mouse if you want to be able to manipulate text easily and without pain.

Speaking of the mouse, the three different buttons have different functions. The left button selects text and positions the cursor (as we’re all used to). The middle button is used to execute commands; you either select some text and middle click on it, or you middle click on a word, and it’ll be executed. If the word/selection is not recognized as an Acme command, Acme will try to execute an external program. The right button is used mainly to open files (if the selected text/word under the cursor looks like a file name) and will search otherwise. In his tour of Acme, Russ showed that it can be extended to do other things, but I was not able to configure my own Acme installation in this way.

Acme separates its workspace into columns, and you can split those columns into windows which will contain actual files. The management of these windows is done with the mouse, of course, and I found it to be pretty efficient and easy. Acme also tries to be somewhat intelligent when it opens new windows, acting as a mini window manager in that respect. This management is efficient and minimal enough that I would really like to see it ported to Emacs.

Executing commands

In Acme, all text can be executed. If you look at the screenshot above, you can see in the lower-left corner the command I used to create the screenshot. I simply typed the command into an empty window, selected the text and middle clicked. Any text, anywhere can be executed that way. If you are going to be using a command often, it may be a good idea to put it in the tag of a window so that it is readily accessible.

You can also use the usual redirection operators from Unix as well as the pipe. For example, if you had a list of names, and you wanted to sort them, you would write |sort somewhere, select the lines you wanted to sort and middle click the command and the lines would then be ordered. If you wanted to insert the current date, you’d write <date and middle-click and the command would be replaced by the date. Finally, if you selected some text and clicked on a command that looked like >cmd, it would run the command with the selected text as input, and the output of the command would be displayed in a new window.

The ease of running commands on text is one of the reason that Acme can be kept so minimal. Why write an editor command to reformat C code when you can simply call indent on the content of the file? I find this strategy to add functionality to an editor extremely interesting (and correct me if I’m wrong, but doesn’t Textmate do something similar?) and other editors could certainly learn from it.

Things I didn’t get to try

If you watch the Acme screencast, you’ll see that Acme can have its own mount point and that all the information about the state of the editor is contained in that directory and can be manipulated to directly affect the editor. Russ showed how his “Slide+” command uses this facility. Unfortunately, I was not able to get Acme to mount properly, so I was not able to explore this feature, but certainly this is very cool. By exposing its internals through a file system and not an internal API, it is possible for external programs to modify the editor; using this ability, it is possible to write Acme “plugins” in pretty much any language we want. I feel this goes a really long way towards making the editor extremely extensible while keeping it very simple.

Another thing I was not able to play with is the right button capabilities of Acme. I was able to search, open files, open files at certain line numbers (if the file has the format file.c:16, Acme will open file.c at line 16), but I was not able to track my UPS orders or open man pages this way. I think this functionality depends on Plumber, a Plan 9 facility, but I’m not sure.

Closing thoughts

Acme is certainly very interesting, it has some great ideas and is really snappy. I don’t think it’ll replace Emacs as my main editor any time soon, but I’m hoping that maybe during Christmas break I can try to use it for actual programming for a while, and see how I like it. I’m guessing that it won’t be a success as I have some very deeply ingrained habits, but nobody ever died from trying to do things in a different way.

I’m also hoping that some Emacs über-hackers look at Acme and find some things to steal!

DCPU-16 implementation in F#

Ashley Feniello has an implementation of Notch’s DCPU-16 computer written in F#. One thing I really like was this pattern:

let mem i = (fun () -> memory.[i] |> int), (fun v -> memory.[i]  registers.[i] |> int), (fun v -> registers.[i]  v), (fun _ -> ())
let pc, sp, o = reg 8, reg 9, reg 10
let get v = (fst v) ()
let set v i = (snd v) i

It makes reading and writing to memory and into registers general, easy and abstract. Very nicely done, Ashley!

Why I Still Use Emacs

At school, I’m known as the Emacs guy; when people have questions about configuring Emacs or making it work a certain way, they often come and ask me. Sometimes, some people ask me why use Emacs at all? Isn’t it a really old editor and aren’t Eclipse or Visual Studio much better? I mean, they don’t have weird key bindings and have intellisense, that’s surely better for a programmer, right?

I will attempt in this post to explain some of the reasons why I still cling to Emacs. Believe me, I don’t think I have any emotional attachment to Emacs; the reason I cannot leave it is that it seems that the grass is yellower everywhere else. I’d love to be able to use something like Eclipse for most/all of my work. Alas, I can’t (or rather, I won’t).

Emacs has a GUI and a CLI interface

I often connect to my university’s server with SSH; since Emacs is capable of running in a terminal, I can use it in those instances. On my desktop, I can use the slightly cuter GTK interface. IDEs like Eclipse are entirely GUI-based, this means that unless you can do X forwarding, you cannot use it remotely. In my case, this makes Emacs available in all instances where I need it.

The interface also consists entirely of text, so you can always use the very useful editing features that you are used to (e.g. searching, copying, etc.). One of the most common example is using the search function in a customize screen to find a certain parameter.

Emacs can be entirely controlled by the keyboard

Related to the point above, Emacs can be worked without ever touching the mouse. This is necessary for working with the CLI interface, but it also allows me to never reach for the mouse when I’m using Emacs. As many Emacs (and Vim) users will tell you, constantly reaching for the mouse can slow you down considerably.

Also, I’ve been using a laptop exclusively for the past 3 years; a track-pad is not as precise or fast as a real computer mouse, so I’m happy when I can perform operations without touching the track-pad.

Emacs has the mini buffer

The mini buffer in Emacs is usually activated with the M-x key sequence and allows the user to type the name of a command. For operations that don’t have a keyboard shortcut, it allows the user to invoke them with the keyboard. No need to hunt down in a series of nested menus to find the command that you want. The mini buffer also allows for auto-completion and history navigation, so the next time you need to run that command, you can get to it much faster. With a GUI, you’d need to re-navigate the menus.

Emacs is self documenting

Emacs comes with a complete documentation system; if I want to know what keyboard shortcuts are currently established, I can type C-h b to have the complete list. C-h k can tell me what command a particular keyboard shortcut. With C-h a, I can find the commands that match a certain regular expression, which is useful to find a command that you don’t know exists. The help system also includes a very complete tutorial and info pages on Emacs, Emacs Lisp and many packages.

Emacs is easy to configure

If you want Emacs to behave a certain way, but don’t know how, you can go to the #emacs IRC channel on irc.freeenode.net and follow these simple steps:

  1. Ask your question
  2. Copy the answer given to you by a helpful user
  3. Paste it in your .emacs
  4. Try it out

It’s that easy to add new configurations to Emacs. If editing Lisp code isn’t your cup of tea, Emacs also has the customize mode to help you out, and this will generate the Lisp code for you.

Configuration being a text file, it means that it’s a great idea to put it under revision control. Push your configurations to a central server and pull them when you use another computer.

Emacs works with all sorts of files

There aren’t many types of files that Emacs doesn’t recognize. There’s a major mode for nearly every programming language you can think of, and for languages you cannot think of.

This trimester, I have four classes that use four different languages: Java, C, C++ and Scheme. I use Eclipse for Java, because that’s required by our professor, but for the other three classes, I use Emacs. In my free time, I also like to play with Haskell and OCaml, which are both supported by Emacs. In the past, I also used Emacs to edit R code, GAMS code (a research operations language), Python code, JavaScript code, Clojure code, etc.

Eclipse is great at working with Java and Visual Studio is great at working with C#, but they’re less great with other languages. I don’t want to have to learn many different tools (with different menus, shortcuts, etc.) to work with the languages I need to use. This is a major reason why I use Emacs; all the basic operations (and sometimes not so basic) that I use are the same regardless of the language I’m editing. That’s very important in keeping my productivity high; I often delete entire lines in Eclipse (Ctrl+D) because I wanted to delete a single character. I cannot imagine what sort havoc I would wreak if I had to use 5 different editors/IDEs.

Emacs has many very useful modes

Emacs is usually made fun of for having a Tetris game in its default distribution. “Why the *@!& does an editor have a Tetris implementation!?” people ask. I agree that Tetris is not terribly useful, but what Tetris shows is what’s possible to implement in Emacs by its users. Here are some non-trivial modes that I use that are extremely useful:

  • calc-mode: a calculator that can work in RPN or infix mode, that has support for large integers, rational numbers, complex numbers, vectors, algebraic expressions, etc. The things you can do in that calculator could be the subject of an entire book. And it’s easily accessible: C-x * * to bring it up and again to make it disappear. It integrates quite nicely into my work-flow.
  • epa-mode: an integration with gnupg making it seamless to open encrypted files, modify them and encrypting them again. I use it for my master password instead of a more involved solution like KeePass. It can also be used to encrypt part of a file by selecting the text and executing the command M-x epa-encrypt-region (no need to find that in a menu ;))
  • org-mode: people have switched to Emacs for this one mode; it’s a mode to edit structured documents (sections, subsections, lists, etc.) It’s used to maintain todo lists, to take notes, to plan projects, etc. There are many videos on the web about it, I suggest you watch them, because org-mode has too many features to list them in this simple bullet point.
  • ido-mode: when people in Eclipse need to view another opened file, they click on the correct tab; to open a file, they double click on the file in the project list. Emacs users use the keyboard for both activities, but by default, the interface is pretty minimal and not terribly efficient. This is where ido-mode comes in: it makes it much faster to open files and switch buffers by showing the list of choices, filtering it as you type, giving you the option of having flex completion (i.e. “abc” would match the string “a##b#c”), etc. Watching a veteran ido user switch buffer can make the spectator dizzy.
  • anything: anything is similar to OS X’s QuickSilver utility; you activate it, start typing what you want and it’ll show you all the possible results, organized by categories. By default, it looks at the files in the current directory, and the opened buffers I believe, but you can configure it to find all sorts of things, such as Emacs commands, man pages, recently opened files, functions, etc.
  • occur-mode: a small mode that I use quite often; you give it a regular expression and it’ll find in that buffer all the occurrences of that regex and display them in a new window that you can navigate. Quite useful!
  • ibuffer: ibuffer can be used to perform operations on many files. For example, if you wanted to replace all instances of “foo” with “bar” in all the opened C files, you’d go to ibuffer, mark the C files, press U and all the files would be changed.
  • tramp: you can open files over an SSH link, an FTP link, you can open files using sudo, etc.

And there are many, many other very useful extensions to Emacs that I haven’t mentioned here. The good extensions are designed in such a way that they can easily be integrated without disrupting your workflow.

Conclusion

Emacs is not perfect, it is lacking in many regards:

  • It has no multi-threading support
  • Elisp is not a great language, and is quite slow
  • Using multiple major modes in a file sucks (e.g. PHP + HTML + JavaScript)
  • Most programming modes have no semantic understanding of the language they support, and thus offer no facilities like intellisense, or re-factoring. (I’m not sure what the progress of the semantic mode is; please comment if you know.)

But I think that for the most part, it compares favorably to the modern IDEs. In the next few years, I imagine that Emacs will start gaining and solidifying the IDE features that many users want. I don’t know what IDEs will do; I would hope that they’d take a step back and learn some of Emacs’ lessons and offer an experience that power users can appreciate more.

EDIT: I’ve tried to fix the newlines problem; let me know if this comes out better.

PyPy’s performances impress me

PyPy has been a project that I’ve heard about for a few years; a new implementation of the Python language. Because it was a young project and CPython worked for me, I never bothered to look at PyPy very closely. A couple weeks ago, I read a message that claimed that the performance of PyPy for CPU-bounded tasks was impressive compared to CPython’s.

Last week in my algorithms class, we learned about greedy algorithm. The first one we looked at was a program that made change. You give it an amount and a set of coins and it returns the smallest number of coins for amount. This is something we do every day without thinking about it. For fun, I wrote an implementation of the algorithm in Python:

from collections import defaultdict

def make_change1(amount, coins):
    total = 0
    solution = defaultdict(lambda: 0)
    current = 0

    while total != amount and current < len(coins):
        if total + coins[current] > amount:
            current += 1
        else:
            total += coins[current]
            solution[coins[current]] += 1

    return solution

Doing the change operation by successive subtraction is not terribly efficient, so I wrote another version that uses integer division instead:

def make_change2(amount, coins):
    solution = {}
    for coin in coins:
        count = amount / coin
        solution[coin] = count
        amount -= coin*count
    return solution

And then I created a small script to test them with a lot of amounts, using Canadian coins:

import sys

if sys.argv[1] == "1":
    make_change = make_change1
    n = 100000
else:
    make_change = make_change2
    n = 10000000

for i in xrange(n):
    make_change(i, [200, 100, 25, 10, 5, 1])

Here are the times of running this script on my Linux laptop:

$ python2 --version
Python 2.7.2

$ time python2 make_change.py 1
real    0m16.236s
user    0m16.236s
sys     0m0.000s

$ time python2 make_change.py 2
real    0m28.638s
user    0m28.491s
sys     0m0.057s

And now with PyPy:

$ pypy --version
Python 2.7.1 (?, Sep 04 2011, 13:10:48)
[PyPy 1.6.0 with GCC 4.6.1]

$ time pypy make_change.py 1
real    0m2.185s
user    0m2.157s
sys     0m0.023s

$ time pypy make_change.py 2
real    0m8.799s
user    0m8.769s
sys     0m0.023s

Clearly this is just one silly, unscientific micro-benchmark, but I plan on trying to use PyPy more in the future to see if it generally performs better than CPython.