Line Numbering

Posted on 2012-07-10 by jcs

DJCB, over at Emacs-Fu, takes note of the new line number command in Emacs 24 that Sivaram wrote about in Got Emacs? and offers up a few suggestions of his own. He shows a very nice trick for accomplishing the same thing and more using replace-regexp. It’s a little more complicated than rectange-number-lines so you probably won’t want to use it except for those cases where rectangle-number-lines (along with its optional FORMAT argument) can’t give you the desired result. Of course, if you’re still using an older version of Emacs it’s a nice way of getting the same functionality that rectangle-number-lines provides.

Posted in General | Tagged | Leave a comment

Magnar Sveen Rocks Emacs

Posted on 2012-07-09 by jcs

Many (many) years ago when I was a freshman at RPI, we called the weekly Physics mass lecture “The Magic Show” because the lectures were spectacular demonstrations that illustrated whatever principle we were studying that week. This week I had the same feeling as I watched Magnar Sveen (of Emacs Rocks! fame) deliver a talk at Web Rebels in Oslo. The sound quality was a little substandard and the pace was rapid but like those old physics lectures it was a spectacular demonstration. In this case, a demonstration of the power of Emacs and its extensibility.

Sveen started by saying that unfortunately Emacs doesn’t have a slide show capability and then put one together right before our eyes. Then he spent the rest of the 18 minutes showing off some of the micro-optimizations he’s developed to speed up his editing. One of these, his multicursor enhancement, was startling and has to be seen to be believed.

This is a really great video, sort of like Emacs Rocks! on steroids. You won’t learn how to program these enhancements or even how to use them, just what’s possible with Emacs. Fortunately, all of Sveen’s code is available on GitHub so you can download the code and try it yourself. The multiple cursor stuff is still very young but worth playing with. I’m looking forward to seeing it on Marmalade when it gets a little more mature.

If you’re an Emacs user and especially if you enjoy the Emacs Rocks! videos you should definitely spend 18 minutes on this talk. You won’t be sorry.

Posted in General | Tagged | Leave a comment

Common Lisp For Noobs

Posted on 2012-07-08 by jcs

Lori Holden over at Ghost Opera, Ltd has a nice post with advice for noobs wanting to get started with Common Lisp. As Holden points out, Common Lisp is beautiful and powerful but has some sharp edges and no commonly agreed upon starting point for newcomers.

The post is aimed at getting the neophyte up and running by listing some references and tools and then walking through a (toy) project. For tools she recommends

  • Emacs/Slime
  • SBCL
  • Quicklisp
  • CL-Project
  • Buildapp and
  • ASDF

That seems like a reasonable list, and truth to tell, I use almost that exact set of tools for all my Lisp work. The only difference is that I use Zach Beane’s quickproject instead of cl-project. Part of that is because I discovered quickproject first but it’s also because cl-project uses a method of package management that differs from what I (and, I think, most Lisp programmers) am used to.

The method pushed by cl-project is based on the style recommendations of Ariel Networks, which I find less than compelling. Still, others can and do disagree so it’s worth checking them and cl-project out if you’re inclined. Holden has a direct link to the Ariel style guide so she’s apparently an adherent.

There’s nothing in this post that will be new to anyone who’s the least bit familiar with Common Lisp but if you’re a newcomer and wondering how to get started, this is a valuable post with lots of good information.

Posted in Programming | Tagged | Leave a comment

ELPA With Emacs 24

Posted on 2012-07-07 by jcs

I just installed Emacs 24 and, as expected, everything went very well except for the package system, ELPA. I don’t have very many packages that I load with ELPA so at least the number of problems were limited.

First, following Xah Lee’s Guide on Emacs 24 Package System page, I moved the old ~/.emacs.d/elpa directory out of the way and then reloaded my packages. The first problem is that you need to replace the

(when
    (load
     (expand-file-name "~/.emacs.d/elpa/package.el"))
  (package-initialize))

with

