March 3, 2003

Playing with LISP

I assure you, it’s little more than playing. Ever since ardent came over and we did some number theory stuff together, I was kind of interested in working out some of the stuff we did with a program so the math wasn’t so burdensome. Additionally, I wanted to learn some LISP, and I’ve found the best way for me to learn a language is generally to jump in and do something with it. I’m doing things like calculating the order of integers in the set (I’m reaching with the formatting, here) Z * n . Here’s a demo of what I’ve written so far:

;; Demonstrate my (primep) function.
* (dotimes (n 10) (format t "~D: ~A~%" n (primep n)))
0: T
1: T
2: T
3: T
4: NIL
5: T
6: NIL
7: T
8: NIL
9: NIL
NIL
;; (factor) breaks a number down into pairs of
;; (prime-component exponent).
* (factor 64)
((2 6))
* (factor 67)
((67 1))
* (factor 16200)
((2 3) (3 4) (5 2))
;; I wrote (unfactor) to reverse (factor), just for
;; testing.  It was scary easy.
* (unfactor (factor 16200))
16200
;; (coprime) tests if all its arguments are coprime
;; relative to all other arguments.  Also scary easy.
* (coprime 24 25)
T
* (coprime 24 14)
NIL
* (coprime 24 25 (* 7 13))
T
;; (euler-phi) is an implementation of Euler's phi
;; function, which finds the number of integers less
;; than or equal to N that are coprime to N.
* (euler-phi 13)
12
* (euler-phi 21)
12
* (euler-phi 137)
136
* (euler-phi 138)
44
;; (z-mod-n), which computes Z mod N.  Stupid easy.
;; In fact, stupid period.  I may transform this into
;; a class so I can make operations on a subset of
;; Z like this.
* (z-mod-n 21)
(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20)
;; (multiplicative-group) finds the multiplicative
;; group of (z-mod-n N).  The multiplicative group
;; seems to be all numbers within (z-mod-n N) that
;; are invertible.
* (multiplicative-group 21)
(1 2 4 5 8 10 11 13 16 17 19 20)
;; (possible-orders) computes all possible orders for
;; any element in the multiplicative group of
;; (z-mod-n N).
* (possible-orders 21)
(1 2 4 3 6 12)
*
;; (order-of-integer) determines the order of the
;; integer A which must be in the multiplicative
;; group of (z-mod-n N).  (Hey, I didn't say I know
;; the meanings of this stuff, just that it's
;; part of number theory and kind of fun to do.)
(let ((n 10))
  (dolist (a (z-mod-n n))
    (format t "~D: ~D~%" a (order-of-integer a n))))
0: NIL
1: 1
2: NIL
3: 4
4: NIL
5: NIL
6: NIL
7: 4
8: NIL
9: 2
NIL
;; This one's for ardent, to check against his notes
;; if he'd like: the orders of all integers in
;; (multiplicative-group 21).
*
(let ((n 21))
  (mapcar (lambda (a)
	    (order-of-integer a n))
	  (multiplicative-group n)))
(1 6 3 6 2 6 6 2 3 6 6 2)

None of my LISP is pretty, I don’t think. I’m still not quite sure what functional programming entails, so I highly doubt I’m doing much if any of it. Furthermore, I haven’t taken the time to optimize any of this. I’ve barely taken the time to ensure that it’s correct (and I don’t know if it does some corner cases properly). Nevertheless, here’s my number theory LISP. This was all done in SBCL 0.7.13 on Linux/PPC.

Here’s a couple of questions I’ve got about LISP so far:

  • How the fuck do you step through a function in the SBCL debugger? I got as far as sticking some stuff like (declare (optimize (speed 0 size 0 debug 3))) in my code, and then inserting a (break) at the top, but once in the debugger nothing seemed to work? I was getting weird errors on (I think!) stuff like (sqrt n) where n = 7, with errors like The value 7 is not of type NUMBER. What the hell? I think I’m going to have to break down and ask #lisp. I apologize in advance.

  • Why do a lot of the examples I’m reading, particularly from Successful LISP use #'function instead of 'function? From some conversation on #lisp today they said that #'function refers to the function as a value or some such. (I’m actually too lazy to go lastlog it.) Yet everywhere in Successful LISP that they use #'function, I’ve been able to use just 'function. For example, in mapcar I can do stuff like (mapcar (lambda ...) ...) whereas the example in Successful LISP was (I think) (mapcar #'(lambda ...) ...). Both seem to work the same, at least in SBCL?

Maybe I’ll find some help on those. BTW, SBCL is way easy to build. I grabbed a 0.7.6 Linux/PPC SBCL binary off their SourceForge.net project page, the SRPM for 0.7.13, and after a little tweaking I built the RPM successfully (took two tries). A build of the RPM took about 1h. SBCL loads fast and seems to perform quite well. I’ve crashed it a few times I think (once just now with (primep 891927571939123), but maybe that was a bit too big) and I’m worried some of my debugging woes are due to bugs in SBCL, but I’m sure that’ll all work itself out in the end. Maybe they’re even PPC bugs. I’ve noticed that all the threading stuff seems to be available only on x86, not any other architectures. SBCL’s threading stuff might be experimental, in fact, but it exists at least. (I wonder if CMUCL has threading on PPC? I wonder if CMUCL has preemptive threading or just cooperative threading.)