Lisp, According to Me

Many other people have talked about Lisp at far greater length and in far more depth than I can. I therefore begin by assuming the reader has at least passing familiarity with Lisp and the oceans of ink spilled in its name.

My Road to Lisp

I started learning Lisp in high school, with (Gambit) Scheme, after being inspired by Steve Yegge's Tour de babel. I read On Lisp and wrote reams of Scheme to implement all sorts of fun things (looking through my old stuff, it seems I managed to generate more than 7 kLOC of Scheme during grade 12). Eventually, however, I realized that I was merely writing libraries, and not actually doing anything with them. This, along with a certain sense of curiosity, led to me taking up Common Lisp.

While I appreciate the conceptual purity of Scheme, I also find complex, powerful systems to be deeply intriguing (more on this in my upcoming post on Perl), so I immediately fell in love with CL. The sheer number of things you can do with it, even beyond macros...CLOS (probably my favourite object system), its unique (AFAIK, but I'm sure I'll be corrected if mistaken) and incredibly system of restarts and exceptions, ASDF, optional type tags...I could go on for ages. As Steve Yegge put it (albeit in a manner not meant to be flattering to CL):

• Scheme is an exotic sports car. Fast. Manual transmission. No radio.
• Common Lisp is Howl's Moving Castle.

While it's true that Common Lisp may not be exactly elegant...which would you rather have, a sports car, or a gigantic, semi-sentient, ambulatory castle with magic powers? I rest my case.

I have used Clojure a little bit, but mostly as a means of learning my way around Java without actually having to learn Java. Quite pleasant, and very nice to see a Lisp dialect that doesn't shackle itself to the legacy of the crufty CL standard, nor to the extreme minimalism of Scheme.

That being said, my language of choice eventually shifted from (Common) Lisp to Factor. I found that pretty much anything I could do in CL I could do at least as easily in Factor, but in a much cleaner manner, in a much more tightly-knit community, and crucially, I could see the evolution of the language over time: Unlike Common Lisp, which has been basically unchanged for longer than I've been alive, Factor is still growing and evolving, and knowing I can (and have, in some small way, I may flatter myself to think) help shape the future direction of the language is a powerful incentive.

Well, that went off on a bit of a tangent (mayhaps I should do an entry of Factor?), so let me try to summarize my attitude towards Lisp. While I was once convinced that Lisp was the language, more experience with other languages has led me to begin to question that. It is indeed a very enjoyable language to program in, and macros are certainly the cat's pajama's, but I'm not sure if it's really that much better than some of the interesting newer languages on the scene, such as Haskell, Factor, et cetera. So...a very nice language, one that I had a long infatuation with, but not necessarily the end-all be-all of languages.

Yay Reading Week!

Well, I'm in Ottawa for my Reading Week now. Managed to get some reading done, though not as much as I'd have liked, due to my foolish decision to reinstall Planescape: Torment on my computer. Gods, but that is a great game...if ever a video game deserved to win a literary award, Torment is it. How can you not love an RPG where your most important stats are Intelligence and Wisdom, followed by Charisma, when virtually all other (especially Infinity Engine) games are all about STR, CON and DEX? Absolutely everything about that game is great: If you have never played it, you owe it to yourself to do so.

Anyway, I unfortunately have not done much (read: any) work on my parser. I was reading the Dragon Book and Beautiful Code, and I decided it would be more fun to implement the "Top-Down Operator Precedence" parser presented in Beautiful Code in Common Lisp. That's the plan...but I've already so many books to read, and coming to my grandparent's house always seems to end with me having several more. So, it will probably be a while before I get down to some serious programming. Maybe on the train ride back?

My Personal NBL

