#{Unspecific}

I’m pleased to announce the release of the first version of Myscsh.

Myscsh is an implementation of the MySQL client/server protocol written entirely in Scheme. This package provides functions to connect to a MySQL database server, authenticate, send queries, and receive and parse result sets. The API is quite low-level: it’s just about reading and parsing messages and sending messages. Thus, using the low-level API of Myscsh requires a bit of knowledge of the MySQL client/server protocol.

Future versions of Myscsh will include a higher-level API for convenient database programming. Myscsh implements the MySQL 4.1 protocol (which has the internal protocol version number 10) and has been tested in conjunction with a MySQL 4.1 server on Linux. It might work with a 5.x server as well, but that’s completely untested. It won’t work with 3.20 servers, that’s for sure.

Download

The latest version is available at

http://www-pu.informatik.uni-tuebingen.de/users/knauel/myscsh/

Why an implementation of the protocol?

An alternative approach for connecting to MySQL is to use the C library libmysqlclient.so. A lot of language implementations provide bindings to this library. Hence, this is a well-tested approach. However, here
are some reasons for implementing the protocol in Scheme:

• No C code to compile, no header files to search for, no shared libraries to search for, and no dynamic modules to load. Less high-tech, less trouble.
• In scsh and Scheme 48, calling C functions from Scheme blocks the whole Scheme system until the C function returns. Hence, sending a complex query to MySQL using the corresponding C function will stop all Scheme threads until the SQL result is available. This is not acceptable, especially since the SQL queries may take seconds to compute. There is no easy way to fix this.
• The Scheme code is quite portable and could be used by other Scheme implementations. The code only uses very few Scheme 48 or scsh specific features, i. e. for network connections.
• Writing C bindings is boring. I have written too much C bindings in the past years.

Implementing the protocol is not a particular original idea: For example, there is a Ruby implementation of the 3.20 protocol.

Source code repository

The latest version of the source code resides in a darcs repository at the following address:

http://www-pu.informatik.uni-tuebingen.de/users/knauel/sw/myscsh/

Known bugs, limitations

Some things that may cause trouble:

• The code completely ignores character encoding issues. It just assumes that the character encoding the Scheme system is using is the right one for communicating with the server. This works in many cases, but is a bad idea in principal.

Some things that have not been implemented or tested yet:

• receiving result sets that contain binary values
• repared statements, parameter messages, and long data packets
• compression

Future work

• Write some documentation
• Add a high-level API for convenient database programming
• Better error-handling using SRFI 34 and SRFI 35

Technorati Tags: Scheme, MySQL, Protocol, Scheme 48, scsh

Finally, I have had some time to finish the Scheme code that generates the MySQL client auth protocol messages. The SHA1 implementation seems to work fine, although it’s quite slow: The specification contains a test case that consists of calculating the hash value of one million a characters. This test took 35 minutes on a 3 GHz Pentium III processor… So, you probably don’t want to replace /sbin/sha1 with the Scheme implementation yet…

However, for small messages, such as the MySQL passwords, the implementation is fast enough. Next on my list: Generating query messages and reading replies. Doesn’t look too complicated. Here’s my code (as a darcs repository):

http://www-pu.informatik.uni-tuebingen.de/users/knauel/sw/myscsh/

Technorati Tags: Scheme, MySQL, SHA1

News on my favorite low priority, by the way project: a pure Scheme implementation of the MySQL protocol. Login for user accounts without passwords seems to work fine. The next thing is to implement the MySQL password algorithm. This involves the SHA1 cryptographic hash functions. There are plenty of implementations in C which I could have used via FFI bindings. However, I didn’t like the idea of an “impure” part in the protocol implementation. Especially not, if the impure part only does some integer arithmetic.

So, I wrote an SHA1 implementation in Scheme. This was a quite nice experience, SHA1 deals with 512 bit message blocks which can easily represented as a bignum in Scheme. The code for chopping the input message into 512 bit blocks is still not complete (preprocessing the message is actually an annoying task), but once this works I hope I can login into MySQL with a password.

Technorati Tags: Scheme, MySQL, SHA1

I’m pretty happy with MacBookPro: For me the transition to an Intel based Mac worked very well. Not problems at all. So far. Till now. This one is really scary:

Welcome to Scheme 48 1.3 (made by knauel on Sat Apr  1 18:38:35 MST 2006)
[...]
> (* 3 1.0)
5.307579804e-315

The scary thing is that this only happens when I use the universal binary of Scheme48 1.3 on a PPC system—the same calculation with exactly the same binary on the MacBookPro yields the correct result. A PPC binary on a PPC machine also calculates the correct result…

