Cops ‘n robbers on the LOoSe

If you couldn’t tell from my extremely clever title, this post is about CLOS. CLOS is the Common Lisp Object System, and it adds object orientation to the language. It was added to the language long after Lisp was started, but because Lisp is “the programmable programming language” its easy to add on important features of new languages to Lisp.

I’ve included code that demonstrates a silly example using CLOS. Thanks to Jon Rowe for thinking up this rather ridiculous problem. There are four criminals, each one is part of the criminal class but each has its own name and distinct greeting, as well as distinct weapon. When asked for a greeting, each one (if its hungry) will tack on a stomach rumbling ‘sound’ to the end of its greeting.

Here is the code.

Prime, Time!

Working some more with Lisp, I’ve made a prime factorization function. It returns the prime factorization of a number. I tested it with our favorite Fibonacci prime + 1, and since I’ve discovered an (incredibly simple to use) timing function these were my results:

CL-USER> (time (prime-factors 99194853094755498))
; cpu time (non-gc) 9,006,099 msec (02:30:06.099) user, 812 msec system
; cpu time (gc) 1,013,917 msec (00:16:53.917) user, 220 msec system
; cpu time (total) 10,020,016 msec (02:47:00.016) user, 1,032 msec system
; real time 10,042,188 msec (02:47:22.188)
; space allocation:
; -648,487,858 cons cells, -2,618,004,168 other bytes, 10,120 static bytes
(2 3 3 83 281 1427 2789 59369)

So in about 2 hours and 45 minutes it finished. The code is not the most efficient way to do this, thats not the point. It does get the job done though and it uses stuff I had previously built, which makes it pretty fun. It handles numbers closer to everyday life quickly:

CL-USER> (time (prime-factors 2345987234))
; cpu time (non-gc) 795 msec user, 0 msec system
; cpu time (gc) 95 msec user, 0 msec system
; cpu time (total) 890 msec user, 0 msec system
; real time 890 msec
; space allocation:
; 2,798,429 cons cells, 10,965,776 other bytes, 0 static bytes
(2 47 139 179549)

Thats a ten digit number in under a second, so not too awful.

Attached you’ll find the code (you’ll need to load the previous code files I’ve posted as well to get this to work). It currently breaks if you initially give it a prime number. I’ll hopefully fix it later, but right now I need to move on to some other stuff. Have you figured out my file naming scheme yet? It has to do with something I was doing while I was writing the code.

Follow Up : Lisp Fun!

I’ve been testing some prime numbers out with the factors function. I tested this Cullen prime: 393050634124102232869567034555427371542904833 and gave it about 21 hours with one core dedicated to it but it never came back.

I tested this Carol prime: 4398042316799 and almost instantly I received:

CL-USER> (factors 4398042316799)
(1 4398042316799)

Right now I’m testing this Fibonacci prime: 99194853094755497. Its been going about 20 minutes now with a core dedicated to it, but its not done yet. Certainly the algorithm could be faster, it wasn’t really meant for what I’m having it do now…so these are just tests “for personal interest”.

Here is a really simple function to test for prime-ness. I actually didn’t test it since currently the REPL is tied up with that Fibonacci prime, but it looks like it ought to work…

EDIT: In under 30 minutes (I didn’t see exactly when it happened) the REPL came back with:

CL-USER> (factors 99194853094755497)
(1 99194853094755497)

I also tested the function and it looks pretty good from my simple tests.

Lisp Fun!

I’ve been learning Lisp for several months now, but this summer I decided to really buckle down and put some effort into it. I definitely like Lisp, and I don’t feel like I even know very much of it. It feels very clean to me; it almost feels more like doing math than programming. I haven’t gotten too far with doing AI in Lisp yet, because I’ve spent most of my time getting to know the language. Things like defun, let, do, dolist, dotimes seem pretty standard for a language, just with different names.

However, things like lambda and defmacro really opened my mind up! These concepts were so different from anything I knew previously that for a while after I read them I though “Man, no one would ever use these because there are better ways to do the things these can do.” What was exciting was when I realized how I didn’t fully grasp their capabilities, and suddenly was able to imagine new things I could do with the power of lambda and especially defmacro.

I’m thinking of a couple projects to do. One of them came out of the Paradigms of Artificial Intelligence Programming book I have. The other one I came up with on my own. My idea is to have a “dungeon solver” where there is a map in some data structure (most likely a list, but we’ll see) that contains zeros for open space, ones for walls, and a goal. Initially I think I’ll just have a little guy randomly walking around the dungeon looking for the goal. Later I may add some more intelligence to the system, such as not going back to places already been unless necessary.

Below I’ve got some code I wrote that deals with finding all the factors of a number and also determining if two numbers are coprimes. Lastly there is a function that finds primes up to a given number you supply. It is not the fastest way to do it, but since I had the factors function already it was so tempting to write the find-primes function that I just went ahead and did it. Thanks, thanks, thanks to Jon Rowe for helping me learn Lisp. Hes awesome, I highly recommend him if you’re looking for a tutor. Alright, heres the code (check the end of the post for a neatly formatted file)!

(defun factors (num)
"This function will find the factors of the argument num."
(let ((l '()))
(do ((current 1 (1+ current)))
((> current (/ num current)))
(if (= 0 (mod num current))
(if (= current (/ num current))
(setf l (append l (list current)))
(setf l (append l (list current (/ num current)))))))
(sort l #'< ))) (defun coprimesp (num1 num2) "Returns t if numbers are coprimes, nil otherwise." (let ((flag t)) (dolist (atom1 (rest (factors num1))) (dolist (atom2 (rest (factors num2))) (if (= atom1 atom2) (setf flag nil)))) flag)) (defun find-primes (top) "Finds primes starting at one and searching up to given number, top." (let ((l '())) (dotimes (x top) (if (= 2 (length (factors x))) (setf l (append l (list x))))) l))

I’m using Lisp in a Box to code all this. Please let me know if you know how to make it so the REPL doesn’t limit output like it does here:

CL-USER> (find-primes 1000)
(2 3 5 7 11 13 17 19 23 29 …)

Also, if you’re an emacs pro and know how to make emacs collapse parenthesis please leave a comment or email me! I’d like to turn this:

(defun find-primes (top)
(let ((l ‘()))
(dotimes (x top)
(if (= 2 (length (factors x)))
(setf l (append l (list x)))))

into something more like this:

(defun find-primes ()
( (())
( ()
( ( (()))

This would really help a lot with parenthesis matching. Well thats it for this post, have a great summer and please leave comments!

(For some reason the code formatting isn’t working well with wordpress, so I’ve included this file with nice formatting.)