Libre Software Meeting 2004

Christophe Rhodes (ed.)
<csr21@cam.ac.uk>

8 July 2004

Table of Contents

Introduction

The following are summaries of the lightning talks held on 8 July 2004 at the Libre Software Meeting 2004, held at ENSEIRB, Bordeaux. The talks themselves were informal, as are these proceedings: the intent was more to air half-formed ideas as a basis for discussion, rather than to present finished work; nevertheless, it is hoped that these ideas may be of interest to the wider Common Lisp community.
Christophe Rhodes, 2 August 2004 (version 1)

1  SBCL Threads


Daniel Barlow
<dan@telent.net>

SBCL includes support for OS-scheduled threads, which are therefore SMP-capable but do not allow Lisp control of the scheduler. This requires x86 and Linux kernel 2.6 or systems with NPTL backports.

1.1  Special variables

The interaction of special variables with multiple threads is mostly as expected, but in places somewhat different from that traditionally implemented e.g. in Allegro CL, Lispworks etc.:

1.2  Mutex support

For controlling access to a shared resource. One thread is allowed to hold the mutex, others which attempt to take it will be made to wait until it's free. Threads are woken in the order that they go to sleep

There isn't a timeout on mutex acquisition, but the usual WITH-TIMEOUT macro (which throws a TIMEOUT condition after n seconds) can be used if you want a bounded wait 
(defpackage :demo (:use "CL" "SB-THREAD" "SB-EXT"))

(in-package :demo)

(defvar *a-mutex* (make-mutex :name "my lock"))

(defun thread-fn ()
  (let ((id (current-thread-id)))
    (format t "Thread ~A running ~%" id)
    (with-mutex (*a-mutex*)
      (format t "Thread ~A got the lock~%" id)
      (sleep (random 5)))
    (format t "Thread ~A dropped lock, dying now~%" id)))

