I Need Closure(s)

Back from the holidays and plowing through the chapters again. The explanation for the various optimizations was good, but I had a hard time figuring out a more "Lisp-like" way of doing the code. Either there isn't, or I haven't quite reached Zen-like Lisp nirvana. I'm open to improvements, here's the code for the generic optimizations and the social network.

For these python translations I'm growing fond of the (incf cl) utilities. It includes macros to make list comprehensions in Lisp, so

sol=[random.randint(domain[i][0],domain[i][1])
     for i in range(len(domain))]

becomes

(defun range-random (low high)
 (+ low (random (1+ (- high low)))))
...
(let ((sol (assemble (range-random (car x) (cdr x)) (<- x domain)))) 

I know that one would be just as easy with mapcar, see incf-cl for better examples.

Here's a graph made from a simulated annealing optimization of the social network graph:

An example of taking data in multiple dimensions and "scaling" it to two dimensions, where the distances between data points is proportional to the multi-dimensional distance. Again, this one is basically an imperative rewrite. I hope to be able to exploit more of Lisp's power in the next chapter, which includes some neural networks. The big revelation from this, if anyone says Lisp is unreadable, I'd show them

fakedist[i][j] = sqrt(sum([pow(loc[i][x] - loc[j][x], 2)
for x in range(len(loc[i]))]))

I replaced clusters.lisp, new code is in it.



Zooming in,

I have Common Lisp code for Chapter 3 up to Hierarchical Clusters. It's longer and not that interesting, so I'll just put up a link to the code. Once again, map and reduce are taking the place of list comprehensions, but other than that it's not particularly Lispy, no macrology or anything. Maybe next time.

Last time's tangent was a shortcut to hash syntax. This time I'm not happy with deleting items out of the middle of adjustable arrays. The code puts items on the end of an array and deletes them out of the middle, from a particular position.
In Python it's
del clust[lowestpair[0]]
What I have is

(defun truep (x) (declare (ignore x)) t)
(setf clust (delete-if #'truep clust :start (car lowestpair) :end (1+ (car lowestpair))))


Instead of PCI's use of the Python Imaging Library or some Lisp equivalent, I used cl-pdf, which was easy to use to make the simple graphs, lines and text. This is the full hierarchical cluster, then a zoom view.

Like many others, I've been reading Toby Segaran's Programming Collective Intelligence. Toby's examples are in Python. Inspired by loucal's posting of code examples in Ruby, I've decided to put up my own Common Lisp examples. These are from Chapter 2, going up to page 15, "Ranking the Critics".

In order to just have the recommendations in the file, I used assoc lists instead of hashes. One place where Python (and Ruby) has it over Lisp is in hash syntax, just critics[person] instead of (gethash person critics) or (cdr (assoc person critics :test #'equalp)). I made a 'critics' function to keep down the verbosity. Is there a good way to change the syntax for hash lookup?

The other big difference is my use of mapcar and reduce everywhere instead of Python's list comprehensions, with the occaisional intersection thrown in.

If the Python source code gets posted, I may try some benchmarks with later examples.

(defparameter *RECOMMENDATIONS* 
  '(
    ("Lisa Rose" . (("Lady in the Water" . 2.5) ("Snakes on a Plane" . 3.5) ("Just My Luck" . 3.0) 
                    ("Superman Returns" . 3.5) ("You, Me and Dupree" . 2.5) ("The Night Listener" . 3.0)))
    ("Gene Seymour" . (("Lady in the Water" . 3.0) ("Snakes on a Plane" . 3.5) ("Just My Luck" . 1.5) 
                       ("Superman Returns" . 5.0) ("The Night Listener" . 3.0) ("You, Me and Dupree" . 3.5)))
    ("Michael Phillips" . (("Lady in the Water" . 2.5) ("Snakes on a Plane" . 3.0) 
                           ("Superman Returns" . 3.5) ("The Night Listener" . 4.0)))
    ("Claudia Puig" . (("Snakes on a Plane" . 3.5) ("Just My Luck" . 3.0) ("The Night Listener" . 4.5) 
                       ("Superman Returns" . 4.0) ("You, Me and Dupree" . 2.5)))
    ("Mick LaSalle" . (("Lady in the Water" . 3.0) ("Snakes on a Plane" . 4.0) ("Just My Luck" . 2.0) 
                       ("Superman Returns" . 3.0) ("The Night Listener" . 3.0) ("You, Me and Dupree" . 2.0)))
    ("Jack Matthews" . (("Lady in the Water" . 3.0) ("Snakes on a Plane" . 4.0) ("The Night Listener" . 3.0) 
                        ("Superman Returns" . 5.0) ("You, Me and Dupree" . 3.5)))
    ("Toby" . (("Snakes on a Plane" . 4.5) ("You, Me and Dupree" . 1.0) 
               ("Superman Returns" . 4.0)))))


(defun critics (reviewer &optional movie)
  (labels ((get-movie (ms m)
             (cdr (assoc m ms :test #'equalp))))
    (let ((movies (cdr (assoc reviewer *RECOMMENDATIONS* :test #'equalp))))
      (if movie (get-movie movies movie) movies))))

(defun similar (person1 person2 distance)
  (let* ((movies1 (critics person1))
         (movies2 (critics person2))
         (common-movies (mapcar #'car (intersection movies1 movies2 
                                                    :test #'(lambda (x y) (equalp (car x) (car y)))))))
    (if (null common-movies)
        nil
        (funcall distance person1 person2 common-movies))))

(defun euclidean-distance (person1 person2 common-movies)
  (let* ((sum-of-squares (reduce #'+ (mapcar 
                                      #'(lambda (cm) 
                                          (expt (- (critics person1 cm) (critics person2 cm)) 2)) 
                                      common-movies)))
         (distance (/ 1 (1+ sum-of-squares))))
    distance))

(defun sim-distance (person1 person2)
  (similar person1 person2 #'euclidean-distance))


(defun pearson-distance (person1 person2 common-movies)
  (let* ((n (length common-movies))
         (scores1 (mapcar #'(lambda (x) (critics person1 x)) common-movies))
         (scores2 (mapcar #'(lambda (x) (critics person2 x)) common-movies))
         (sum1 (reduce #'+ scores1))
         (sum2 (reduce #'+ scores2))
         (sum1-sq (reduce #'+ (mapcar #'(lambda (x) (* x x)) scores1)))
         (sum2-sq (reduce #'+ (mapcar #'(lambda (x) (* x x)) scores2)))
         (psum (reduce #'+ (mapcar #'* scores1 scores2)))
         (num (- psum (/ (* sum1 sum2) n)))
         (den (sqrt (* (- sum1-sq (/ (expt sum1 2) n)) (- sum2-sq (/ (expt sum2 2) n))))))
    (if (zerop den) 0 (/ num den))))

(defun sim-pearson (person1 person2)
  (similar person1 person2 #'pearson-distance))
         
(defun top-matches (person &optional (n 5) (similarity #'sim-pearson))
  (let* ((scores (mapcar #'(lambda (x) (cons (funcall similarity person x) x)) 
                         (remove-if #'(lambda (x) (equalp x person)) (mapcar #'car *RECOMMENDATIONS*))))
         (sorted-scores (sort scores #'> :key #'car))
         (len (length sorted-scores)))
    (if (<= len n)
        sorted-scores
        (butlast sorted-scores (- len n)))))

"The best way to solve a problem is often to redefine it." - Michael Rabin, via Paul Graham
"I don't like assembly language." - Richard Cook

Last August I got a Lego NXT robot, and of course I wanted to program it in Lisp. I got Frank Klassner's RCXLisp code and the NXT programming manual, and made a start, looking at opcodes and twiddling bits, and jump offsets, but it was, well, opcodes and bits, and I just wanted to make the robot do things, and it was a big hurdle, and so I procrastinated, and did other things. All that munging with assembly wasn't that interesting a problem to me, and when (if?) I got some output, and it didn't work, then I'd have to try to decipher the disassembled code, and act like the NXT VM, and "run" it...

The light bulb went off a couple of weeks ago. Other people have done most of the heavy lifting for me - there were compilers for other languages for the NXT. I didn't have to get from Lisp to assembly, I just had to get from Lisp to the intermediary language, which would catch syntax errors and I could look at my program's output without going crazy. After some looking around I decided to go with NXC, which has a C syntax. The advantage of a C syntax instead of, say, Basic or Lua is that I have a pretty good head start. Since Javascript has a syntax that's close to C, I started with parenscript and am modifying it to turn it from a Lisp->Javascript compiler into a Lisp->NXC compiler.

I've made a few changes, enough to let me compile a test program

(defconstant *MYNUM* 100)

(defun runout (offset multiplier)
(-num-out 0 offset (* *MYNUM* multiplier)))

(defthread (main :primary t) ()
(let ((x 0))
 (setf x 1)
 (runout *LCD_LINE1* x)
 (setf x 2)
 (runout *LCD_LINE2* x)
 (-wait 10000)))

into

#include "NXCDefs.h"

#define MYNUM 100


sub runout(int 
           offset,
           int 
           multiplier) {
  NumOut(0, offset, MYNUM * multiplier);
}

task main() {
  int x = 0;
  x = 1;
  runout(LCD_LINE1, x);
  x = 2;
  runout(LCD_LINE2, x);
  Wait(10000);
}

which produces



I may pretty it up more when I understand parenscript more, but it compiles and runs and it isn't meant to be read by humans.

The next "architectual/philosophical" decision is how closely to follow the original RCXLisp syntax. That would give me some access to more example programs, but the NXT has more capabilities than the RCX, and there's a Google Summer of Code project "NXTLISP" working on a (I'm assuming) a Lisp->NXT VM compiler, so I may wait to see the syntax for that.

Or not. NXC has a rich set of C-style macros for things like turning on multiple sets of motors that's different than how RCXLisp does it, plus I'm thinking about keeping the language more generic so it can target multiple robot C compilers, such as the First VEX.

I'll post more as I go - the next thing to ponder is the best way to handle typing of NXC variables; int, short, long, byte, bool and string. Other robot C compilers may have other types. I may try Common Lisp type declares, or I may put the types in a list with the variable name, with just the variable name meaning "int".

Labels: lisp, NXT, robot

At IBM's Java page, Bruce Tate writes articles about other languages and the features that they have that other languages don't. His latest is on Lisp. The usual intro stuff, but he could have spent a little more time on macros; his example is
(defmacro times_two (x) (* 2 x))
With not much more he could have shown an actual language extension. Hey Bruce, would a 'while' have killed you?

Labels: lisp

If you go back to my first posting, you'll see that before Common Lisp the language I used for home programming was OCaml. I still prefer Lisp's uniform syntax and macros, but Ocaml has a soft spot in my heart.

That's why I was looking forward to Apress' "Practical OCaml", which was going to be OCaml's answer to "Pratical Common Lisp", even doing some of the same projects - good for comparison.

Well, reviews are coming in, and the short version is, except for the prose and the code, the book's just fine. For the sarcasm impaired, the amazon reviews are all one star, and even the book's technical reviewer is not thrilled with it.

Some reviewers are even concerned that this will discourage others from writing a good OCaml book or learning OCaml. Thank you, Peter, for doing such a good job on "Pracital Common Lisp".