24 Jan 2010

Update 2010-2-04: A lot of the information below is out of date. There is an update here: Wisp Screencasts.

This is a project I've been wanting to do for some time, and I finally got around to doing it. I spent the last few days implementing my own lisp interpreter in C. Today, after sinking in about 48 hours of work, I believe I completed enough of it to consider it in a working state, with a code base stable enough that other interested people could contribute. It was really exciting to see everything come together today.

You can make a clone of the Wisp repository with Git. Go ahead; don't be shy,

git clone http://git.nullprogram.com/wisp.git

To build it, all you need is a C99 compiler, make, yacc (i.e. Bison), and lex (i.e. Flex).

It doesn't use the readline library or one of it's clones to make a nice interaction command line, so it's a good idea to run it with rlwrap. That's what I've been doing. If you plan on writing Wisp code in Emacs, putting this in your .emacs will give you all the syntax niceties,

(add-to-list 'auto-mode-alist '(".wisp\\'" . lisp-mode))

You should also be able to run it as an inferior lisp and send code to it like a normal lisp. I haven't done this yet myself.

I think the name is apt, because it really is a wisp of a lisp. As of this writing, it weighs in at 1500 lines of code and is still very feature-light. I haven't actually read any material about writing lisp interpreters, so I've been winging it based on my experience with it. It's already taught me a lot of subtle things about lisp that I hadn't been aware of before.

