Tag Archives: lisp

Clojure: a pretty good lisp

I had had a look at clojure when it had first come out. It looked interesting, but was in its infancy. I recently started looking at it again. It is slightly different from Common Lisp. A very interesting thing about clojure is that, being “hosted” on the Java virtual machine, it has access to java libraries.

Here is a little clojure program I wrote (following the book “The Joy of Clojure”):

(ns tut1.gui
  (:gen-class))

(defn f-values [f xmax ymax]
  "Return a vector "
  (for [x (range xmax)
        y (range ymax)]
    [x y (rem (f x y) 256)]))

(defn draw-values [frame f xmax ymax]
  (let [gfx (.getGraphics frame)]
    (.clearRect gfx 0 0 xmax ymax)
    (doseq [[x y v] (f-values f xmax ymax)]
      (.setColor gfx (java.awt.Color. v v v))
      (.fillRect gfx x y 1 1))))

(defn draw-graphic [frame f xmax ymax]
  "Draw f(x y) for all x,y combinations on a 200 by 200 GUI frame."
  (let []
    (.setVisible frame true)
    (.setSize frame (java.awt.Dimension. xmax ymax))
    (draw-values frame f xmax ymax)))

(defn remove-graphic [frame]
  (.dispose frame))

And I call it from the repl like so:

tut1.gui=> (def frame (java.awt.Frame.))
#tut1.gui/frame
tut1.gui=> frame
#<Frame java.awt.Frame[frame0,0,22,0x0,invalid,hidden,layout=java.awt.BorderLayout,title=,resizable,normal]>
tut1.gui=> (draw-graphic frame bit-xor 300 300)
nil

which draws a pretty graphic. But, but, but! The important point in all this is that we are using Java libraries and object, from a REPL, dynamically. We can instantiate java objects, call methods on them, etc. For example, when I get tired of the graphic drawn above, I can remove it by running this on the REPL:

tut1.gui=> (.dispose frame)
Advertisements

Measuring performance of Lisp functions

Consider the following exercise (Ex. 1.5 in “Paradigms of Artifical Intelligence Programming” by Peter Norvig):

Write a function to compute the dot product of two sequences of numbers, represented as lists. The dot product is computed by multiplying corresponding elements and then adding up the resulting products. Example:
(dot-product '(10 20) '(3 4)) => 110

Here are four implementations (the first one is mine, the other three are the solutions to the exercise in the book)

1. My solution: Recursion with accumulator — tail call optimized (TCO)

(defun dot-product (lst1 lst2 &optional (acc 0))
  "Computes the dot product of two sequences, represented as lists."
  (if (not lst1)
      acc
      (let ((x (first lst1))
	    (y (first lst2))
	    (lst11 (rest lst1))
	    (lst22 (rest lst2)))
	(dot-product lst11 lst22 (+ acc (* x y))))))

2. Solution 1 in PAIP: apply and mapcar

