I expected that it would be really useful to working on medium sized projects such as libraries. I’m sure it will be but today I wanted to experiment with a small, single .lisp file project. I decided to try out Quickproject to see how it would work for a really small project. It was a revelation as to how much easier it made things. I started with

(quickproject:make-project "~/lisp/levenshtein/")

then opened the ~/lisp/levenshtein/levenshtein.lisp file and started hacking. When I got finished I was able to load it with Quicklisp even though I had not configured ASDF to search ~/lisp/ for projects. I’m really impressed with how easy and useful it is. If you regularly write in Common Lisp you really need to get Quicklisp and Quickproject. They’ll make your life a whole lot more pleasant.

So to encourage people not to engage in piracy, they’re going to force
everyone to watch yet another annoying, time-wasting,
gratification-delaying warning screen that can only be avoided by
engaging in piracy.

Really, these notices are completely useless. If you’re going to pirate, these won’t give you a second’s pause. If, like most people, you don’t pirate movies it’s just an annoying inconvenience that make you feel sympathy for the pirates and loathing for the studios.

This is a way of helping library writers get their libraries tested in as many environments as possible. It seems like a good idea so if you are willing to donate a few cycles it’s a worthwhile exercise. See Sedach’s post for details.

That has forced me to understand Common Lisp better and to become a more proficient Lisp programmer. At this point, I’m ready to say goodbye to Scheme. Common Lisp doesn’t have as simple a design but it is much more powerful. It’s easy to implement the named let functionality with a macro (see LoL for an implementation) and as Doug Hoyte argues in Let Over Lambda, Lisp-2 is arguably better than Lisp-1. I’m not yet convinced of that last statement but using CL exclusively for the last month has made the difference fade into the background. That leaves only continuations. They’re certainly powerful but CL provides a way of doing everything I used them for.

One huge advantage of Common Lisp is that it’s standardized in a way that Scheme isn’t. I recently changed from Clozure CL to SBCL and I haven’t had to make any code changes. It’s very hard to do the same thing is Scheme. When I changed from Dr. Scheme (now Dr. Racket) to Guile I had to rewrite a lot of code. That carries over to libraries. It was pretty hard to find libraries that worked with any Scheme and although there are certainly CL libraries that use non standard features of a certain implementation and are not as a result portable, most libraries work just fine with any Lisp. Notable exceptions are things, like networking, that are not part of the standard. But even there, Zack Beane shows a very nice way of handling the differences with his Quicklisp implementation.

Finally, there’s a subtle difference in the feel of the two languages. CL seems to give me more power to solve problems. Thus, although I was a little annoyed that Guile won’t build under Lion (I know, it’s free and the code is there to fix), in retrospect, I think it was actually a good thing. It has made me reconnect strongly with my first Lisp and that’s working out very well for me.

• Makes it super easy to download libraries (see this post, for example) and keep them up to date.
• Manage my own projects.

That second item is, in many ways, even nicer than the ease with which you can retrieve libraries. Quicklisp can also load your local projects, so it’s easy to just do a

(ql:quickload "some-local-project")

to load your project into Lisp so that you can continue working on it. If your project is a library, Quicklisp will automatically load it for other projects that depend on it (via the .asd file).

Today, I was trawling around on Beane’s site, Xach.com, and came across an excellent article he wrote about Making a small Lisp project with quickproject and Quicklisp. If you’re a Lisper and haven’t read this, you should head on over right now to see how a master does things.

One of the interesting things I learned from the article was quickproject. If you’ve ever put together a system with ASDF, you know that the process can be a little fiddly. You need to build the package.lisp file, the project.asd file, and your actual code files. Quickproject does much of the work for you. It will build default package.lisp and project.asd files based on the information you give it. It will even make an empty project.lisp file so that you open it in your editor and get right to work.

Naturally, quickproject is available with Quicklisp so I loaded onto my system. I haven’t had a chance to use it yet but I plan to start with my next project.

In any event, here are my solutions. All the commenters who gave an answer for problem 1 (Given a list of integers from 1 to n but with one of the integers missing, write an efficient algorithm to find the missing integer.) gave the same O(n)/O(1) algorithm for time/space, namely just sum the integers up and subtract the sum from (n² + n) / 2 to find the missing number.