Technorati Tags: Scheme48

The semester has ended; time to prepare the next semester. Two weeks ago I conducted a lot of job interviews with students applying as TAs for the introduction course “Informatik I” starting in October. There was a gap of about 5 to 10 minutes after each interview—too few time to something reasonable. So I spent the time on a low-priority project: an implementation of the MySQL protocol for Scheme. Well, even though I normally enjoy hacking low-level stuff, I wish I had more tool support. For example, I wish I had an ASN.1 compiler for Scheme. I really would like to be able to write a ASN.1 notation of the packet and turn this description into a Scheme function which parses the packet. This would be even cooler than better binary parsing functions. An ASN.1 compiler for Scheme would open a wide range of uses. For example, the LDAP protocol is specified in terms of ASN.1. It would be so cool to have a portable pure Scheme implementation of LDAP! Writing bindings for the LDAP client library is an option, but that’s not portable nor lightweight. (I’ve written such bindings for scsh, but that was just another waste of time: Lots of boring C code, annoying GC problems, and so on.) Other famous uses of ASN.1: digital certificates a la X.509 and PKCS7, Kerberos V messages, SNMP, and I bet one could specify lots of binary file formats in terms of ASN.1.

Note to myself: Once you have more time, spend it on hacking a ASN.1 compiler.

(BTW, once I managed to assemble correct “client authentication” packets for the MySQL protocol, I’ll post a link to the darcs repository.)

Technorati Tags: MySQL, Scheme, ASN.1, LDAP

I’ve been working on a control-flow analysis for Scheme 48 for a while now. In this analysis, functions represented as maps are omnipresent: variable environments map bindings to abstract values, binding environment map this to that, and so on. It’s quite easy to represent these functions as association lists, which is how they are represented now. Well, obviously a kind of hash table would be much faster.

However, most of the domains of these functions are actually represented by complex Scheme record types which makes it hard to come up with a reasonable hash function. Actually, in many cases it would be the best solution to use the memory address of the Scheme record as the hash value: Many of the association lists use eq? as the comparison operator anyways. However, you can’t do that in Scheme: There is no way to get the memory address of an object. Which makes sense: The Scheme implementation is free to move the program values around at any time. And implementations with a moving garbage collector do this all the time. Hence, a hash table that uses the address as a key must be rehashed after each garbage collection. Some implementations such as PLT Scheme offer such functionality and call such tables eq?-hash tables.

During the last weeks I started to implement eq?-hash tables (which I call id-tables) for Scheme 48. That just seemed to be a good idea. Here is how they work. I have added a new “stob type” (think of it as a record type defined by the VM) for id-tables to the VM and added new instructions for adding, searching, and deleting items in that table. An id-table consists of two fields: A counter field that says how many values are currently stored in the table and a vector which is the actual hash table. The entries of the vector are a lists of pairs. Each pair consists of the object used as the key and the object used as the value for this key. It’s necessary to remember the key object since the hash function (the address of the key object modulo the vector size) may map more than one object to the same vector index. Well, this is just the usual simple representation of a hash table.

Things get interesting when a garbage collection occurs: Scheme 48’s two space copier moves the key objects (and all other objects) two the new heap space, hence the hash key of the object changes. The id-table and it’s content is treated like any other Scheme object. Hence, after the garbage collection there is a copy of the id-table in the new heap space. All addresses in the table’s vector are updated to the corresponding new addresses. That’s fine, but in general the objects are now at the wrong index: We need to rehash. Rehashing is quite easy: Traverse all entries of the vector, re-calculate the hash-key for each key object and either move the entry to a new index in the vector or leave it untouched (in case the hash functions maps the old and new address to the same index). All this is done in place: The rehashing modifies the copy of the hash table instead of copying the contents to a fresh vector. The latter would probably be a little bit easier and faster, but harder to implement: rehashing happens just after the garbage collection and it’s a bad idea to allocate new heap space in this situation (Actually, these post-gc cleanup hooks are part of the GC process). However, the in-place rehashing has the disadvantage that the algorithm actually might re-calculate the hash function for each object twice (worst case). I think that’s a fair trade-off, calculating the hash function should be very fast.

A diffrent solution would be to treat the id-tables specially during the garbage collection. But I found that complicated: The objects in the table don’t have their new addresses yet and doing the whole copying and so on is a tedious business. The advantage would be that the id-tables are easy to find: The GC algorithm traverses the heap and this way just stumbles over the id-tables. The post-gc rehashing mechanism I have implemented has to involve some extra machinery to find the id-tables: The constructor for id-tables registers the freshly created id-table in a global list. The rehashing procedure uses this list to find all id-tables.