(defun dot-product1 (lst1 lst2)
  (apply #'+ (mapcar #'* lst1 lst2)))

3. Solution 2 in PAIP: recursive without TCO

(defun dot-product2 (lst1 lst2)
  (if (or (null lst1) (null lst2))
      0
      (+ (* (first lst1) (first lst2))
	 (dot-product2 (rest lst1) (rest lst2)))))

4. Solution 3 in PAIP: iteration and indexing

(defun dot-product3 (lst1 lst2)
  (let ((sum 0))
    (dotimes (i (length lst1))
      (incf sum (* (elt lst1 i) (elt lst2 i))))
    sum))

Performance

We test the solutions like this:

Set up some test data:

CL-USER> (defparameter *a* (make-list 100000 :initial-element 1))

dot-product: Use the time macro to measure the performance of the function dot-product:

CL-USER> (time (dot-product *a* *a*))
Evaluation took:
  0.002 seconds of real time
  0.001302 seconds of total run time (0.001301 user, 0.000001 system)
  50.00% CPU
  3,450,092 processor cycles
  0 bytes consed

100000

The function does not allocate any new memory, uses 50% CPU on average and finishes in 0.001302 seconds for a 10,000 element list.

Similarly, we test the other three functions:

dot-product1:

CL-USER> (time (dot-product1 *a* *a*))
Evaluation took:
  0.003 seconds of real time
  0.002625 seconds of total run time (0.002611 user, 0.000014 system)
  100.00% CPU
  6,967,544 processor cycles
  3,205,632 bytes consed

100000

dot-product2:

CL-USER> (time (dot-product2 *a* *a*))
Control stack guard page temporarily disabled: proceed with caution
...

This one aborted because it ran out of stack space before it could complete.

dot-product3:

CL-USER> (time (dot-product3 *a* *a*))
Evaluation took:
  58.350 seconds of real time
  58.347480 seconds of total run time (58.330376 user, 0.017104 system)
  99.99% CPU
  155,215,653,812 processor cycles
  0 bytes consed

100000

So it seems my solution is twice as fast as the fastest one in PAIP and has the advantage of not using any extra memory, whereas the PAIP solution takes up nearly 3MB (32 bytes per element). My solution is 44,813 times faster than the PAIP solution that does not allocate extra memory. Admittedly, the PAIP solutions are not about getting into performance but more about showing how to write code in Lisp; and neither has the author delved into Tail-Call-Optimization yet; so I am not criticizing PAIP at all.

Well, dot-product1 looks very concise and elegant, doesn’t it? What if we try to run it with a larger list?

CL-USER> (defparameter *a* (make-list 1000000 :initial-element 1))
*A*

And now, alas, it also exhausts the stack space:

CL-USER> (time (dot-product1 *a* *a*))
Control stack guard page temporarily disabled: proceed with caution
; Evaluation aborted on #<SB-KERNEL::CONTROL-STACK-EXHAUSTED {100341FE93}>.

Presumably this is because we are trying to pass in 1,000,000 arguments to apply and the arguments have to be pushed on to the stack. Perhaps we can tweak this a bit so that the arguments are not pushed on to the stack:

(defun dot-product4 (lst1 lst2)
  (reduce #'+ (mapcar #'* lst1 lst2) :initial-value 0))

And now this function does run:

CL-USER> (time (dot-product4 *a* *a*))
Evaluation took:
  0.212 seconds of real time
  0.210735 seconds of total run time (0.182024 user, 0.028711 system)
  [ Run times consist of 0.143 seconds GC time, and 0.068 seconds non-GC time. ]
  99.53% CPU
  563,737,032 processor cycles
  47,974,560 bytes consed
  
1000000

Hmm.. it seems to be allocating even more bytes per element than before (47 bytes per element) and there is now some GC overhead. What about my function?

CL-USER> (time (dot-product *a* *a*)) ; *a* is a list with a million elements
Evaluation took:
  0.014 seconds of real time
  0.013474 seconds of total run time (0.013462 user, 0.000012 system)
  92.86% CPU
  36,021,059 processor cycles
  0 bytes consed
  
1000000

Still jolly good!

Update

Svente posted another (more efficient, very readable) solution in the comments below:

(defun dot-product5 (lst1 lst2)
  (loop for element1 in lst1
       for element2 in lst2
       sum (* element1 element2)))

This code uses two nested for loops and a (invisible, hidden) local variable to hold the sum. How does it perform?

CL-USER> (time (dot-product5 *a* *a*))
Evaluation took:
  0.007 seconds of real time
  0.007470 seconds of total run time (0.007470 user, 0.000000 system)
  100.00% CPU
  19,859,546 processor cycles
  0 bytes consed
  
1000000

It performs very well indeed; better than my recursive solution.

Summary
CPU, time, memory taken with a list of 10,000 elements:

Soluton CPU % Time (s) Processor cycles/element Bytes consed
dot-product 50.0% 0.001302 34.5 0
dot-product1 100.0% 0.002625 69.7 3,205,632
dot-product2 does not even run to completion
dot-product3 99.99% 58.35 1552 0

CPU, time, memory taken with a list of 1,000,000 elements:

Soluton CPU % Time (s) Processor cycles/element Bytes consed
dot-product 100.0% 0.010221 27.2 0
dot-product4 99.21% 0.1259 336 48M
dot-product5 100.0% 0.0079 21.2 0

Lisp on Mac OS X Lion

I did not have any Lisp installed on my newish Macbook Pro. I thought I’d revisit my previous post on how to get SBCL + Emacs + SLIME working on Linux and update it for Mac OS X, using Aquamacs instead of Emacs. However, I found that someone has written a very good post on making Aquamacs + SBCL + SLIME working on Mac OS X Lion already.

Up and running with Emacs, sbcl, and SLIME

While I normally program in Python, a part of me wants to quickly hack some lisp code every now and then. Especially during those long minutes when my automated tests are running.

I realized that long neglect had left me without a working lisp setup. Here is how I got it up and running again.

Step 1: Get rid of system lisp and slime

The version of sbcl and SLIME in my Ubuntu system is not recent enough for my liking. So I get rid of them:

$ sudo apt-get -y remove sbcl slime common-lisp-controller
$ sudo apt-get -y autoremove # get rid of packages we don't need anymore
$ sudo rm -rf /var/cache/common-lisp-controller

Step 2: Install common requirements

cd ~/
sudo apt-get update
sudo apt-get -y install emacs22
sudo apt-get -y install cvs
sudo apt-get -y install git-core
sudo apt-get -y install darcs
sudo apt-get -y install subversion
sudo apt-get -y install build-essential
sudo apt-get -y install autoconf
sudo apt-get -y install curl
sudo apt-get -y install sbcl
sudo apt-get -y install texinfo
sudo apt-get -y install tetex-bin
sudo apt-get -y install xloadimage

Step 3: Get clbuild

$ mkdir lisp
$ cd lisp
# for fresh install of clbuild
$ darcs get http://common-lisp.net/project/clbuild/clbuild
$ cd clbuild
# Or, to update existing clbuild
$ cd clbuild
$ darcs pull

Step 4: Get latest SBCL

$ ./clbuild update sbcl
$ cd source/sbcl
$ sh make.sh
$ cd doc/manual
$ make
$ cd ../..
$ echo > ~/.sbclrc
(require :asdf)
(push "/home/parijat/lisp/clbuild/systems/" asdf:*central-registry*)
^D
$

Step 5: Setup SLIME

$ ./clbuild update slime

Now, we need to add this slime configuration to our .emacs file:

(push "/home/parijat/lisp/clbuild/source/slime" load-path)
;; Common Lisp Mode
(setq inferior-lisp-program "/usr/local/bin/sbcl")
(add-to-list 'auto-mode-alist '("\\.lisp$" . lisp-mode))
(add-to-list 'auto-mode-alist '("\\.cl$" . lisp-mode))
(add-to-list 'auto-mode-alist '("\\.asd$" . lisp-mode))
(require 'slime)
(slime-setup)
(eval-after-load "slime"
 '(progn
    (setq slime-complete-symbol*-fancy t
          slime-complete-symbol-function 'slime-fuzzy-complete-symbol
          slime-when-complete-filename-expand t
          slime-truncate-lines nil
          slime-autodoc-use-multiline-p t)
    (slime-setup '(slime-fancy slime-asdf))
    (define-key slime-repl-mode-map (kbd "C-c ;")
      'slime-insert-balanced-comments)
    (define-key slime-repl-mode-map (kbd "C-c M-;")
      'slime-remove-balanced-comments)
    (define-key slime-mode-map (kbd "C-c ;")
      'slime-insert-balanced-comments)
    (define-key slime-mode-map (kbd "C-c M-;")
      'slime-remove-balanced-comments)
    (define-key slime-mode-map (kbd "RET") 'newline-and-indent)
    (define-key slime-mode-map (kbd "C-j") 'newline)))
(add-hook 'lisp-mode-hook (lambda ()
                           (cond ((not (featurep 'slime))
                                  (require 'slime)
                                  (normal-mode)))
                           (indent-tabs-mode nil)
                           (pair-mode t)))

Note: pair-mode is a nice package for inserting balanced parentheses, quotes, braces and square-brackets, etc., which I installed earlier by hand.

Now we can launch emacs, and start slime with “M-x slime”.

Caveat

For some reason, after doing the above, slime would still not start. Doing a “M-x slime” would throw me into the sbcl debugger with the error message that sbcl could not find “/usr/share/common-lisp/systems/slime/swank-loader.lisp”, or something like that (I could be wrong about the exact path). After much head-scratching (and grepping my ~/lisp directory), I figured out I had to change the emacs customization variable slime-backend. This can be done by doing “M-x customize-group RET slime-lisp RET” and changing the value of “Slime Backend” to simply “swank-loader.lisp” (the file should be in the same directory as “slime.el”). We can also give an absolute path to the file. I found that the value of this variable was set wrongly (an artifact of using apt-get installed slime, I guess) and hence sbcl was not able to load the correct file.

My First Emacs Lisp Function


(defun how-many-chars ()
(interactive)
(message "We are %d chracters into this buffer."
(- (point)
(save-excursion
(goto-char (point-min))
(point)))))

GNU Emacs, SLIME, Allegro

For some reason, I decided that I just had to switch to GNU Emacs from XEmacs on my WinXP laptop. So I went and downloaded Emacs 22.1 for Windows and installed it.

Setting it up for Erlang was easy: I added this to C:\Documents and Settings\Parijat\.emacs:


;; Erlang:
;; Add the location of the elisp files to the load-path
(setq load-path (cons "C:/erl5.5.4/lib/tools-2.5.4/emacs" load-path))
;; set the location of the man page hierarchy
(setq erlang-root-dir "c:/erl5.5.4")
;; add the home of the erlang binaries to the exec-path
(setq exec-path (cons "c:/erl5.5.4/bin" exec-path))
;; load and eval the erlang-start package to set up everything else
(require 'erlang-start)

Now, to setup Common Lisp. I use Allegro CL 8.0 Free Express Edition. (Yes, one day I’ll buy the full version and repay Franz, but only after getting myself Lisp Certified ;-)) I was following the instructions at http://www.franz.com/emacs/slime.lhtml and http://common-lisp.net/project/asdf-install/tutorial/setup.html .

This is what I did:

1. Opened up ACL and loaded asdf into it:


International Allegro CL Free Express Edition
8.0 [Windows] (Aug 17, 2007 22:59)
Copyright (C) 1985-2006, Franz Inc., Oakland, CA, USA. All Rights Reserved.

This development copy of Allegro CL is licensed to:
Trial User

CG version 1.81.2.23 / IDE version 1.80.2.21
Loaded options from C:\Documents and Settings\Parijat\My Documents\allegro-prefs.cl.

;; Optimization settings: safety 1, space 1, speed 1, debug 2.
;; For a complete description of all compiler switches given the current optimization settings
;; evaluate (EXPLAIN-COMPILER-SETTINGS).

[changing package from "COMMON-LISP-USER" to "COMMON-GRAPHICS-USER"]
CG-USER(1): (require :asdf)
; Fast loading C:\Program Files\acl80-express\code\ASDF.001
T

2. Then, downloaded asdf-install and unpacked it into “C:\Documents and Settings\Parijat\asdf-install” (the source tarball has several nested directories called asdf-install; the innnermost contains the .asd file, and that’s the one I am referring to here).

3. Told asdf about this directory:

CG-USER(4): (pushnew "c:/Documents and Settings/Parijat/asdf-install/" asdf:*central-registry* :test #'equal)

and compiled and loaded asdf-install:

CG-USER(5): (asdf:operate 'asdf:compile-op 'asdf-install)
CG-USER(6): (asdf:operator 'asdf:load-op 'asdf-install)

4. Well, all this stuff was in the end to get SLIME. I went to http://common-lisp.net/project/slime/#downloading and found the link to the latest SLIME. Now, on Windows, it seems asdf-install can’t download and install tarballs off net (at least on Allegro CL). Then I downloaded and put the slime tarball in C:\Temp. Then:

(setq asdf-install::*verify-gpg-signatures* nil)
(setq *cygwin-bash-program* "c:/cygwin/bin/bash.exe")

and then:


CG-USER(7): (asdf-install:install "C:/Temp/slime-2.0.tgz")

This did not work, complaining:


Warning: Cannot find tar command "C:\\PROGRA~1\\Cygwin\\bin\\bash.exe".
Error: Unable to extract tarball C:/Temp/slime-2.0.tgz.

It seems my mod to *cygwin-bash-program* did not take effect inside asdf. Wonder why. I even quit Allegro, restarted it, defined *cygwin-bash-program* before compiling and loading asdf-install. No luck. (One thing I did not try was to define asdf-install:*cygwin-bash-program* instead of vanilla *cygwin-bash-program*). So I just went and hardcoded tar-command() in installer.lisp to return “C:\\cygwin\\bin\\bash.exe”.

Now the above command works.

5. The Franz documentation instructs me to start “mlisp.exe” or “alise.exe” LISP image (see next step). But my ACL 8.0 express did not come with these images; it only has “allegro-ansi.exe”. So, following the README in the acl80-express directory, I create the images, by starting allegro-ansi.exe, and in the “Debug window”, typing the following:

CG-USER(1): (build-lisp-image "sys:mlisp.dxl" :case-mode :case-sensitive-lower
:include-ide nil :restart-app-function nil
:restart-init-function nil)
CG-USER(2): (sys:copy-file "sys:allegro-ansi.exe" "sys:mlisp.exe")

Now, I have a mlisp.exe and mlisp.dxl. Sure enough, clicking on mlisp.exe launches a console LISP without the GUI.

6. Now I have to load slime into Emacs. According to the instructions on the Franz webpage, I created a file “C:\Documents and Settings\Parijat\.slime.lisp”, with the contents:

(load "C:/Documents and Settings/Parijat/.asdf-install-dir/site/slime-2.0/swank-loader.lisp")

(sys:with-command-line-arguments (("p" :short port :required)
("ef" :long ef :required))
(restvar)
(swank::create-server :port (parse-integer port :junk-allowed nil)
:style :spawn
:dont-close t
:coding-system (or ef "latin-1")))

and added this to my .emacs:

;; Allegro LISP + SLIME
(push "c:/Documents and Settings/Parijat/.asdf-install-dir/site/slimw-2.0/" load-path)
(require 'slime)
(slime-setup)

(setq slime-multiprocessing t)
(setq *slime-lisp* "C:/Program Files/acl80-express/mlisp.exe")
(setq *slime-port* 4006)

(defun slime ()
(print "this is my slime")
(interactive)
(shell-command
(format "%s +B +cm -L \"c:/Documents and Settings/Parijat/.slime.lisp\" -- -p %s --ef %s &"
*slime-lisp* *slime-port*
slime-net-coding-system))
(delete-other-windows)
(while (not (ignore-errors (slime-connect "localhost" *slime-port*)))
(sleep-for 0.2)))

I restart emacs. I say “M-x slime”. And wait. The mlisp.exe window shows up, but no connection.

I figure that the problem is in (swank:create-server :port …) which is supposed to start the swank server, does not work. If I run it in the mlisp.exe window, the command does not return (okay, maybe it is not supposed to). I can’t telnet to port 4006 on the localhost, though.

Puff!!! It used to be simpler.