Scrolling with Lion, Redux

Posted on 2012-06-02 by jcs

As I wrote yesterday, my laptop recently had major surgery. That appears to have gone well but when I got the machine back I noticed that it had Snow Leopard installed instead of Lion. I knew they were going to wipe the drive so I wasn’t surprised by the fresh install but I was surprised that they had installed OS X 10.6 instead of OS X 10.7. I called Apple to see why they had done that but the tech didn’t have any idea why it happened. My guess is that the tech who did the work thought the machine was too old for Lion, although that is not the case.

In any event, it was easy to download and install Lion again so that wasn’t much of a problem but while I was working with Snow Leopard I noticed that the screen scrolling had reverted to the classical (pre-Lion) action—swiping down with 2 fingers moved toward the bottom of the screen etc. When I first installed Lion, one of the things that really impressed and pleased me was the new scrolling method. I really liked it and got used to it almost immediately. Now, here I was back with the old method and it really drove me crazy. It just seemed so unnatural. Irreal readers who don’t use Macs will wonder what all the fuss is about but I can tell you that once you’ve used the new method, going back to the standard way is torture. The metaphor of grabbing the screen and pushing it in the direction you want to go is very natural and fades into the background almost immediately. When I was stuck using the old method, it felt like I had suddenly been teleported to a Bizaro world where everything worked backwards.

I’ve only been using the new scrolling for about 10 months but it has become so ingrained that using something else is unsettling. Keep in mind that I’d been using the standard method for years and years but had no trouble adapting to the new way. Now going back seems like torture. That’s how we know Apple got this one right.

Posted in General | Tagged | Leave a comment

Back!

Posted on 2012-06-01 by jcs

Annnnnd, I’m back. For the one or two of you who may have wondered were I’ve been, here’s the story. Last month, between the fifteenth and twentieth, I was in New York. I didn’t have to a chance to queue up any posts but it was only 6 days and I was confident that you all could find something to amuse yourselves in some other corner of the Internet. The real problems came when I got back; two things occurring together conspired to take me offline for almost another two weeks:

  • My laptop died and Apple had to do major surgery (including replacing the logic board).
  • I got flat-on-my-back-sick with some sort of flu-like infection.

That meant that I was stuck in bed with no laptop, no way to blog, and no way to program. It was not the happiest of times. I still had my iPad, which (barely) prevented me from going insane, but it’s not the same, believe me.

In any event,things should be pretty much back to normal now and we can head out together to explore the Irreal.

Posted in Administrivia | Leave a comment

Using Quickproject

Posted on 2012-05-10 by jcs

Earlier this week I wrote about Using Quicklisp and mentioned another Xach project, Quickproject (the link takes you to Github, but the best way to get it is with Quicklisp). What quickproject does is to initialize a project.asd, package.lisp, project.lisp, and README.txt files for a project. The idea, as explained in Beane’s post on building small Lisp projects, is to bootstrap a project by setting up initial versions of the files you’ll need for an ASDF loadable project.

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.

Posted in Programming | Tagged | Leave a comment

John Gruber On The Latest DVD Silliness

Posted on 2012-05-09 by jcs

ars technica is reporting that DVDs and Blu-rays will now carry two unskippable government warnings. These warnings—the usual nonsense about going to hell and jail if you copy the DVD/Blue-ray—will be shown back-to-back for 10 seconds each and will be unskippable. Gruber deadpans

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.

Posted in General | Tagged | Leave a comment

cl-test-grid

Posted on 2012-05-08 by jcs

Vladimir Sedach has a post up that describes the cl-test-grid project. The idea is that Quicklisp users download the cl-test-grid, tell it what CL implementations are available, and run the test. It runs tests against many of the libraries in the latest Quicklisp release and sends the results to a public report site and a bug tracker site.

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.

Posted in Programming | Tagged | Leave a comment

Scheme and Common Lisp

Posted on 2012-05-07 by jcs

I’ve been using Scheme and Common Lisp almost exclusively for over 10 years. During that time, I tended to favor Scheme because I liked its clean design and simplicity, the named let, continuations, and the simplicity that being a Lisp-1 brought. As I posted recently, Guile Scheme is broken on OS X Lion. It’s still broken and as a result I have been using Common Lisp exclusively.

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.

Posted in Programming | Tagged , | 4 Comments

Using Quicklisp

Posted on 2012-05-06 by jcs

Back in March I wrote that I had loaded and starting using Zach Beane’s Quicklisp. Since then I have used it with several small projects and I really like it. It does two things 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.

Posted in Programming | Leave a comment

A Message From The EFF

Posted on 2012-05-05 by jcs

Posted in General | Leave a comment

Solution to the Two Challenges

Posted on 2012-05-04 by jcs

The other day, I presented two Elisp coding challenges. I specified Elisp because Irreal readers tend to like Emacs related posts. The down side of that is that several of you worried about bignums and other Emacs limitations. That wasn’t my intent—I just thought the problems were interesting and might even come in handy someday in an interview.

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 (n2 + 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 delta1 be the difference between the sum of the integers and the sum of the integers from 1 to n, and delta2 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 = delta1 and
  • repeated2 – missing2 = delta2.

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

  • repeated = (delta2 + delta12) / 2 delta1
  • missing = (delta2 – delta12) / 2 delta1

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>
Posted in Programming | Tagged , | 2 Comments

Playing with Common Lisp’s Compiler Macros

Posted on 2012-05-03 by jcs

Back in April, Robert Smith of Symbo1ics Ideas wrote an excellent post on solving the m-of-n Boolean Circuit problem. The problem is nominally about building a boolean circuit having n inputs that returns TRUE if at least m of the inputs are TRUE. Most of us aren’t electrical engineers, of course, so Smith quickly recasts the problem as building a function that does the same thing.

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.

Posted in Programming | Tagged | Leave a comment