Optimizing Lisp

Over at the Lisp Subreddit, they have a pointer to an interesting 2006 paper on How to make Lisp go faster than C by Didier Verna. One of the persistent myths about Lisp is that it’s slow. That comes from the old days when Lisp was interpreted but it hasn’t been true for a long time.

Verna shows that Lisp can be as fast as C and sometimes even a bit faster. This always seems counterintuitive but it shouldn’t. After all, the C compiler and the Lisp compiler both do the same thing: they compile their source languages into machine language. It’s really (mostly) a matter of how good the compilers are. Yes, there are things like garbage collection but especially for numerical work there’s no reason that one should run faster than the other.

What’s interesting to me are the reddit comments. They were mostly along the lines of, “Yeah but you have to add all these yucky declarations into the source code and it makes it ugly.” To me that completely misses the point. Leaving aside the fact that you always need declarations in C, the point is you can quickly develop a first version, working interactively with Lisp. If the situation calls for it, you can speed things up by adding declarations and declamations to the code. Usually you won’t need to but when you do, Lisp has the appropriate tools available. You get the best of both worlds: you can easily prototype an application and then, if needed, make it production-strength by added a few declarations.

In any event, if you use Lisp and would like a nice introduction to optimizing your code, give Verna’s paper a read.

Posted in Programming | Tagged , | Leave a comment

Before There Was Snowden

The New York Times has an absolutely fascinating story about a 43 year old crime that was, until recently, unsolved. It’s a story that shows there is nothing new under the sun. It’s also a story intrinsically involved with the U.S. Government’s last scandal involving spying on its citizens.

The crime was the theft from an FBI office in a suburb of Philadelphia of documents that showed the FBI was spying on Americans, trying to infiltrate anti Vietnam war groups, and incite them to perform illegal acts so that the antiwar movement would be discredited. The documents, subsequently mailed to a number of newspapers, were instrumental in getting the Church commission, that investigated the aforementioned last scandal, formed.

The parallels with the Snowden story are astounding. The NYT story at the link has a 13 minute video about the story that will seem very familiar. After the revelation, the government tried desperately to bury the story. When the papers published it anyway, high ranking government officials lied on the record. The FBI assigned 200 agents to track down the perpetrators.

The way the people involved were finally discovered makes the story all the better. Whatever your thoughts on the Vietnam War—or even if you don’t have any—and on the Snowden affair, you really need to watch that video. If nothing else, it’s a great caper story.

Posted in General | Tagged | Leave a comment

Slime Moving to Github

Xach is reporting that Slime is moving to Github. That’s great news but mostly it’s good news for Xach who no longer has to deal with CVS to get the latest version of Slime for Quicklisp. For the rest of us, Xach handles that for us when we use Quicklisp.

If you’re not already using Quicklisp, believe me you’re missing out and should get it installed right away. It will take care of updating Slime for you and you’ll never have to worry about it again. All you need do, once Quicklisp is installed, is evaluate

(ql:quickload "quicklisp-slime-helper")

and follow the instructions to install and configure Slime.

If you choose not use Quicklisp for some reason, the move to Github will make your life a bit easier.

Posted in Programming | Tagged , , , | Leave a comment

How To Reallocate Memory

Chris Taylor has a nice post on reallocating arrays. The problem is a common one: you initially allocate an array (or other data structure) and later want to make it larger. In C, for example, you would use the realloc function. The problem at hand is how much additional memory to request with the reallocation. You’d like to arrange things so that some of the memory can be reused in further reallocations. Taylor explains exactly what this means in his post.

The theoretical answer turns out be that you should increase the current allocation by a factor of ≈1.618 or, to be precise, by the golden ratio. As a practical matter, a factor of 1.5 is probably a good value. None of this is of great import, of course, but the mathematician in me was charmed by the result. The golden ration keeps popping up in unexpected places.

Posted in Programming | Leave a comment

FIDO

Ars Technica is reporting that Microsoft has joined the FIDO alliance. The FIDO, Fast IDentity Online, alliance is an industry group that is developing protocols to replace the passwords for access to Web sites. The idea is to use public key cryptography to replace the current password system. The macro view is that you would have a public/private key pair for each site you visit. The site would hold the public key and you would hold the private key. When you log onto a site, they would send you a random message, which you would sign with your private key. The site would check the signature and, if legitimate, sign you on.

Notice how this solves several problems with the current system. The three major problems with passwords are:

  1. Users choose weak passwords
  2. Users reuse passwords
  3. Sites don’t properly hash the stored passwords

The public key cryptography solves the first problem because the user doesn’t choose a password and the keys are secure by construction. The password reuse problem also goes away because the site generates the key pairs so, again, the user doesn’t have an opportunity to do the wrong thing. Finally, even if a bad guy is able to recover the public keys from a site they can’t recover the private keys to gain access to the site. After all, in public key cryptography the public keys are available to anyone through the key servers.

