Advising Factor (Aspect Oriented Programming, if you're nasty)

I've been pretty busy the last couple of weeks with school, so I haven't been able to get any real (read: non-school related...I am not a fan of Verilog) programming done. So, the other day, I decided to try and implement something neat in Factor. After thinking about it for a bit, I decided to try to implement what is known as "advice" in Lisp and "aspects" in Java.

I had tried to do something similiar to this in Scheme a couple of years ago, but that was not pretty: Since functions in Scheme are just symbols bound to functions, I had to keep track of the advice to call around each function externally (e.g. in a globally-scoped table). The alternative was to redefine the function to add the advice directly into the body, which was even uglier, and didn't allow you to undefine advice. Gross. In Factor, however, this is made much, much, much easier by the fact that words are tuples. This allows me to easily annotate and add properties to words (and I do mean easily--the whole vocab is only fifty-six lines (plus 21 of docs and 63 of tests (more tests than code, yeah!))).

How it works

The implementation of advice is actually quite simple: When we first advise a function, we annotate it to call call-before, call-after, and call-around. These words look properties of the word (named before, after and around, respectively), which contain hash-tables of the given type of advice for the function and call them. The before and after type advice is quite easy to implement (just call a list of quotations, either before or after the main body (which, as Slava points out, really should be a macro or some such for performance reasons)), but around is a little trickier...But, I am very tired now and I have a calculus midterm tomorrow morning, so I'll write about that part sometime soon.

Oh, and if you're interested, you can grab my code from git://factorcode.org/git/jamesnvc

Hopefully not much more on extra/lisp

I've been working on it for far too long, but I think I'm almost done the Factor side of extra/lisp. I've done a little more work since I last wrote and now the only thing remaining is, unfortunately, something of an open problem; Namely, the propagation of locals into literals (more specifically, cond within lambdas).

So, what have I done?

I've only really made three changes since I last wrote, which are as follows:

1. Allowing multiple forms in the body of an expression.

   This was something that was really just due to my carelessness in the first place: When I wrote the s-exp to quotation translator, it would only take the first form. This first manifested itself as a problem when trying to write begin as a macro.

2. Begin as a special form

   I originally had begin as a macro, but soon realized that this was untenable, since the stack needed to be cleared after each form: That is, we want (begin 1 2 3) to leave just a three on the stack, but if done as a macro, the stack would look like 1 2 3. So, begin is now a special form, which essentially just wraps with-datastack and a drop around each form in the begin.

3. Changing macro-expansion time

   Oh boy. This one is embarrassing. Originally macros were expanded as the forms were being called. Given that macros being called at compile-, not run-time is really the whole point of macros, I have no excuse. But anyway, it's been fixed now.

So, what's left?

At this point, the only thing not working satisfactorily is locals and cond. Since I've defined if in terms of cond, this means that things like ((lambda (x) (if x ...))...) won't work, because the x isn't properly visible in the if. I'm not entirely sure how I'm going to fix this...but I'll figure it out soon!

Postscritpt: I guess I'm on Planet Factor now? Thanks Slava!

Update: As per Slava's comment, locals in cond now work in git, so everything is working now! Yay!

Blogging from Emacs

As a brief diversion from the Factor stuff I've been working on, I wanted to just share a bit of information that someone out there may find useful.

g-util.el and various frustrations

Since I first saw it, I wanted to use the gblogger-* functions for emacs that g-util.el gives. However, I ended up having a bunch of problems that I was unable to fix and soon gave up. However, yesterday I decided to have another go at it and managed to get it working! It turned out to only require two changes, but they didn't seem to be well-documented anywhere...So, without further ado, here's how to get the g-util stuff working in emacs (your mileage may vary, of course):

1. Make sure the shell is set to bash. I initially had the shell set to zsh, which resulted in parsing errors
2. It seems that w3m-buffer doesn't work as the g-html-handler. I set it to switch-to-buffer, which seems to work

And that's it! Enjoy blogging via Emacs!

Factor and Emacs!

As previously mentioned, I've been working on an implementation of Lisp in Factor. Although it's been tough, progress is being made. However, I'm taking a short break from that to work on something just as fun - writing a (better) factor-mode for emacs.

While Factor does come with a factor mode (in factor.el), it has some warts that I don't really like. For one, it doesn't support customization (via customize-group). I'm also not too fond of it's font-lock (that is, syntax highlighting) support, so I'm working on fixing that too. Once I get that working, I'm also going to add some factor-specific movement functions, and prehaps the ability to look up definitions of words and the like. I'd really like to have eldoc-like display of the stack effect of the factor word at point. That would probably entail having a nice inferior-factor mode too, which should be entertaining.

That's it for now!

So yeah, just a quick summary of what I'm up to now. Emacs is just so much fun, not only to write code in, but to write code for! Next time I write, I'll hopefully have made more progress on both factor-mode and extra/lisp.

Factor and Lisp, part three

Since last time I wrote about the state of my lisp-in-factor implementation, not much actual forward progress has been made. Instead, I was embroiled in a struggle to figure out how I was to properly implement the passing of arguments to lisp functions, specifically in the case of function calls.

The problem:

First, some background on my lisp converter: It essentially works by converting lisp forms to factor quotations in the following manner: (foo bar baz) ⇒ [ bar baz ] T{ lisp-symbol f "foo" } funcall (By the way, the T{ ... } is a literal tuple, which you may know as an object. So, T{ lisp-symbol f "foo" } is the literal (i.e. you could type that directly into a Factor listener and it would recognize it as a lisp-symbol object) for a lisp-symbol object whose delegate is f (which they usually are, since delegates are deprecated) and whose name field is "foo") In other words, we get a quotation containing the arguments to the function, which funcall will look up and then call appropriately. Certain primitive forms (e.g. quote, lambda, etc) are built-in primitives that are translated at parse time, but everything else will follow this general form.

Okay, that works...but what if we have something like this? (list 1 2 (list 3 (list 4) 5)) Hm...well, if we translate it the same why we did above, it ends up looking like this: [ 1 2 [ 3 [ 4 ] T{ lisp-symbol f "list" } funcall ] T{ lisp-symbol f "list" } funcall 5 ] T{ lisp-symbol f "list" } funcall Now, this is a problem...the argument list for that outer list is a literal quotation, which includes inner quotations, lisp-symbols and funcall words. This means that the arguments to list, rather than numbers and other lists (which is clearly what is intended here) will be quotations, symbols, and words...which is not what we want at all.

So, how to fix this? Well...I tried a few, fairly hackish methods, such as doing a pretty hideous reduce over the quotation inside funcall, to find occurences of the funcall word, then execute funcall on the last two elements of the quotation...blah, gross. I had been thinking...what I basically want to do is call the argument-list quotation, but somehow keep the result of calling it in a quotation. I toyed with the idea of making everything in the argument list into quotations, then doing a [ call ] map over the argument list (that is, evaluate each element of the quotation, putting the result into another list). However, doing this would require some fairly significant refactoring, and would make the rest of the code much less elegant, as the argument list shown above, rather than [ bar baz ], it would have to be [ [ bar ] [ baz ] ], or, even worse, [ [ 1 ] [ 2 ] [ [ 3 ] [ [ 4 ] [ ... ] ] ] ]...you get the idea. Very gross. However, while on #concatenative the other day, I asked slava about the possibility of writing a word that word that would take a quotation, call it, then put everything that calling the word put on the stack into a quotation...

Will that work?

It turns out that a superior version of the word I was looking for already exists: with-datastack. This word takes an array, which acts as the stack, a quotation, which it calls, and returns the array/stack, which now has the results of calling the quotation. For example: { 1 2 3 } [ + ] with-datastack . would output { 1 5 }. This can now be used to easily rectify my problems! In funcall, before looking up the variable name and calling the resultant quotation, it does 1array [ call ] with-datastack >quotation to the quotation which contains the argument list. Simple, easy, and clear!

What next?

Although I've said it before, it looks like I'm nearly done the factor side of this...All I have left to do is fix up my implementation of macros and provide facilites for loading and interpreting/compiling lisp files and I'll be just about done! At that point, I'll start bootstraping the lisp implementation in lisp itself, but the real "hard work" will be done. Wish me luck!

Factor and Lisp, part two

I've been continuing my work on extra/lisp, and I've finally realized the solution to my current problem, that of macros. The solution, in a nutshell, was to replace the arrays I'd been using to represent lisp s-expressions with actual linked lists. After Slava pointed this out to me, I began work on a simple implementation of the lists. However, my work had not gone far, when the good doublec suggested that, as there was a great deal of overlap, I move my extra/lisp/conses to extra/lists and merge it with extra/lazy-lists (now known as extra/lists/lazy). This took a while, as I also ended up refactoring lazy-lists to use new style accessors and then had to go through all the vocabs that used lazy-lists (which actually wasn't that many) to figure out which needed to be USING: lists, lists.lazy or both.