So, for the—third? Fourth?—time, I decided to try to get back into Factor. It is a really neat language, Slava is a cool and very smart guy...I like the idea of concatenative languages, and learning a new programming paradigm is always a fun thing to do. If I can just get Emacs integration working, and then figure out how to actually do things (I guess I'll go and read all the archives of Slava's and Daniel Ehrenberg's blogs). Wish me luck!

Politics Annoys Me

So, I've had some trouble coming up with something to write in the past few days. I blame this on Noam Chomsky: I started reading Failed States the other day, and it fills me with rage—I can't read it for more than forty minutes at a stretch, or I just get too filled with rage to read. The only things I was considering was how best to overthrow the corrupt regime that currently rules over the United States. However, I really didn't want to start writing about politics on this blog, at least not anti-Bush/US articles, for reasons that I will now elucidate: Other people are stupid. You see, I both take great pleasure from being an elitist snob it all things and believe that the general public is deeply stupid. Therefore, when I have the same opinion of something as the aforementioned "General Public", I feel that I must either conceal that opinion, or assume that this opinion is wrong, and begin seeking some new, untapped, and contrary viewpoint that I can get behind.

Well, that was weird. Just wanted to write something, to maintain momentum. Hopefully the next entry will be more interesting.

The Algorithm Saga Continues

Last time, I talked about some problems that I encountered while trying to write my implementation of Algorithm X, promising at the end to give it's current state next time. That, of course, was a shameless delaying tactic, while I tried to get the bugs out. However, about an hour ago, I finally ironed out the problems I'd been having, and it seems to be working now. I'll write unit tests soon, I promise. Anyway, this time I want to talk a bit more about the problems I had, and then hopefully get to what worked.

A Brief Segue Into Things That Annoy Me

As I mentioned in the previous entry, I had to put in what I'm referring to as a “tag” for each row; an alphabetical character which doesn't change as the row index does, to allow me to reference in a meaningful way the rows that are chosen while recursing on sub-matrices of the original matrix. However, I really don't like the way I did it. It's an ugly kludge, and I really want to find a better way to do it. As it is, having the cons pairs as the values of the hash makes the sparse-matrix class far less general, and as I ranted about last time, if there's one thing that drives me crazy, it's specific solutions. What if I want to use that implementation of sparse matrices in something else? I'm carrying around these characters that are completely useless to me, just taking up space. It's also forced me to change the implementation of various methods in non-obvious ways. If anyone actually read this, I'd solicit suggestions for a better method...

We Now Return to Your Regularly Scheduled Ravings

So, one thing that I learned in the course of implementing this was how to make asdf work. All my previous common lisp programs had been fairly small, but I figured that I should probably learn how make require-able packages. Unfortunately, most of the tutorials I found were on how to make one's package asdf-installable. Luckily, the fine people on #lisp were able to give me a hand, and everything went smoothly.

So, now the moment you've all been waiting for: My algorithm X implementation in all it's glory

(defun algorithm-x-solve (matrix)
  "Given a sparse-matrix, determine the exact spanning set, using Knuth's Algorithm X.  Returns a
list of rows which compose an exact spanning set"
  (labels (        
           ;; Helper function that gives a list of the cols of the matrix, sorted by least filled to most
           (get-min-cols (mat)
             (sort (range 1 (cols mat)) (lambda (a b) (< (length (rows-filled a mat)) (length (rows-filled b mat))))))
           
           ;; Function to perform the main recursive step of the solver
           (rec (r mat acc)
             
             ;; Find the first column with the least rows filled (Step 2)
             (let* ((col (car (get-min-cols mat)))
                    (cur-row (get-tag r mat))
                    (poss-rows (mapcar #'(lambda (r) (get-tag r mat)) (rows-filled col mat))))
               
               ;; Perform step 5
               (let* ((rows-to-drop nil)
                      (cols-to-drop
                       (loop for j from 1 to (cols mat)
                          when (= (get-entry r j mat) 1) collect j
                          when (= (get-entry r j mat) 1)
                          do (loop for i from 1 to (rows mat)
                                when (= (get-entry i j mat) 1)
                                do (unless (member (get-tag i mat) rows-to-drop)
                                     (push (get-tag i mat) rows-to-drop))))))
                 
                 (dolist (rw (sort rows-to-drop #'char>))
                   (setf mat (drop-by-tag rw mat)))
                 
                 (dolist (cl (reverse cols-to-drop))
                   (setf mat (drop-col cl mat))))
               
               (cond
                 ((matrix-empty-p mat)
                  (cons cur-row acc)) ;; Done, (Step 1) return the rows of the solution
                 ((null (rows-filled (car (get-min-cols mat)) mat))
                  nil) ;; A column is empty, failed
                 (t ;; Else, find a row (Step 3) 
                  (loop for row in (rows-filled (car (get-min-cols mat)) mat)
                     for ret = (rec row (copy-matrix mat) (cons cur-row acc)) then
                       (rec row (copy-matrix mat) (cons cur-row acc))
                     until ret finally (return ret)))
                 )))
           )
    
    (let ((poss-rows (rows-filled (car (get-min-cols matrix)) matrix)))
      (loop for row in poss-rows
         for ret = (rec row (copy-matrix matrix) nil) then (rec row (copy-matrix matrix) nil)
         until ret finally (return (or ret 'failure))))))
 

Yeah...it is pretty ugly. The bit that took the longest to get right was the "Perform Step 5" segment. Initially, I was dropping the rows and columns while looping across them which (obviously, in retrospect) caused things to go wrong, as the index variable of the loop was now off. Frankly, it was embarrassing how long it took to get that right.

Well, there it is. Next, I guess I'll try make a sudoku solver with that. And wither then? I'm thinking:

1. Displaying the puzzles with cl-pdf or Vecto
2. Generating sudoku puzzles
3. Writing a compiler of some sort

But we'll see...

On Algorithm X, Sudoku, Common Lisp, and Pants

So, as I mentioned in my previous post, my current proramming project is trying to implement Knuth's Algorithm X in Common Lisp. I was initially going to write a sudoku solver, but realized that I was basically copying Peter Norvig's solver, so I decided to try and generalize. You see, I am very anal about having general solutions to problems. An example: I recently acquired a pair of pants with a nifty little pocket on the side of the leg, between the hip pocket and the side pocket. Now, I always need more pockets, as I tend to carry tons of random things with me. However, I never use that pocket, although it would be idea for my keys and phone. Why? Because it isn't a general solution to the problem of carrying my stuff: I'd need to have that pocket on all my pants before I started using it. Right, I'm crazy.

Anyway, enough about pants. While looking at the wikipedia article on the mathematics of sudoku, I came across the intriguing fact that sudoku (along with n-queens, among others) can be reduced to the problem of finding an exact covering set for a sparse matrix, a problem which Donald Knuth developed an algorithm to solve. Without further ado, I decided that this was to be my next programming challenge.

(Note: Before reading further, you might want to at least glance at the Wikipedia article on the algorithm)

As I began considering the program I was to write, I decided to first make an implementation of sparse matrices. I'm sure that there are other Common Lisp packages for that far better than mine, but I figured that having control over the representation of the matrix would make it much easier to write the solver. I'm glad I did too, as I've since had to change my matrix implementation several times. Initially, I had the matrix as a class with slots for the number of rows and columns, and a hash table keyed on the (1-indexed) rows, with the values being a list of integers corresponding to the occupied columns in that row. However, some time later, I realized a fundamental flaw: The way I had designed the algorithm, I had no way of knowing which row of the original matrix the reduced rows I was choosing in the recursive stage corresponded to. The quick hack that I'm currently using was to change the values stored in the hash table to cons pairs of (<occupied columns list> . <id character>). The idea is that all the places (which were few, by design) that were directly accessing the hash would just have the (gethash …) replaced with (car (gethash …)).

Of course, there ended up being other places where things went weird, such as when mapping over the hash, and one annoying bug that took me a while to track down: One of the common operations the algorithm performs is dropping rows and columns from the matrix. Of course, we don't want to trash the original matrix, so we make a copy of the matrix to pass to the recursive stage. Okay, but to copy the matrix, we need to copy the hash table that maps the rows to occupied columns. Okay, we can do that too, thanks to a helpful soul on #lisp:

(defun copy-hash-table (ht)
  "Shallow hashtable copy."
  (let ((nht (make-hash-table :size (hash-table-size ht))))
    (maphash (lambda (key value)
               (setf (gethash key nht) (if (listp value) (copy-list value) value)))
             ht)
    nht))

The problem was that, since the value was now a list, I needed to copy the list, otherwise the destructive drop-* operations would alter the original matrix. Once I figured out that this was the problem, the solution was a simple replacing of the setf in the code above with (setf (gethash key nht) (if (listp value) (copy-list value) value)). You may (fairly) point out that I don't need the check if value is a list, since it always will be. Remember what I said at the beginning about specific solutions though? Even that makes me unhappy…

Well, it's after 1:00 AM now, so I think it's time to wrap this up. Tune it next time to learn the current state of my implementation!

I guess I need to figure out how to get syntax-highlighting with Blogger...Let's see if I can get it working for the next post! Update:Looks like I've got emacs htmlize-region to play nicely with Blogger, huzzah

A New Beginning?

Well, after creating this blog some time ago, with the intention of never using it, I think I may have changed my mind. I have no idea how many times I've decided to try writing and then never come back to it, but whatever. We'll see how it goes.

So, introduction. I'm James Cash, EngSci 1T1 at ye olde University of Toronto. I like programming. Alot. Especially in obscure languages. Currently, I'm using Common Lisp mostly, but I'll probably end up using Python in the job I'm hoping to get. My friend David Wolever hooked me up with Greg Wilson, who is quite a nice guy. High hopes there. As long as I don't have to use C++, I'm happy. Quite frankly though, the notion that someone would pay me to program boggles the mind, so I'll be glad regardless.

So, Common Lisp...obvious, I'm also a big fan of Emacs (both of those can be traced back to my reading of Steve Yegge). I used to use Scheme a fair bit, mostly Gambit Scheme, but moved to Common Lisp when I realized that it's alot more fun to write programs than libraries. I've played around with Haskell, which was tons of fun, quite beautiful, but I do enjoy dynamic typing so. Currently, I'm playing around with implementing Knuth's Algorithm X in CL, which is fun, albeit a bit of a challenge. Planning to make a sudoku solver out of that when it's complete.

I bought the Dragon Book a while ago, but haven't been able to get very far in it (EngSci does not lend itself very well to hobbies). I very much enjoy writing parsers, so I'm planning on writing some sort of compiler after I finish with the Algorithm X dealie. Thinking of doing the front-end it OCaml, which is fun to write parsers in, maybe back-end in Lisp. Probably try to write an ECMAScript 4 to (Assembly | Some sort of bytecode). Which reminds me, I need to read up on Parrot or JVM bytecode. Thank Cthulhu for reading week...

Well, there's a brief introduction, to the no-one who will read this. Hopefully I'll actually update this. Thanks for reading!