The Ars post has some of the details on how the protocol is envisioned to work. As you’d expect, getting the details right is the hard part. The system has to be easy for users and site operators alike. FIDO’s plans call for submitting the result of their research to a body such as the IETF for standardization.

Posted in General | Tagged | Leave a comment

Serializable Emacs Objects

Christopher Wellons over at null program has a very nice post on readable closures in Emacs. With the introduction of lexical scoping and, consequently, closures in Emacs 24 it’s nice to discover that Elisp closures are readable. That is, you can print them and read the resulting text back in to create an object that is equal to the original.

The post is a bit more general than the title suggests. It provides a list of Elisp objects that are readable and another of those objects that are not. I don’t think I’ve ever seen that information written down before so it’s very useful. For example, as of Emacs 23, Emacs hash tables are readable. That’s something I didn’t know. Actually, Emacs does a better job of serializing its objects than Common Lisp does. As Wellons explains, a lot of that has to do with the fact that Elisp compiles to byte code.

Even if you aren’t interested in closures, this post is worth reading for what it tells you about serialization in Emacs Lisp.

Posted in General | Tagged , | Leave a comment

The Sins of the Technical Press

Regular readers know that I’m inclined to a jaundiced view of the press. They are, far too often, biased and lazy and write stories that aren’t simply wrong but the opposite of the truth. The late Michael Crichton famously described this in a speech where he discussed the Gell-Mann Amnesia Effect.

One would hope that the technical press would do better but, sadly, they are in many ways worse. Consider, for example, this righteous takedown by John Gruber of Christopher Mimms’ article in Quartz. The nonsense that passes for reporting is unbelievable. As Gruber says, much of it is obviously and provably untrue.

The technical press appears to be at their worst when reporting or commenting on Apple. I’m not sure what it is but something about Apple seems to drive reporters crazy. Don’t take my word for it; read Grubers post. He describes the results in great detail. One needn’t be an Apple Fan Boy to see how wrong and unfair much of the reporting on Apple is. And although they seem at their worst when reporting on Apple, they don’t do a whole lot better in general.

Posted in General | Tagged | Leave a comment

Popup Windows in Emacs

Kris Jenkins has a nice post on using the popup package to pop up help windows in Emacs. He shows a tiny amount of Elisp that pops up the system help for the symbol at point. It would be easy to adapt it to pop up other types of help or any other information.

You can get the popup package from Marmalade through ELPA. Read the README at github to learn about its capabilities. It’s a nice package.

Posted in Programming | Tagged , | Leave a comment

Bozhidar Batsov on Emacs 24.4

Over at Emacs Redux, Bozhidar Batsov is promising a peek at some of the Emacs 24.4 features. Because he contributed code to the release, he’s followed the development carefully and has been using it exclusively for the last six months so he’s in a good position to give us some insights into the new release.

His first post, on a smarter show-paren-mode, is already up. It’s got an animated gif that shows the new mode in action. The mode now matches a number of delimiters including language specific ones such as do/end.

Both posts are well worth your time. Of course, that’s true of all the posts at Emacs Redux.

Last-Minute Update

As I was getting ready to publish this, I noticed that Batsov has published his second post on rectangular selection. As in the show-paren-mode post, he demonstrates the new functionality with an animated gif. It’s a little hard—at least on my MacBook Pro—to see the highlighting so look carefully.

Posted in General | Tagged | Leave a comment

RTFM

Some time ago1, I noticed that the Org footnote mechanism was not working correctly. As with similar footnote facilities, you add a footnote by marking where you want the footnote to appear in the text and then adding a paragraph starting with the same marker that contains the text of the footnote. Usually, you add the footnote definition in the next paragraph so that the definition is near its reference in the text. For example, the text generating the above footnote is

Some time ago[fn:1], I noticed that the Org footnote mechanism was not…


[fn:1] Most likely when I upgraded to Org Mode 8.

Org is supposed to collect the footnotes and put them at the end of the page on which they occur. Instead, the footnotes were being added at the spot where they were defined. Org mode is under constant development so I assumed, as I had with Magit, that one of the updates introduced the error and that it would be fixed the next time I updated. In the meantime, I just moved the footnote definitions to the end of the text.

When I finally got around to updating however, the error was still there. So I did what I should have done originally: I read the manual. It turns out that somewhere along the line Org was updated to require two blank lines after the footnote definition. That was presumably so that you could have a multi-paragraph footnote. Once I added to second blank line, everything worked correctly.

As geeks, we’re fond of invoking the RTFM mantra but sometimes we forget it ourselves. Anyway, this post is a heads up to anyone who is experiencing the same problem.

Footnotes:

1

Most likely when I upgraded to Org Mode 8.

Posted in General | Tagged , | Leave a comment