Game Jam

The first part is a journal of thoughts as they were happening, so try not to laugh at me too hard. The second part is a bit of reflection on the project so far. This is a summary/record of my week participating in the 2011 Spring Lisp Game Jam. Hopefully, it's useful to someone (the very act of writing it was very useful to me).

---

April 23

I did the first public facing push of this code-base at about 4:00 am my time today, and then curled up into bed. When I got up at 10:30, there was already a bug report waiting for me. Not off to a spectacular start...

The problem turned out to be how cl-css handles file compilation. Specifically, it fails if the directory it's trying to compile to doesn't exist. At this point, I'm ready to load up cl-fad to whip up a simple fix, except that cl-fad doesn't have a function to create directories. Okay... maybe it's a Lisp primitive then? A quick search for "directory" over at the hyperspec symbol index turns up nothing. So...huh? I spend 10 minutes checking the cookbook and googling fruitlessly[1]. That doesn't discourage me though. I commonly run into situations where I have a naive mental model of a given problem that some Lisper has already built an elegant solution to. So I google the more general case common lisp making directory, which turns up a lispworks doc page abut ensure-directories-exist.

This is what I meant. When I'm making a directory, I really just want a place to put some specific file. Abstracting the basic directory creation means that I don't have to special-case the situation where multiple nested directories are required, and I also don't need to worry about checking whether the directory exists before creating it. Elegant. Maybe this is a good start. Day 1 and I'm already learning something.

April 24

I went pretty batshit on the code-base today, removing anything that looked like an unnecessary additional step. I'd been keeping the model and view as separate as possible because of an assumption that there would be some sort of SQL database involved in the game eventually. I may still need to switch to one at some point, so the move might come back to bite me in the ass, but the barriers got broken down. Mostly it was intermediate functions all over the place that slightly simplified the next set of intermediate functions[2]. Things like planet-info and inventory which took model structs and returned plists instead. To be fair, that actually did help at some point; since there doesn't seem to be a way to map over a struct, it was very easy to dump an entire plist into the view with a loop.

Anyway, I made the decision during my shower that I'm keeping the struct approach since I think it might help with the concurrency issues I'll be facing next. There's also one decision from earlier that's sort of coming back to haunt me there. The way that a given captain's current planet is stored is as a string of that planets' name. That meant that I needed a function called planet-name->planet early on, and it meant that any manipulation of the current planet happened directly on the *galaxy*. It's fine for a single player, but more would cause some odd errors that wouldn't be particularly fun. The way I'm thinking of solving that is by having each captain copy out the current planet, and keep track of transactions they conduct. The total changes would then get applied when they travel. A given market could still dip into the negatives in some circumstances, but it should serve to make it much harder to force an error on an opponent sharing your planet.

Finally, markets behave differently now. Instead of static prices, each market generates a new price from the *tradegoods* and averages (By which I mean "gets the arithmetic mean of") that with its current price. It just makes sure that markets tend to stabilize over time, while hopefully keeping enough fluctuations to make profit possible.

April 25

Changed up a lot more of the system. Today, I focused on the purchase!/convey! end of things rather than the basic model. Basically, captains now have a copy of the planet they take with them and merge transactions back later. As I mentioned yesterday, this isn't a measure to make sure that no more product leaves a planet than absolutely should. In fact, I'm tempted to make deficit exports an explicit mechanic, upping the price of a good fairly substantially if it slides into the negatives. That would also play off a tweak I want to make to the market-produce! function. Namely, generating (+ 4d20-30 (/ productivity tech-level)) instead of the current (+ 2d20 (/ productivity tech-level)) to allow goods to be consumed as well as created by planets[3].

Today's lesson[4] was that state is fucking hard. Introducing side-effects to a primarily functional system played more hell with my code than I thought it would. I still don't know if I squashed every possible bug with that transaction system. It's enough to make me go paranoid and start sprinkling asserts in the vicinity of all setfs and !s. I won't yet; I'll wait 'till something unexpected blows up, but I can see an argument for it here. The end result is that this game should now be playable by more than one human at a time. There's no explicit goals yet, I'm going to save that for later, I think, but you can still get a few friends together on a lan[5] and play economic hell with a small galaxy with the game as it stands.

[Break time to remodel my kitchen. Did a bit of light view coding, but nothing interesting to report.]

April 28

Spent today mainly on the UI end. Making it pretty-ish and squashing a few display bugs I came across. Still not happy with the default theme, but it's all I'll have time for in a week. I did make an effort to completely disconnect it from all other code, so others can theoretically just push a folder of images+theme.css to add a new one. The entire experience was a bit surreal; in the middle of using GIMP to do some graphic design work, I found myself embroiled in a conversation on Reddit about how GIMP is not good enough to do design work. Since the best argument I read was "But, I like Photoshop!" I'll stick with the free[6] version, thank you.

Part of that UI tweaking mentioned above was adding jQuery and jQuery UI to the codebase. I didn't want to have to tell people to go download it themselves, and there's really nothing that needs to be done other than putting them in the correct directories. The downside is that this is now considered a Javascript project by GitHub. Which, ok, I guess is true by character count, but it still feels inaccurate.

April 29

I realized earlier today that my time's officially up for this little project[7]. Technically, time ran out about an hour ago, but I kinda got into the swing of things and decided to finish one last TODO before doing a final check-in for the event and collecting my thoughts. That ended up taking more time than I thought it would, but it really was my own fault for giving into indecision for so long. The game looks passable, it plays nicely, doesn't seem to blow up[8] and is actually pretty fun[9]. I really shouldn't have picked out something this ambitious for a week I knew I'd be occupied, but hey. Such is life, I guess. I'll keep working on it for as long as I can stand to look at the code-base, but for the moment, it's done.

Anyway, lets get to the juice; here's the distillation of what I learned in trying to put together a small-ish game in Lisp over the course of a week.

Incremental beats planned...

It was honestly surprising how true this turned out to be. I started out trying to plan out as much stuff as possible into the future, going so far as to put several levels of indirection into the model in case of a switch to a relational database later. That... was a tremendous waste of time. Both in the sense that useless code was produced as a result, and that I then had to spend time going through call-trees to figure out what a given function was actually doing. I got fed up with that fairly early on in the week and went on an already noted rampage through the model, deleting everything that I wasn't actively calling right now, preferably in multiple places.

Overall, the time spent just diving in and writing code resulted in a lot more of the final code-base than carefully plotting out where I needed to go[10]. That's probably partly a result of the plans not being comprehensive enough, and partly a result of the plans changing mid-way. I'd argue that's healthy though; there are some specific interaction points that I'd have been hard pressed to predict in advance, but that became perfectly obvious when I tried to implement them properly.

Don't read this as "don't plan", because it does save a bit of time, but not as much as I thought[11]. My best guess is that there's some point of diminishing returns with planning. You want to do about that much because doing less causes some pretty serious headaches in terms of direction, but if you do more, you're not helping (and are likely hurting). That's just a hypothesis based on my experience, of course, I'd love to see some experimental data about it.

...but remember to fix it up

The other side of the incremental approach is that it ends up producing a lot more code. The main catch is that you need to remember to stay flexible, since you might be changing large portions of the system at any given point. Even so, prospective coding still turned out to be a very powerful tool. Producing more code does mean that you have to periodically measure and cut again. There are already two places where I can see a lack of planning costing me efficiency, but I'm not sure I would have been able to predict that in advance.

Distractions hurt. A lot.

That really shouldn't even need saying, but there you have it. Trying to code up a storm doesn't work out very well when you're also re-modeling your kitchen. I'll know for next time, I guess. The one upshot is that it resulted in a system that's easy to fit in my head basically by necessity, because I had no hope whatsoever of getting an entire 8 hour stretch of time devoted to it.

