Lisp Weenies

Posted on 2014-11-18 by jcs

What’s wrong with the picture in A Cat Cons, my post from yesterday?

Posted in Programming | Tagged , | 2 Comments

The Longest Common Subsequence

Posted on 2014-11-18 by jcs

Atabey Kaygun has another great post. This time it deals with finding the longest common subsequence of two sequences. First Atabey describes a simple algorithm for finding the longest common subsequence and then implements it in Common Lisp. The surprise is that it took over 4.4 seconds to calculate the longest common subsequence of the two sequences 

(6 9 5 1 3 5 4 0 7 4 9 1 1 3)
(7 10 2 8 9 11 1 10 7 9 11 8 10 0 5 6 11)

The algorithm is recursive but this seems like a lot of time for a such short input. What’s going on?

Atabey gives us the answer. He memoizes his code using the code that I discussed previously. When he does this—simply using mem-defun instead to defun to define his function—the time drops to 0.006 seconds. Take a look at his lcs function and see if this surprises you. It did me. You have to think carefully about what’s going on to see why the memoization made any difference at all let alone such a dramatic one. Atabey’s post is definitely worth a read.

Speaking of memoization, if you missed PuercoPop’s comment to my previous post on the subject, be sure to follow his link to Fare Rideau’s beautiful article exploring Common Lisp implementations of the Fibonacci sequence. You’ll be glad you did.

Posted in Programming | Tagged , | Leave a comment

A Cat Cons

Posted on 2014-11-17 by jcs

Via Magnar Sveen we have this offering from Dmitry Ignatiev

Posted in General | Tagged , , | Leave a comment

Sharp Quote and Emacs

Posted on 2014-11-17 by jcs

Artur Malabarba has some good advice on sharp quoting Elisp functions. It’s common for Elisp programmers to use a single quote (i.e the quote form) to mark functions. Malabarba explains why it’s better practice to use #' (i.e. the function form) to indicate a function.

This is a great post (as usual for Malabarba) and all Elisp programmers should read it.

Posted in Programming | Tagged , | Leave a comment

Amazon and the Publishers

Posted on 2014-11-16 by jcs

Over at Vox.com, Matthew Yglesias has a provocative article on the contretemps between Amazon and the publishing industry and with Hachette in particular. It’s mainly been portrayed in the press as an argument over prices but Yglesias says that’s just a side show.

The truth, he says, is that the publishing industry is dying and its current battles with Amazon won’t alter that fact regardless of the final outcome. The reason for the industry’s imminent death is that it no longer provides any benefit.

That wasn’t always true, of course. It used to be that books had to be typeset, printed, bound, and shipped to retailers. It was virtually impossible for authors to do these things on their own so the publishers provided a necessary service. With the advent of ebooks, those services are no longer required. Software to take an author’s manuscript and produce an ebook is widely available, often for free. And, of course, printing, binding, and shipping are not required at all.

What about marketing, then? Surely one of the key services a publisher provides the author is marketing. Yglesias says that, in fact, the publishers are terrible at marketing. He says that the current argument between Amazon and Hachette proves this. If Hachette actually was good at marketing they could simply market their books to other vendors and directly to the public at large.

You may or may not agree with Yglesias but one thing he says is certainly true: the fight between Amazon and Hachette really boils down to who gets to keep the extra profits flowing from the fact that producing another copy of an ebook is essentially cost free. Amazon says they should be used to reduce the price. Hachette wants to keep them. Inasmuch as Hachette and the other publishers have been claiming for years that ebooks cost about the same as physical books to produce, I’m not inclined to accept their arguments.

Yglesias has other arguments supporting his thesis so you should definitely go read what he has to say. It’s a fascinating idea you don’t hear very often—at least in public.

Posted in General | Tagged | Leave a comment

Being Smart

Posted on 2014-11-15 by jcs

Matt Blaze has a realization that probably applies to us all. I know it applies to me.

(via Jean-Philippe Paradis)

Posted in General | Tagged | Leave a comment

Day of the Year

Posted on 2014-11-15 by jcs

This is really a note to myself. The other day I needed to figure out what day of the year it was. I was pretty sure that the Unix date command could tell me but I couldn’t remember how to do it and it wasn’t clear from the manual. It turns out the answer is there but not obvious.

The first thing to know is that a starting character of + in the argument tells date that a custom display string is coming. In that string you can use any of the strftime options. One of those is %j for the Julian day of the year. Thus, the answer is simply 

date +%j

which for today gives 

319
Posted in General | Tagged | Leave a comment

Using Emacs and Org Mode for a Journal

Posted on 2014-11-14 by jcs

Howard Abrams has an excellent post on journaling with Emacs and Org Mode. The post documents how his use of Org Mode evolved over time so you can see what (at least for him) worked and didn’t work. That’s very useful for figuring out your own strategy even if you settle on something different from what he did.

One of the things I like about his approach is that he uses org-capture to make his entries. That’s nice because no matter what you’re doing you can pop up a capture buffer, make a quick entry, and go back to what you were doing with very little effort. That makes it easier to maintain the journal because it’s almost frictionless.

Another nice thing I learned from his post is autoinsert. It allows you to automatically insert text to the start of a file when you first create it. It’s another in the long list of ways that Emacs can make your workflow more frictionless.

Even if you’re not interested in maintaining a journal, you should give this post a read. You may learn a useful technique or two.

Posted in General | Tagged , | Leave a comment

Counting Spanning Trees

Posted on 2014-11-13 by jcs

I really enjoy Atabey Kaygun’s blog. If you like Mathematics and Lisp, you’re sure to enjoy it too. A typical post looks at a mathematical problem and either presents a solution or experiments with the problem with Common Lisp.

One of his recent posts considers spanning trees (ST) and how to count them. Most of us—at least those who have taken an algorithms course—are familiar with the simple construction to find an ST but may not know how to count them.

Atabey introduces the notion of the Laplacian of a graph, \(L\), defined by \[l_{ij} = \begin{cases} \text{deg}(i) & \text{if } i=j,\\ -1 & \text{if there is an edge between } i \text{ and } j,\\ 0 & \text{otherwise}. \end{cases}\]

Kirchhoff’s theorem tells us that the number of spanning trees is equal to any of the minor determinants of the Laplacian. This is a pretty neat result and one that I didn’t know. Atabey’s post has a couple of worked examples and Lisp code to make the calculations.

As I said, if you like Mathematics and enjoy programming in Lisp, you should definitely give this post a read.

Posted in General | Tagged , | Leave a comment

Org Mode and Reproducible Research

Posted on 2014-11-12 by jcs

EmacsNYC has another great video up. This time, its Evan Misshula talking about Org-mode and reproducible research. Misshula is a graduate student in Criminal Justice at CUNY who does a lot of statistical research on Criminal Justice matters.

Like me, he’s a big advocate of reproducible research and spends much of his presentation talking about how Org-mode can facilitate that. In the first part of the talk he explains why reproducible research is so important. If you’re any kind of scientist, the statistics that he gives will set your hair on fire.

As a result of the high error rate with research that is not reproducible, Misshula refuses to review or cite any papers that aren’t reproducible and he urges other researchers to do the same. As I said, the statistics for research that is not reproducible is staggering. Sadly, this applies to Computer Science as much as it does to other disciplines. Watch the video to learn the details.

Posted in General | Tagged , | Leave a comment