We Have Lift-Off

Page 5 of this month's Michigan Business Report (a pretty badly formatted PDF) talks a little bit about i/net and what we're working on.

It's even mostly accurate.

NASA has awarded the Kalamazoo-based software firm a six-month, $70,000 contract to develop a conversational interface for the Complex Event Recognition Architecture (CERA) technology I/NET created under a previous contract. Created to manage life-support systems on space missions, CERA can recognize and analyze complex situations, either prompting operators to act or making corrections on its own. The new conversational interface, as I/NET President and CEO Stephen Markee describes it, uses voice commands to provide a "kinder, gentler" way to interact with the CERA system. "We like to say that our conversational interface allows users to talk with computers and equipment, not at them," he said. "Whereas older systems only recognize specific words and phrases, our software can monitor and analyze the context of an entire conversation, which makes it far more versatile and easier to use."

That's the sort of thing we're using lisp for.

That's Impossible!

Benjamin Young:

Sometimes when I am debugging a computer program I come across a situation where I think I understand the entire state of the computer, and there is no way that whatever bug is happening could actually happen. At these moments, I have to look around and worry: "Is this the moment when the universe loses its ordered behavior? Will the sun come up tomorrow? Are my friends popping in and out of existence this very moment? IS THIS WHERE IT ALL ENDS???" Then I think "oh, wait, that variable's not supposed to be zero," and go along under the laws of nature once more.

Norvig's Law

Norvig's Law (via emu)

"Any technology that surpasses 50% penetration will never double again (in any number of months)."

Heh.

On Startups

On April 15, Paul Graham is giving a talk on "How Startups Work" at Northeastern University. I'd love to go to this; if only it were at Northeastern Illinois University, which is only a thousand miles closer to me.

Weird, I didn't know that Paul Graham studied at RISD. It all makes sense now--You can sense he has a somewhat broader background than the typical computer scientist.

8 Bit Lisp in ROM

vsync found a lisp cartridge for the Acorn on ebay.

LISP is the language of artificial intelligence, an intriguing alternative to BASIC and faster executing in a number of ways. These items are complete with boxes as pictured. To use LISP it is necessary to find the book LISP PROGRAMMING ON THE ACORN ELECTRON. It was not supplied with the cartridge at the time. However, the LISP interpretation is the common '79 standard so if you have any book on LISP programming, that will suffice.

(ebay screenshot)

I did some searching but couldn't find lisp-on-a-cartridge for anything other than the Acorn.

more FFI

This excerpt from a post by Duane Rettig seems at least slighty relevant to standard FFI and automatic FFI generation:

For #3, I was almost ready to disagree with Thomas Bushnell because I believed that it is necessary to use C functionality to interface to C library functions. This is especially true for the need to parse .h files, and to get the correct definitions and interfaces based on particular #define constants. If you doubt this, just try to figure out, for example, HP's sigcontext structure, which has layer upon layer of C macrology to define a large number of incompatible structure and interface definitions.

However, I had to back off on any such disagreement, becuase it certainly is _possible_ to write any of these interface functions in lisp, using such facilities as our Cbind tool to pre-parse the header files and to thus present all pertinent information to the lisp-in-lisp code. However, I still am not inclined to do such a thing, because it would be specialized toward lisp bootstrap, and thus not useful for anything else. And why not use C at what it does best (parse C header files)? Besides, even our Cbind facility uses the gcc front-end to do the initial parsing, so in essence a non-lisp compiler part would still be used. Bottom line; it is more convenient to write our os-interface code in C, because it interfaces to C libraries. I suppose that we would remove such C interfaces if we were porting our lisp to a Lisp operatring system.

UFFI

Kevin Rosenberg's UFFI aims to be a universal foreign function interface for lisp that currently supports ACL, LispWorks and CMUCL, and should soon support Corman Lisp.

UFFI's design priorities:

• Code using UFFI must operate correctly on all supported implementations.
• Take advantage of implementation-specific optimizations.
• Provide a simple interface to developers using UFFI.

