I've been looking for a nice implementation of LISP to run on my N800, too.

My preference would be something like XLISP so that it can be run in an interpretted mode. Someone would have to Hildonize the interface (start with XLISPWIN?).