The solution to the second problem (Given a list of integers from 1 to n but with one of the integers missing and another repeated, find an efficient algorithm to find the missing and repeated numbers.) is similar except the we sum the numbers and their squares. If we let delta₁ be the difference between the sum of the integers and the sum of the integers from 1 to n, and delta₂ be the difference between the sum of the squares of the integers and the sum of the squares of the integers from 1 to n, we have:

• repeated – missing = delta₁ and
• repeated² – missing² = delta₂.

From there, some very easy algebra (the quadratic terms drop out) we get

• repeated = (delta₂ + delta₁²) / 2 delta₁
• missing = (delta₂ – delta₁²) / 2 delta₁

Now it’s easy to write an algorithm that’s linear in time and constant in space (modulo some increase in size for bignums if we’re using a language that supports them).

(require 'cl)
(defun solve (n repeat missing)
  (let ((numbers (cons repeat
                       (delete missing (loop for i from 1 to n collect i))))
        (sum-1-to-n (/ (* n (1+ n)) 2))
        (sumsq-1-to-n (/ (* n (1+ n) (+ n n 1)) 6))
        (units 0)
        (squares 0))
    (dolist (i numbers)
      (incf units i)
      (incf squares (* i i)))
    (let ((delta1 (- units sum-1-to-n))
          (delta2 (- squares sumsq-1-to-n)))
      (message "repeated number is %d, missing number is %d"
               (/ (+ delta2 (* delta1 delta1)) (* 2 delta1))
               (/ (- delta2 (* delta1 delta1)) (* 2 delta1))))))

I didn’t bother to randomize the list because I don’t make any use of the fact that it’s (almost) in numerical order. Some readers calculated the length of the list but I assumed that n was given as part of the problem. If not, it’s simple to count them up as we sum the numbers and their squares and then calculate sum-1-to-n and sumsq-1-to-n afterwards.

When we run solve, we get the expected answer

ELISP> (solve 100 35 78)
"repeated number is 35, missing number is 78"
ELISP>

That’s a pretty easy problem with some obvious solutions but Smith asks how we might go about finding an optimal solution. Optimal in the sense that each input is examined at most once and that a solution is returned as soon as the answer can be definitely determined. That leaves out solutions that just spin through the inputs counting those with a value of TRUE. Smith finds a general formula for the solution and uses that to write a function to make the check.

Then things get interesting. Next, instead of writing a function to make the check he writes a function to generate Lisp code to make the check. With just a little cleverness—you’ll think, “Oh, I would have thought of that”—he has the function generating optimal code. The next step is to take that code and turn it into a compiler macro. Now when the function is called to check if m of the n inputs are TRUE the function will generate direct code if it can and call the iterative function if it can’t.

This is the best description of compiler macros that I’ve come across. I was going to blog about them myself but I couldn’t do better without just copying his post so you should definitely go take a look if you’re a Lisper.

1. Given a list of integers from 1 to n but with one of the integers missing, write an efficient algorithm for finding the missing integer.
2. Given a list of integers from 1 to n but with one of the integers missing and another integer repeated, write an efficient algorithm for finding the missing and repeated integers.

In both problems the numbers in the list are in no particular order.

So the challenge is to write the two algorithms in Emacs Lisp. The interviewer expected a O(n log n) algorithm for time for the second problem. Can you do better?

Don’t go over to Khnovanova’s blog until you have solved the problems because there are spoilers in the comments. After you solve the problem, though, be sure to read her story about “hiring the smartest people in the world.”

The only problem was that there are a lot of functions but no documentation other than the doc strings in the functions. I thought about writing a quick script to extract them for use as documentation when I thought that this was surely something that someone else had already done. So I fired up Quicklisp again and found Edi Weitz’s DOCUMENTATION-TEMPLATE library. I had Quicklisp retrieve it for me, loaded it at the REPL, typed

(create-template 'simple-date-time :target #P"~/Desktop/dt.html")

and ended up with nicely formatted html documentation that I added to the documentation stack in my browser.

Sadly, it only works with LispWorks, SBCL, and AllegroCL but if you have one of those systems and need some documentation for a library, this is a quick and easy way to generate it. If you want to see what the finished product looks like, here is the documentation for DOCUMENTATION-TEMPLATE generated with DOCUMENTATION-TEMPLATE.