Cleaning Up My Emacs Environment

Posted on 2011-05-18 by jcs

While I was installing magit the other day, I decided it was a good time to do a little digital house cleaning. I keep all my important file groups—writing, software development, blogging, and personal—in Git repositories. Oddly, given that these all flow through Emacs, I didn’t have my Emacs environment in Git. As I wrote yesterday in my Magit post, one of the primary uses for these Git repositories is to keep my various machines in sync so not having .emacs.d in Git made no sense at all.

Part of the problem was some early poor choices on my part. I installed the Org-mode distribution as a subdirectory of .emacs.d. There’s nothing necessarily wrong with that but I had it in there as a Git repository. A while back I decided to try to put .emacs.d in Git but the nested Git repositories didn’t work out so well—not at all, in fact. When I finally got around to installing magit I already had some Emacs packages in my tools directory, so I moved the Org-mode repository out of .emacs.d and into tools. I had already replaced .emacs with init.el in .emacs.d so all I had to do was initialize .emacs.d as a Git repository, clone it as a bare repository, and move the cloned repository to the server with the rest of the repositories.

Many people like to break their .emacs into several files with a separate file for each mode or function. Some even use Babel’s literate programming facilities to tie everything together. I keep everything in one file otherwise I’d never be able to find anything. That means that I don’t have much in my .emacs.d but init.el and some elisp files for small packages that don’t need their own subdirectory. Here’s what it looks like

auto-save-list/
dired+.el
dired+.elc
gnuplot-gui.elc
gnuplot.elc
htmlize.el
init.el
paredit.el
quack.el
slime/
tramp
tutorial/
xml-rpc.el

Looking at that list, I could probably get rid of quack.el since Geiser has pretty much taken over its functions. Unfortunately the .emacs.bmk file lives in my home directory by default and there doesn’t appear to be a way to change it. That’s not really a problem for me because I don’t use book marks but it would be nice to get everything in one place. I suppose I could set a symbolic link if I did start using them.

Posted in General | 6 Comments

Magit

Posted on 2011-05-17 by jcs

One of the first things I did when I started using Emacs was to install the git.el package that interfaces with Git. I chose git.el because it worked the same as the rest of the Emacs source control interfaces. There’s not much to do to install the package but somehow I must have messed it up because I could never get it to commit.

I use Git mostly to keep versioned backups of my work and to move data between the machines that I use. I have Git repositories on a local server that I can push to and pull from. It’s not hard to pop into a shell buffer and just call Git by hand and that’s what I fell into doing. Every once in a while I would try M-x git-status again and, of course, it still didn’t work. I checked that I had the latest version but other than that I didn’t look into the problem further.

All this time, what I really wanted to use was magit but I had it in my head that it was better to stick with a package that had a UI the same as for all the other SCM systems. Then one day it occurred to me that I use only Git and that, gee, maybe I could learn another interface if the need arose. But I still didn’t install magit. I know, I know, I’m a lazy, lazy person.

A few days ago I saw this video by Alex Vollmer and decided that I really should give it a spin. I’m very pleased that I did. The result is similar to what happened when I discovered I could FTP right out of dired. It hasn’t changed my life but it has made my work flow easier and more efficient. Even more important, I find that I do a lot more commits and pushes than I did before. I used to put off committing until I had several files or until I needed to refresh my files on another machine. Now it’s so simple that I do it as soon as I finish with a file. That means the repositories on the server are always up to date and I don’t have to trudge over to my main machine to push everything so that I can pull it onto another machine—I just pull and get the latest files.

It turns out that magit is very sensitive to the .git/config files so if you want to use it you will need to get those right. Here’s what I have for my local set up. 

[core]
        repositoryformatversion = 0
        filemode = true
        bare = false
        logallrefupdates = true
        ignorecase = true
