I’ve mentioned Jean-Philippe Paradis’ Common Lisp Tip Tweets before. He’s reorganized the site a bit and categorized the tweets so that it’s easier to find what you’re looking for. If you don’t follow him on Twitter, it’s worth stopping by his site every once in a while to check out the new tips.
My favorite new tip since my last visit:
CL tip: Indentation-saving trick: (multiple-value-bind (a1 a2 b c1 c2 c3) (multiple-value-call #'values (values 1 2) 3 (values 4 5 6)) ...)
Steven Goss over at the zero bit stream has another great Common Lisp post. His idea is to compare a minimal Haskell Quicksort routine to the same function written in Common Lisp. A case can be made that the result is not really Quicksort in either language because of the performance profile but they do follow the Quicksort algorithm and are interesting even if they aren’t useful as production code.
Goss’s final result makes use of a list comprehension macro that is interesting in its own right but the first attempt is also nice. Here’s Goss’s code for the first attempt:
(defun quicksort (list) (when list (destructuring-bind (p . xs) list (let ((lesser (remove-if-not (lambda (x) (< x p)) xs)) (greater (remove-if-not (lambda (x) (>= x p)) xs))) (append (quicksort lesser) (list p) (quicksort greater))))))
Notice how it makes the structure of the Quicksort algorithm explicit. Of course it doesn’t choose the pivot in an intelligent way—which can result in n2 behavior—and all those remove-if-not and appends are each tacking on O(n) penalties but you still have to love the beauty and brevity of the code.
Quicksort, like any other industrial strength algorithm, is hard to get right. As I mentioned in my post on Jon Bentley, perfecting the Quicksort algorithm is definitely not trivial. This implementation doesn’t come close but it is useful because it makes the structure of Quicksort clear and because it shows how Common Lisp can express algorithms in a beautiful way.
Often times when doing research for a blog post I will collect a series of URLs that I could potentially use as a link in the post. Nothing new or exciting there; almost every blogger doubtlessly does the same thing.
There’s a minor annoyance though. I use Org mode to write my blog posts and while I’m still in the research phase it’s too early to turn a URL into an Org link. After all, I don’t yet know where the link will end up in the post or what the anchor text associated with it will be. Therefore when I’m actually writing the post I have to either edit the link by hand or snarf & barf the URL into Org mode’s link generation machinery.
To make the process a little easier, I wrote the following bit of Elisp. Putting the cursor on a URL and calling org-linkify will prompt for the anchor text and turn the URL into an Org link.
(defun org-linkify (label) "Turn a URL into an org-mode link." (interactive "sLabel: ") (let ((url (thing-at-point 'url)) (bnds (bounds-of-thing-at-point 'url))) (delete-region (car bnds) (cdr bnds)) (insert (concat "[[" url "][" label "]]"))))
With this code I can collect URLs in the Org mode file associated with the post and then either delete them or turn them into links as I write. I still have to move the URL to the proper place in the text of the post, of course, but org-linkify makes the rest of the process a bit easier.
Update: Daniel points out in the comments that Org mode already handles this use case with the normal link machinery.
There’s a great article over at Ars Technica about password cracking and how easy it’s become. The ease with which passwords can be cracked are the result of two things:
Consider the Project Erebus v2.5 computer used to win this year’s Crack Me If You Can contest. It has 8 AMD Radeon HD7970 GPU cards, costs just $12,000, and can brute force the entire 8 character (lower case, upper case, symbols, numbers) NTLM keyspace in just 12 hours. Think about that. If you have a password protecting something important and it’s less than 8 characters, you might as well not bother.
The other thing affecting cracking efficiency is the recent release of millions of real word passwords gathered from the exploits of Gawker, Sony, LinkedIn, and others. This helps in two ways. First, it provides a dictionary of potential passwords to try. Second, it gives insight into how users choose their passwords. It turns out that there are some very common patterns in use and knowing these patterns makes it easy to automate the generation of trial passwords using those patterns.
Be sure to follow the link and read the Ars Technica article. It’s a bit long but there’s a lot of really good information in it. The conclusion that the article reaches is that you can still have a secure password if
If you have any on-line presence at all, you really need to read this article. It will scare you into password sanity.
As most of you have heard by now, Daniel Weinreb, one of the Lispers’ Tribal Elders and user/beta tester of the original Emacs, died on September 7. The Boston Globe and Xconomy have obituaries but surprisingly Weinreb had some interaction with Xah Lee who has a very nice reminiscence of those interactions (including thoughts on Emacs, old and new) and provides links to some of Weinreb’s interesting writings.
The links and recollections provide a sort of short summary of Weinreb’s professional life and are well worth a read. Like Lee, I’m sad at his passing.
Dan Goodin over at Ars Technica has an interesting and scary article about cracking his neighbors’ WiFi network passwords. Sadly, this turns out to be a lot easier than it should be. The general process is
All of this is pretty discouraging. What can you do to make your network secure? The answer, as it often is, is to choose sensible passwords. CrowdCracker and similar services work by trying an extensive dictionary of possible passwords against the captured authentication handshake. If you choose a well-known or even an obscure but known password, the attacker will have your password in a matter of minutes (see the article for details).
Goodin’s recommendation is one we’ve discussed many times at Irreal: choose a password of several words such as those generated by Diceware as I discussed here, here, here, and here. A password such as “quartz apple some perfume bring token” will not appear in any password dictionary, is relatively easy to remember, and has enough entropy to be effectively unbreakable. The links above show two computer programs to generate passwords such as this but all you really need is one or more dice as explained on the Diceware Site.
The other possibility is to use a password manager, such as 1password, that allows you to generate passwords that are too long and random to remember. Again, these will not appear in any dictionary so the attacker’s only recourse is brute force. With sufficiently long passwords this will, as a practical matter, be impossible.
Password security is under attack as never before so it’s more important than ever to Choose a strong, long, random password and never reuse it.
For those looking for a prepackaged Emacs configuration, there is another option available: Cabbage. The configuration is meant to be flexible and extensible and the hope is that a community will emerge around it.
If you’re not enthusiastic about dedicating an arbitrarily large proportion of your mental cycles to tweaking your .emacs file, this may be for you. Even if that doesn’t describe you, perhaps you’ll find some interesting ideas. Worth a look.
Fred Wilson over at AVC has a post about the new HBO GO iPad app. It seems that the app has an Airplay button that allows the user, one would think, to stream the content to a TV. It turns out, though, that Wilson could get only the audio portion to stream. The video would not appear. After some research, Wilson discovered that, no, this isn’t a bug or user error: it’s a feature.
Wilson makes some good points:
That last point is, it seems to me, the important one. Big Media is relentlessly user hostile but can’t understand the lack of sympathy they get over piracy. On the surface, they should get that sympathy. After all, they spend billions of dollars producing content only to see it stolen. That hurts not just the fat cats but the “little people” such as writers, actors, crew, and all the others who help get the product out the door.
Once you look beneath surface, though, a different picture emerges. Most of the damage is self-inflicted. As I discussed in my post Scientific American on Piracy, Big media encourages piracy by not making the content available legally.
The HBO GO Airplay flap is another example. Rather than let users consume the media in a way that is convenient for them, Big Media erects pointless obstacles. The thing is, they aren’t really effective obstacles. Users will simply stream the content from somewhere without the obstacles. As one of the commenters on Wilson’s post put it, “it’s their way of supporting torrents”.
Stephen Goss over at the zero bit stream has a great post on concurrency in Common Lisp using ChanL. ChanL is a Common Lisp library that implements the Newsqueak concurrency paradigm. Newsqueak was developed by Rob Pike and is described in this Google talk and a series of papers including Bell Labs Computing Science Technical Report No. 143. These, in turn, were inspired by C.A.R. Hoare’s Communicating Sequential Processes.
I first watched Pike’s talk a couple of years ago and was so impressed that I downloaded the papers and source code for the Newsqueak interpreter. In the end, I never did much with it because it meant learning another language with limited application to the sorts of problems I was working on. ChanL is a win for me because it leverages a language I already know. Best of all, it’s available through Quicklisp so installation is trivial.
Goss gives a simple example of ChanL’s use in his post. He builds a quick application that downloads a list of 4 Web pages in the same time that it takes to download one. Pike’s talk gives several more examples of using the CSP paradigm to solve a variety of problems. The talk, like all of Pike’s offering, is excellent and well worth your time. If you haven’t seen it, I recommend you spend an hour on it even if your aren’t a Lisper or interested in CSP.
Update:
give → gives
I agree with every one of these 20 controversial programming opinions.
Aside:
Does anyone else find it astounding that “vetted” interviewees could not write code to calculate the area of a circle in any language? Or is astounding too weak a word?
Afterward:
There has been a bit of pushback to the original list of 20 controversial programming opinions. Many commentors and posters felt that they weren’t really that controversial. James Hague and Bill the Lizard have published their own lists. I mostly agree with Hague and with about 25% of Bill’s list.
Update: options → opinions