The Trabb Pardo Knuth Algorithm in Elisp

Posted on 2012-04-27 by jcs

The latest Programming Praxis Exercise is interesting. Back in 1973, Luis Trabb Pardo and Don Knuth published an algorithm that was meant to assess the power of a programming language. The algorithm was 

Ask for 11 numbers to be read into a sequence S
Reverse S
For each number in S
  Call some function to do a mathematical operation on the number
  If the result overflows
    Alert the user
  else
    Print the result

That seems simple enough but notice how it involves arrays (lists would be more natural in Lisp but the intent was to use arrays), indexing, I/O, iteration, general functions, mathematical functions, and error detection. Be implementing the algorithm in a language you get a good feel for how the language handles common programming tasks.

Naturally, I had to try it out in Lisp. I used Emacs Lisp as a sort of minimal Lisp but still got a very nice and concise implementation. 

(require 'cl)
(let ((s (make-vector 11 0)))
  (dotimes (i 11)
    (aset s i (read-number "Enter a number: ")))
  (coerce (reverse (coerce s 'list)) 'vector)
  (mapc (lambda (n)
          (print (condition-case nil (expt 2 n) ((overflow-error) "OVERFLOW"))))
        s))

If I had used a list instead of an array, I wouldn’t have needed the two calls to coerce but I would have needed two reverses if I filled the list in the most natural way.

The condition-case is like try/except from other languages. It performs the exponentiation and returns the result unless an overflow error occurs in which case it returns OVERFLOW. Whatever is returned is then printed. The only problem I had was getting an overflow. Generating an overflow is hard in most Lisps because of their bignum facilities. Emacs Lisp doesn’t use bignums but it does handle overflows in the interpreter. A sexpr like (expt 10 1000) just returns 0. If you use (expt 10.0 1000) it returns 1.0e+INF. Division by zero does generate an error but its an arith-error not an overflow-error. If anyone knows how to generate an overflow in Elisp, leave a comment.

Posted in Programming | Tagged , | 4 Comments

The WikEmacs Elisp Cookbook

Posted on 2012-04-26 by jcs

I stopped by WikEmacs today to see how the site was progressing. It looks pretty nice and has obviously seen some hard work by its contributors. Being me, I immediately went to the Emacs Lisp Cookbook to see how it looked. It’s pretty much the same as the EmacsWiki Elisp Cookbook but a little better formatted and with some of the material rearranged. So while there isn’t much new material it is nice to see that it’s migrated to WikEmacs.

I don’t take a stand on whether one site is better than the other; I’m just happy to see more information about Emacs collected together wherever folks feel most comfortable contributing. If you haven’t checked WikEmacs out lately, drop by and see what you think.

Posted in Programming | Leave a comment

And So It Begins

Posted on 2012-04-25 by jcs

Tor/Forge, part of the Macmillan empire announced that they will start shipping their ebooks without DRM starting in July. This is the beginning of the DRM death spiral predicted by Charlie Stross (although he has tempered that prediction a bit in his analysis of Tor’s announcement).

John Scalzi weighns in with his own thoughts and an announcement that his forthcoming novel, Redshirts, will be DRM-free even though it will be released in June. Like Stross, he views this as a positive move.

I am hopeful that this action will trigger the collapse of DRM in the publishing industry. Once the publishers see that the earth continues to orbit the sun even without DRM, I expect that they will all jump on the bandwagon.

Posted in General | Tagged | Leave a comment

Decimalizing Latitude and Longitude

Posted on 2012-04-24 by jcs

Xah Lee has reintroduced a challenge from last year. Given a string of latitude/longitude is degrees, minutes, seconds, write a function that returns them as signed decimal numbers. That is, 

"37°26′36.42″N 06°15′14.28″W" → (37.44345 -6.253966666666667)

I remember looking at this challenge last year and thinking it wasn’t very interesting but when I started thinking about it this time, I realized that there are a couple of twists that do make it interesting.

Here’s my solution in Elisp: 

(require 'cl)

(defun decimalize-lat-lon (lat-lon)
  "Decimalize latitude longitude
\"37°26′36.42″N 06°15′14.28″W\" --> (37.44345 -6.253966666666667)"
  (let (result)
    (dolist (ll (split-string lat-lon " +"))
      (destructuring-bind (deg min sec dir)
          (split-string ll "[°′″]")
        (if (string= "" dir) (error "malformed lat-lon %s" ll))
        (let ((factor (if (member dir '("S" "W")) -1 1)))
          (push (* factor (+ (string-to-number deg)
                             (/ (string-to-number min) 60.0)
                             (/ (string-to-number sec) 3600.0))) result))))
    (reverse result)))

Elisp purists might complain about my using dolist, destructuring-bind, and push from the Common Lisp package but they’re convenient and don’t do anything that can’t be done a bit more verbosely in pure Emacs Lisp. The real workhorse in this function is the Elisp split-string function. It gets used twice: once to split the original string into latitude and longitude and once to break the latitude and longitude into their constituent parts.

The check on whether dir is the empty string really checks for any missing constituents and is just a sanity check. I didn’t bother rounding the numbers to any particular number of decimal places or making the function a command. Either of those are easily done if the user needs them.

Update: Mickey over at Mastering Emacs and Aaron Hawley in the comments give nice solutions using Emacs calc. Mickey’s post shows off some of the great features of calc so be sure to take a look.

Posted in Programming | Tagged , | 2 Comments

A Key Sequence For revert-buffer

Posted on 2012-04-21 by jcs

The other day I was trawling through Aaron Hawley’s excellent Emacs Reference Sheet and came across the entry for【Ctrl+x Ctrl+v Return】saying “same as previous.” The previous entry was for revert-buffer. My first thought was “How did I not know this?” I use revert-buffer a lot when I’m syncing files between computers with Git so this would really be useful to me. My next thought was, “Gee, I should blog about this.”

I remembered that every time I call revert-buffer it tells me that I can run it with【Super+u】 as well as with a menu. I always ignored these because I don’t have a 【Super】 key and I avoid using the menu interface. Why didn’t it tell me about the much easier【Ctrl+x Ctrl+v】? So I called【Ctrl+h k Ctrl+x Ctrl+v】to see what it said. Of course, it said that【Ctrl+x Ctrl+v】runs find-alternate-file (actually ido-find-alternate-file in my case), something I already knew but forgot in the excitement of discovering something new. I was disappointed that my discovery didn’t work out. I thought that Hawley must have made a typo.

Today, I came across the same entry and this time I noticed that 【Return】 at the end of the 【Ctrl+x Ctrl+v】. Suddenly, it all made sense. The 【Ctrl+x Ctrl+v】 does run find-alternate-file and the 【Return】 selects the current buffer’s file so the result the same as revert-buffer.

This is another one of those small things about Emacs that doesn’t seem like much but does, in fact, make my life easier. It was there all the time if I’d had the wits to see it. Fortunately, I had Hawley to help me see the light.

Posted in General | Tagged | 6 Comments

Let Over Lambda

Posted on 2012-04-19 by jcs

Last year, I reported that most of the book Let Over Lambda was posted on the Internet. I recommended that anyone interested in Lisp take a look at it. I still make that recommendation but be warned: you will end up buying the book to read the rest of it. Daniel Higginbotham summed it up best by writing “…holy crap is it exciting to read!”

I agree. As soon as I finished with the on-line parts, I ordered the book despite my resolve to not buy anymore dead tree books. Now I notice that the book is available via iBooks for the bargain price of $13.99. If you have an iPad (or an iPhone and don’t mind reading with the small screen) you no longer have an excuse not to read this book.

While reading Let Over Lambda I had the same feeling of delight and discovery that I felt when I first read Structure and Interpretation of Computer Programs. This is only the second book that’s affected me that way. If you’re a Lisper, you need to read this book. Really.

Posted in General | Tagged | Leave a comment

The Emacs clean-buffer-list Command

Posted on 2012-04-17 by jcs

Some time ago, I enabled save-desktop-mode in Emacs and I’ve been really happy with it. I generally never close Emacs but sometimes I need to restart it for one reason or another or an OS upgrade requires me to reboot. Since I have a number of buffers that are always open, restarting Emacs was a pain before I started saving the sessions. Now when I restart Emacs, everything is just like it was before the restart. A downside of save-desktop-mode is that the buffer list grows and grows. Every once in a while I run ibuffer to get a list of active buffers and cull the list.

Today, I discovered the clean-buffer-list command that automates the process. The idea is that buffers that haven’t been displayed recently are closed. The meaning of “recently” is, of course, configurable along with other attributes of the process. This is the command that the so-called Midnight Mode uses. My machines are usually asleep at midnight so in order for me to use automatic cleaning I’d have to schedule it for when I’m on the machine and I don’t want to do that.

Happily, I can just run clean-buffer-list when I notice that the number of buffers is getting over large and have the list culled automatically for me. Another win for Emacs.

Posted in General | Tagged | 3 Comments

More On The Death Of DRM

Posted on 2012-04-16 by jcs

John Gruber over at Daring Fireball has his own take on the Charlie Stross post that I wrote about yesterday. Like me, Gruber thinks it’s a great post and that Stross is right in his beliefs of what it means for publishes but he disagrees that it means the end of DRM. The reason for that is that Gruber thinks old-school media executives are incapable of shaking their belief in the need for and efficacy of DRM.

I sure hope he’s wrong because if he isn’t, I don’t see how publishers can avoid the Amazon Apocalypse. It’s easy to say they deserve it and enjoy a moment’s schaden freude but it will be bad for readers too in the long run. After all, how long is Amazon going to sell their products at loss after they have secured a virtual monopoly on the retail sale of ebooks?

Posted in General | Tagged | Leave a comment

The End Of DRM?

Posted on 2012-04-15 by jcs

Although the title of this post puts me in jeopardy of having Betteridge’s Law applied, two recent posts by prominent writers lead me to believe that the end of DRM is near. A couple of weeks ago, Publishers Weekly posted an interesting article by Cory Doctorow entitled A Whip to Beat Us With. The article argues that by insisting on DRM, publishers have given retailers like Amazon a whip to beat them with. The idea is that DRM leads to device lockin, which means that a retailer with a large number of ebook customers can demand concessions from the publishers because the readers can’t leave without losing their current libraries and so the publishers’ customers become the retailer’s customers.

All that’s pretty standard stuff and well known to the type of people who read Irreal. Yesterday, Charlie Stross published a post in which he said the meaning of the DOJ suit against Apple and the publishers is that the publishers’ plan B for preventing Amazon from destroying them has failed and that they now have no other option but to open up the market by selling ebooks without DRM. Stross points out that with the current situation, Amazon has the best of both worlds: an (effective) monopoly at the retail level and a monopsony at the wholesale level.

That’s not good for readers in the long run, of course, but it’s deadly for the publishers. If Amazon controls access to a large part of the ebook reader base it can demand crippling concessions from the publishers.

Both articles are interesting and I urge you to spend a few minutes reading them. For the first time I have hope that the publishers will finally abandon DRM. They better; their continued existence depends on it.

Posted in General | Tagged | Leave a comment

Elisp Input With History And Completion

Posted on 2012-04-13 by jcs

Xah Lee has a nice post up dealing with getting user input with completion and history in Emacs. I usually just use interactive with “s” or possibly “f” or “F” but Lee shows us a better way.

Did you know that there are functions specifically for reading path names and regular expressions? I didn’t but I can already see how they can be useful especially given the completion functionality. In particular, the read-regexp function is useful because the user can enter the regular expression without worrying about double escaping everything:

^\(ab*\.xxx\)$ → ^\\(ab*\\.xxx\\)$
Posted in Programming | Tagged , | 1 Comment