[remote "org-repo"]
        fetch = +refs/heads/*:refs/remotes/org-repo/*
        url = ssh://bedia/home/jcs/repos/org.git
[branch "master"]
        remote = org-repo
        merge = refs/heads/master

The [core] section of the configuration was auto-generated by Git, and the [branch "master"] section was generated by magit. That leaves the fetch line in the [remote "org-repo"] section. If you don’t have that, things will still work, mostly, but you get error messages in your magit-status buffer for some of the remote items.

Posted in Programming | Leave a comment

Mean!

Posted on 2011-05-16 by jcs

This is just mean. Mean, but funny. It’s also awe-inspiring in the same disturbing way that someone who memorizes the Boston phone directory is.

Posted in Programming | Tagged | Leave a comment

Google Code University

Posted on 2011-05-16 by jcs

Recently, via Hacker News, I came across this link to Google Code University. The University consists of introductions to a variety of subject matter in software development and Web programming. Some are internal courses that Google uses to train their own engineers and others are from outside sources such as Princeton, Stanford, University of Washington, and many more. They have courses on Programming Languages, Web Programming, Web Security, Algorithms, Android, Distributed Systems, Tools, and Google APIs and Tools.

As I have only minimal HTML and CSS skills and no Javascript skills at all, I decided to try out the HTML, CSS, and Javascript from the Ground Up course. It’s about 2 hours long and is broken up into several videos and exercises. There is a zip file with course material so that you can follow along and work the exercises. As you would expect from a 2 hour course, I’m hardly and expert Web designer after going through the material but I did learn some things I didn’t know before. More importantly, I came away with a refined way of thinking about HTML, CSS, Javascript, and the relationships between them.

The course is perfect for someone like me. I let Org-mode do most of the heavy lifting in generating HTML and only occasionally insert HTML code manually to tweak the result. Some of the tricks I learned from the course will help me do this in a more effective way. The CSS material will help me refine the look of my new Home page once I get around to setting it up.

All in all, the course was enjoyable and well worth my time. I will probably try out some of the other courses too. They have a wide variety and many of them look interesting.

Posted in Programming | Leave a comment

Setting the Babel Evaluate Confirm Status

Posted on 2011-05-15 by jcs

Because Babel provides a facility to execute arbitrary code, it presents a security risk. Code blocks are evaluated when a document is exported as well as when a user explicitly asks for evaluation by typing C-c C-c in the block. To prevent an unwary user from unintentionally executing malicious code, Babel asks for confirmation before executing any code block. That’s a sensible precaution and one that I leave on even though it can be disabled.

There are times, however, when it’s really inconvenient. For example, in the Calling Babel From A Table post, Babel asks for confirmation for each table cell. In that case, I wanted to turn off the confirmation request. You do that by setting org-confirm-babel-evaluate to nil. That’s a long name and if a week goes by without my using it, I won’t remember the name and will have to look it up. It’s also a pain to type. Also, there’s no way to check whether you forgot to turn it back on other than by looking at org-confirm-babel-evaluate.

Here’s a little function that does all that in a convenient way and that has a name short enough to remember. Just add it to your .emacs or init.el file. 

(defun babel-confirm (flag)
  "Report the setting of org-confirm-babel-evaluate.
If invoked with C-u, toggle the setting"
  (interactive "P")
  (if (equal flag '(4))
      (setq org-confirm-babel-evaluate (not org-confirm-babel-evaluate)))
  (message "Babel evaluation confirmation is %s"
           (if org-confirm-babel-evaluate "on" "off")))

Calling babel-confirm will tell you if confirmation is on or off. If you give it a prefix argument (call it as C-u M-x babel-confirm) it will toggle the setting and tell you what the new setting is.

If this isn’t fine enough control, you can also set org-confirm-babel-evaluate to a function. The function is passed the language of the code block and the block itself. The function can decide if the block is safe or not and return t to have Babel ask for confirmation or nil to just execute the block. All this is explained in the Org manual’s Miscellaneous section.

Posted in Programming | Tagged | 1 Comment

Kicking the Hornet’s Nest

Posted on 2011-05-14 by jcs

Bloomberg Businessweek has an article up entitled Sony: The Company That Kicked the Hornet’s Nest. It’s about the break in and Sony’s penchant for suing and prosecuting “hackers.” There’s not much new in the article (although their telling of the story is interesting) but it is, I think, a bad sign for Sony when even Bloomberg is beating up on them. The article makes the point that it will be months, if not years, until the full extent of the damage to Sony, both in dollars and damage to their brand, will be known.

Posted in General | Leave a comment

Fibonacci Run Times

Posted on 2011-05-14 by jcs

­

This posts combines the results of the last two posts. I thought it would be interesting to compare the actual run times of the three methods of calculating Fibonacci numbers so I put together a Babel table like the one in the Calling Babel From A Table post and ran the experiment. The results were a little disappointing because they didn’t really give me much information. The table below gives the times (in 100 Hz timer ticks) that the 3 methods took to calculate fibn for various values of n. (The code is the same as in the Calculating the Fibonacci Numbers post.)

n Recursive Iterative Logarithmic
10 0 0 0
20 0 0 0
30 15 0 0
40 1899 0 0
50 234539 0 0
100 Too Long 0 0
1000 Too Long 0 0
10000 Too Long 1 0
100000 Too Long 40 0
1000000 Too Long 8952 5

As expected, the recursive method quickly becomes impractical, taking 39 minutes to calculate fib50. The iterative method doesn’t register any time at all until fib10000 and is still under half a second for fib100000. The time for the iterative method to calculate fib1000000 is misleading because the wall clock time was much longer. The reason for that was that it used up all the memory (4 Gigs) and spent a lot of time swapping. Presumably this was the result of the big nums representations taking up memory. Interestingly, I could watch the garbage collector at work. The free memory would get down to a few MB and then start to climb again. Then it would drop again. This happened several times.

The results for the logarithmic method don’t provide much information other than that if you want to calculate fibn for large n you should use that method.

Posted in Programming | Leave a comment

Calculating the Fibonacci Numbers

Posted on 2011-05-13 by jcs

If, like me, you’re fascinated by the Fibonacci numbers you should take a look at Robin Houston’s The Worst Algorithm in the World post over at the Bosker Blog.

Houston lists and analyzes the three main ways of calculating fib(n):

  • The naïve recursive method that results from programming right from the definition 
    (define fib-rec
  (lambda (n)
    (if (< n 2)
        n
        (+ (fib-rec (1- n)) (fib-rec (- n 2))))))
  • The iterative method, which can be seen as a dynamic programming solution 
    (define fib-it
  (lambda (n)
    (let fib ((k n) (a 1) (b 0))
      (if (zero? k)
          b
          (fib (1- k) (+ a b) a)))))
  • The logarithmic method, which is similar to fast exponentiation (see Exercise 1.19 of Structure and Interpretation of Computer Programs) 
    (define fib-log
  (lambda (n)
    (define sum-of-squares
      (lambda ( a b)
        (+ (* a a) (* b b))))
    (define fib
      (lambda (n p q a b)
        (cond ((= n 0) b)
              ((even? n) (fib (/ n 2) (sum-of-squares p q)
                               (+ (* 2 p q) (* q q)) a b))
              (else (fib (- n 1) p q (+ (* b q) (* a q) (* a p))
                          (+ (* b p) (* a q)))))))
    (fib n 0 1 1 0)))

Readers of this blog will know that the recursive method is horribly inefficient and Houston shows that, in fact, calculating (fib-rec n) takes 2 × fibn+1 – 1 calls to fib-rec. Thus (fib-rec 100) calls fib-rec 1,146,295,688,027,634,168,201 times.

We’re used to seeing just the first few terms (0, 1, 1, 2, 3, 5, …) of the Fibonacci sequence and it’s easy to forget how rapidly it grows. Here are the values of fibn for some relatively small n:

n fibn
0 0
10 55
20 6765
30 832040
40 102334155
50 12586269025
60 1548008755920
70 190392490709135
80 23416728348467685
90 2.880067194370816e+18

Another interesting thing that Houston points out is that the iterative method is actually O(n2) not O(n) as often supposed. That’s because when the numbers get large you must use a multiprecision numeric library and can no longer add the terms in constant time.

Finally, Houston gives a nice way of looking at fib-log and why it works. As I say, this is a really interesting post and worth a few minutes of your time.

Posted in Programming | Leave a comment

Calling Babel From A Table

Posted on 2011-05-12 by jcs

While I was reading the Lisp Idioms article that I blogged about yesterday, it occurred to me that the first example on accumulating a list presents an excellent opportunity to talk some more about Babel and how to use it with Org-mode tables. It will also give us a nice, if trivial, example of Reproducible Research.

Most Org-mode users are aware of the spreadsheet capabilities of Org-mode tables. You can, for example, sum all the values in a row or column or perform other familiar operations on the data. With Babel, you can also have a cell make a call to a Babel code block to get its value. Whereas in our previous examples we’ve used code blocks to build new tables, in this example we will first build the table and then have the code blocks populate (most of) the cells.

To review, in the Lisp Idioms article one of the examples was of ways to accumulate a list from a stream of values. This is, of course, a common operation in Lisp and Scheme and there are some mildly diverse ways of doing it. Just for variety, we will write our functions in Scheme rather than Common Lisp.

Cons the items onto a list and reverse the results at the end

The most common way of doing this is shown in the first code block. The cntr definition just provides a stream of integers—a new one each time it’s called. The E1 function does the actual work of assembling the list and the let at the end just calls E1 and calculates the time it took to do its work. All this should be very familiar to even beginning Scheme programmers. 

(define cntr ((lambda () (let ((k 0)) (lambda () (set! k (1+ k)) k)))))
(define E1
  (lambda (n)
    (let loop ((k n) (lst '()))
      (if (zero? k)
          (reverse lst)
          (loop (1- k) (cons (cntr) lst))))))
(let ((start (get-internal-run-time)))
  (E1 n)
  (/ (- (get-internal-run-time) start) internal-time-units-per-second))

The next code block is almost the same as the first except that it uses reverse! instead of reverse to reverse the list. Theoretically, reverse! should be faster because it reuses the cons cells from the first list rather than making a separate list from scratch. 

(define cntr ((lambda () (let ((k 0)) (lambda () (set! k (1+ k)) k)))))
(define E2
  (lambda (n)
    (let loop ((k n) (lst '()))
      (if (zero? k)
          (reverse! lst)
          (loop (1- k) (cons (cntr) lst))))))
(let ((start (get-internal-run-time)))
  (E2 n)
  (/ (- (get-internal-run-time) start) internal-time-units-per-second))

Append the items onto the end of the list

In some sense this is the most intuitive, if naive, method if you are not a Lisp or Scheme programmer. The problem is that append must search down the list each time to find the list’s end and is therefore very inefficient. No serious Lisp or Scheme programmer would ever do this. 

(define cntr ((lambda () (let ((k 0)) (lambda () (set! k (1+ k)) k)))))
(define E3
  (lambda (n)
    (let loop ((k n) (lst '()))
      (if (zero? k)
          lst
          (loop (1- k) (append  lst (list (cntr))))))))
(let ((start (get-internal-run-time)))
  (E3 n)
  (/ (- (get-internal-run-time) start) internal-time-units-per-second))

Place the items in a vector in the order in which you retrieve them

This is certainly the fastest method and the one that, say, C programmers would use. Its problem is that you have to know the largest number of items that you can get so that you can preallocate the vector. Common Lisp has a way of extending vectors and the Lisp Idioms article has an experiment for that method but Scheme doesn’t have resizable vectors so we don’t have that case. 

(define cntr ((lambda () (let ((k 0)) (lambda () (set! k (1+ k)) k)))))
(define E4
  (lambda (n)
    (let ((vec (make-vector n)))
      (let loop ((k 0))
        (if (= k n)
            vec
            (begin
              (vector-set! vec k (cntr))
              (loop (1+ k))))))))
(let ((start (get-internal-run-time)))
  (E4 n)
  (/ (- (get-internal-run-time) start) internal-time-units-per-second))

Running the experiment

We start with a table like this: 

|       n | Reverse | Reverse! | Append   | Vector |
|---------+---------+----------+----------+--------|
|       1 |         |          |          |        |
|       2 |         |          |          |        |
|    1024 |         |          |          |        |
|    4096 |         |          |          |        |
|   16384 |         |          |          |        |
|  262144 |         |          | Too Long |        |
| 1048576 |         |          | Too Long |        |

The code blocks have the same names as in the header. For example, the first code block has a 

#+SRCNAME Reverse(n)

just above it. The last two rows of the Append column are set to “Too Long” because the Append method takes too long to run for lists of those sizes. All the other cells in columns 2–5 are empty.

Next, we set the code for each of the empty cells to ‘(sbe @1 (n $1)). This is easily done with the table editor and results in the TBLFM line 

#+TBLFM: $2='(sbe @1 (n $1))::$3='(sbe @1 (n $1))::$5='(sbe @1 (n $1))::@2$4..@7$4='(sbe @1 (n $1))

sbe is a macro that calls the code block with the name of its first argument and passes the code block the rest of its arguments. The @1 means row one of the current column and thus refers to the name of the code block from the table header. The $1 in the second argument means column 1 of the current row and thus refers to the n-value for this cell.

Now all we need do is put the point anywhere in the table and type C-u C-c C-c and the table will be filled in with the run times.

n Reverse Reverse! Append Vector
1 0 0 0 0
2 0 0 0 0
1024 0 0 1/100 0
4096 0 0 6/25 0
16384 1/100 0 387/100 0
65536 1/100 1/100 1321/20 1/100
262144 1/25 3/100 Too Long 3/100
1048576 19/100 13/100 Too Long 1/10

get-internal-run-time returns number of 100 Hz ticks used by the Guile interpreter (thus internal-time-units-per-second = 100). As expected, the Vector method is fastest but not by as much as we might expect. The other interesting result is that except for really long lists, reverse! does not outperform reverse to any significant extent. The Append method, of course, is out of the running.

This post is a simple example of Reproducible Research because everything needed to reproduce the post is contained in a single the Org-mode file. If this were a serious research paper, any scientist could request a copy of the file and run the experiments for his or herself.

Update: Corrected the definition of get-internal-run-time.

Posted in Programming | Tagged | Leave a comment

An Oldie but Goodie

Posted on 2011-05-11 by jcs

I stumbled across this list of Lisp idioms on Hacker News yesterday. I’ve seen it before and if you’ve been around for a while, you probably have too. Still, it’s always fun to read it again. I enjoy the terse elegance of the little snippets of code. Who would not be charmed by this one-liner to take the transpose of a matrix (stored as a list of rows)? 

(apply #'mapcar (cons #'list matrix))
Posted in Programming | Tagged | 1 Comment