And then, things get interesting!

After this, things began to get odd...A test starting failing in extra/lists/lazy. It seemed that >>nil? (which, if you're not familiar with factor is a "new-style" accessor: You'd use it like obj new-nil?-val >>nil?, and would leave the modified obj on the stack - elegant, n'es pas? (the converse of that would be nil?>>, which would work like obj nil?>>, and would leave obj's value of nil? on the stack)) was being called on the wrong type of object: That accessor is supposed to be called on a memoized-cons, but was being called on a lazy-filter. This seemed patently impossible to me, as the only place that the word was called was in a method of memoized-cons, meaning that the only possible value that could be on the stack was a memoized-cons.

n After puzzling this one over for a while, and vainly trying to use Factor's normally very usefully walker to determine what was happening, I brought the matter to the attention of the gurus of #concatenative. At the recommendation of doublec, I tried inserting print statements in the word, to figure out where the object was changing from a memoized-cons to a lazy-filter.

The results left me even more puzzled than before.

My descent into madness intensifies

Initially, I tried just printing out the object that >>nil? was dispatching on: As expected, I saw that, while the first dozen times it was called, it was receiving the proper memoized-cons object, it was indeed ending up with a lazy-filter. Okay...that shouldn't be happening, but I already know that it is, so that's at least somewhat expected. What happened next was, however, quite unexpected.