Deadlines help. A lot. No, more than that.

I've had this project on the back-burner for close to four months. In those four months, I've managed to put together a half-way decent name generator and comb over the code-base for Elite for Emacs a dozen times or so. In the past five days or so, I did the rest of it[12]. The deadline helped get me in gear where I probably would have sat indecisively for a further few months. Even with all the distractions, I easily did four times as much work since the beginning of the game jam as I did since starting on this.

Reflection helps. A lot. No, more than that. Keep going. A bit more. Ok, there.

Even more than the deadline, the fact that I had to look at this from different perspectives helped a lot. It wasn't just writing code, there was also a lot of brain power spent on thinking about how I would explain the code, what it meant in the grander scheme of the project, and whether there was a better way of doing it. It's a bit counter-intuitive, but it seems that reflection (thinking about things you've just done) is a lot more useful and a lot more productive than planning (thinking about things you're going to be doing soon). I didn't end up explaining it very well regardless, but the process of thinking up said explanations seemed to help in the construction regardless.

I don't know enough

Probably the biggest one. I'm not sure if any hypothetical reader can apply this, but I sure as hell will. I've got a lot of learning left to go in pretty much every direction. First, I get the feeling that most of the model could have been put together much better using CLOS than my current approach of structs and functions. For example, planet-produce!, add-to-market!, banned? and local?[13] would have made more sense as methods. I can say that without actually knowing much about CLOS other than the name, and I'll be going through documentation and tutorials as soon as I can squeeze it into my day. The 3D math is also something I'm rusty on. I could swear I used to know this stuff back in high school, but got surprisingly little use out of it since. It would have helped a lot. Specifically, having a clearer understanding of 3D transformation would have let me create an actual 3D interface instead of faking it poorly with layers. I've ... gotta work on that. Lastly[14], I still have no clue how to use loop properly. I gather I'm not alone since it gets its own chapter in both PCL and the CL Cookbook, but it still caught me by surprise how deep the construct is.

So there. I knew I knew little, but it turns out I knew less than I knew.

That's certainly something to fix for next time.

---

Footnotes

1 - [back] - "I guess Lisp can't create directories." Is what I would have thought about two years ago

2 - [back] - And by "slightly", I mean "almost not at all"; the functions that did do necessary abstraction are still there

3 - [back] - Produced, on balance, but it opens up that scarcity mechanic

4 - [back] - Or, rather, reminder.

5 - [back] - Or an open server, if you're feeling especially frisky

6 - [back] - Libre, not gratis (although GIMP is that too).

7 - [back] - leastwise, my time for the Game Jam is up

8 - [back] - even when there are multiple people playing at once

9 - [back] - though at the moment, it's really a lot of economic activity for its own sake because I didn't get to TODO: Goals or TODO: Ship upgrades yet

10 - [back] - which is to say, most of the code resulting from careful planning was later replaced by code that had an immediate, unplanned need

11 - [back] - and probably not as much as you think, if you're a Joel fan

12 - [back] - which is to say, ported it from Elisp to CL, a working market system, GUI with faux-3D interface, debugging and a copious amount of testing

13 - [back] - and others besides, I'm sure

14 - [back] - or, at least, the last specific thing I was surprised to find myself ignorant of

Writing Less C in Lisp

It seems that I only ever get around to working on this pet project when I'm sick (which I was earlier this week). It's taken almost 5 months at this point, but the hours counter is really closer to ~15, which means that I could have done the work during a single, particularly slow, weekend.

Anyway, moving on, I've been plaing around with the codebase for Elite for Emacs (and there's a post around here somewhere that details some of the blunders it contains). Today, I'm dealing with the next level up; not pointing out where primitives are being misused, but pointing out needless patterns where they don't belong and showing one way of composing them properly. Actually, now that I look at it, I'd better take a single pattern out and deconstruct it lest I bore the ever-living shit out of everyone, including me. I'm also not eliding anything this time, this is going to deal with specifics from the Elite for Emacs 0.1 codebase and how I'm thinking about re-implementing them.

Describing Things

Actually, before I get to that one,

Random Numbers

At a cursory examination, I've found myrand, randbyte, rand1 and gen_rnd_number (and no uses of the the built-in rand function). They may or may not do similar things. The author also insists on tracking his own random number seed in a global variable (and re-generating it with a function named mysrand). Here's a sample

