gameylisp

arnesi continuations

2006-09-23T02:39:00.000+10:00

I've just moved back to the UK from Australia. With a few days of jet-lagged downtime I've managed to fit in some fiddling with CL. The CVS version of SBCL now appears to work with Slime under Win32 (which is very very cool), and I've been playing with with-call/cc from arnesi. It took a bit of fiddling to realise that you need to use defun/cc - documentation seems to be quite thin on the ground. Once I twigged, it was pretty easy to port Fig 22.4 of OnLisp to CL:

(defparameter *paths* nil)

(defun/cc choose (choices)
  (if (null choices)
   (fail)
   (let/cc cc
  (push (lambda () (kall cc (choose (cdr choices)))) *paths*)
  (kall cc (car choices)))))

(defun/cc fail ()
  (if (null *paths*)
   (kall arnesi::*toplevel-k* '@)
   (funcall (pop *paths*))))

So that now Fig 22.3 can be written:

(defun/cc two-numbers ()
  (list (choose '(0 1 2 3 4 5))
  (choose '(0 1 2 3 4 5))))

(defun parlor-trick (sum)
  (with-call/cc
 (let ((nums (two-numbers)))
   (if (= (apply #'+ nums) sum)
    `(the sum of ,@nums)
    (fail)))))

How much memory gets allocated when you call a generic function?

2006-06-21T22:40:00.000+10:00

I was wondering what actually happens when you call a generic function - specifically, how much memory would get allocated. I've become a bit addicted to clisp's ext:times macro because it provides quite a good insight into the performance characteristics of a function.

I knocked together a quick test and got some results...and then got distracted making a nice way to collect and display the results. It turned into quite a fun little one-evening project that exercised some string manipulation and use of format.

So here's the code to define my 'show-bytes-allocated' macro:


(asdf:oos 'asdf:load-op "split-sequence")
(import 'split-sequence:split-sequence)

(defun make-adjustable-string ()
  (make-array '(0) :element-type 'base-char :fill-pointer 0 :adjustable t))


(defmacro times-to-string (&body body)
  `(let ((times (make-adjustable-string))
         result)
     (with-output-to-string (*trace-output* times)
       (setf result (ext:times ,@body)))
     (values result times)))


(defmacro bytes-allocated (&body body)
  `(let ((result))
     (destructuring-bind (head perm-count perm-bytes temp-count temp-bytes)
         (find-if (lambda (e) (equal (first e) "Total"))
                  (mapcar (lambda (l) (split-sequence #\Space l
                                                      :remove-empty-subseqs t))
                          (split-sequence #\Newline
                                          (multiple-value-bind (r s) (times-to-string ,@body)
                                            (setf result r)
                                            s)
                                          :remove-empty-subseqs t)))
       (declare (ignore head perm-count temp-count))
       (list (read-from-string perm-bytes) (read-from-string temp-bytes) ',@body result))))


(defmacro show-bytes-allocated (&body body)
  `(progn
     (format t "~20A ~20A ~10@A ~10@A~%" "Form" "Result" "Permament" "Temporary")
     (format t "~63,,,'-A~%" "")
     ,@(mapcar (lambda (form)
                `(destructuring-bind (permament temporary f r) (bytes-allocated ,form)
                   (format t "~20S ~20S ~10D ~10D~%" f r permament temporary)))
               body)))

This let me quite easily write a little test, creating a couple of classes and a generic function:


(defclass foo ()
  ())


(defclass bar ()
  ())


(defgeneric com (thing))

(defmethod com (thing)
  (declare (ignore thing))
  'something)

(defmethod com ((thing foo))
  (declare (ignore thing))
  'foo)

(defmethod com ((thing bar))
  (declare (ignore thing))
  'bar)


(defparameter athing nil)
(defparameter afoo (make-instance 'foo))
(defparameter abar (make-instance 'bar))


(show-bytes-allocated
  (com athing)
  (com afoo)
  (com abar)
  (com athing)
  (com afoo)
  (com abar))

Here's the output:


Form                 Result                Permament  Temporary
---------------------------------------------------------------
(COM ATHING)         SOMETHING                   192      15716
(COM AFOO)           FOO                          52       1744
(COM ABAR)           BAR                          52       1772
(COM ATHING)         SOMETHING                     0          0
(COM AFOO)           FOO                           0          0
(COM ABAR)           BAR                           0          0

So we can see that the first time a generic function is called on a particular thing it goes away and allocates a bunch of stuff, but then subsequent calls to it don't need any more allocations.

Disassembling (function com) after each call is quite instructive too - you can see how the function is modified each time. I expect that there's a limit to how many specialisations it'll keep around. It helps my mental model of generic functions to know that they behave in this way.

Another interesting thing I found whilst writing it is that nearly every time I'm tempted to use dolist, I always end up actually using mapcar.

Silly idea?

2006-06-17T23:32:00.000+10:00

I wonder if it's worth considering setting up something that'll generate C++ code from sexps? Similar to the various HTML or HLSL/CG generators. Might be interesting to think about...

Update Functions

2006-06-14T22:59:00.000+10:00

Ah, it's been a while.

I managed to get even better performance by precreating all the bitmaps for the cells. Obvious really, but it's now running pretty well.

Since the whole point of this exercise is for me to experiment with lisp features I've been experimenting with storing an update and render closure in each cell. This has worked out really nicely, allowing me to have a more efficient board update when opening up empty cells and also the ability to do neat effects like control the speed that the board opens up.

So the function below creates an update function that'll expose surrounding cells on the next update:

 
(defun show-surrounding-cells ()
 (make-updatefn (board ix iy) 
 (do-surrounding-cells (mine-x mine-y board ix iy) 
   (let ((cell (aref (board-cells board) mine-x mine-y))) 
  (when (cell-mine-count cell) 
   (setf (cell-updatefn cell) (update-expose))))) 
 nil))

It's also possible to create animation effects by using an update function and a render function sharing the same closure:


(defun hit-mine (cell speed) 
  (let ((count *cell-size*) 
  (delay speed)) 
   
 (labels 
  ((render (bitmap board ix iy left top right bottom cell mouse-inside) 
      
     (draw-cell bitmap board ix iy left top right bottom cell mouse-inside) 
 
     (let ((remain (- *cell-size* count))) 
    (alleg:blit *invisible-cell* bitmap 
       remain remain 
       (+ remain left) (+ remain top) 
       (- *cell-size* (* 2 remain)) (- *cell-size* (* 2 remain)))))) 
 
   (setf (cell-renderfn cell) #'render) 
 
   (make-updatefn () 
  (cond 
    ((zerop delay) (decf count) (setf delay speed)) 
    (t (decf delay))) 
  (if (zerop count) 
   (progn 
     (setf (cell-renderfn cell) nil) 
     nil) 
   self)))))

So this one makes the invisible cell bitmap shrink to nothingness leaving the new one behind.

I can create higher-level update functions as well. One useful one is delay, that just waits a certain number of frames before switching the given function in.


(defun delay-update (count function) 
  (make-updatefn () 
 (decf count) 
 (if (zerop count) 
  function 
  self)))

However, this leaves open the possibility of setting an update function over the top of another one that might be doing useful work. We can deal with this nicely with a combine update function:


(defun combine-updatefn (fn1 fn2) 
  (make-updatefn (board ix iy) 
 (setf fn1 (when fn1 (funcall fn1 board ix iy)) 
    fn2 (when fn2 (funcall fn2 board ix iy))) 
 (cond 
   ((and fn1 fn2) self) 
   (fn1 fn1) 
   (fn2 fn2) 
   (t nil))))

This runs both the update functions, eventually removing itself when one of the sub ones finishes.

As a debugging aid I can print out the current function on each cell, and it should be possible to set it up to inspect a particulary cell by clicking on it. Very cool potential there.

The great thing about this is that means I can store arbitrary data on a cell and do processing on it without having to make room for it in my main cell datastrucure. So by doing this I've decoupled the update logic and animation data from my simple board representation. Of course this sort of thing isn't limited to lisp, but it's an interesting way to think about it that falls into place quite naturally.

My latest distraction is trying to get SLIME and CLISP to work better with macro argument lists. I've been doing some hacking replacing lisp's standard defmacro with my own version that stores away some extra data, but I think the proper solution is going to be modifying CLISP itself.

Profiling and Optimisation

2006-04-13T14:52:00.000+10:00

I've managed to spend some time profiling. It turns out that it makes things much easier if everything is put in a package - then you can do slime-profile-package rather than fiddling with profiling each function individually.

The first results shows that we're spending most of our time talking through CFFI to get values of variables. This turned out to be mostly things like *font* and *mouse-x*. So I've added a system to allow easy updating of these variables through a couple of macros - define-updateable-var and update-var that uses the symbol plist to record a function to execute when updating the variable. Now I only calculate colors on initialisation and grab the updated version of things like *mouse-x* once per frame. This has resulted in much better performance - the fan on my laptop doesn't turn on while running it anymore and it seems to hover around 30% of CPU usage. I've also inlined draw-cell which made quite a big difference.

The new profile shows a much more evenly distributed set of function calls.

I'm going to be spending some time now playing around with cl-emb and cl-who to generate a photo-album style website.

Nearly playable...

2006-03-18T14:38:00.000+11:00

Managed to find some time for some more fiddling. I've made the board display a bit prettier and it detects mouse presses and updates it all. It's dog slow at the moment though - is actually unplayable unless I compile it. Guess it's time to learn about profiling and optimising in lisp.

A couple of useful macros came out of it:

with-board-geometry sets up an environment where a bunch of useful variables are defined - cell-width, total-width, total board area, etc. So the mouse click detection and board drawing code both use this.
do-all-cells iterates over all the cells in the board and evaluates the given form on them.
do-surrounding-cells iterates over all the cells surrounding a given cell
do-steps is a simple wrapper around do that increments a given variable by a certain amount for a given number of times. This is used when drawing the board.

So it is nice to have code that looks like this:


(do-all-cells (ix iy board)
  (update-cell-visibility board ix iy))


(defun add-counts-for-mine (board mine-x mine-y)
"Increment the mine counts for all cells surrounding mine-x mine-y"
(let ((cells (board-cells board)))
 (do-surrounding-cells (ix iy board mine-x mine-y)
   (when (cell-mine-count (aref cells ix iy))
  (incf (cell-mine-count (aref cells ix iy)))))))

cl-alleg on Sourceforge

2006-03-12T00:20:00.000+11:00

I've set up a sourceforge project for hosting the Allegro/CFFI stuff: http://cl-alleg.sourceforge.net/

Taking shape

2006-03-04T14:20:00.000+11:00

I started getting some of the stuff from Allegro's test.c going but very quickly got bored of that so I've started some actual work on the game itself.

There's a main loop going that attempts to run an update function 60 times a second and render the screen as often as it can. (I'm not convinced my version is working quite how I expect it to though!) I've got a very basic 'button' class that monitors the mouse and works like a button in a GUI. There's also the simple first-pass at the game logic - storing a minesweeper grid and calculating the number of neighbouring mines and that stuff.

Something that struck me while writing this is just how natural it feels to work with lexical scoping. I didn't really think about the fact that I was passing closures to an 'onclick' style function in my button object - it just turned out that way after I wrote it the first way I thought of. Very nice.

I'm also looking into setting up somewhere to host the source for the allegro / cffi stuff.

Hello World!

2006-02-25T21:07:00.000+11:00

I've got Allegro's exhello.c working from within clisp. It's quite cool to be able to type stuff in a SLIME REPL and get an Allegro window up.

For what it's worth here's the code:


;;; The hello world example
(defun test-hello-world ()
(with-allegro
   (progn
     (install-keyboard)
  
     (unless (set-gfx-mode *gfx-autodetect-windowed* 320 200 0 0)
       (set-gfx-mode *gfx-text 0 0 0 0)
       (error "Unable to set graphics mode"))
  
     ;; set_palette(desktop_palette)
  
     (clear-to-color *screen* (make-col 255 255 255))
  
     (with-acquire-screen
         (textout-centre-ex *screen*
                            *font*
                            "Hello, world!"
                            (/ (screen-w) 2)
                            (/ (screen-h) 2)
                            (make-col 0 0 0)
                            -1))
  
     (read-key))))

Things that are slightly different from the straight forward C version are:

the with-allegro and with-acquire-screen macros that wrap up the install_allegro / exit_allegro calls inside unwind-protects
screen-w and screen-h are actually macros (just like they are in the C version) but unlike the C version macros look different whereas in C they just look like variables

install_allegro requires a pointer to errno. I couldn't find a way to get hold of that from CFFI, but it looks like passing a NULL pointer works. Dodgy!

Also read-key doesn't seem to actually work until I've switch focus a few times. It's fine in full screen mode. Odd.

Wrapping stuff up with CFFI is an absolute breeze. Here's a few examples:


(defcvar "screen" :pointer)

(defcfun "clear_to_color" :void
 (bitmap :pointer)
 (color :int))

(defcfun "acquire_screen" :void)

CFFI automatically converts the C-style names into more LISP-style ones. So screen becomes *screen* and clear_to_color becomes clear-to-color. You can provide your own LISP name as well if you want. CFFI just smells of quality.

So what problems did I have? Well they were all to do with getting set up - once that was done it was a breeze actually hooking things up.

The first mistake was to try and build Allegro from sources in Microsoft Visual Studio 2005 express. VS2005 doesn't come with the platform SDK or DirectX SDK and so I had to download and install those. Then it turned out that the Allegro fix.sh script didn't have the changes for msvc8 that the fix.bat script has. Then I considered that I'd have to try and set my environment variables up. Then I downloaded the binary distribution of Allegro for VC8!

That was my second mistake. I don't know about manifests and at this point I don't care what they are or why they are. But I do care that every time I tried to link against alleg42.dll I'd get an error about not being able to find msvcrt80.dll. This seems to be a well known problem and the quickest fix of course would be to just download the allegro binary compiled in an earlier version of VC.

Armed with that I tried to get CFFI working. That needed ASDF so I had to get that working. Now all of the docs do say how to set up search paths, but it is kinda buried deep. It took a bit of fiddling, but I finally got them all talking to each other.

All in all I'm quite pleased with that. It looks like getting the Allegro interface isn't going to be too hard to do. I think my next task might be to try and get bits of the main test app up and running.

The beginning....

2006-02-25T13:45:00.000+11:00

So here I am! I've been writing video games professionally for the last 6 years or so and at the same time have started to get interested in LISP, probably as result of the smug LISP weenies on c2.com.

I've got started...I've read Practical Common Lisp online and bought a copy of ANSI Common Lisp. Of course the next big problem after that is choosing an implementation. Since I run Windows at home (it's just too convenient to have the same OS at work and at home) I'm not exactly spoiled for choice. I don't want to use a commercial implementation, so I'm playing around with CLISP, at least until the Windows port of SBCL becomes more stable. My rough guess (not based on anything concrete) is that CLISP have the same sort of performance as something like Ruby or Python. We'll see!

My first exercise was to get an accounting system for dealing with all the rent at my house written. Quite simple stuff really, but it got me familiar with writing, reading and editing LISP. At the same time I found myself playing a lot of multiplayer minesweeper under MSN messenger. I started thinking that it'd be quite cool to try and write a real-time (ie not turned based) version of this. So that's my current project, and this blog is going to try and track my progress.

Current status is a few ideas, and no visible working graphics library for clisp. That's my first task. I figured I'd try and get some bindings sorted out for Allegro. Why Allegro? Well, firstly I've used it before and secondly it was written by my mate and I think he'd find it quite cool to have lisp bindings for it!

So - I've gotta get Allegro built on my machine and then start hooking up functions for it. CFFI seems to be worth looking at for this.

Lets see how far I get before I get bored!