(make-thread #'thread-fn)
(make-thread #'thread-fn)

1.3  Waitqueue/condition variables

These are based on the POSIX condition variable design, hence the annoyingly CL-conflicting name. For use when you want to check a condition and sleep until it's true. For example: you have a shared queue, a writer process checking ``queue is empty'' and one or more readers that need to know when ``queue is not empty''. It sounds simple, but is astonishingly easy to deadlock if another process runs when you weren't expecting it to.

There are three components: Important stuff to be aware of:
  1. when calling condition-wait, you must hold the mutex. condition-wait will drop the mutex while it waits, and obtain it again before returning for whatever reason;

  2. likewise, you must be holding the mutex around calls to condition-notify;

  3. a process may return from condition-wait in several circumstances: it is not guaranteed that the underlying condition has become true. You must check that the resource is ready for whatever you want to do to it. 
(defvar *buffer-queue* (make-waitqueue))
(defvar *buffer-lock* (make-mutex :name "buffer lock"))

(defvar *buffer* (list nil))

(defun reader ()
  (with-mutex (*buffer-lock*)
    (loop
     (condition-wait *buffer-queue* *buffer-lock*)
     (loop
      (unless *buffer* (return))
      (let ((head (car *buffer*)))
        (setf *buffer* (cdr *buffer*))
        (format t "reader ~A woke, read ~A~%" 
                (current-thread-id) head))))))

(defun writer ()
  (loop
   (sleep (random 5))
   (with-mutex (*buffer-lock*)
     (let ((el (intern
                (string (code-char 
                         (+ (char-code #\A) (random 26)))))))
       (setf *buffer* (cons el *buffer*)))
     (condition-notify *buffer-queue*))))

(make-thread #'writer)
(make-thread #'reader)
(make-thread #'reader)

1.4  Miscellany

2  ASDF/ASDF-INSTALL


Daniel Barlow
<dan@telent.net>

2.1  Using asdf-install

(require 'asdf-install)
(asdf-install:install 'split-sequence)
downloads, compiles and installs the SPLIT-SEQUENCE package, as well as any packages it depends on that are not already installed. It works using specially formatted links on CLiki pages: to asdf-install the foo package, www.cliki.net/foo is expected to contain a link 
:(package "http://www.example.com/foo.tar.gz")
to the location from which foo.tar.gz and foo.tar.gz.asc (see below) can be downloaded.

2.2  GNU Privacy Guard

Anybody can change a CLiki page, which may cause you to load arbitrary code into your lisp. This is usually considered Not Good, so we do crypto signature checking using the GNU Privacy Guard.

asdf-install performs three checks:
  1. The signature exists;
  2. You trust that the signer is who he says he is: a GPG trust relationship exists between you and him;
  3. You trust the signer's good intentions and Lisp abilities: asdf-install maintains a list of Lisp hackers' fingerprints in $HOME/.sbcl/trusted-uids.lisp.
Every time you meet a Lisp hacker, exchange GPG keys with him. Likewise Debian developers, who have invested serious time into their PGP web of trust so are great people to piggyback off.

2.3  Writing your own packages

  1. Write an asdf system definition that knows how to compile/load the system. There is documentation (hidden in a README file), but most people copy an existing one.

  2. Tar it up.

  3. Create a detached GPG signature.

  4. Upload both files somewhere.

  5. And add a link on CLiki. Finito.
More information is available from http://www.cliki.net/asdf-install

3  Making McCLIM use less ugly fonts


Andreas Fuchs
<asf@boinkor.net>

Using a typical CLIM application in the http://clim.mikemac.com/ McCLIM means putting up with a Courier font for all text (unless the application specified the use of another text family for output). Changing that involves either hacking (and recompiling) the application or hacking (and, expensively, recompiling) McCLIM - both of which aren't optimal nor interesting solutions, especially for new users of McCLIM.

I present a way of making McCLIM use a different default font for text that does not involve recompilation of anything. Unfortunately, this method isn't very good lisp code either, but it's a drop-in solution that works for now. (The McCLIM developers that were present during the talk agreed that it would be a better idea to make the fonts settable at run-time via a sane mechanism.)

What happens is this: The CLX backend defines mappings of CLIM font names to actual X fonts. These are set up for the CLX port when the first display is opened. So, the code at
http://boinkor.net/lisp/font-hackery.lisp defines an :around method for the font initialization generic function, and rebinds the default font mapping to something that is more desirable to the user.

4  Case sensitive Common Lisp packages


Bruno Haible
<bruno@clisp.org>

This talk presents a way to allow Common Lisp to be programmed in a case-sensitive way, while at the same time allowing seamless integration with legacy Common Lisp programs that assume case-insensitive behaviour.

The goal is to make possible Common Lisp programs with case sensitive symbols. Example: 
> (list 'MacOS 'X)
(MacOS X)
There are implementations of this feature (Franz Inc.'s Allegro CL), but they don't allow legacy Common Lisp programs to be used at the same time, thus creating a schism in the CL world and posing a major obstacle to the adoption of this modern style.

Here an approach is presented that allows case-sensitive packages and case-insensitive packages to coexist in the same process and interoperate with each other. Example: 
    OLD.LISP
(IN-PACKAGE "OLD")
(DEFUN FOO () ...)

   modern.lisp
(in-package "NEW")
(defun bar () (old:foo))
(symbol-name 'bar) => "bar"

4.1  How it works

  1. There is the notion of case-sensitive packages. When a package is declared or created, it can take the option :case-sensitive t. The effect of this declaration is that the reader doesn't uppercase the symbol name before calling intern. Similarly, the printer, when printing the symbol name part of a symbol (i.e. the part after the package markers), behaves as if the readtable's case were set to :preserve.
  2. There is the notion of case-inverted packages. When a package is declared or created, it can take the option :case-inverted t. What this means, is that in the context of such a package, symbol names are case-inverted: upper case characters are mapped to lower case, lower case characters are mapped to upper case, and other characters are left untouched. (Mapping lower case characters to upper case is not particularly desirable, but it doesn't matter since symbol names with lower case characters are rare in the ``old'' world. However, what matters is: It is essential that the mapping be injective and covariant w.r.t. string concatenation. The chosen case-flipping satisfies this.) Every symbol thus conceptually has two symbol names: an old-world symbol name and a new-world symbol name, which is the case-inverted old-world name. The first symbol name is returned by the function CL:SYMBOL-NAME, the modern one by the function ci-cl:symbol-name. An implementation may choose to store only one of these two symbol names, and compute the other one on the fly. The two package invariants involving strings hold whether you view them using CL:SYMBOL-NAME or ci-cl:symbol-name: Therefore the package system continues to work either way. The internal functions for creating or looking up symbols in a package, which traditionally took a string argument, now conceptually take two string arguments: old-style-string and inverted-string. (Again an implementation is free to choose a different internal working, such as either always passing old-style-string, or always passing inverted-string, or passing string and invertedp arguments.) For a few built-in functions, a variant for the case-inverted world needs to be defined: These variants, together with the unmodified symbols from the COMMON-LISP package, can conveniently be exported from a CASE-SENSITIVE-COMMON-LISP package, with nicknames CS-CL and CI-CL. Similarly, a package CS-CL-USER playing the same role as CL-USER, but for the case-sensitive world, can be provided.
  3. The handling of package names is unchanged. Package names are still usually uppercase.
Note that gensyms and keywords are still treated traditionally: even in a case-sensitive package, (eq #:FooBar #:foobar) and (eq ':KeyWord ':keyword). We believe this has limited negative impact for the moment, and can be changed in a second step, a few years from now.

4.2  Migration tips

The following practices will pose no problems when migrating to a modern case-sensitive world: The following practices will not work in a case-sensitive world or can give problems:

5  Using the MOP for a Foreign Language Interface to Java


Bruno Haible
<bruno@clisp.org>

This talk explains how the MOP can be used to define the critical parts of an object-oriented foreign language interface in a portable way.

We assume at the basis that we have a Common Lisp implementation that can
  1. access Java objects,
  2. call Java functions and methods,
  3. generate Java bytecoded classes.
Note: Java and CL can be tied in different ways: The precise nature of the Java / CL coupling is not relevant here.

The goal of the project would be create subclasses of Java classes like this: 
(defclass <hello-panel> (javax.swing.JComponent)
  ((hello-label :type javax.swing.JLabel))
  (:metaclass java-class))

(defmethod paintComponent ((c <hello-panel>) (g java.awt.Graphics))
  ...)
The MOP is used in three areas.

5.1  Class Definition Customization

compute-superclasses is modified 1. to take into account java.lang.Object as superclass when no superclass is specified. 2. to ensure a proxy class for redirecting Java public/protected methods into Lisp. (Namely, every time a Lisp class L is defined as being a subclass of a Java class J, under the hood, a Java subclass J' of J is defined, and L is defined as inheriting from J', not J.)

compute-slots has a modified :around method to allocate slots in Java objects vs. its Lisp counterpart, taking into account the fact that in Java, slots of type `double' take two words instead of just one (assuming 32-bit words).

5.2  Slot Access Customization

slot-value-using-class is modified to take into account whether a slot is allocated on the Java side or on the Lisp side of an object.

5.3  Method Customization

A class java-method, subclass of standard-method, is created with a :function argument, that invokes a Java method. This is necessary to make Java methods visible as first-class objects in the Lisp world.

6  Efficiently handling multiple network clients


Éric Marsden
<emarsden@laas.fr>

6.1  Introduction

6.1.1  Context: the c10k problem

How can we service 10000 concurrent clients from a single lisp image? (Even 1000 clients is a challenge!)

Problems:

6.1.2  Potential I/O strategies

Two main concurrency strategies: Combined with various I/O strategies:

6.2  SERVE-EVENT

6.2.1  CMUCL's SERVE-EVENT mechanism

CMUCL includes a serve-event mechanism that is quite well designed and convenient to use. API:

6.3  Hazards

6.3.1  SERVE-EVENT traps

6.3.2  Luke Gorrie's delay exploit

Here is the handler that is installed by add-fd-handler and called upon activity on this socket: 
   (defun server-handle-connection (number socket)
     (let ((stream (sys:make-fd-stream socket :input t))
           (successful nil))
       (unwind-protect
            (with-standard-io-syntax
              (say "Connection #~D read ~A" number (read stream))
              (setq successful t))
         (close-connection stream)
         (unless successful (say "Connection #~D aborted!" number)))))
Here is a case with two clients, A and B, where A must wait for B to finish a request before being able to proceed, even though all of A's data is available to the server. 
   (defun delay ()
     (with-clients (a b)
       (send a first-half)
       (send b first-half)
       (send a second-half)
       (sleep 5)
       (send b second-half)))
Both clients connect and send half of a request, with A sending first. The server enters ``blocking'' READ, first for A and then for B, and awaits more input.

The relevant parts of the server's Lisp stack look like this: 
  (SERVE-EVENT)
  (READ B)
  (SERVE-EVENT)
  (READ A)
  (SERVE-EVENT)
  (SERVER-LOOP)
Next A sends the rest of his request. But what can we do with it? Nothing yet: we cannot return from (READ A) without first returning from (READ B), and B is still blocking. A must wait for B's request to complete. In the test case this takes a few seconds.

This case can occur if the network fails between client and server, and it's easy to trigger deliberately (maliciously).

Partial solution: timeouts on streams

6.3.3  Error propagation exploit

Another issue presents itself from looking at the previous stack diagram. What if an unhandled condition is signalled in the read of B?

With our server it will propagate right up the stack and be handled by server-loop. That means that an error triggered by client B will cause client A's handler to be unwound from the stack, aborting his connection in the process.

Fix: always handle all errors in an event handler

6.4  Framework

6.4.1  Safe use of serve-event

Use a framework that decouples I/O handling from request processing: Limitations: Code for the framework is available at http://www.laas.fr/~emarsden/etc/event-server.lisp.

Stress-tested using seige: limited by 100 Mb/sec Ethernet

6.4.2  Future work

For non-blocking I/O, we use a CMUCL-specific function named sys:read-n-bytes instead of the standard read-sequence. The CL standard does not specify any way of doing non-blocking I/O.

This function reads directly from a file descriptor, so it doesn't cooperate well with libraries like the cmucl-ssl bindings to OpenSSL that also require access to file descriptors (in the case of cmucl-ssl, replacing fd-stream functions by FFI calls to the OpenSSL library functions SSL_read and SSL_write).

Simple-streams might be a nice way to do non-blocking I/O in a semi-standardized fashion.

For very high performance, it would be good to avoid copying of data in lisp and lisp ® TCP (zero-copy issues, requiring interaction with the operating system).

7  :IEEE-FLOATING-POINT


Christophe Rhodes
<csr21@cam.ac.uk>

The :ieee-floating-point feature in a Common Lisp implementation
if present, indicates that the implementation purports to conform to the requirements of IEEE Standard for Binary Floating Point Arithmetic.

-- the ANSI Common Lisp standard
IEEE 754 only specifies the results of basic operations: in Common Lisp terms, the arithmetic +, -, *, /, and sqrt operators, the rounding operators, and coercion. However, it specifies not only the return values, but also the effect on the floating point state: certain operations are specified to raise exceptions (which can be selectively masked). For instance, (/ 1.0 0.0) should return single float positive infinity, but should also raise the division-by-zero exception.

This is relatively uncontroversial in the Common Lisp world -- though implementations differ over whether the trap results in an Lisp-level condition being signalled. However, the IEEE 754 standard also suggests that, if possible, trapping operations should provide sufficient context for the user to be able to know the causes of the trap: passing operands and the attempted operation to any condition handler. At present, no Common Lisp implementation does this to a meaningful extent.

There are other, conceptually simpler, disconnects between the requirements of IEEE 754 and Common Lisp, such as the result of (sqrt -1.0); Common Lisp integrates complex numbers fully with its arithmetic operations, and sqrt is defined to return the prinicipal value, whereas IEEE 754 prescribes a NaN return value and the :invalid trap.

If there is one thing clear about the :ieee-floating-point keyword feature, then, it is that its meaning is unclear; a simple meaning that current practice is compatible with is that the basic operations on floating point numbers give IEEE 754-compatible return values. However, a best-faith attempt to implement more advanced semantics would probably have value.

In a situation where the intended meanings are unclear, it is often preferable to attempt to write tests first, as this firstly establishes what interfaces are necessary, and secondly clarifies assumptions. A project for testing IEEE floating point semantics has been started2 and includes translations of previous testing attempts (primarily for the Fortran and C languages) into Common Lisp, with some implementation-specific support code which it is hoped will form the nucleus of an IEEE floating point interface.

Some ``advanced'' features of IEEE floating point semantics are demonstrably possible to support: various Common Lisp implementations have interfaces allowing the user to control the rounding mode, the precision or masking of trap extensions (such as the x86's denormalized-operand trap). There remain, however, unanswered questions, such as whether the behaviour of round (or fround, or ftruncate) is sensitive to the FPU rounding mode; whether the reader is sensitive to the rounding mode (so that, for instance, (read-from-string "1.0e9999999999") should return single-float-positive-infinity if the rounding mode is towards negative infinity), and whether it makes sense to specify traps taken during the computation of transcendental functions.

8  Some things about XML-RPC


Rudi Schlatte
<rudi@constantly.at>

8.1  What is it?

xml-rpc is a lightweight remote procedure call specification that uses HTTP as transport protocol; the payload is encoded with XML. The (short) spec resides at http://www.xmlrpc.com/spec.

xml-rpc has a fixed set of scalar datatypes: Composite datatypes are array and struct (associative array of string to any value).

Arrays and structs are dynamically-typed-language-friendly since they don't force all their elements to be of the same type.

8.2  Why should we care?

xml-rpc is easy to understand and use, and libraries exist for multiple languages. As mentioned, it is also friendly to dynamically-typed languages. It is used in the blogging community for offline weblog editors (http://www.xmlrpc.com/directory/1568/bloggingApis). The lisppaste bot at http://paste.lisp.org/ can be driven over xml-rpc as well. http://common-lisp.net/project/lisppaste/lisppaste.el is a snippet of code that defines an Emacs `lisppaste-region' command.

8.3  How is it used?

The following examples use the s-xml-rpc library at http://www.common-lisp.net/project/s-xml-rpc/.

8.3.1  Client side:

(call-xml-rpc-server '(:host "betty.userland.com") "examples.getStateName" 41)
=> "South Dakota"

8.3.2  Server side:

(defun add2 (x y)
  (+ x y))

(import 'add2 s-xml-rpc:*xml-rpc-package*)

8.4  Any other things?

There are some layered semi-standards, the most useful of which are:

9  Problems with extensible streams


Rudi Schlatte
<rudi@constantly.at>

9.1  Motivation for extensible streams

We want something like this: 
(make-instance 'db-stream
                :select-string "select blob from movies where title = 'xXx'")
or 
(make-instance 'socket-stream :remote-host "google.com" :remote-port 80)
... and be able to use read-sequence on the resulting object.

The two existing approaches are Gray streams3 and simple-streams4, each with its own set of problems.

9.2  Gray streams

Gray streams have the virtue of being supported by almost all CL implementations currently in use. The disadvantage of Gray streams is that subclassing can lose in interesting ways. An example would be a mixin class that keeps track of the column position of a stream: 
(defmethod stream-read-char :around ((stream column-counting-mixin))
   (let ((result (call-next-method)))
     (if (char= result #\Newline)
         (setf column-position 0)
         (incf column-position))
     result))
The equivalent function either must or must not be implemented for stream-read-char-no-hang, depending on whether the stream class that is extended via this mixin implements read-char-no-hang by calling read-char or not. There is no way to write this mixin in a general way!

Another issue is that Gray streams don't define stream-read-sequence and stream-write-sequence; CL implementations differ in the way they make this functionality available to the user.

Finally, the fact that every stream operation involves a generic function call might or might not be a performance problem.

9.3  simple-streams

simple-streams make the following assumptions: simple-streams originated in Allegro Common Lisp; a partial implementation is available in cmucl, and in sbcl (in the sb-simple-streams contrib module).

Sadly, simple-streams are underspecified in places (notably, external-format handling), and the device protocol for implementing new types of streams can be described as ``hairy''. Also, some details of the specification seem to be mandated by implementation needs.

9.4  Perspective

As a result of discussions at the Libre Software Meeting, a mailing list was created for further discussions of extensible streams5.

1
See http://cvs.telent.net/cgi-bin/viewcvs.cgi/bordeaux-mp/Specification?view=markup.
2
see http://www.common-lisp.net/project/ieeefp-tests for more information.
3
http://www.nhplace.com/kent/CL/Issues/stream-definition-by-user.html
4
http://www.franz.com/support/documentation/6.2/doc/streams.htm
5
see http://common-lisp.net/mailman/listinfo/streams-standard-discuss.
This document was translated from LATEX by HEVEA.