"Well," I thought. "I can see that it's a lazy-filter here...but it must be a memoized-cons when it enters...I know, I'll put print statements throughout the word, so I can see just where it changes!"

Now, below is the word sans debugging print statements:

M: memoized-cons nil? ( memoized-cons -- bool )
    dup nil?>> not-memoized? [
        dup original>> nil? [ >>nil? drop ] keep
    ] [
        nil?>>
    ] if ;

(if you don't understand this, go to the Factor home page, and start learning)

After adding various debugging print statements, it looked like this:

M: memoized-cons nil? ( memoized-cons -- bool )
    "Entering nil?: " write dup class . dup nil?>> not-memoized? [
        "True branch: " write dup class . dup original>> nil? [ "Now at >>nil?" write over class . >>nil? drop ] keep
    ] [
        "False branch: " write dup class . nil?>>
    ] if "\n" write;

So now, after reloading lists.lazy and running the test case, I get a bunch of output like this:

Entering nil?: memoized-cons
True branch: memoized-cons
Now at >>nil?: memoized-cons

Entering nil?: memoized-cons
False branch: memoized-cons

Entering nil?: memoized-cons
True branch: memoized-cons
Now at >>nil?: memoized-cons
  

So, ready for the weird stuff? Here're the last two calls...

Entering nil?: memoized-cons
False branch: memoized-cons

Now at >>nil?: lazy-filter
  

Um...what? The print statements at the begining of the word, and on the conditional branch that was taken aren't being called. It seems that it's somehow jumping into the middle of the word, without calling anything prior to this one section.

What Next?

Well, I have no idea why this happening. doublec hypothesizes that I've exposed a bug in method dispatch. I'm not sure what else I can do, if that is indeed the case...I guess I'll wait until Slava returns and see if he can figure it out.

In the meantime, I guess I'll keep working on extra/lisp, which was the point of this whole exercise, was it not?

Update:The next day, I went through the code some more and realized I was looking at the wrong place: The bug was actually in the code for lazy-filters, and had to do with the transititon to new-style accessors. The skip word needed a drop at the end, since the new >>foo has the stack effect ( obj newval -- obj ), while the old version it replaced, set-obj-fo had the effect ( newval obj -- ).

Factor + Lisp = It Doesn't Get Much Better

So, I've started work on my first real Factor project: Writing a implementation of Lisp in Factor (which is referred to as "extra/lisp", as that is where it lives in the Factor repo). I'm having some weird problems with local variables and transformations, but it's going pretty well, and I am having tons of fun with it.

So, how does it work?

The structure of the Lisp compiler is fairly simple: First, it parses the Lisp code from a string into a Factor data structure using Chris Double's (a.k.a. doublec) awesome peg.ebnf, which allows you to just write out the EBNF for your grammar. The really neat thing about this is that, rather than your typical parser generator, this creates a "packrat" parser, which supports both direct and indirect left recursion. Very cool!

After the string is parsed, I then run a simple recursive transform on the code. Such is the beauty of Lisp, that I only need about five special cases (currently lambda, quote, if,begin, and cond - and yes, I know I don't need both cond and if, but it's easier this way). In general, the transformation turns (foo bar baz) into [ bar baz foo ] , albeit with some funny tricks to deal with variadic functions.

Current Status

Well, right now, it's failing when calling lambdas. Apparently, in the lambda-quotation [| x | x ], the two x's are not eq?. Not quite sure why, but I'm working on it. Once I get that working, all I really have left to do is do macros (which shouldn't be too hard, as I can just piggy-back off Factor's MACRO: (or so I hope)), and then I can start bootstraping it in Lisp. Should be fun!

Addendum

By the way, if you're interested, you can take a look at what I've done so far at git://factorcode.org/git/jamesnvc, or take a look in the main Factor repo (under "extra/lisp") as Slava pulls it in.

Almost there....

I haven't been able to write for a while, what with the trying to not fail my first year. Tomorrow is the last day of exams though, so I hope to start writing again soon. So, quick update: I'm programming pretty much exclusively in Factor now. It is tons of fun: Factor is pretty much the coolest language I've used (including Lisp!), and being able to talk (via IRC) with the creator and chief architects of the language is really neat. I've made some minor commits so far, namely writing the deployment tool for *nix platforms, which was actually pretty easy. Right now, I'm working on implementing a Lisp compiler in Factor, which is tons of fun. It's coming along pretty well now and I hope to finish it off when I finish exams. So, off to study more for ECE...I shall return!

Nothing to say

I've been too busy the past while to set aside time to write here. In fact, I feel like I should be studying linear algebra or something instead of writing this. Oh well...if I don't write this, I'll just waste even more time reading archives of Coding Horror or something.

So, I haven't been able to do much programming recently, which is kind of disappointing. Oh well...this summer! I'm thinking of contributing to some open source projects this summer, that will be good experience, I think. I have been playing around with a bunch of different languages though: I still want to use Factor more, but Common Lisp is always close to heart, reading why the lucky stiff and Tim Bray are making me think of Ruby, a few posts on OCaml tempting me back in that direction...blah. Too hard to choose one thing to do. Especially when, you know, I really shouldn't be doing any of that, what with the workload I have now.

So...I don't really have anything to write here. Just wanted to post something to keep this active. I'll try to think of something interesting to write about this week, promise!

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.

On Taste

Note: Before reading this entry, you should probably read Paul Graham's essay on the same topic. In fact, you should read all, they're quite good.

So, yesterday I was talking to a friend about how a mutual acquaintance of ours, while being a nice guy, had remarkable poor taste. Most of his favorite authors, television shows, video games, etcetera, were almost uniformly what one would charitably refer to as "trashy", or less charitably refer to as "bad".

Well, since you read Paul Graham's article I pointed you to at the beginning (you're so studious!), you understand the premise that no, he isn't entitled to his opinion in this case: Some things just aren't as good as others, and liking those things equates to bad taste. So, my question is, can you learn better taste? I'm sure that you could learn to like things that are better—if we took away some hypothetical person's bad music, movies and books, and had them just listen to Tchikovsky, watch Citizen Kane, and read Shakespeare (or whatever we'd agree upon is good, for some value of "good"), they'd probably get used to it eventually—but does that necessarily mean one will have better taste? Would one still seek out better materials, or would they remain unable to tell the difference in quality between Dan Brown and William Faulkner?

This is not a trivial problem.

I'm really not too sure what the answer is. In fact, as writing this, I realized how poorly defined "taste" is: When giving my examples of "good" things to force feed someone, I knew full well that people would have issue with some of the items. How can we objectively assess how good something like art/entertainment is? I do agree with Paul's thesis that there is such a thing as good taste or bad taste, but I think that one can only really assess it by what they create, since judging what they like is too hard, and will probably be reflected in their creations anyway.

Of course, all this does is move the problem from defining judging if what they like is good to judging if what they've made is good. However, I would intuitively say that this is a more tractable problem: If they've made something elegant, that works well, and is appealing to some statistically significant (for some value of "significant") audience. Essentially, I think that the popularity of the creation is positively related to one's taste, if not directly proportional. Then again, if that's a valid metric, why can't we use it to assess what people like (I think I'm starting to tread into a Zen and the Art of Motorcycle Maintenance-esque "what is Quality" question, which is an established Hard Problem...)? Is there some fundamental difference in judging someone by what they make, rather than by what they like?

Again, not a trivial problem

That being said, I think there is a difference. When you create something, you have to actively think about how this system is going to be designed: You have to consider all aspects of it, while when one is the passive recipient of something, you typically only notice the most superficial level. Therefore, when choosing what you like, it will probably be based on popularity first, since that is most likely the criteria you encounter. On the other hand, if you create something, then you see every aspect of it: At that point, it's being good or bad is more dependent on your taste, as it controls every aspect of what is being designed.

Well, not sure if that made sense to anyone else, but whatever. No-one reads this anyway (except you, of course. Thanks!).

In any case, my original question is still unanswered: Is it possible for someone to learn good taste? With my new pseudo-definition of taste, I would now say yes, it is. You can improve your taste (at least as it pertains to a particular domain) by good designing things. Determining how to design good things is left as an exercise to the reader.

Next time!

So, with my Algorithm X implementation done, I probably should design the sudoku solver that it was originally for...but, know what I think will be more fun? Writing a lexer/parser for ECMAscript 4. Hopefully, this will turn into the front-end for the compiler I keep planning on writing...

Anyway, laughs aplenty sure to follow!

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!