Right know it's very simple. It doesn't yet support any syntax beyond parenthesis (no ' quoting). No closures. No garbage collection, as I'm still working out how I'm going to do that. Dynamically scoped, since that's a lot easier to do. And, like Scheme, it's a lisp-1, meaning functions and variables share a common namespace. I hope to expand it to include some features from other lisps like Arc (particularly the anonymous function syntactical sugar), Common Lisp, and Scheme.

However, it does have already anonymous functions, which many popular languages still don't have. :-) It's far enough along to let you define crazy stuff like this,

(defun example (n)
  (if (<= n 0)
      (lambda (x) (* x 10))
    (lambda (x) (* x 2.0))))

Which you can call, interactively in this case, like so,

wisp> ((example  1) 20)
40.000000
wisp> ((example -1) 20)
200

Because there's no garbage collection yet, it leaks memory like a sieve. For garbage collection, I think I'll do a mark-and-sweep, marking objects based on their reachability from the symbol table. That still leaves some corner cases -- such as worrying about objects in limbo in the evaluator -- that I'm not sure about. I need to be careful not to free objects still in use. Still working that one out.

It has the multiplication, addition, subtraction, and division implemented, as well as the greater-than and less-than operators. Lisp macros are implemented. A number of special forms are defined, like let, if, set, defun, defmacro, car, cdr, not, progn, lambda, and while. All of the predicates are implemented. It has a C interface, which is how all the above got defined. I already have some functions and macros defined in terms of Wisp code, too. Most of the needed functions at this point are trivial to add, though a bit tedious, so I'm mostly trying to focus on the core parts of the interpreter right now.

It's amazing how much the internal code looks like lisp written in a C dialect. I have CAR and CDR macros defined, which get used all over the place, and code frequently uses them to walk lists like lisp code would.

The core struct that everything works with the the object struct. It's defined as such,

typedef struct object
{
  type_t type;
  void *val;
} object_t;

The type_t field comes from this enumeration,

typedef enum types
  { INT, FLOAT, STRING, SYMBOL, CONS, CFUNC, SPECIAL } type_t;

The type indicates what type of data the void pointer points to, making it sort-of polymorphic. Note the CONS type, the cons cell, used to create lists,

typedef struct cons
{
  object_t *car;
  object_t *cdr;
} cons_t;

There's the familiar car and cdr pointers. There are a bunch of helper functions to manipulate and build these. For example, c_cons() creates a cons cell,

object_t *c_cons (object_t * car, object_t * cdr);

Look familiar? Yup, that's the lisp cons function. Since the nil symbol is available in C code as NIL you can chain these together in C to make a list,

object_t *lst = c_cons (c_int(10), c_cons (c_str ("hello"), NIL));

Which puts together the simple list,

(10 "hello")

Since that's so cumbersome to write out, there's a parser that can read nice lisp code and use all those same functions to make the lists. Hence, the lisp reader.

If you want to help, it's pretty easy to add more CFUNCs, C functions that are exposed to Wisp lisp code. Right now, I'd like to expose the whole C math.h library, provide a nice I/O interface, and expose a bunch of string functions. The TODO file in the repository contains more things to be done.

Wisp will probably be getting it's own "project page" here at some point in the future. When it does, I'll update this post to point to it.

Oh, and I decided to make this available under a 2-clause BSD license, so someone could easily plug it into another program as an extension language (once Wisp has matured first, of course). That would be cool.

15 Jan 2010

Common Lisp is possibly the most advanced programming language. Think of pretty much any programming language feature and Common Lisp probably has it. Since lisp is the programmable programming language, when someone invents a new language feature it can probably be added to Common Lisp without even touching the language core.

However, if you're interested in digging into Common Lisp to try it out, you may find yourself quickly running into walls just getting started. It's a lot different than other programming environments you may be used to. The Common Lisp tutorials generally skip this step, assuming the user has an environment, or leaving that setup for the "vendor" to handle. So, here's a guide to setting up a great Common Lisp environment with Emacs and SLIME. It should work with any Common Lisp implementation and any operating system that can run Emacs (i.e. most of them). Even a much less capable one like Windows.

First, you need to pick a Common Lisp implementation and install it. Ideally, it should end up in your PATH. Like C, the language is defined solely by its standardized specification, rather than some canonical implementation. Steel Bank Common Lisp (SBCL) is currently the highest performing implementation, it's Free Software, and it runs on a wide variety of platforms, so take a look at that one if you're not sure.

Next, install Emacs. We're using Emacs not just because it's the best text editor ever created. :-D It's because that's what SLIME is written for, and Emacs is a lisp-aware editor. Really, Emacs is a lisp interpreter that happens to be geared towards text-editing. It's accused of breaking the rules of unix by being a single, monolithic program, but it's really a whole bunch of small lisp programs. You can even have a lisp REPL in Emacs (ielm), similar to what we will have once we're done here. It's plays very well with Common Lisp.

If you're unfamiliar with Emacs, you should stop here and familiarize yourself with it a bit. Really, you could spend a decade learning Emacs and still have more to learn. The tutorial should be good enough for now. Fire up Emacs and run the tutorial by pressing control+h then t. In Emacs notation, that's C-h t. C-h is the help/documentation prefix, which can be used to look up variables/symbols (v), functions (f), key bindings (k), info manuals (i), the current mode (m), and apropos (searching) (a). In the info manuals, you should be able to find the full Emacs manual, Elisp reference, and Elisp tutorial, since they are generally installed alongside Emacs these days. Nearly anything you might need to know can be found inside the included documentation.

Next, install SLIME. I'll be a bit more specific for this one. Make a .emacs.d directory in your home directory (whatever your HOME environmental variable is set to). This is a common place to put user-installed Emacs extensions. You will be putting your slime directory in here. There are two basic ways to obtain SLIME, as indicated right on their main page. You can do a CVS checkout of the SLIME repository, which allows you to follow it and run the latest version. Or you can grab a snapshot of the repository, which is provided, and dump it in there. Since I like you so much, I'll give you a third option. Here's a Git repository, maintained by someone very kind, that follows SLIME's CVS repository,

git clone git://git.boinkor.net/slime.git

Ultimately, you should have a directory ~/.emacs.d/slime/ that contains a bunch of SLIME source files directly inside.

Now, we tell Emacs where SLIME is and how to use it. Make a .emacs file in your home directory, if you haven't already, and put this in it,

(add-to-list 'load-path "~/.emacs.d/slime/")
(require 'slime)
(slime-setup '(slime-repl))

Once it's saved, either restart Emacs, or simply evaluate those lines by putting the cursor after each them in turn and typing C-x C-e. If you did everything right so far, you shouldn't have any errors. (If you did, go back up and see what you did wrong.) If your Common Lisp installation didn't end up in your PATH as "lisp" (not uncommon) for some reason, you may need to tell Emacs where it is. For example, I can point directly to my SBCL installation with this line,

(setq inferior-lisp-program "/usr/bin/sbcl")

If everything is set up right, fire up SLIME with "M-x slime". It should compile the back-end, called swank, and run a Common Lisp REPL as an inferior process to Emacs. You should end up with a nice prompt like this,

CL-USER>

At this line, you can start evaluating lisp expressions as you please. But this isn't where the true power of SLIME comes in yet. I'll give you an example: make a new file with a .lisp extension and open it. Throw some lisp in there,

(defun adder (x)
  (lambda (y) (+ x y)))

Type C-x C-k and it will send the current buffer over to be compiled and loaded. This code here uses a closure, so you know you aren't accidentally using Emacs lisp, as it doesn't have closures. At the REPL you can call it,

CL-USER> (funcall (adder 5) 6)

Which will print the return value, 11. That's all there is to it. You write code in the buffer, then with a simple keystroke send it to the Common Lisp system to be evaluated and loaded. Because the SLIME key bindings eclipse the Emacs lisp key bindings, you can type this same line in the lisp source buffer place the cursor at the end, and type C-x C-e, which will send it out to Common Lisp to be evaluated. Look at the mode help (C-h m) to see all the key bindings made available.

This is a great programming environment that makes Common Lisp all the more fun to use. You run a single, continuous instance if your program growing it gradually. (This is exactly how I built my Emacs web server with elisp.) You can test your code as soon as soon as it's written.

The setup can get even more advanced. The Common Lisp REPL need not be running on the same computer. It can be running on another computer, as long as SLIME is able to connect to it over the network. Several developers could even share a single Common Lisp process running on a common machine. Lots of possibilities.

If you don't have a Common Lisp book yet, there's Practical Common Lisp, which you can read at no cost online or download for reading offline. It's based on an Emacs and SLIME setup, so you'll be right on track.