I love this project. The design looks well thought out, the level of activity is high, the documentation is good, and it is implementation/platform inclusive (even the often-forgotten MCL has been thought of).

Most importantly, I think UFFI can help make cclan-style repositories even cooler, by making it easier to write certain types of very useful libraries and utilities (I'm thinking of 3D graphics, speech recognition, maybe parsing XML) and make them relatively portable.

While I believe that a standard FFI would be useful, Erik Naggum thinks the idea is bogus, and what's really needed are tools to automate the process of generating FFI definitions for particular implementations. This is where I mention Tim Moore's cool cparse FFI definition generator. Hey, what if we took both UFFI and cparse and... no, never mind, that's just crazy talk.

OK, I admit it. I'm hoping UFFI and cparse will let me play with QuickDraw3D in lisp under windows and unix.

"Orbitz Reaches New Heights"

From the article "Orbitz Reaches New Heights" in New Architect magazine (formerly Web Techniques):

The high-level algorithms are almost entirely in Lisp, one of the oldest programming languages. You're excused for chuckling, or saying "Why Lisp?" Although the language can be inefficient if used without extreme caution, it has a reputation for compactness. One line of Lisp can replace 20 lines of C. ITA's programmers, who learned the language inside and out while at MIT, note that LISP is highly effective if you ditch the prefabricated data structures. "We're something of a poster child for LISP these days," says Wertheimer. "Lisp vendors love us."

The downside of using a sometimes-maligned language is that it's hard to find good Lisp programmers. Today, only half of ITA's coders are Lisp gurus. For its own Web site, ITA relies on server-side Java, partly because of the availability of capable Java programmers.

Actually, there is no excuse for chuckling.

Varying Mileage

Dan Barlow comments on his experiences using cmucl (well, sbcl) as a web server (including cliki):

For the record, the site that served you this page is running on the pretty similar SBCL (you wouldn't guess) using Araneida, and doesn't even use MP, instead hooking into the same event loop as SBCL uses for IO at the top-level. It does have Apache in front of the CL web server to act as a proxy, which tends to avoid most of the "slow/malicious client" problems.

CMUCL Crankypants

On the lispweb mailing list, Andrew Wolven asked "I was wondering how well the multithreading performs on x86 cmucl for application servers like imho and portable allegroserve. Is it good enough to use for a production web server?"

I've recommended at work that we should probably look for an alternative to cmucl for production Echo servers. It doesn't take very long spent trying to work around limitations or bugs before it would be more worthwhile to pay a lot of money for a commercial implementation that's stronger in the areas that are important in our application (multiprocessing, for one).

So this is the gist of my reply:

I consider cmucl to be just barely "production quality." The multiprocessing facility in particular is a weakness. Its cooperative threading is a big disadvantage, and I didn't find even that to be very stable. Plenty of times I found myself either with an unresponsive listener or in the low-level debugger, with no recourse but killing lisp.

As a web server, if you're not doing too much work per request, you might be OK. Unless you go to a lot of trouble requests are going to be serialized. This seems rather horrible to me, and is probably enough to knock cmucl out of contention for high traffic sites. And I think you'd have to take special care to keep a single messed up client (or malicious clients) from hanging your site.

It didn't work very well for our application to do much work other than being a web server, either; No http requests will be handled until the currently running thread blocks.

I'm expecting to be disagreed with, maybe I'll learn I am mistaken.

Bad News

Bad news in C:

Bus error

Bad news in Lisp:

*A2 gc_alloc_large failed, nbytes=280.

   Generation Boxed Unboxed LB   LUB    Alloc  Waste   Trig    WP  GCs Mem-age

          0: 57283   186     0     0 235067080 325944  7229904    0   1  0.0000

          1: 39320  6773     0     0 188259968 536960 17584304 18257   1  0.5524

          2:  3299   557     0     0 15745952 48224 17745952 3299   1  0.0000

          3:  6655  1112     0     0 31712872 100760  2000000 6654   0  0.5008

          4:  3329   560     0     0 15877040 52304 17877040 3326   1  0.0000

          5:  9982  1945    71     0 48991072 152736 34892128 9994  28  0.6714

          6:     0     0     0     0        0     0        0    0   0  0.0000

   Total bytes alloc=535653984

That's what happens when cmucl runs out of memory.

I learned two things about cmucl's memory management.

1. You can increase its memory with -dynamic-space-size=<megs> (but unfortunately I don't think there's any documentation of what the default is; I guess you have to read the C source).
2. Its garbage collector is conservative(!). Well, actually, it looks like it has a precise heap representation but treats the stack conservatively.

So either Echo has a memory leak or cmucl has a memory leak or it's just using more memory than I would have expected or the default dynamic space size is unexpectedly small.

Dead Ant Cam

I had an ant fetish for a while.

I wanted to make a movie that was a re-telling of the Faust story in an ant nest. I turned one scene into a Tivo essay (I decided at the last minute not to send it in, a decision I still regret. Everyone won.

Execution of a fire ant (Solenopsis invicta) queen. Workers immobilize an unwanted queen by pulling on her legs and antennae, then they gradually bite and sting her to death.

Last year I had an ant farm, and I set up an antcam--just a little QuickCam pointing at the farm, taking a snapshot every 60 seconds and ftping it to my web server. Unfortunately, all but two of the ants died within 24 hours. So it became dead antcam. For the next two months it updated the image of the dead ants every 60 seconds. I think that might have been an internet first of some kind.

Commercial Lisp Success (with Free Software)

Don Geddis' $250M lisp success story (Paul Graham and Robert Morris got about $50M, so they were obviously only 20% as successful) on cmucl-impl:

My company was a comparison shopping web site called Cadabra. We did all our development in Franz's Allegro CL. They were so excited, we wrote up a silly press blurb for them: http://www.franz.com/success/customer_apps/data_mining/cadabra.lhtml

In January 2000, Cadabra sold to GoTo.com (now Overture Services, NASDAQ:OVER) for $250M (in stock -- worth _much_ less over time!). As part of the acquisition, we converted the application from ACL to CMUCL in a month or so, to escape from Franz's severe licensing demands.

Sadly, about a year ago Overture shut down their comparison shopping division. So the software is no longer in use.

"Franz's severe licensing demands" sure sound familiar. It's the same reason we're trying to use cmucl at i/net.

More Other Links

lemonodor now offers instant access to the openmcl-devel, opensource@franz, and sbcl-devel mailing lists. And that's not all. My friend and i/net's CTO, Will, has two weblogs, willwhim and the digital car.

You could probably waste an entire day on the preceding links alone. But why take chances? We also give you Paul Snively, Jim Flanagan, Dan Moniz' tdw, and finally Dan Barlow's diary.

Ideas for Arc

Paul Graham has posted the list of features people are requesting for Arc, the lisp variant he is designing.

Whatever your feelings on Arc, you should read through the comments to see what some of the smartest people in computer science think are important, practical features, and where they think Lisp has gone wrong.

Here are a few excerpts that struck me for whatever reason, either because I strongly agree, I find them particularly intriguing, or they instantly evoke visions of comp.lang.lisp erupting into hellish flamewars:

David Moon: "S-expressions are a bad idea."

Peter Norvig: "car and cdr are warts; why not hd and tl?"

Olin Shivers: "If you provide regexps, then you should feel a moral obligation to also provide context-free grammars, i.e., a parser tool, as well."

Pinku Surana (an ex-Neodesicer, like me!): "Check out Todd Proebsting's TR on 'Programming Shorthands'. It's about 'pronouns' in PL syntax. http://www.research.microsoft.com/~toddpro/"

Jim Bullard (another ex-Neodesicer, if you can believe it): "One thing I especially like about Python are the primitives used to specifiy range."
[Added 4:55 pm, March 12]

Ken Anderson has some interesting statistics:

I put together these statistics from a common lisp application

27,935 Function and macros
6,328 Function or macros with keyword arguments

Distribution of number of arguments (no keyword case):

0=1254
1=12961
2=4063
3=1885
4=628
5=302
6=173
7=95
8=69
9=69
10=34
11=18
12=27
13>= 29

Distribution of keyword usage:

(&KEY)=2048
(&OPTIONAL)=1663
(&REST)=1176
(&BODY)=988
(&KEY &REST)=217
(&ALLOW-OTHER-KEYS &KEY)=60
(&REST &OPTIONAL)=51
(&KEY &OPTIONAL)=48
(&ALLOW-OTHER-KEYS &KEY &REST)=43
(&KEY &REST &OPTIONAL)=9
(&BODY &OPTIONAL)=6
(&REST &WHOLE)=6
(&BODY &WHOLE)=4
(&AUX)=4
(&ALLOW-OTHER-KEYS &REST &OPTIONAL)=2
(&OPTIONAL &WHOLE)=1
(&AUX &KEY)=1
(&WHOLE)=1

From this i'd conclude that most functions have 3 or less arguments and that keywords are used less than about 1/3 of the time.

&key seems to be used as much as &optional and &rest combined.

Statistics don't lie: &aux is evil.

Lisp DLLs in ACL

Yesterday a fellow programmer, Bob Lane, reminded me of a serious bug in ACL's ability to create Windows DLLs.

We have a natural language processor/task execution system that is written in Lisp. In order to make it easy to use from within other programs (e.g. our telematics simulator), I used ACL's facility for building Windows DLLs.

Creating a DLL around lisp is not too difficult. You really end up writing a tiny wrapper in C, which compiles to the actual DLL (for DPMA, there's about 500 lines of C that compiles to a 70K library, with all debugging info). The wrapper code makes a call that starts your lisp image running, and that's pretty much it.

Well, it's actually somewhat more complicated than that. Every lisp function that you want to be able to use from outside the DLL has to have a C wrapper.

For example, DPMA has its own task description language, which is basically a way to write special kinds of programs, which we call RAPs. There is an interpreter that runs, processing the RAPs associated with the active tasks. In the DPMA engine, there is a lisp function that runs one "step" of the interpreter. I wanted the DLL to export a method for calling that function. In the C wrapper, I wrote

int WINAPI DPMAInterpreter_Step(TDPMAInterpreterStatus *status)
{
  int success;
  dtrace(ENTER, "DPMAInterpreter_Step: &status=%d", status);
  if (!ldpma_interpreter_step)
    success = -1;
  else
    success = (*ldpma_interpreter_step)(status);
  dtrace(EXIT, "DPMAInterpreter_Step: success=%d, status=%d", success, *status);
  return success;
}

This provides an exported C function that calls the lisp function, a pointer to which is in the variable ldpma_interpreter_step.

I don't mind too much that I have to write a C wrapper around every lisp function. It's not a bad place to vet arguments from the C world and do translation of lisp return values.

Wart #1: Callbacks

However, the way that the ldpma_interpreter_step function pointer gets the right value in the first place does seem like a bit of a wart to me. It works like this:

1. You export an InitializeDPMA C function from your DLL, that users of the DLL have to call first thing.
2. InitializeDPMA starts up ACL and sends a string to the lisp image to be evaled. In my case, "(dpma-initialize)".
3. The dpma-initialize function has to make a foreign function call to pass an array of function pointers corresponding to the lisp functions you want to be able to call. It has to call a well-known function you export from the C wrapper.
4. The C function has to save away the pointers to lisp functions for use by the wrapper functions.

(flet ((rf (f) (ff:register-function f nil t)))
  (let* ((cb (list (rf #'DPMA-EXIT)
		   (rf #'DPMA-INTERPRETER-START)
		   (rf #'DPMA-INTERPRETER-STOP)
		   (rf #'DPMA-INTERPRETER-REGISTER-STATUS)
		   (rf #'DPMA-KNOWLEDGE-LOAD-FILE)
		   (rf #'DPMA-SHOW-REGISTER)
		   (rf #'DPMA-SHOW-GET-LEVEL)
		   (rf #'DPMA-SHOW-SET-LEVEL)
		   (rf #'DPMA-AGENDA-GET)
		   (rf #'DPMA-AGENDA-INSTALL-GOAL)
		   (rf #'DPMA-AGENDA-RESET)
		   (rf #'DPMA-ERROR-REGISTER)
		   (rf #'DPMA-WARNING-REGISTER)
		   (rf #'DPMA-PRIMITIVE-POST-INPUT-TEXT)
		   (rf #'DPMA-PRIMITIVE-REGISTER-TIME)
		   (rf #'DPMA-SKILL-SYSTEM-REGISTER)
		   (rf #'DPMA-SKILL-SYSTEM-POST-EVENT)
		   (rf #'DPMA-INTERPRETER-STEP)
		   (rf #'DPMA-KNOWLEDGE-RESET)
		   ))
	 (cb-array (make-array (length cb)
			       :element-type 'fixnum
			       :initial-contents cb)))
    (set_lisp_callbacks cb-array)))

The C code for receiving them looks like

/* Not part of the API; intended only to be used by Lisp */

void WINAPI set_lisp_callbacks(int *cb)
{
  ldpma_exit = (LDCB_EXIT) cb[0];
  ldpma_interpreter_start = (LDCB_INTERPRETER_START) cb[1];
  ldpma_interpreter_stop = (LDCB_INTERPRETER_STOP) cb[2];
  ldpma_interpreter_register_status = (LDCB_INTERPRETER_REGISTER_STATUS) cb[3];
  ldpma_knowledge_load_file = (LDCB_KNOWLEDGE_LOAD_FILE) cb[4];
  ldpma_show_register = (LDCB_SHOW_REGISTER) cb[5];
  ldpma_show_get_level = (LDCB_SHOW_GET_LEVEL) cb[6];
  ldpma_show_set_level = (LDCB_SHOW_SET_LEVEL) cb[7];
  ldpma_agenda_get = (LDCB_AGENDA_GET) cb[8];
  ldpma_agenda_install_goal = (LDCB_AGENDA_INSTALL_GOAL) cb[9];
  ldpma_agenda_reset = (LDCB_AGENDA_RESET) cb[10];
  ldpma_error_register = (LDCB_ERROR_REGISTER) cb[11];
  ldpma_warning_register = (LDCB_WARNING_REGISTER) cb[12];
  ldpma_primitive_post_input_text = (LDCB_PRIMITIVE_POST_INPUT_TEXT) cb[13];
  ldpma_primitive_register_time = (LDCB_PRIMITIVE_REGISTER_TIME) cb[14];
  ldpma_skill_system_register = (LDCB_SKILL_SYSTEM_REGISTER) cb[15];
  ldpma_skill_system_post_event = (LDCB_SKILL_SYSTEM_POST_EVENT) cb[16];
  ldpma_interpreter_step = (LDCB_INTERPRETER_STEP) cb[17];
  ldpma_knowledge_reset = (LDCB_KNOWLEDGE_RESET) cb[18];
}

where all the LDCB... things are typedefs for a pointer to a function with the appropriate arguments and return values.

Blech. You can see how this would be unwieldy if you had even a few dozen lisp functions you wanted to export from the DLL.

Wart #2: Callbacks

Yeah. Callbacks again, but this time instead of C-to-lisp, the problem is with lisp-to-C.

The DPMA C API allows people to register error handlers, which are called if something goes wrong during RAP interpretation, for example. The problem is that given a pointer to a C function, I don't see any way in ACL to directly call that function from lisp.

Any problem in computer science can be solved with another layer of indirection. -- David Wheeler

What I do is define and export functions from my C code that accept C function pointers and whatever arguments the functions expect, and call those from lisp.

void WINAPI hack_error(TDPMAErrorMethod m, const char *msg)
{
  dtrace(ENTER, "hack_error");
  (*m)(msg);
  dtrace(EXIT, "hack_error");
}

Blech again.

Finally, the Bug

I discovered that the DLL created by ACL doesn't clean up after itself properly. The TerminateLisp function that is supposed to shut down the lisp image doesn't work. According to Franz it is due to a design flaw that isn't easy to fix.

Possibly related to the problem with cleanup is a problem with re-initialization. The issue comes up when developing a Visual Basic application that makes use of the lisp DLL: The typical VB development process involves starting the VB IDE and working semi-interactively. Starting your VB app, pausing it, stopping it, editing it, and restarting. It's not entirely dissimilar from how development is done in lisp. Unfortunately, this doesn't work if your VB app uses a DLL produced by ACL.

Once you stop your lisp-dll-using VB application, you can't start it again. Your app will crash if you try (eventually). You have to completely exit the VB IDE, start it up again, and reload your project. It is exactly as annoying as if you had to exit lisp and reload your code every 5 minutes.

Franz has no solution. They say "Visual Basic is keeping the acli601.dll loaded in its memory between each run of your project and not bringing in a new one so that lisp can start approppriately. InitializeLisp is not designed to start lisp with the previous dll in Visual Basic's menmory."

They do suggest a workaround, however: instead of building a normal DLL, build a lisp OLE object. That's not necessarily a bad idea, it's just not what I want, and it doesn't assuage my annoyance at the fact that the normal DLLs are buggy.

amanset

American Analog Set makes music that my brain is sure it has heard before (like some of Brian Eno's old stuff). It's as if they discover these perfect dream pop/space rock/whatever melodies that have existed forever.

I held off on getting their newest album because I was afraid of being disappointed. Finally, I bought it. I wasn't. million young / american analog set

Wheels On Your Mama

I don't think there is any point in me mentioning Joel Spolsky's essays here as if everyone doesn't already know about them. I just wanted to quote this bit about your mama from his new piece on the importance of design:

My friend, you can put wheels on your mama but that doesn't make her a bus, and if you think you can refactor your wrongly-implemented file-copy function to make it preemptive rather than threaded as quickly as I could write that sentence, you're in deep denial.

February FTX3J13

The February issue of Dan Barlow's Free the X3J Thirteen! is available.

The most exciting news is that "A new vendor-neutral (i.e. not Debian-dependent) package format was proposed for cCLan..."

Feverish Evaluation

Steve Zellers: "When I'm sick, I have the weirdest dreams. Last night, I dreamt I was a lisp interpreter evaling (fact 10000). I kept running out of stack space and had to add more."

Condition Handling

Kent Pitman has made his paper "Condition Handling in the Lisp Language Family" available online.

The most important idea in it is that "condition handling is primarily a protocol matter." I'm coming to believe (after using a couple different sockets libraries) that an API that doesn't specify when and what conditions occur is probably an unusable API. Paul Snively says that the Pink (Pink! remember Pink?) mantra was "exceptions are part of the interface", and it is absolutely true, and too often forgotten (well, by me at least).

Java enforces exceptions-are-part-of-the-interface, and as usual, that's overkill. Libraries need to be written by thoughtful programmers; squelching compiler errors doesn't necessarily make one thoughtful.

Yadda Lambda: Lisp Magazine

Gene Michael Stover is soliciting articles for Yadda Lambda, a free online lisp "magazine". The first issue is scheduled to be published around April 1.

To get a sense of what the publication will be like, or if you're interested in contributing, take a look at the list of suggested topics (Michael's golden rule is "if after reading an article, a Lisp programmer thinks I'm glad I read that, it was interesting, then that article probably belongs in Yadda Lambda.")