(require 'package)

After that change I was able to add Marmalade to the list of package sites.

The next problem was that when I restarted Emacs, I got an error saying it couldn’t load smex, one of the packages that I load with ELPA. Everything seemed OK: smex was loaded onto my machine and seemed fine. The bit of Elisp in init.el was what the documentation said it should be but I couldn’t get it to load from init.el. I went searching on the Web and after a few useless links I found this page on Emacs 24 Package System Problems, again from Xah Lee. In order to get things to work you have to add an explicit load path for some of the packages (smex, magit, dired+, and key-chord for me). My first pass at this was to add commands to explicitly add the load paths:

(add-to-list 'load-path "~/.emacs.d/elpa/smex-1.1.2/") ; XXX Emacs bug
(require 'smex)
(smex-initialize)
(global-set-key (kbd "M-x") 'smex)
...

This is annoying because the path will have to be changed when I upgrade. It’s doubly annoying because ELPA worked just fine without having to do this in Emacs 23. Rather than keep dealing with this every time I upgrade one of the problem packages, I added

(defconst elpa-loads '("smex" "magit" "dired" "key-chord"))
(mapc (lambda (p) (if (file-directory-p p) (add-to-list 'load-path p)))
      (directory-files "~/.emacs.d/elpa" t
                       (concat "^\\("
                               (mapconcat 'identity elpa-loads "\\|")
                               "\\).*")))

to my init.el. With that change, the only maintenance required is to add any new problem packages to elpa-loads.

The Emacs 24 ELPA problem appears, from some of the other links I looked at, to be that Emacs 24 deals with the ELPA packages after it has finished processing the .emacs or init.el file and, therefore the .emacs or init.el file knows nothing about the packages. That means you can’t set package variables because they haven’t been loaded yet. As far as I could find out, the only solution is to load the files with require and that requires that there be a path to the .el or .elc files.

Doubtless, this will all be resolved soon so I’m not overly exercised about it. Now that I have things working again, it’s time to explore the new Emacs 24 and see how it improves my life.

Update: Added explicit check for directory when setting paths.

Posted in General | Tagged | 10 Comments

Emacs Rocks! #11

Posted on 2012-07-06 by jcs

The always entertaining and informative Magnar Sveen has a new episode of Emacs Rocks! up. In Episode 11 he demonstrates swank.js a package that brings the JavaScript REPL to Emacs in much the same way that swank brings us the Common Lisp REPL.

If you are a JavaScript programmer and aren’t already using swank-js you should view Sveen’s video without delay. He shows a simple animation of a bouncing ball and then makes changes to the code that are immediately reflected in the animation. This is good stuff.

Posted in Programming | Tagged | Leave a comment

The Emacs 24 Package System

Posted on 2012-07-05 by jcs

Back in March, I blogged about installing ELPA in Emacs 23. At the time I pointed to a page by Xah Lee on how to do this. Now that Emacs 24 is out it’s worthwhile revisiting the Emacs package system. In Emacs 24, ELPA is built in so all that’s necessary is to set the repositories that you want to get packages from.

Again, Xah Lee has us covered with an updated page. If you’ve recently updated to Emacs 24 and don’t know about ELPA, you should take a look at Lee’s page about it. He’s got all the information on how to use it and how to upgrade from ELPA for Emacs 23 to ELPA for Emacs 24. Once you get ELPA set up, everything is much easier. You can download packages and have them available without having to worry about setting up paths or special directories. It’s easy to update and delete packages so there’s no need to worry about checking in with a package’s home page to see if there’s an update—ELPA will tell you.

If you’re an Emacs user and aren’t using ELPA you’re making your life more difficult than it has to be. Seriously, check out Lee’s page and get ELPA up and running. It will make your life a lot better.

Posted in General | Tagged | 2 Comments

Transcript of the Chua-Wiegley Chat Video

Posted on 2012-07-04 by jcs

For those of you who prefer reading to listening, Sacha Chua has posted a transcript of her recent video chat with John Wiegley. As I previously described, the chat was about how Wiegley leverages the power of Emacs to optimize his daily work flow. Chua has a link to the video on the page with the transcript so if you haven’t seen it, you have your choice of reading the transcript or watching the video. Or, if you’re an overachiever, both.

Posted in General | Tagged | Leave a comment

Oh Oh: RSA SecurID 800 Token broken

Posted on 2012-07-03 by jcs

The RSA SecurID 800 token is a small USB device that authenticates users when they sign on to secure computers. It offers two factor authentication and contains encrypted keys and credentials that are, in theory, inaccessible to users or attackers. Now Ars Technica is reporting that researchers have a developed a new attack that recovers the keys in about 13 minutes.

Needless to say, this is really bad news for RSA. It’s also bad news for many other manufacturers of similar devices since their tokens are also susceptible to the attack. The exploit is a modified Bleichenbacher attack (from the 1990s) that reduces the work enough to make the inefficient Bleichenbacher attack practical.

The Ars Technica article has a link to a paper describing the attack but for the curious non-expert, I recommend this post by Matthew Green. It does a good job of describing the problem and gives an outline of how the attack works.

Posted in General | Tagged | Leave a comment

The Google Billboard Puzzle

Posted on 2012-07-02 by jcs

A recent Programming Praxis problem resurrected the famous Google billboard puzzle. Back in July of 2004, Google put up billboards all over the country reading

{FIRST 10-DIGIT PRIME IN CONSECUTIVE DIGITS OF E}.COM

Those who solved the problem and followed the link found another puzzle whose answer was the password to a second site. The second site was an invitation to submit a CV to Google. All-in-all a pretty effective way of advertising for the type of engineers that Google was looking for.

The first puzzle (finding the 10-digit prime) isn’t hard in principle: generate the digits of e and check each consecutive group of 10 for primality. But consider for a moment how you would have gone about solving the problem. The first step is generating the digits of e. A recent Programming Praxis problem deals with this but the algorithm is complicated and given in terms of the code used to implement it. That’s neither interesting nor enlightening and in any event we only want the digits once so there’s no point in spending a lot of time writing code to generate them. Instead, we can go to this NASA site and get the first million digits of e already calculated for us. Of course, it may be that the first 10-digit prime is not in the first million digits but, in context, that seems unlikely and it is, in any event, easy enough to check that it’s worth using as a first attempt.

The second problem is checking for primality. A 10-digit number is small enough that we can simply try factoring them using, for example, the Unix factor command. But it just so happens that I have an implementation of the Miller-Rabin primality test lying around so let’s just use that.

;; In case you want to finish in this lifetime.
;; Using ash makes no appreciable difference.
;; (pushnew :use-ash *features*)
(defun modexp (b e n)
  "Modular exponentiation"
  (flet ((sqmod (x n) (mod (* x x) n)))
    (cond ((zerop e) 1)
#-use-ash ((evenp e) (modexp (sqmod b n) (/ e 2) n))
#-use-ash (t (mod (* b (modexp (sqmod b n) (/ (1- e) 2) n)) n))
#+use-ash ((evenp e) (modexp (sqmod b n) (ash e -1) n))
#+use-ash (t (mod (* b (modexp (sqmod b n) (ash e -1) n)) n)))))

(defun canonicalize (n)
  "Express n as (2^r)s + 1, where s is odd."
  (do ((r 0 (1+ r)) (s (1- n) (ash s -1)))
      ((oddp s) (values r s))))

(defun check (r s n)
  "Miller-Rabin primality check"
  (let* ((n-1 (1- n)) (a (1+ (random n-1))))
    (or (= (modexp a s n) 1)
        (dotimes (j (1+ r) nil)
          (if (= (modexp a (* (ash 1 j) s) n) n-1)
              (return t))))))

(defun primep (n)
  "Make 50 checks for primality of n. Probability of a false positive is
less than 8e-31."
  (if (or (and (/= n 2) (evenp n)) (< n 0))
      nil
      (multiple-value-bind (r s) (canonicalize n)
        (dotimes (k 50 t)
          (if (not (check r s n))
              (return nil))))))

The Miller-Rabin test is probabilistic so each number has 50 checks applied to it before it’s accepted as prime.

With those two parts of the solution in place, it’s easy to find the prime

(defparameter eo10  ;;digits truncated for display
  "271828182845904523536028747135266249775724709
369995957496696762772407663035354759457138217852
516642742746639193200305992181741359662904357290
033429526059563073813232862794349076323382988075
319525101901157383418793070215408914993488416750
92447614606680822648001684774...")

(defun search-for-prime ()
  (let ((end (- (length eo10) 10)))
    (do ((i 0 (1+ i)))
        ((> i end) nil)
      (with-input-from-string (s eo10 :start i :end (+ i 10))
        (if (miller-rabin:primep (read s))
            (return (subseq eo10 i (+ i 10))))))))

When we run this, we get the solution almost immediately

CL-USER> (search-for-prime)
"7427466391"

We can, if we like, check this using factor but a 50 iteration Miller-Rabin test is pretty definitive. In terms of this problem, we’ll know right away if we’re wrong because 7427466391.com won’t resolve.

Posted in Programming | Tagged | Leave a comment

Programming Metric: -2000 LOC

Posted on 2012-07-01 by jcs

Over at Folklore, Andy Hertzfeld has a wonderful story about management’s obsession with non-sensible programming metrics. Who among us has not, at one time or another in our career, been subjected to a manager who thought that lines of code written was an excellent way of measuring programmer productivity? If your answer is, “Not me” then you are either extraordinarily lucky or just starting out.

Hertzfeld relates how in 1982 when Apple was making a big push to get the Lisa software out the door, some manager decreed that every programmer would submit a weekly report detailing how many lines of code they had written that week. Bill Atkinson, author of Quickdraw, the main interface designer, and, as described by Hertzfeld, the most important Lisa developer, thought the whole thing was silly and that his job was to write the smallest most efficient code he could.

One week, while working on the Quickdraw region calculation engine, Atkinson rewrote the code, replacing the algorithm with a more efficient one that made the calculations 6 times faster and reduced the size by 2000 lines of code. In that week’s report, Atkinson recorded his productivity as -2000 lines of code. Heltzfeld reports that after a couple of weeks management no longer asked Atkinson to fill out the report.

It’s one of those stories that makes you think, “Gee, I wish I’d done that.” These days, you probably find this obsession with lines of code only in large corporate coding farms but to those who’ve been there, the story is hilarious.

Posted in Programming | Tagged | Leave a comment