I should mention that at the moment I have only considered the two space copy collector of Scheme 48. So, the id-tables won’t work with the upcoming new generational collector yet. Actually, id-tables is the second approach. I started with an implementation of stable names, but I gave up this approach. Various reasons, might tell later.

Technorati Tags: Scheme 48, Scheme, garbage collector, PLT Scheme, id-tables

I’m missing MySQL bindings for Scheme 48 or scsh. Well, I wrote ODBC bindings for scsh a few years ago, but using ODBC on UNIX systems is just too painful. Looking at ruby, I found out that it seems to be fairly easy to implement the MySQL protocol. Although there is no official documentation, there are some hints available on the web and the ruby source code is a second source of information. I’ll convince the next student entering my office door that this is a perfect term project.

Technorati Tags: Ruby, MySQL, Scheme, Scheme 48, scsh, ODBC

During the last six months I advised a student on her project for her diploma thesis which, of course, involved scsh. It’s a web-application for sharing, organizing, storing, displaying, and manipulating images. Think of it as an crossbreed of applications like iPhoto, ImageMagick, and flickr.com. Completely written as Scheme SUrflets. To my knowledge this application, named PhotoBase, is the largest SUrflet application so far (16000 LOC).

The basic idea is that users can upload their images either via HTTP-upload or by choosing an directory in the server’s file-system into an archive. This archive is basically some hierarchical directory structure on the server. The archive is accessible for registered users only. An administrator grants an user the right to create photo albums from the archive pictures. The idea is the following: the archive stores an immutable original copy of the image and albums contain selections of maybe modified images of the archive. An user may grant the right to view and comment the pictures of an album to other users, user groups, or the public. Albums may be static or dynamic. Dynamic albums are basically SUrflets which allows the application to do all the stuff like displaying comments, searching for photos and so on. A static album is just a directory full of image files and HTML files. Thus, works on all web-servers. Albums are generated by templates, i. e. module that is expected to implement a certain interface. PhotoBase has two neat standard templates. However, it’s very easy to write new templates.

Besides the albums there is a web-based image editor. This editor displays the image to be edited along with some widgets to modify the image such as buttons for resizing, rotating, enhancing contrast, and lots of other stuff. The server uses ImageMagick to actually carry out those operations. The editor also has an “undo preview bar” which displays a thumbnail version of the image in a certain state of manipulation. Clicking on such a thumbnail returns to that state of the image. A sequence of these operations may be safed as a “batch program” and applied to a set of pictures at once.

An user may add meta information to a picture such as all kind of descriptions (place, people, etc). In fact users define a set of meta data fields that are stored for a photo and may enter that information themselves or let other users edit this information on the album pages. Next to this user-specific meta data, there is also global meta data stored in the archive. This information includes the exif information read by ImageMagick’s identify program and a tag (for searching).

PhotoBase stores meta data as S-expressions in files, so there is no database involved. To keep the access to the information fast, a seperate thread reads the meta data from disk and waits for request on a synchronous Concurrent ML channel. Thus, all SUrflet instances share one thread that keeps the data for them. The server thread also saves the information to disk at regular intervals.

Three things need to be done before an initial release of PhotoBase:

• Review and committ some patches for SUnet needed by PhotoBase (HTTP upload, for example)
• Make it easier to specify where PhotoBase stores its archive
• Provide an install-script

That’s not an awful lot of work…

Technorati Tags: Scheme, PhotoBase, Concurrent ML channel, EXIF, scsh, SUnet

I forgot to mention that the web-page for the 2006 Scheme Workshop in Portland is online.

Technorati Tags: Scheme

I just started to use SVK to create a personal mirror and local branches of the Scheme 48 Subversion repository. I’ve created a local branch, added some files and committed the changes. Then, strange things started to happen. First thing I noticed:

[0 knauel@albert bla] svk diff benv.scm
=== benv.scm
==================================================================
Cannot display: file marked as a binary type.

For some reason, svk (or svn?) thinks that my Scheme source file is a binary file. However, svk (or svn?) doesn’t seem to be completly unaware of files ending with scm. The files marked as “binary” had an svn:mime-type property:

[1 knauel@albert bla] svk proplist benv.scm
Properties on benv.scm:
   svn:mime-type
[0 knauel@albert bla] svk propget svn:mime-type benv.scm
Lisp/Scheme program text