(defun gen_rnd_number ()
  (let ((a)
        (x))        
    (setq x (logand (* (fastseedtype-a rnd_seed) 2) #xFF));
    (setq a (+ x (fastseedtype-c rnd_seed)))
    (if (> (fastseedtype-a rnd_seed) 127)
        (setq a (1+ a)))
    (setf (fastseedtype-a rnd_seed) (logand a #xFF))
    (setf (fastseedtype-c rnd_seed) x)
    (setq a (/ a 256)); /* a = any carry left from above */
    (setq x (fastseedtype-b rnd_seed))

    (setq a (logand (+ a x (fastseedtype-d rnd_seed)) #xFF))
    
    (setf (fastseedtype-b rnd_seed) a)
    (setf (fastseedtype-d rnd_seed) x)
    a))

I'm not sure why Lisp coders get stick for re-implementing infrastructure if this is reasonably common in the outside world. Building your own byte-oriented random number generator is something a Lisp can do, but[1] you really shouldn't. If you were in the middle of writing your own implementation of rand in Elisp, Common Lisp or Scheme before you started reading this, please just do us both a favor and stop.

Now then.

Describing Things

Here's how Elite for Emacs generates planet descriptions.

(defun elite-for-emacs-planet-description (galaxy-index system-index)
  "Return planet description"
  (let ((planet-sys)
        (rnd_seed))
    (setq planet-sys (aref (aref elite-for-emacs-galaxies-in-universe galaxy-index) system-index))
    (setq rnd_seed (copy-fastseedtype (plansys-goatsoupseed planet-sys)))
    (setq elite-for-emacs-planet-description "")
    (goat_soup "\x8F is \x97." planet-sys)
    elite-for-emacs-planet-description))

Which actually lulled me into a false sense of security the first time around because it seemed

1. functional-ish
2. short
3. simple

There's one thing there that should have set alarms off though. What kind of name is goat_soup?

(defun goat_soup (source planet-sys)
  (let ((c)
        (rnd)
        (source-list nil)
        (tmp)
        (i)
        (len)
        (x))
      (setq tmp (split-string source ""))
      (setq source-list nil)
      (while tmp
        (setq c (car tmp))
        (setq source-list (append source-list (list (string-to-char c))))
        (setq tmp (cdr tmp)))
      (while source-list
        (setq c (car source-list))
            (if (< c #x80)
                (setq elite-for-emacs-planet-description (concat elite-for-emacs-planet-description (list c)))
              (progn
                (if (<= c #xa4)
                    (progn (setq rnd (gen_rnd_number))
                      (setq tmp 0);;true: non-zero, zer=false
                      (if (>= rnd #x33)
                          (setq tmp (1+ tmp)))
                      (if (>= rnd #x66)
                          (setq tmp (1+ tmp)))
                      (if (>= rnd #x99)
                          (setq tmp (1+ tmp)))
                      (if (>= rnd #xCC)
                          (setq tmp (1+ tmp)))
                      (goat_soup (nth tmp (nth (- c #x81) desc_list)) planet-sys); .option[()+(rnd >= 0x66)+(rnd >= 0x99)+(rnd >= 0xCC)] planet-sys))
                  (progn ;;switch...
                    (cond ((= c #xB0);;planet name
                           (setq elite-for-emacs-planet-description 
                                 (concat elite-for-emacs-planet-description 
                                         (capitalize (plansys-name planet-sys))))
                           ;;(insert (capitalize (plansys-name planet-sys)))
                      )
                     ((= c #xB1);; /* <planet name>ian */
                      (setq tmp (capitalize (plansys-name planet-sys)))
                      (if (and (not (string-match "e$" tmp)) (not (string-match "i$" tmp)))
                          (setq elite-for-emacs-planet-description (concat elite-for-emacs-planet-description tmp))
                        (progn ;;(setq tmp "helleinooio")
                          (setq elite-for-emacs-planet-description (concat elite-for-emacs-planet-description (substring tmp 0 (1- (length tmp))) "ian" ));;(insert (substring tmp 0 (1- (length tmp))))
                          )))
                     ((= c #xB2);;/* random name */
                      (setq i 0)
                      (setq len (logand (gen_rnd_number) 3))
                      (while (<= i len)
                        (setq x (logand (gen_rnd_number) #x3e))
                        (if (/= (aref pairs x) 46);;46='.' (string-to-char ".")
                            (setq elite-for-emacs-planet-description (concat elite-for-emacs-planet-description (char-to-string (aref pairs x))))
                             )
                         (if (and (> i 0) (/= (aref pairs (1+ x)) 46))
                             (setq elite-for-emacs-planet-description (concat elite-for-emacs-planet-description (char-to-string (aref pairs (1+ x)))))
                             )
                         (setq i (1+ i)))
;;                                              case 0xB2: /* random name */
;;                              {       int i;
;;                                      int len = gen_rnd_number() & 3;
;;                                      for(i=0;i<=len;i++)
;;                                      {       int x = gen_rnd_number() & 0x3e;
;;                                              if(pairs0[x]!='.') printf("%c",pairs0[x]);
;;                                              if(i && (pairs0[x+1]!='.')) printf("%c",pairs0[x+1]);
;;                                      }
;;                              }       break;

                       ))))))
            (setq source-list (cdr source-list)))))

The kind that designates a procedure built out of dead things, most of which you'd really rather not think about.

I've removed the irrelevant comments[2], but the above is still considerably longer than what I consider good style for a single function. Later on, there's a snippet of code that looks like

(defconst desc_list
  (list
;; 81 */
        (list "fabled" "notable" "well known" "famous" "noted")
;; 82 */
        (list "very" "mildly" "most" "reasonably" "")
;; 83 */
        (list "ancient" "\x95" "great" "vast" "pink")
;; 84 */
        (list "\x9E \x9D plantations" "mountains" "\x9C" "\x94 forests" "oceans")
;; ... continues for a further 69 lines

What it does in context, basically, is take the string "\x8F is \x97." and expand it out recursively until all the "byte" references are gone and it ends up with a little semi-sensical, explanatory description like "The planet is reasonably famous for its inhabitants' ingrained shyness but scourged by deadly edible wolfs." or "The planet is famous for its pink parking meters.".

The non-lisp thing I hinted at last time, and wanted to discuss this thime out, is this idea of byte-orientation. This is an architecture built by someone used to assembly or C, that then tried to shoehorn the same way of looking at the world into Lisp. I wouldn't mind so much, but it's far too easy to imagine someone hacking together a system like this and thinking to themselves "Wow, this really sucks. I could have done it MUCH more efficiently in C, and I wouldn't have had to deal with all this 'list' and 'setq' nonsense. I guess Lisp is just a language for masochists...". Going against the grain of any language creates the impression that it's less powerful than it really is, and this is a prime example.

I took a minute out at the beginning of this post to point out how this codebase re-implements random number generation at a very low level. Well, the reason I consider it an egregious mistake here is that the main place I found that particular generator used is in goat_soup above. In other words, the coder set up a list (and associated various bytes with each element), then used gen_rnd_number to generate an appropriate byte and then pick out an element from the resulting list. The really funny part is that I could see this being implemented as a performance optimization in a C version of this game, but when you're dealing with string representations of bytes that you have to split and convert before operating on, any performance gains fly directly out the window.

It's beside the point, though. Remember, Lisp is a symbolic language. So here's a Lispier way of generating some planet descriptions.

(defparameter *planet-desc-grammar*
  (list :root '((" is " :reputation " for " :subject) 
                (" is " :reputation " for " :subject " and " :subject) 
                (" is " :reputation " for " :subject 
                 " but " :adj-opposing-force " by " :historic-event)
                (" is " :adj-opposing-force " by " :historic-event) 
                (", a " :adj-negative " " :syn-planet))
        :subject '(("its " :adjective " " :place) 
                   ("its " :adjective " " :passtime) 
                   ("the " :adj-fauna " " :fauna) 
                   ("its inhabitants' " :adj-local-custom 
                    " " :inhabitant-property) 
                   :passtime) 
        :passtime '((:fauna " " :drink) (:fauna " " :food) 
                    ("its " :adjective " " :fauna " " :food) 
                    (:adj-activity " " :sport) 
                    "cuisine" "night-life" "casinos" "sit-coms") 
        :historic-event '((:adj-disaster " civil war") 
                          (:adj-threat " " :adj-fauna " " :fauna "s") 
                          ("a " :adj-threat " disease") 
                          (:adj-disaster " earthquakes") 
                          (:adj-disaster " solar activity")) 
        :place '((:fauna :flora " plantations") (:adj-forest " forests") 
                 :scenery "forests" "mountains" "oceans")
        :technology '(:passtime "food blenders" "tourists" "poetry" "discos") 
        :inhabitant-property '(("loathing of " :technology) 
                               ("love for " :technology) 
                               "shyness" "silliness" "mating traditions") 
        :fauna '("talking tree" "crab" "bat" "lobster" "shrew" "beast" "bison" 
                 "snake" "wolf" "yak" "leopard" "cat" "monkey" "goat" "fish" 
                 "snail" "slug" "asp" "moth" "grub" "ant") 
        :flora '((:fauna "-weed") "plant" "tulip" "banana" "corn" "carrot") 
        :scenery '("parking meters" "dust clouds" "ice bergs" 
                   "rock formations" "volcanoes") 
        :reputation '((:emphasis " " :reputation) 
                      "fabled" "notable" "well known" "famous" "noted") 
        :emphasis '("very" "mildly" "most" "reasonably") 
        :drink '("juice" "brandy" "water" "brew" "gargle blasters") 
        :sport '("hockey" "cricket" "karate" "polo" "tennis" "quiddich") 
        :food '("meat" "cutlet" "steak" "burgers" "soup") 
        :adjective '((:emphasis " " :adjective) 
                     :adj-local-custom :adj-fauna :adj-forest :adj-disaster 
                     "great" "pink" "fabulous" "hoopy" 
                     "funny" "wierd" "strange" "peculiar") 
        :adj-fauna '(:adj-threat "mountain" "edible" "tree" "spotted" "exotic") 
        :adj-negative '((:adj-negative ", " :adj-negative) 
                        "boring" "dull" "tedious" "revolting") 
        :adj-local-custom '("ancient" "exceptional" "eccentric" "ingrained" "unusual") 
        :adj-forest '("tropical" "vast" "dense" "rain" "impenetrable" "exuberant") 
        :adj-disaster '("frequent" "occasional" "unpredictable" "dreadful" :adj-threat) 
        :adj-threat '("killer" "deadly" "evil" "lethal" "vicious") 
        :adj-activity '("ice" "mud" "zero-g" "virtual" "vacuum" "Australian, indoor-rules") 
        :adj-opposing-force '("beset" "plagued" "ravaged" "cursed" "scourged") 
        :syn-planet '("planet" "world" "place" "little planet" "dump")))

That's the data, at any rate. The above uses all the original words and combinations from the Elisp codebase (I did add "Australian, indoor-rules" to the activity adjective list, but that's all), so the descriptions popping out of it should be the same as those coming out of goat_soup and friends. Note that the * surrounding the variable name denote a global variable[3]. Note also that instead of using byte relations, the plist approach lets me avoid splitting strings in intermediate steps. A terminal is a string and a non-terminal is an atom. The way to unfold these is

(defun expand-production (production grammar)
  (cond ((stringp production) production)
        ((symbolp production) 
         (expand-production (pick-g production grammar) grammar))
        ((listp production) 
         (reduce (lambda (a b) 
                   (concatenate 'string a (expand-production b grammar))) 
                 (cons "" production)))))

pick-g is a function that takes a key and grammar, and returns a random expansion of that key in that grammar.

(defun pick-g (key grammar) 
  (let ((choices (getf grammar key)))
    (nth (random (length choices)) choices)))

In other words,

• a string gets returned
• an atom gets expanded (by looking it up in the grammar and picking a random possible expansion)
• a list gets expanded (by expanding each of its elements)

* (expand-production :root *planet-desc-grammar*)

" is fabled for its inhabitants' ancient love for ice tennis"
* (expand-production :root *planet-desc-grammar*)

", a revolting little planet"

All I have to make sure is that these get displayed along with the planet name and we're golden. This is the sort of elegance that Lisp is capable of when you go with the grain. ~140 lines of flaming death and side effects replaced by two recursive functions and a plist that succinctly and accurately signal the intent of the programmer. I wouldn't be particularly surprised if there's an even simpler way to accomplish the same thing, actually.

Naming Things

Planet names seem like they should be implemented the same way, given what they really are. In fact, I did just implement them as another grammar that depends on the same functions to unfold, but the original takes a different approach.

;; buried at line ~103 of a single function that generates a planet
  ;set name
  ;init alphabet pairs
  (setq pair1 (* (logand (lsh (seedtype-w2 s) -8) 31) 2))
  (tweakseed s)
  (setq pair2 (* (logand (lsh (seedtype-w2 s) -8) 31) 2))
  (tweakseed s)
  (setq pair3 (* (logand (lsh (seedtype-w2 s) -8) 31) 2))
  (tweakseed s)
  (setq pair4 (* (logand (lsh (seedtype-w2 s) -8) 31) 2))
  (tweakseed s)
  ;Always four iterations of random number
  (setq planet-name
        (concat 
         (code-to-char (aref pairs pair1))
         (code-to-char (aref pairs (1+ pair1)))
         (code-to-char (aref pairs pair2))
         (code-to-char (aref pairs (1+ pair2)))
         (code-to-char (aref pairs pair3))
         (code-to-char (aref pairs (1+ pair3)))))
  (if (/= longnameflag 0)
      (progn
        (setq planet-name 
              (concat
               planet-name
               (code-to-char (aref pairs pair4))
               (code-to-char (aref pairs (1+ pair4)))))))
  (setf (plansys-name thissys) (stripout planet-name "."))

pairs showed up in goat_soup too, and it's defined as

(defconst pairs 
  "..LEXEGEZACEBISOUSESARMAINDIREA.ERATENBERALAVETIEDORQUANTEISRION"
  "Characters for planet names.")

s is passed as an argument to the planet-generator, the rest of which I won't inflict upon you, I think you may have gotten the idea already. In other words, planets are restricted to 4 syllable names put together by side-effect in the procedure that creates planets. They're put together by using byte operations on a string that represents the valid pair combinations contained in a planet name.

Well, seeing as I already put together a convention for unfolding components to strings by using a recursive function and a plist, I figured I'd do the same for this. Code reuse is good, I hear.

(defparameter *planet-name-grammar*
  ;be mindful of name probabilities if you try to reduce duplication here
  (list :root '((:starter :link :ender) (:starter :partition :ender) 
                (:starter :partition :link :ender) 
                (:starter :partition :root) 
                (:starter :link :link :ender) (:starter :ender))
        :starter '((:starter :link)
                   "aa" "ae" "al" "an" "ao" "ar" "at" "az" "be" 
                   "bi" "ce" "di" "ed" "en" "er" "es" "ge" "in" 
                   "is" "la" "le" "ma" "on" "or" "qu" "ra" "re" 
                   "ri" "so" "te" "ti" "us" "ve" "xe" "za")
        :ender '((:link :ender) 
                 "aa" "al" "at" "di" "ti" "so" "ce" "re" "za" 
                 "in" "ed" "or" "an" "ma" "ab" "ge" "aq" "en" 
                 "ri" "ve" "ag" "qu" "us" "es" "ex" "ae" "on" 
                 "bi" "xe" "le" "is" "er" "be" "la" "ar" "az" 
                 "io" "sb" "te" "ra" "ia" "nb")
        :link '((:link :link) (:link :link)
                "at" "an" "ri" "es" "ed" "bi" "ce" "us" "on" 
                "er" "ti" "ve" "ra" "la" "le" "ge" "i" "u" 
                "xe" "in" "di" "so" "ar" "e" "s" "na" "is" 
                "za" "re" "ma" "or" "be" "en" "qu" "a" "n" 
                "r" "te" "t")
        :partition '("-" "'" " ")))

[4]And that's that. It unfolds into planet names with the same mechanisms

* (string-capitalize (expand-production :root *planet-name-grammar*))

"Ri Orleio"
* (string-capitalize (expand-production :root *planet-name-grammar*))

"Xenain"

* (string-capitalize (expand-production :root *planet-name-grammar*))

"Es'Ae"

string-capitalize just makes sure it looks like a proper name (it's a lisp primitive, so I won't define it here). The important part, which I'll likely cover in a future post, is that making things functional aids in composeability. The setq sequence from the original codebase has no hope of being reused anywhere because it intentionally grubs about in the surrounding state. If nothing else, the expand-production approach ensures that if I ever need a planet name in some other context, I can easily generate it. Also, as we've seen already, abstracting out the general pattern of "compose strings from a given pattern of components" easily pays for itself with even one instance of reuse.

My Sinister Purpose

The reason I've been picking away at this codebase isn't idle fancy[5], or an intense hatred of Sami Salkosuo[6]. It's that I've been putting together a little web game based on it. It's still not done, mind you, but I'm going to try to put something together fairly soon for you to poke at (even if it's ugly as sin from the visual perspective to start with). If nothing else, I'm tossing the ported Common Lisp codebase up onto my GitHub this weekend so that some other pedantic bore can pick apart a project I was just doing in my spare time. After two articles full of bitching about poor style and inelegant expression, it seems like it's only fair.

---

Footnotes

1 - [back] - Especially considering the situation.

2 - [back] - Which weren't particularly horrible, most of them were upholding the time-honored tradition of testing by printf

3 - [back] - It's not enforced except in one or two places, but it is a style convention. SBCL will bitch at you if you try to do something like (let ((*foo* '(bar baz))) ...), for example. Not refuse to run it of course, but it'll warn you that it's using a lexical binding for *foo*.

4 - [back] - That's the first time that my blog-mode highligher chugged for a second before coming back with the result, by the by, take a look at the source code and see if you can see why.

5 - [back] - Or at least, not just idle fancy.

6 - [back] - Which I don't have. I've never met the guy, and he couldn't possibly have known that I'd be going through his hobby-horse with a sledgehammer at some point in the distant future of 2011.

Switching

This won't be a long entry, but I still have to get it down out of my head before long.

I had this 24 inch iMac around for a few years. Got it back when 2GB of ram was a lot and a 2.4 Ghz single core was blazingly fast. Played around with it for a while and it served well for various design tasks. When I switched gears to more development than design a couple of years ago, I also put together a modest Linux machine. It actually started out with worse specs than the Mac. A much smaller hard drive, 1GB of ram and I forget how fast the processor was. Definitely not very; I remember getting the cheapest AMD I could find. It could grow though. I've always liked tinkering and building machines, but having used Macs through my university years made me forget how much fun it was for a little while. Before long, I was tuning and tweaking again. A slightly better processor here, a bit more ram there. Eventually, SSDs got cheap enough that I could afford a small one. The Linux machine began to rival, and eventually surpass the shiny giant.

I kept the Mac as a design machine, just to run Photoshop/Illustrator and (occasionally) Flash. After about half a year of this, I realized that my time was spent primarily in Emacs on the Linux machine and secondarily in a browser/terminal (on either machine). The miniscule remainder was actually using Photoshop/Illustrator. I had also taken up GIMP for smaller jobs, just so I wouldn't have to switch back and forth between computers. It became obvious that as shiny as it was, the Apple desktop wasn't doing much for me, so I gave it to my fiancee. She fell in love with it, not that she would admit that as a former Windows user. And I mean "user" in the sense of "end user". A computer is a tool that lets her do the stuff she's really interested in. She doesn't care how it functions on the inside, as long as it does what she wants it to. In any case, she got quite comfortable with the Apple setup in short order.

Well, earlier today, the Mac died.

She was doing something random with her Kindle when it shut down randomly. It wouldn't come back up, or respond to any of the start-up keys, and it wouldn't boot from its installation DVD either. So we were staring down the OS X equivalent of the blue screen of death. The problem potentially wasn't as simple as the hard drive getting borked. Given that the mere process of replacing a hard drive for one of these units involved supplies we'd have to go shopping for, she decided she'd just switch[1]. She wouldn't go back to Windows, so I got her onto Ubuntu without much convincing.

Ok, that was the background. Here's the story.

I mentioned being a graphic designer. Actually that should probably say "Graphic Designer" because I have the degree to back up those capitals. So when I say that I underestimated the importance of UI on the decision making of end-users, understand the implications.

She was intensely disappointed by pretty much everything she's seen of other Linux machines, so I more or less gave up on turning this into a house that respects the four freedoms [2]. The thing that ended up placating her is, and I shit you not, cairo-dock set to auto-start at login with the spaces widget removed and the trash icon enabled. OpenOffice is close enough to MS Word for the stuff she does, Rhythmbox syncs with her iPod and her browser of choice is available. She still wants Photoshop, so I may need to resort to some VirtualBox shenanigans, but I'm hoping to get her using GIMP instead. Those are nitpicks though. It turns out that dock and the iPod syncing were the deal-breakers.

This isn't meant to be funny, by the way. It's here to serve as a reminder of how small a change it takes for an end user to willingly switch.

---

Footnotes

1 - [back] - I've got some extra supplies lying around. Nothing terribly impressive, but still enough to put together a half-way decent backup machine in an hour or so if I need to.

2 - [back] - It's still not incidentally. As I said, she owns a Kindle, and an iPod from a while back, but our desktops are now all open source software and commodity hardware.

A Little Bit of Elisp

I've had too much Common Lisp coding at work this week. I basically did two 12 hour sessions across Wednesday and Thursday, then a 4 hour on Friday with a little time off for fighting PHP-related fires and a bit of sleep. So today, I took a break. And what did I do on my break, you might ask?

I hacked Emacs Lisp.

I tell ya, my fiancee loves me. That's right. I took a break from my Common Lisp day-job by getting up on Saturday and dusting off some old Elisp code I had lying around. I touched up some git-mode customizations, an etags library I sometimes use, and my .emacs itself, but my main target was the blog-mode module (which I've actually been using to write these articles, except for one awkward brush with a markdown converter). It has served, but the code was far from elegant, and there were a couple of features I've been meaning to add, but never quite got around to, always telling myself to just get through the blog post instead. The code is still far from elegant, so I won't talk about that, but the features are there.

First thing, and probably the most pressing, is that those nice highlighted code-blocks were getting annoying. It would work fine for plain gray text (which I use sometimes, in small inline snippets), but to do it properly, I had to paste code into a separate buffer, turn on the correct highighting mode, run htmlize-buffer on it, then paste it back into the blog post and maybe tweak it for good measure. I figured that my ideal interaction would be the code auto-detecting what language I'm using and highighting correctly, but one step back would be asking for a highlighting mode and applying it to the code I wanted to htmlize. So here's how that looks

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; <pre> and <code> definitions
(definsert code-block "<pre>" "</pre>")
(definsert inline-code "<code>" "</code>")

;; region versions are more complicated to accomodate htmlize
(defun region-to-inline-code (code-mode)
  "HTMLize just the current region and wrap it in a <code> block"
  (interactive "CMode name: ")
  (let* ((start (region-beginning))
         (end (region-end))
         (htmlified (get-htmlified-region start end code-mode)))
    (delete-region start end)
    (insert-inline-code)
    (insert htmlified)))

(defun region-to-code-block (code-mode)
  "HTMLize the current region and wrap it in a <pre> block"
  (interactive "CMode name: ")
  (let* ((start (region-beginning))
         (end (region-end))
         (result (get-htmlified-region start end code-mode)))
    (delete-region start end)
    (insert-code-block)
    (insert result)))

(defun get-htmlified-region (start end code-mode)
  "Returns a string of the current region HTMLized with highlighting according to code-mode"
  (let ((htmlified nil))
    (clipboard-kill-ring-save start end)
    (get-buffer-create "*blog-mode-temp*") ;;using 'with-temp-buffer here doesn't apply correct higlighting
    (with-current-buffer "*blog-mode-temp*"
      (funcall code-mode)
      (clipboard-yank)
      (setq htmlified (substring (htmlize-region-for-paste (point-min) (point-max)) 6 -6)))
    (kill-buffer "*blog-mode-temp*")
    htmlified))

I pasted that block in from my code file, highlighted it, then typed C-c C-p emacs-lisp-mode [ret], in case you were wondering. The result was that pretty block above. region-to-code-block and region-to-inline-code are actually the same function except for which insert they use, and I would factor that out if it ever got to the point that there needed to be a third function doing the same, but it doesn't seem worth it for just two functions.

EDIT:

Ok, ok goddammit. Here. They're simplified now.

(defun region-to-inline-code (code-mode)
  "HTMLize just the current region and wrap it in a <code> block"
  (interactive "CMode name: ")
  (htmlized-region code-mode #'insert-inline-code))

(defun region-to-code-block (code-mode)
  "HTMLize the current region and wrap it in a <pre> block"
  (interactive "CMode name: ")
  (htmlized-region code-mode #'insert-code-block))

(defun htmlized-region (code-mode insert-fn)
  (let* ((start (region-beginning))
         (end (region-end))
         (result (get-htmlified-region start end code-mode)))
    (delete-region start end)
    (funcall insert-fn)
    (insert result)))

Sun, 27 Mar, 2011

I uh, also put in an edit block function and a footnote manager[1]. The edit blocks are pretty self-explanatory; just a block with a date at the bottom to indicate when I did the thing. After a couple of definition macros[2], it's actually a one-liner.

(deftag edit "<span class=\"edit\">EDIT:\n\n" (concat "\n" (format-time-string "%a, %d %b, %Y" (current-time)) "</span>"))

The footnote manager is a bit more complex. I've actually been doing them manually for the last little while, which started to get frustrating[3]. The process was to put a numbered tag down with <a name="somethingHopefullyUnique">, and hook it up to a correspondingly numbered [back] link at the bottom of the page, then write the footnote, then find my way back. The linking turns out to be the hardest part there, because these posts potentially get displayed together on my blog, so I had to be very careful to make the name unique across the entire blogs' history, not just within that article[4]. With this new function, instead it's C-c f to insert a fresh footnote, or C-c C-f to convert the selected region to a footnote. The links are generated and numbered automatically, so all I have to do is actually write the footnote[5].

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; footnote definitions
(defun insert-footnote ()
  "Inserts footnote, and a return link at the bottom of the file. 
   Moves point to footnote location."
  (interactive)
  (progn (footnotes-header)
         (let ((footnote-name (format-time-string "%a-%b-%d-%H%M%S%Z-%Y" (current-time)))
               (num (number-to-string (+ 1 (count-footnotes)))))
           (insert "<a href=\"#foot-" footnote-name "\" name=\"note-" footnote-name "\">[" num "]</a>")
           (goto-char (point-max))
           (insert "\n\n" num " - <a href=\"#note-" footnote-name "\" name=\"foot-" footnote-name "\">[back]</a> - "))))

(defun region-to-footnote ()
  "Inserts a footnote at point and return link at the bottom. Moves the current region to the end of the file. 
   Leaves point where it is."
  (interactive)
  (save-excursion (kill-region (region-beginning) (region-end))
         (insert-footnote)
         (yank)))

(defun footnotes-header ()
  "Inserts footnote header if not already present"
  (unless (save-excursion (search-forward blog-footnote-header nil t))
    (save-excursion 
      (goto-char (point-max))
      (insert "\n\n" blog-footnote-header))))

(defun count-footnotes ()
  "Returns the number of footnotes in the current file. Used for human-readable note labels"
  (interactive)
  (save-excursion
    (if (not (search-forward blog-footnote-header nil t))
        0
      (let ((count -1))
        (while (progn (setq count (1+ count))
                      (search-forward "<a href=\"#note-" nil t)))
        count))))

Boy, that's playing hell with the highlighting right now. It's fairly self-explanatory; count-footnotes counts up how many footnotes I have left, footnotes-header checks if there's a footnote header in the post already[6], insert-footnote just creates a new footnote/backlink and takes me to the bottom of the page to write it, and finally, region-to-footnote takes the current region and converts it to a new footnote (leaving the point where it is).

Even though it's a simple, and specific[7] piece of code, I still learned a lot by testing it out like this. Specifically, the code formatting functions need to accept nil as an argument[8] (which should take 5 minutes), and the footnote section needs a way to re-number footnotes and jump between corresponding note/back links (which seems like it could take a while).

I'm going to sleep now though; I'll leave those features for the next time I need a break from Common Lisp.

EDIT:

Ok, so it was actually slightly less than 5 minutes to get the code argument done; one line change did it (see if you can guess which one)

(when (fboundp code-mode) (funcall code-mode))

The latest is now up at github.

Sun, 27 Mar, 2011

---

Footnotes

1 - [back] - And yes, since you ask, I am basically using this post as a way to test the editing mode I'm talking about.

2 - [back] - If you want to see the definition macros, check out the github page I started for my little utility files. The documentation is extremely light, but it's only because I fully expect to be the only one using these.

3 - [back] - To the point that I would frequently include a long, rambling paranthetical comment instead of putting the damned thought in a footnote, where it belongs. Interface difficulties really do lead to a lot of shoddy work, it seems.

4 - [back] - The way I'd been doing that was by using the article name and a number in the href and name parameters. The mode is actually better, using a date and timestamp.

5 - [back] - I still haven't found a way to automate writing these columns, but that's not the same as saying it can't be done.

6 - [back] - And adds one if it doesn't exist yet.

7 - [back] - Which is to say, it had a very specific goal in mind.

8 - [back] - (and default to fundamental-mode in that case)

Javascript with a Lisp

Obviously, I'm not a vet yet, so take these musings on Parenscript with a grain of salt. Also, feel free to look up the tutorial they provide for a more hands-on approach; I'm just talking about my experience with it, not attempting to teach it.

There are some ugly, un-abstractable patterns in JavaScript code (which you'll be familiar with if you've ever done more than a tiny bit of jQuery development). They show up often, and you can't really do much about them in JS without resorting to eval. Which you shouldn't do. Parenscript knocks most of them out cold. The argument about jQuery being Good Enough™ also turns out to be moot, since you can easily compose work in both (that is, include jQuery and use Parenscript to generate framework code rather than plain JavaScript). I've created exactly three JS files with this so far, and here are some macros that I'm not sure I'd be willing to do without (I'll start small).

(defpsmacro $ (selector &body chains)
  `(chain (j-query ,selector)
          ,@chains))

That's the pretty essential one I mentioned last time; it just lets you do things like

($ ".target-div" 
     (css (create :height 30 :background-color "#f00")) 
     (effect "explode" 3000))

it's just keeping pace with jQuery. Next up

(defpsmacro \ (&body body) `(lambda () ,@body))

I... honestly wasn't expecting to use this. I'm borrowing Haskell's anonymous function notation for brevity, but only because there's no actual λ key on my keyboard. This is something you don't even notice while coding in JavaScript. You just get used to having to wrap various random things in function () { ... }. It never occurs how annoying this is until you get the chance to do away with it.

(defpsmacro doc-ready (&body body)
  `($ document
      (ready (\ ,@body))))

Told you \ would come in handy (and this is one of the about twenty places it shows up in a 70-line parenscript file). This isn't particularly interesting; just shortcut notation for $(document).ready(function () { ... });.

(defpsmacro defpsajax (name (&rest args) url &optional (success '(lambda (data) ($d data))))
  `(defun ,name ,args
     (chain $ (ajax (create :url ,url
       :data (create ,@(loop for a in args collect (intern (to-str a) :keyword) collect a))
       :context (@ document body)
       :type "POST"
       :success ,success
       :error (lambda (a b error) ($d a b error)))))))

An odd note; I have to quote the default optional function (as above), but I must pass unquoted lambdas in, otherwise it barfs. This one's a bit heavier. It's a shortcut for defining ajax functions. This is the sort of thing you just plain can't do in vanilla javascript. You'd have to define it as

function defPsAjax(address, dataSet, fn) {
    if(!fn) fn = function (data) {$d(data);};
    $.ajax({ url: address,
             type: 'post',
             data: dataSet,
             success: fn,
             error: function (a, b, error) {$d(a, b, error);}
           });
}

and then use it by doing something like

function foo(bar) {
    defPsAjax("/url", { "bar": bar }, function (data) { baz; }); 
}

instead of being able to

(defpsajax foo (bar) "/url" (lambda (data) baz))

I have two problems with that. First, it doesn't kill the boilerplate around defining foo (which you don't have to deal with if you use the macro). Second, that shorter macro definition expands into a full $.ajax call, which means there's no additional overhead from foo calling defPsAjax at runtime. Together, those problems prevent you from properly expressing things in vanilla jQuery; you'll incur (significant) readability and (probably trivial) performance penalties by creating enough intermediate functions. Neither penalty piles up if you use defpsmacro.

There are also a few nice things I get for free (rather than having to define them). As I mentioned last time, having who-ps-html (for easy HTML generation with javascript) and format (for string templating) was already enough to tempt me into using parenscript. Putting strings together in js is fugly. I'm aware of the hacks, and they're not nearly as satisfying as just having a proper string-formatting primitive available in the language. Trying the same tactic with strings which contain HTML tags crosses over into pug fugly territory without so much as a warning. Even if you absolutely must concatenate strings at runtime, (+ foo ", " bar " || " baz) is still easier than foo + ", " + bar + " || " + baz. There's a couple of other similarly useful things that you don't see until you work with them. let and let* are both supported, for starters. let* is actually pretty straightforward

(let* ((a 2)
       (b (+ 2 a)))
    (foo a b))

expands into

var a = 2;
var b = 2 + a;
foo(a, b);

but the equivalent let maintains the limitation that declarations don't refer to each other.

var a1 = 2;
var b = 2 + a;
foo(a1, b);

That might be problematic if you're the sort of person who names variables with numbers at the end. I'm not, so I'll take it.

Another free advantage is optional arguments and implicit returns.

(defun foo (bar &optional (baz "mumble")) baz)

expands into the javascript

function foo (bar, baz){
    if(baz === undefined) {
       baz = "mumble";
    }
    return baz;
}

That's it for the good stuff I've discovered so far (although if you don't agree that macros, easy html formatting, real optional arguments and implicit return are a pretty big pile of win, you might be a JavaScript programmer[1]).

Lets talk about where Parenscript can bite you in the ass.

First, avoid it if you're a lisp newb. There are a lot of parentheses running around when you write your javascript code this way, and just one can make the difference between $(foo).bar({'a': b}); and $(foo).bar.create('a', b);. The real downfall here is that, unlike in plain Common Lisp, it won't throw an error about unbalanced parentheses (if you don't have enough parentheses, it'll still tell you, but it won't give you the typical "expecting [n] args" error if you transpose one). Instead of erroring, it will generate incorrect JS code. This is actually a good argument for using macro-heavy parenscript code because the fewer actual expressions you have to type, the less chance there is that you mistype one. Use your macroexpander and show-paren-mode aggressively.

Second, the chain macro has some fairly odd behaviour with other macros, and it keeps you from abstracting certain patterns without resorting to ps* instead of ps. For instance

(defpsmacro highlight (&optional (color "\#0f0"))
  `(effect "highlight" (create :color ,color) 500))

Having defined that, I would expect (ps ($ "foo" (highlight))) to expand into $("foo").effect('highlight', { 'color': '#0f0' }, 500);, but it actually does $("foo").highlight();. If I wanted to get that first expansion, I'd have to define highlight as

(defun highlight (&optional (color "\#0f0"))
  `(effect "highlight" (create :color ,color) 500))

and call it by doing (ps* `($ "foo" ,(highlight))). That's not actually horrible (we're only into regular fugly here) but it prevents you from fully using your macroexpander, does no work at macroexpansion time and requires you to quote your input. Manageable, but still a net loss.

The last part is that your javascript definitions share the Lisp namespace. Which makes sense, since one of the goals of Parenscript is to have js and CL interoprerate at some level, but it still caught me slightly by surprise. What I mean specifically is

(ps (defun foo () bar))

In addition to expanding out to function foo () { return bar; }, it also defines a Lisp function in the current package called foo. The reason I found this out is that I have a habit of giving JS ajax functions the same name as the functions they'll be interacting with on the server side. Don't do that. I spent a good 15 minutes trying to debug a very odd wrong number of arguments error before realizing that I was accidentally shadowing the function I needed to call.

As a final note, and this should really go without saying, parenscript is not a way to avoid learning JavaScript or jQuery (or your framework of choice). It's a way to simplify development work with them after you know them cold and have more than a few hours logged with Common Lisp. Use it properly and it'll serve you well, go in with a broken/incomplete understanding of JavaScript at your own peril.

---

1 - [back] I'm putting this footnote here because I don't want that comment to sound bigoted. I make a distinction between "someone who knows JavaScript" (a programmer who, among other languages, also uses JavaScript) and "JavaScript programmer" (someone who knows only JavaScript and is zealously convinced it's Good Enough™). I have nothing against the first group. I have the same contempt for the second group that I reserve for all [x] programmers, whether [x] is JavaScript, C, Java, Basic, C#, Haskell or Lisp.

Puzzling with Lisp

This post started out as a reply to a lisper on codereview.stackexchange.com. It got pretty long, so I ended up posting the final solution there, and the story here. For those too lazy to click, the problem was given as

;; Cryptoarithmetic. In cryptoarithmetic problems, we are given a problem wherein the digits are replaced
;; with characters representing digits. A solution to such a problem is a set of digits that, when substituted
;; in the problem, gives a true numerical interpretation. Example:
;;   IS
;;   IT
;;   ___
;;   OK
;;
;;   Has a solution { I = 1; K = 1; O = 3; S = 5; T = 6}.  For each of the below cryptoarithmetic problems,
;;   write a program that finds all the solutions in the shortest possible time.
;;
;;   IS     I
;;   IT    AM
;;   __    __
;;   OK    OK

The original poster put up a brute force solution, so I figured I'd follow suit (I'm sure there's a way to reduce the problem space significantly, but I've spent quite enough time on this puzzle. If you'd like to upstage me, feel more than free).

Ok, so I sat down for a while (probably longer than I should have) and thought how I would actually put together a brute-force solution to this. Basically, the ideal scenario is: for the input IS IT OK, I would have a function to compute (= (+ IS IT) OK).

    (lambda (s i |t| o k) ;; T is a reserved symbol, so I must escape the t
      (= (+ (digits->number i s) (digits->number i |t|)) (digits->number o k)))

If I had this function, I could simply

    (loop for i from 0 to 99999
          when (apply [that function] (number->digits i)) 
          collect (number->bindings i '(s i |t| o k)))

EDIT:

I was severely under-optimistic here; the ideal situation would be to have a function that does

(lambda (s i |t| o k)
  (when (= (+ (digits->number i s) (digits->number i |t|)) (digits->number o k))
    (list "s" s "i" i "t" |t| "o" o "k" k)))

which I could then use by doing (loop for i from 0 to 99999 when (apply [that function] (number->digits i)) collect it) Let this be a lesson to you; always apply the maximum amount of wishful thinking (the response over at CR has solution-fn generate this function rather than the original) Fri, 08 Apr, 2011

That would give me the list of all single-digit bindings for the letters "S I T O K" that satisfy the problem. Ok, so what do I need for that? First off,

    (defun digits->number (&rest digits) 
       (parse-integer (coerce digits 'string)))

    (defun number->digits (num &optional (pad-to 5)) 
       (coerce (format nil (concatenate 'string"~" (write-to-string pad-to) ",'0d") num) 'list))

    (defun numbers->bindings (num bindings)
       (let ((digits (number->digits num)))
          (mapcar (lambda (b d) (,b . ,(parse-integer (format nil "~a" d)))) bindings digits)))

those helpers were mentioned, and seem simple enough (I'm defining them as naively as possible, with no eye to performance right now, so don't bother pointing out that strings are slow). The last thing I need is something that takes a problem string (like "it is ok") and returns that lambda above. So, here's the magic trick.

    (defmacro solution-fn (problem-string)
      (let* ((terms (string->terms problem-string))
             (args (remove-duplicates (apply #'append terms))))
        `(lambda ,args
           (= (+ ,@(loop for term in (cdr terms) collect `(digits->number ,@term)))
              (digits->number ,@(car terms))))))

That introduces one more helper function, string->terms, which should return '((|o| |k|) (|i| |t|) (|i| |s|)) given "is it ok". It actually doesn't matter what order the rest are in, as long as the "answer" ("ok" in this case) is the first element. Here's what the function looks like:

    (defun string->terms (problem-string)
      (reverse
       (mapcar (lambda (s) (mapcar (lambda (i) (intern (format nil "~a" i))) 
                                   (coerce s 'list)))
               (cl-ppcre:split " " (string-downcase problem-string)))))

you'll have to install and include cl-ppcre to use cl-ppcre:split. I recommend [quicklisp](http://www.quicklisp.org/beta/) for your installation needs. I'm downcasing to avoid that problem with T being a reserved symbol.

Tadaaah!

    (loop for i from 0 to 99999 ;;careful to enter these correctly
          when (apply (solution-fn "is it ok") (number->digits i)) 
          collect (numbers->bindings i '(|o| |k| |t| |i| |s|))) ;;note the re-ordered args to match output from `solution-fn`

Gives you the solution in reasonable time.

...

That's not very satisfying though, is it. With this solution, we'd need to manually figure out the order of arguments in the final function, and we'd have to enter the correct number of 9s for those arguments. Whenever there's an easy-to-miss detail in the code somewhere, I like to make sure it's as hard to miss as possible. The best way to make it hard to miss is to tell the program to take care of these details itself. To quote Olin Shivers

I refuse to do things computers can do. -Olin Shivers

    (defmacro solve-for (problem-string)
      (let* ((terms (string->terms problem-string))
             (args (remove-duplicates (apply #'append terms)))
             (nines (parse-integer (coerce (make-list (length args) :initial-element #\9) 'string))))
        `(loop for i from 0 to ,nines
               when (apply (solution-fn ,problem-string) (number->digits i))
               collect (numbers->bindings i ',args))))

Now, (solve-for "it is ok") will give you the answer you need. And it'll work for similar problems. That's not really the solution yet though; the problem asks for "shortest possible time", and so far I've been paying for simplicity with increased runtime. I don't trust myself here though; a priori reasoning about efficiency is fine for a first stab at the problem, but when I want to optimize, the profiler is my friend. After turning profiling on for my helper functions in SLIME and running solve-for for "it is ok", "its not ok", "i am ok", "i am not ok" and (accidentally) "it no ok", M-x slime-profile-report spits out...

  seconds  |     gc     |     consed     |    calls   |  sec/call  |  name  
-----------------------------------------------------------------
    62.983 |      1.732 | 23,736,407,072 | 11,203,305 |   0.000006 | NUMBER->DIGITS
    14.780 |      0.092 |  3,777,455,536 | 43,600,000 |  0.0000003 | DIGITS->NUMBER
     0.037 |      0.004 |     11,936,688 |      3,305 |   0.000011 | NUMBERS->BINDINGS
     0.000 |      0.000 |         37,008 |          8 |   0.000000 | STRING->TERMS
-----------------------------------------------------------------
    77.800 |      1.828 | 27,525,836,304 | 54,806,618 |            | Total

So the bottleneck is clearly number->digits by a pretty wide margin and this really shouldn't come as a shock given how I've been representing digits. Time to change that.This is where I'll resort to some light side-effect. When I get a big, necessary performance boost in return.

    (defun number->digits (num &optional (pad-to 5))
      (let ((temp num)
            (digits nil))
        (loop do (multiple-value-call 
                     (lambda (rest d) (setf temp rest digits (cons d digits)))
                   (floor temp 10))
              until (= pad-to (length digits)))
        digits))

And, of course, I need to go back and make sure that the appropriate functions are now expecting a list of integers rather than a list of chars. That ends up very slightly simplifying numbers->bindings

    (defun numbers->bindings (num bindings) 
      (let ((digits (number->digits num))) (mapcar (lambda (b d) `(,b . , d)) bindings digits)))

and complicating digits->number

    (defun digits->number (&rest digits)
      (apply #'+ (loop for d in (reverse digits) for i from 0
                       collect (* d (expt 10 i)))))

Lets see. After solve ing for "it is ok", "its not ok", "i am ok", "i am not ok" and (not accidentally this time) "it no ok" again:

  seconds  |     gc     |     consed    |    calls   |  sec/call  |  name  
----------------------------------------------------------------
    10.993 |      0.752 | 7,199,265,488 | 43,900,000 |  0.0000003 | DIGITS->NUMBER
     5.009 |      0.224 | 1,069,467,616 | 11,304,260 |  0.0000004 | NUMBER->DIGITS
    0.0003 |      0.000 |       634,880 |      4,260 |  0.0000001 | NUMBERS->BINDINGS
     0.000 |      0.000 |        48,224 |         10 |   0.000000 | STRING->TERMS
----------------------------------------------------------------
    16.002 |      0.976 | 8,269,416,208 | 55,208,530 |            | Total

Which is a pretty drastic improvement to number->digits. digits->number is doing worse now though. I'll try out something else. Intuitively, this should be worse, but you never know 'till you try a few million times.

    (defun digits->number (&rest digits) (parse-integer (format nil "~{~a~}" digits)))

  seconds  |     gc     |     consed     |    calls   |  sec/call  |  name  
-----------------------------------------------------------------
    61.560 |      2.489 | 27,440,408,672 | 43,900,000 |   0.000001 | DIGITS->NUMBER
     3.973 |      0.004 |         96,832 | 11,304,260 |  0.0000004 | NUMBER->DIGITS
     0.004 |      0.000 |        593,920 |      4,260 |   0.000001 | NUMBERS->BINDINGS
     0.000 |      0.000 |         47,232 |         10 |   0.000000 | STRING->TERMS
-----------------------------------------------------------------
    65.537 |      2.493 | 27,441,146,656 | 55,208,530 |            | Total

Ok, looks like I didn't need the profiler to figure that one out; intuition is sometimes right. I'm reverting to the numeric version, and the only other things I'll test is inlining solution-fn and changing a reverse out for nreverse in digits->number. It doesn't seem like these will make a huge difference, but it should improve the memory situation by a bit (and digits->number is hurting on conses).

  seconds  |     gc     |     consed    |    calls   |  sec/call  |  name  
----------------------------------------------------------------
     7.627 |      0.400 | 4,363,098,528 | 43,900,000 |  0.0000002 | DIGITS->NUMBER
     4.388 |      0.160 |   776,123,744 | 11,304,260 |  0.0000004 | NUMBER->DIGITS
     0.004 |      0.000 |       876,544 |      4,260 |   0.000001 | NUMBERS->BINDINGS
     0.000 |      0.000 |        21,600 |          5 |   0.000000 | STRING->TERMS
----------------------------------------------------------------
    12.019 |      0.560 | 5,140,120,416 | 55,208,525 |            | Total

Not bad. 3 fewer seconds of runtime in exchange for a single lambda inlining and one additional character in a function name. At this point,

    (progn (solve-for "it is ok") 
           (solve-for "its not ok") 
           (solve-for "i am ok") 
           (solve-for "i am not ok") 
           (solve-for "it no ok"))

runs in just under 15 seconds with profiling off (and about a minute with the whole package profiled), which is pretty good by my estimation. I think I'll cut it here. I've already spent about two hours on this article, and that feels like it's more than enough. If I had a mind to improve it, I'd focus on a few specifics.

• Firstly, digits->number can do some of its calculations at macroexpansion time (since by that point, we know what number of digits we're expecting in each term, we could create a custom function with the specific arity we need instead of using a &rest argument).
• Secondly, numbers->bindings can be folded into solution-fn (so that it generates a function that returns either a set of bindings, or nil, instead of t or nil). That should save another couple of seconds.
• Thirdly you could parallelize this operation. Remember, we're just applying a function to each element of the list of integers between 0 and 99999... Since there are no sequential data dependencies, there's no reason it couldn't be broken up into equal pieces across a server cluster if you wanted to solve "the quick brown fox jumps over the lazy dog".
• Finally you could spend some time figuring out an algorithmic solution

By the by, I'm experimenting with a markdown converter this time (instead of using my blog-mode. Some assembly has been required in a couple of places (mainly that paste of the problem, and the profiler reports), but I'll try again next time, with this in mind. I'll also see what it takes to get some code highlighting up ins using just markdown.

EDIT: I've gone back over this post with blog-mode. The markdown generator was messing up entirely too many things for my liking (and didn't give me code highlighting to boot). Well, I tried it at least... Fri, 08 Apr, 2011