Wednesday, December 28, 2005


I've done quite a bit of work with SQL and there are two things that always occur to me when I'm using it: 1) it's really quite simple in terms of what each command does and how it does it and 2) it is really ugly; it is syntactically inelegant, inconsistent and inefficient. So what should I do? Yes, re-create it or at least a workable sub-set of it!

Lisp should be good for making a working SQL-alike. I can use bottom up design to abstract myself from list access to SQL's set like operators and I can get some practice using macros to replicate SQL's 3i syntax. And it'll give me something to do over the holidays, of course I'm currently unemployed so every day is a holiday! ;(

Layer 1: Basic database structure.
What does a database, table, column, row look like? How can I get tables from a database, columns or rows from a table, fields from a row etc. Here's what I decided on (in my own unique BNF that may or may not bear any resemblance to real BNF)
database -> (database (table*))
table -> (table (column*) (row*))
column -> (column column-name column-number)
row -> (row (datum*))

At this stage I can create items and get at their contents but other than that they are in the same table there is no relation between rows and columns.

Layer 2a: Adding/Removing items.
This layer just adds/removes tables to databases and columns and rows to tables.
It also maintains some basic data consistency like database, table and column name uniqueness and that rows have the correct number of elements for the tables they are added to.
I'm feeling pretty good about this because it allows me to do something that normal database systems generally can't: add and remove columns from tables in a live database while maintaining data consistency.

Layer 2b: Getting and setting data.
Using only table column and row objects (or their unique names) I can get and set at each data item uniquely.

Layer 3: Proto-SQL.
This is where things start to get interesting. I decided to make the SELECT statement and the row eliminator (WHERE clause functionality) return a temporary table. This seems like it could be pretty horrible for performance but it makes my life very easy because all the other operators can accept a temporary table just as easily as one that's connected to a database.
This layer also has the first macro the so called parse-where and my first ever use of eval-when for its sidekick expand-where.
This is also where the first major limitation occurs, consider:
WHERE (string= "COLUMN1" "VALUE1")
In normal SQL column names are double quoted and strings are single quoted. You can't do this (easily) in lisp because of #'quote/' so no database value can have the same value as a database, table or column name. I do plan to get around this using symbols at some point but not right now.

Layer 4: Real SQL-like.
This part is all macros that re-arrange, de-reference and error check the 4 implemented statements: SELECT, INSERT, UPDATE and DELETE-FROM (delete's already taken).
There are some real limitations: no order by, no joins, no sub-selects and some departures from SQL that I think make it better: where clauses are lisp expressions and the set clause for an update statement is a list of column-names and new values.

(in-package :looseql)
(defun test ()
(setf *databases* nil)
(let* ((database (make-database "DB1")))
(add-table (make-table "TABLE1") database)
(add-column (make-column "COLUMN0") (get-table-by-name database "TABLE1"))
(add-column (make-column "COLUMN1") (get-table-by-name database "TABLE1"))
(add-column (make-column "COLUMN2") (get-table-by-name database "TABLE1"))
(add-database database)
(setq *current-db* database)

(print 'inserts)
(insert INTO "TABLE1" VALUES ("INS00" "INS01" "INS02"))
(insert INTO "TABLE1" VALUES ("INS10" "INS11" "INS12"))
(insert INTO "TABLE1" VALUES ("INS20" "INS21" "INS22"))
(insert INTO "TABLE1" VALUES ("INS30" "INS31" "INS32"))
(insert INTO "TABLE1" VALUES ("INS40" "INS41" "INS42"))
(insert INTO "TABLE1" VALUES ("INS50" "INS51" "INS52"))

(print 'inserts-into-columns)
(insert INTO "TABLE1"("COLUMN0" "COLUMN1") VALUES ("INS0" "INS1"))
(insert INTO "TABLE1"("COLUMN1" "COLUMN2") VALUES ("INS1" "INS2"))
(insert INTO "TABLE1"("COLUMN0" "COLUMN2") VALUES ("INS0" "INS2"))

(print 'databases-after-inserts)
(print *databases*)

(print 'select-without-where)
(print (select ("COLUMN1" "COLUMN2") from "TABLE1"))

(print 'select-with-where)
(print (select ("COLUMN1" "COLUMN2") from "TABLE1" where
(or (string= "COLUMN0" "INS0")
(null "COLUMN1"))))

(print 'select-*)
(print (select * from "TABLE1"))

(print 'select-into)
(let (var)
(select ("COLUMN0") INTO (var) FROM "TABLE1"
WHERE (string= "COLUMN0" "INS50"))
(print var))

(print 'update)
(update "TABLE1" SET (("COLUMN1" "UPD1")
("COLUMN2" "UPD2"))
WHERE (not (or (string= "COLUMN0" "INS0")
(string= "COLUMN0" "INS00")
(string= "COLUMN0" "INS10")
(string= "COLUMN0" "INS20"))))

(print *databases*)

(print 'delete-from-with-where)
(delete-from "TABLE1" WHERE (null "COLUMN0"))

(print *databases*)

(print 'delete-from)
(delete-from "TABLE1")

I think that for three days work its not too shabby.
I also think that the name's pretty cool LooSeQL: Lisp SQL, loose because it's not only loosely SQL and also its loosely typed and finally I hear SQL refered to as 'sequel' a lot, I think 'squil' would be more accurate, so SeQL is better because we can all agree that it sounds like 'sequel'. It would be better if I used CLOS then I could say that it was Lisp Object Oriented SeQL, maybe next version.

Get the full source here.

Tuesday, December 20, 2005

New IFS-designer version.

Thanks to Alexey Dejneka for supplying the latest fixes to allow cmucl to benefit from porable sdl:surface type declarations and fix some issues in the README. So following the instructions may actually result in a usable system! I also put the examples back that I forgot to include last time.

The latest version is 0.1.2 and it now requires uffi.

Saturday, December 17, 2005

Fixes for IFS Designer in sbcl.

I can't remember exactly why I stopped using sbcl. It used to be my default lisp. I suspect that when I started using slime I just found that cmucl was easier. I'm happy to report, however, that sbcl works with slime (and has done for a while); I was just to busy/lazy to give it a try.

I released the first version of the IFS Designer that does animation and the first feedback that I get is that it doesn't work under sbcl. After a bit of investigation I found that it actually does work but sbcl was emitting a warning every time I referenced an sdl:surface. An IFS typically requires 1000s of points to be drawn so getting a warning for each was a big performance problem. A little help from sbcl-help and some type declarations and all is well. Get the 0.1.1 version, and thanks Zach, I'll be testing under sb and cmu cl from now on.
Under sbcl the IFS Designer is actually faster than under cmucl now. From not working to faster than my development environment, how amusing.

Thursday, December 15, 2005

IFS Designer animates!

The IFS Designer finally does what I intended from the very beginning. It creates animated IFS fractals YAY! It's not polished but the basic functionality of creation, animation and exporting is there. I've also consolidated it so that the matrix library and the required ltk-goodie are in the 0.1.0 archive. You still have to copy the .asd files to the right place because I have no idea how to work adsf-install. I expect that'll change soon if Peter Seibel and his gardening team has anything to do with it.

The animation functionality it pretty simple: you set the keyframes and the program will generate a smooth set of tween frames. The animation you see above is a result of 6 keyframes. I've added a short animation creation to the tutorial to the README.

I'd love to get some feedback from anyone who installs this even if you hate it, tell me.

And now I'm going to bed, good night.

Thursday, December 08, 2005

Reddit, Linkit, lisp, java and Wesnoth.

Reddit was the one general news source that could be relied upon to have lisp news on the front page. Is it too much to ask that we not alienate ourselves from a great opportunity to reach a bigger audience? I guess it is.
This whole thing makes us lispers look like vindictive idiots, again. I give credit to the Linkit people for doing more than yabbering impotently at one another. It's more than I could manage but Linkit's supposed to be a proof of concept but all it proves is that seven hours isn't enough time.
When I visited Linkit I was surprised to find that voting didn't work. This is, to my mind, one of the three fundamental features of reddit along with karma and user submissions. I know it only took seven hours but ten, twelve or even twenty-four hours to a fully working replica of reddit is a much better claim than seven hours to a broken imitation. Nice logo though.

In other news I recently had to take a java test for employment with a certain company. Java's 'features' irritated me for a while, but then I gave up trying to make java do it my way and bent to java's will. Things went a lot better after that and my code got smaller and prettier. A lesson for all of us I think.

Also, go and play Battle for Wesnoth, its great.

Friday, December 02, 2005

A couple of Ltk goodies.

I've had cause to play with Ltk quite a lot so I thought I'd share the widgets I've made. I wrapped up the BWidget tree control and a couple of other BWidgets that go along with it. The BWidget tree control works reasonably well, supports drag and drop and all the usual tree stuff so there it is. Enjoy.

The other widget is one I build from scratch. It's an animation controller widget. It supports multiple draggable frame and keyframe pointers and user controlled progress bars as well as bars that synch with frame generation. It's all CLOS so to use it all you have to do is inherit from frame and keyframe, override the frame creation methods and it'll do the rest. Nice. I created this one to use with the IFS program so that I can create custom IFS animations and it's quite handy but then I would say that.

So grab them here and run the #'test function in either asdf package for a crumby demo.

I other news I've started to learn prolog. I'm reminded of when I first started to learn lisp and the time I had to spend to understand the simplest procedure. It's also clear to me that, despite their many differences, if I didn't already know lisp it'd be a lot harder. Recursive unification makes my head hurt but at least I get the recursive part!

Tuesday, November 29, 2005

Linksys and wireless networking fun.

So I just spent essentially the last two days configuring our new wireless network. I decided on Linksys hardware because it is cheap and has a reasonable reputation. The router lived up to the reputation but both of cards were a problem.

My laptop runs Debian Linux. This is where the trouble started. I checked the compatibility list before I bought the hardware and the card was listed so I was happy. Of course it was listed, they're all listed. The only problem is that most of them have a blank space in the table where the driver name should be. Oops and arrrrgh. At this point I was worried but a little frantic googling yielded ndiswrapper.

My normal process for setting up new software that I don't fully understand is to find as many different sets of instructions as I can and try to follow them all simultaneously. This approach usually doesn't work too well but this time it was a success. Thank-you ndiswrapper!

The other computer runs win98 but at least it's not ME. To me this is like saying, "I fell from a third storey window but at least I didn't land on a spike!". I have been spoiled by Debian and, dare I say it, XP. I had forgotten what it was like to have to repeat all the steps until every mouse click and keyboard entry is perfectly executed.

The installation seemed to be going well until the configuration utility crashed. The configuration utility would only run once; after a new installation and would always crash right after I entered the passphrase. So I couldn't get it out of infrastructure mode (static IP). Reluctantly I reverted to the classic uninstall, reinstall cycle. The first uninstall deleted the windows dhcp libraries. After a number of failed installations and some failed un-installations, I found the correct steps to make it work:
  1. Uninstall the drivers and config utility, be thorough.
  2. Re-install the drivers causing the dhcp libraries to be re-installed (from my dusty old win98 CD).
  3. Reboot and quit the config utility before it has chance to crash.
  4. Change the advanced settings for the card in the windows network dialog to Ad Hoc mode and reboot again.
  5. The config utility will run again. Let it pick up the network, enter the passphrase.
  6. Hit OK, get a success message and quit as quickly as possible.

It worked and I have subsequenly enabled the security settings and it all still works.

Tuesday, November 08, 2005

IFS Designer Update and Tutorial

I've made some more updates to my IFS Designer. I think it's actually quite usable now as most of the changes are GUI changes. The main window is still just a mess of buttons but I'm just waiting until I've got enough functions to warant a menu. If I made one now it'd be save, load, exit and draw and that's just not worth my trouble putting a menu together and it's not worth your trouble to make the extra click. Anyway, here's the list of changes I did make:
  • There is now a README that contains a short tutorial. If you don't know what an IFS fractal is this won't tell you but it will tell you how to make one and a pretty one too!
  • Added a CHANGELOG, mostly to prevent me from claiming non-new features as new, also there's a (mercifully short) bug list.
  • Integrated the event loops for Ltk and cl-sdl to allow live update of IFS display. This was simply a case of telling the cl-sdl event loop to run ltk:process-events when it's idling. I initially felt a bit wrong about this. I thought Ltk should be in charge, not some subsidiary window that's only there to show the pretties. I like cl-sdl too but I wouldn't want to build a GUI with it! I got over myself when I realised that not only was it the path of least resistance but that the cl-sdl event loop spent most of it's time idling anway.
  • Separated the cl-sdl display window from the IFS class hierarchy so now it displays a given IFS rather than displaying itself. This is a bit of a no-brainer, the interface is not that which it controls/displays. Sometimes it's just easier (to start with) to lump it all together and then seperate it out once you've decided which bits should go where. I guess this design method is similar to the oft cited optimisation analogy of crystalisation. You start out using lists and no type information at all. Then as you find the optimisation bottlenecks you add the necessary declarations that allow a fast program to crystalize out of the mailliable, but slower un-typed lisp. Similarly with design you start out with lots of interconnected objects then as the desired functionality becomes clearer you can start to pull them appart until you have a nice clean, modular design.
  • Made cl-sdl display window exitable by changing a slot value. Now who's in control! :)
  • Closed windows now re-open automatically. When you close an Ltk window it is just hidden by default so it only needs to be made visible again not re-created; which is nice.
There's lots of extra code in the archive that's getting ready to implement exciting new features but not yet. It will give you an idea of what's on my mind though.

There's a new version of the matrix library that you'll also have to get for this new version to work.

Monday, October 31, 2005

IFS Designer Update

I just uploaded a new version of my IFS designer. The changes are:
  • Added save and load functions
  • Added some simple examples (sierpinski triangle, fern, square and square spiral)
  • You can now use the left mouse button to move (translate) the view for both the transform display window and the fractal window.
  • You can now use the right mouse button to zoom (scale) the view for both the transform display window and the fractal window.
  • Fixed an evil little bug with the transform selector that was causing IFS performance to be very poor. It should select the transforms at random weighted by the size of the determinant but instead it picked the last transform much more often. This caused the point density of the fractals to be all wrong but the fractals were still mostly the right shape. I love resillient algorithms, especially ones that can survive me!
The next issue I have to tackle is that the cl-sdl based fractal viewer (the rest is ltk) has it's own event loop so you have to quit it (hit q) before you can go back to editing the transforms. I guess I'll have to mesh the ltk and cl-sdl event loops together.

Friday, October 28, 2005

IFS Designer first Release

I have just made the first release of my IFS Designer program.
The new features are:
  • Generates IFS Fractals in an SDL window. I realize that this is the whole point but since it's the first release even core functionality is a new feature!
  • SDL window allows you to zoom into the fractal you've created. This is useful because many of the nice familiar fractals are contained in a unit square so without zooming they'd just be a dot and where's the fun in that?
  • The interface allows you to easily select and manipulate transformations that make up the fractal. Thanks Ltk!
  • Choose the number of points you draw for the fractal so you can get almost instant results or dense images.
  • LLGPL License for both the IFS Designer and the matrix library

Of course feedback is always welcome.

Monday, October 24, 2005

IFS Designer Project starts to take shape.

I've been putting in some work on my new and interesting project. It's a fun little app developed in common lisp with Ltk (a lisp interface into tcl/tk) in slime. It allow you to design 2D IFS fractals by graphically manipulating the transforms that comprise them.
I really like the IFS algorithm because it's just sooo simple:
  1. Take a number of transformations (scale, rotate, translate). Three is enough to produce a nice standard fern-like fractal.
  2. Starting at the origin, apply the transforms in a random order (weighted by the size (determinant) of the transformation matrix)
  3. After about 100-200 iterations, start to draw the points.
  4. Finish when you feel the image is dense enough.
Simple eh?
I'm no mathematician but the why goes like this:
  • The transforms represent a fractal attractor - the transforms are a very concise description of a set of points in space.
  • Each transform maps a part of the attractor onto itself - when you start on the attractor and apply one of the transforms the result will still be on the attractor.
  • Applying a transform to a random point will make it closer to the attractor - I suppose this is why it's called an 'attractor' :) . This is why you discard the first few points, to make sure you're at least near the attractor when you start to draw the points.
  • Weighting the picking of the transforms by determinant isn't actually necessary but it does improve the performance of the algorithm.
I'm not ready to show off any IFS fractals (yet) but I can give you the matrix library I developed for this project.

Thursday, October 20, 2005

My new blog, Yay!

The purpose of this blog is not just to big-up myself. I will be doing that plenty don't worry but the real purpose of starting this is to force myself to actually let other people see some of the software I write.

I'm a big fan of open source software and I'd like to achive the dual ends of entertaining myself and giving something to the movement that has given me so much great software. In order to do that I'm going to have to open myself to criticism. I'm sure that I'm not the only one who has developed a nice little library of interesing stuff but is too scared that people will think that it's rubbish to actually do anything but play with it myself. So I have resolved to stop simply masturbating and start, no no that's as far as I'm prepared to push that particular metaphor.

I guess I'll also be putting some other stuff up here as the mood takes me, it will probably mostly be to do with sci-fi books but I expect the occasional post about UK/US culture shock will creep in as I get out there more and find a job and stuff.