Sunday, March 30, 2003

I was looking at the Lush programming language recently. It's a dialect of Lisp that has many support libraries for numerical programming, neural networks, signal processing and image capturing. What it can do with the free package is quiet impressive. It has both an interpreter and the ability to compile to C and prides itself on the speed of its C code for numerical use. You can also mix C and Lisp code in the same function. Even interpreted the speed is pretty quick. They give the example of a harmonize function: (de harmonize (n) ((-double-) n) (let* ((z 0.0) (i 0.0)) ((-double-) z i) (while (< i n) (incr i) (incr z (/ i))))) In compiled mode, calling this with (harmonize 1000000) it takes about 0.2 seconds on my machine (333 Mhz P2) which seems to me to be very quick. It was substantially faster than compiled Goo code which took on the order of 30 seconds. The interpreted version was even faster than the compiled Goo and also faster than interpreted Common Lisp (using CMUCL). The problem with Lush is its version of Lisp is extremely old. It predates Common Lisp and Scheme. It does not have true closures and a number of other modern Lisp features. I was curious to see if CMUCL could beat the compiled Lush code. CMUCL is a good high performance Common Lisp and it gives a lot of information when you compile code telling you where it could not optimize due to various things (usually inability to determine the type of variables). The equivalent Common Lisp code to the Lush code is: (defun harmonize (n) (declare (optimize (safety 0) (speed 3)) (type fixnum n)) (let ((z 0.0) (i 0)) (declare (type fixnum i) (type single-float z)) (loop while (< i n) do (incf i) (incf z (/ 1.0 i))) z)) Compiling this code in CMUCL and then running (harmonize 1000000) completed in 0.13 seconds. (harmonize 2000000) in 0.24 seconds. It definitely wins out in the speed, now if only it had some of the libraries Lush had. But I imagine it's easier to port those libraries across (since they are really just FFI to other libraries) to CMUCL than to get equivalent speed increases out of Lush and improve its old Lisp dialect. As a point of reference, Corman Lisp runs the same harmonize function above in 2.8 and 5.7 seconds for (harmonize 1000000) and (harmonize 2000000) respectively. 4:15:17 AM

Here's an interesting article on implementing coroutines in 'C' in a portable fashion. The method uses the same trick as "Duff's Device". With a few macros it makes the code look almost readable: int function(void) { static int i; crBegin; for (i = 0; i < 10; i++) crReturn(1, i); crFinish; } This is a function that returns the numbers from 1 through to 10 on successive calls. crReturn is commonly known as 'yield' in other systems I've used. What it does is return a value from the function but on the next call of the function execution proceeds at the statement immediately following crReturn. It's easy to work out what is happening when you expand the code: int function(void) { static int i, state = 0; switch (state) { case 0: /* start of function */ for (i = 0; i < 10; i++) { state = 1; /* so we will come back to "case 1" */ return i; case 1: /* resume control straight after the return */ } } } Notice the case statement nested within the for loop. That's the same trick that Duff's Device uses. The article goes on to include other examples of usage and why this style of programming is useful. It's a worthwhile read even if you don't plan to use the trick, as it gives you an understanding of what you can do with languages that have coroutines or generators built in. 3:51:47 AM