There may, indeed, be other applications of the system than its use as a logic.

— Alonzo Church, A Set of Postulates for the Foundation of Logic

2018-08-27 Eggs updated to CHICKEN 5

I’ve recently ported most of my Scheme libraries to CHICKEN 5.

In particular, the following libraries are now available: begin-syntax, fuse, git, isaac, magic, module-declarations, pledge, r7rs, schematic, sysexits, type-extensions, and with-current-directory. I’ve also renamed my getopt library to optimism and released it to the egg servers.

I won’t be porting the following eggs, which are obsolete and unsupported: bitcoin, glfw, and yahoo-finance.

I’ll probably also port combinator-birds for fun, but it won’t be released to the egg servers.

2018-02-15 Improved Scheme language support in Vim

The next release of Vim, version 8.1, will include the runtime files from my vim-scheme plugin, and I’ll be maintaining Vim’s built-in Scheme support from now on.

Development will still happen in the linked repository, so you can continue to use the plugin if you want to stay as up-to-date as possible.

If you run into any problems editing Scheme with stock Vim, however, please don’t hesitate to contact me. Patches are also very welcome. In particular, I’d like to extend the keyword highlighting to support dialects other than CHICKEN (which is already pretty well-covered).

2016-05-30 Command line keyword arguments

Lately I’ve been using the following trick as a quick and dirty way to handle command line arguments:

(define (command-line-data)
  (map (lambda (s) (call-with-input-string s read))
       (command-line-arguments)))

(define (main #!key (foo 1) (bar 'abc) (baz '()))
  (printf "~s ~s ~s~n" foo bar baz))

(apply main (command-line-data))

The command-line-data procedure just converts a program’s arguments to a list of Scheme data, which isn’t too interesting by itself. The real trick is to write your main procedure so that it accepts whatever keyword arguments you want your program to accept, then invoke your program as though you were calling it from Scheme code:

$ csc -R ports program.scm
$ ./program foo: -1 bar: xyz baz: '(1 2 3)'
-1 xyz (1 2 3)

I still haven’t decided whether this is terribly clever or just plain terrible.

2016-05-10 Packaging self-contained CHICKEN programs

This is a short walk through the process of packaging a dynamically-linked CHICKEN 4.x application for binary deployment.

Note that this does not apply to CHICKEN 5.x! Newer versions of CHICKEN support static compilation, which is the preferred option.

CHICKEN 4.x on the other hand doesn’t prescribe a process for this, and there are lots of ways to achieve similar results, but this is one approach that has worked well for me in the past.

But First: The Easy Option

Before I describe how to manually bundle an application, I should mention the automatic method that’s almost guaranteed to work for normal programs:

$ csc -deploy <program>.scm
$ chicken-install -init <program>
$ chicken-install -deploy -prefix <program> [<egg> ...]

That’s it. These three commands:

  1. Compile a program and place it, along with the CHICKEN runtime, into a directory named after the input file.
  2. Copy all of CHICKEN’s standard libraries into the directory.
  3. Install eggs, including their dependencies, into the directory.

The reason I’m going to explain an alternative, albeit more complicated, approach to packaging is that this simple method can potentially result in very large application bundles. This is because it bundles every file from the installed eggs that your program could possibly use at runtime, regardless of whether they’re truly needed. This can be wasteful of disk space, but if package size isn’t an issue I suggest you take the easy route.

Bundling the Runtime

If you’re still reading, you’ve picked the hard option. Good choice. As an example program we’ll be packaging a CHIP-8 emulator I wrote in the spirit, though not the deed, of itch.io’s Spring 2016 Lisp Game Jam. To start with, clone the project and fetch its dependencies:

$ git clone -b chicken-4.x https://git.foldling.org/chick-8.git
$ cd chick-8
$ chicken-install -s -x begin-syntax ncurses r7rs

This will download and install the two eggs this program uses into CHICKEN’s extension repository. You can verify that they’ve been installed with chicken-status, and you can see what files they’ve included with chicken-status -f begin-syntax ncurses r7rs.

The commands to actually build the project look like this:

$ csc -X chick-8-syntax -R ncurses chick-8-curses.scm -c
$ csc -X chick-8-syntax -R r7rs -X r7rs -uses chick-8-curses chick-8.scm chick-8-curses.o

Don’t worry too much about the specifics here, just know that these two commands compile the program, and the second is the one that actually produces an executable. If you run the resulting file, it should print a usage message:

$ ./chick-8
usage: chick-8 [options ...] <file>
[... more output ...]

We now have a binary that works fine locally, but requires that the host system have CHICKEN installed. If you were to copy it onto another machine with the same architecture but without a CHICKEN runtime, it would fail with an error like the following:

$ ./chick-8
./chick-8: error while loading shared libraries: libchicken.so.8: cannot open shared object file: No such file or directory

Luckily, the “CHICKEN runtime” is just a single shared library and, as with the easy option, we can use the compiler’s “-deploy” flag to automatically bundle it with our program in a directory:

$ rm chick-8
$ csc -deploy -X chick-8-syntax -R r7rs -X r7rs -uses chick-8-curses chick-8.scm chick-8-curses.o
$ ls chick-8
chick-8
libchicken.so.8
$ ldd chick-8/chick-8
    linux-vdso.so.1 (0x00007ffc783e4000)
    libchicken.so.8 => /home/evhan/chick-8/chick-8/libchicken.so.8 (0x00007f6b8f402000)
    libm.so.6 => /lib/x86_64-linux-gnu/libm.so.6 (0x00007f6b8f0de000)
    libdl.so.2 => /lib/x86_64-linux-gnu/libdl.so.2 (0x00007f6b8eed9000)
    libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007f6b8eb35000)
    /lib64/ld-linux-x86-64.so.2 (0x000055f8feeca000)

There’s lots more information about this feature in the CHICKEN manual.

Bundling Eggs

At this point if you run the resulting program you’ll hit an error:

$ chick-8/chick-8

Error: (require) cannot load extension: ncurses

We’ve bundled the CHICKEN runtime, but we’re still missing the program’s egg dependencies. Luckily, eggs are mostly just shared libraries that can be copied into our application directory just like “libchicken.so”. The tricky part is usually figuring out exactly what files to copy, but the CHICKEN compiler has a (slightly obscure) option that can help with that.

Returning to our csc(1) invocations, if we add “-debug M” to both, we’ll see a list of “static” and “dynamic” library requirements for each file. Don’t worry about the static requirements – those are handled at compile time – but do take note of the dynamic ones:

$ csc -X chick-8-syntax -R ncurses chick-8-curses.scm -c -debug M
; requirements:
((static chicken-syntax eval library srfi-4 srfi-18)
 (dynamic ncurses))
$ csc -X chick-8-syntax -R r7rs -X r7rs -uses chick-8-curses chick-8.scm chick-8-curses.o -deploy -debug M
; requirements:
((static posix chick-8-curses library eval chicken-syntax ports srfi-18)
 (dynamic numbers scheme.base r7rs))

From this we can tell that we need to copy at least1 the “ncurses”, “numbers”, “scheme.base”, and “r7rs” libraries from the extension repository into our program directory. We could do this manually for each object:

$ cp "$(chicken-install -repository)/r7rs.so" chick-8
[... and so on ...]

But it’s easier to just use chicken-status(1) to list the files in the repository and filter for the ones we need:

$ chicken-status -f | \
   grep -E '(ncurses|numbers|r7rs|scheme.base).so' | \
   xargs -I % cp % chick-8
$ ls chick-8
chick-8
libchicken.so.8
ncurses.so
numbers.so
r7rs.so
scheme.base.so
$ chick-8/chick-8
usage: chick-8 [options ...] <file>
[... more output ...]

With that, we have a freely-relocatable application bundle that that requires nothing of its host but a working C library2.

Packaging the Result

With this self-contained version of our program, we’re not too far from a package in a format such as deb(5) or rpm(8).

Most OS-specific package formats boil down to a handful of archive files, usually compressed, containing an application’s files and a bunch of metadata. Learning the vagaries of any one of these formats is quite a task, let alone trying to support many of them at once. Thankfully, there are tools that can help.

One such tool that I like is fpm. That link has the details, but for our purposes it’s enough to know that we can hand fpm a directory and it will give us a package in return.

Let’s build that directory. We’ll call it “package”, copy our bundled files inside, and link to the binary itself from /usr/bin:

$ mkdir -p package/usr/bin package/usr/libexec
$ cp -fR chick-8 package/usr/libexec
$ ln -fs /usr/libexec/chick-8/chick-8 package/usr/bin/chick-8

Now we just pass our “package” directory off to fpm. In this example I’m building a Debian package, but you can control the output format with the -t argument:

$ gem install fpm # if necessary
$ fpm -s dir -t deb -a native -C package \
      --name chick-8 \
      --version 0.0.1 \
      --license BSD \
      --description 'CHIP-8 emulator' \
      --depends "libc6 (>= 2.3)" \
      --depends "libncurses5 (>= 5.0)" .
Created package {:path=>"chick-8_0.0.1_amd64.deb"}
$ dpkg --info chick-8_0.0.1_amd64.deb
 new debian package, version 2.0.
 size 1760812 bytes: control archive=619 bytes.
     291 bytes,    12 lines      control
     498 bytes,     7 lines      md5sums
 Package: chick-8
 Version: 0.0.1
 License: BSD
 Vendor: evhan@capsaicin
 Architecture: amd64
 Maintainer: <evhan@capsaicin>
 Installed-Size: 5450
 Depends: libc6 (>= 2.3), libncurses5 (>= 5.0)
 Section: default
 Priority: extra
 Homepage: http://example.com/no-uri-given
 Description: CHIP-8 interpreter
$ dpkg --contents chick-8_0.0.1_amd64.deb
drwxr-xr-x 0/0               0 2016-05-14 14:32 ./
drwxr-xr-x 0/0               0 2016-05-14 14:32 ./usr/
drwxr-xr-x 0/0               0 2016-05-14 14:32 ./usr/share/
drwxr-xr-x 0/0               0 2016-05-14 14:32 ./usr/share/doc/
drwxr-xr-x 0/0               0 2016-05-14 14:32 ./usr/share/doc/chick-8/
-rw-r--r-- 0/0             138 2016-05-14 14:32 ./usr/share/doc/chick-8/changelog.gz
drwxr-xr-x 0/0               0 2016-05-14 14:32 ./usr/
drwxr-xr-x 0/0               0 2016-05-14 14:32 ./usr/bin/
lrwxrwxrwx 0/0               0 2016-05-14 14:32 ./usr/bin/chick-8 -> /usr/libexec/chick-8/chick-8
drwxr-xr-x 0/0               0 2016-05-14 14:32 ./usr/libexec/
drwxr-xr-x 0/0               0 2016-05-14 14:32 ./usr/libexec/chick-8/
-rwxr-xr-x 0/0         4583656 2016-05-14 14:32 ./usr/libexec/chick-8/libchicken.so.8
-rwxr-xr-x 0/0          173936 2016-05-14 14:32 ./usr/libexec/chick-8/ncurses.so
-rwxr-xr-x 0/0          150904 2016-05-14 14:32 ./usr/libexec/chick-8/scheme.base.so
-rwxr-xr-x 0/0           21640 2016-05-14 14:32 ./usr/libexec/chick-8/r7rs.so
-rwxr-xr-x 0/0          188096 2016-05-14 14:32 ./usr/libexec/chick-8/chick-8
-rwxr-xr-x 0/0          463536 2016-05-14 14:32 ./usr/libexec/chick-8/numbers.so

As you can see, fpm has added a changelog and filled in some default metadata for us. You’ll typically want to tweak this metadata to reflect reality, which can be done with the program’s many command-line flags (see fpm --help).

While a package built this way is totally unsuitable for inclusion in a distro’s official repositories – I’ve no idea how many RPM packaging guidelines something like this breaks, for example, but I’m pretty sure it’s not none – it’s a fine way to distribute packages within your own infrastructure, or to end users who just want an easy way to install your software.


  1. One major problem that this article totally glosses over is that of transitive dependencies: if an egg your program uses depends on another library at runtime, you’ll need to copy that one too.↩︎

  2. That’s a lie, this example also requires a working ncurses library.↩︎

2015-01-27 snow2 repository

I’ve created a snow2 repository containing some of my pure-R7RS Scheme libraries. I hope to include the rest shortly.

It’s available here, and ought to be compatible with sethalves’ snow2-client and ashinn’s snow-chibi programs.

2013-07-16 Compiling statically-linked CHICKEN Scheme programs with extensions

While static compilation with extensions isn’t officially supported by the CHICKEN 4.x toolchain (chicken-install(1) et al.), it’s usually possible. However, doing so means compiling the extension and all of its dependencies yourself.

A simple example of this follows. The general strategy is to:

  1. Fetch each extension’s source.
  2. Compile each extension into units and import files.
  3. Compile your program in the presence of the import files.
  4. Link your program with the units.

All of the information here is available in more detail in the CHICKEN manual – I’ve just extracted the relevant parts and added a narrative.

Also, note that this post only applies to CHICKEN 4.x. In CHICKEN 5.0 static linking is handled automatically when you pass the “-static” flag to csc(1) and the C compiler, so none of the following contortions are required.


Our goal is to produce a statically-linked program that uses the uri-generic extension, which itself uses the matchable and defstruct extensions.

We’ll start with matchable. Fetch its source with chicken-install -retrieve.

$ chicken-install -retrieve matchable > /dev/null
$ ls matchable
matchable.meta
matchable.scm
matchable.setup
matchable-test.scm
match-simple.scm

Each extension includes several files we’re not interested in1, and then one – if we’re lucky – primary source file. For this extension, that’s matchable.scm.

To use this file statically, we compile it to an ELF object as a “unit”, then link that object into our final program.

$ cat program.scm; echo
(use matchable)
(match '(1 . 2)
  ((x . y)
   (display "Hooray!")
   (newline)))

$ csc -unit matchable -emit-import-library matchable -c matchable/matchable.scm -o matchable.o
$ ls matchable.*
matchable.import.scm
matchable.o
$ csc -uses matchable -c program.scm -o program.o
$ csc -static program.o matchable.o -o program
$ file program
program: ELF 64-bit LSB  executable, x86-64, version 1 (GNU/Linux), statically linked, for GNU/Linux 2.6.32, BuildID[sha1]=7678fccb131e4f92a0ef199f985b110079df7dbf, not stripped
$ ./program
Hooray!

So far, little has changed from the manual’s example of compiling multiple files. The important differences are:

  1. The addition of the -unit and -uses flags.
  2. The addition of the -emit-import-library flag.

The -unit and -uses flags enforce the compilation model described in the manual as CHICKEN’s basic mode of operation, despite the fact that neither matchable.scm nor program.scm declare any units as described2.

The -emit-import-library flag causes one additional file, matchable.import.scm, to be produced when compiling matchable.scm. This file contains compile-time information about the matchable module that’s used by csc when it’s imported into another program3.

Now, do the same for defstruct.

$ cat program.scm; echo
(use matchable defstruct)
(defstruct point x y)
(match (make-point x: 1 y: 2)
  (($ point 1 2)
   (display "Yippee!")
   (newline)))

$ chicken-install -r defstruct > /dev/null
$ csc -unit defstruct -cJ defstruct/defstruct.scm -o defstruct.o
$ csc -uses matchable,defstruct -c program.scm -o program.o
$ csc -static program.o defstruct.o matchable.o -o program
$ file program
program: ELF 64-bit LSB  executable, x86-64, version 1 (GNU/Linux), statically linked, for GNU/Linux 2.6.32, BuildID[sha1]=4cd22ac0bd74ba3721fbfb6c4dc8dc2eb5e4a170, not stripped
$ ./program
Yippee!

The binary now includes both matchable and defstruct4.

You can see where this is going. For each extension we use, and for each extension any of those extensions use (and so on, recursively – this is Scheme, after all), build an object with -unit and declare it as a dependency of every file that uses it with -uses.

One last time, with uri-generic (remember, that’s why we started down this rabbit hole in the first place). Here, uri-generic uses matchable and defstruct, while our program uses only uri-generic.

$ cat program.scm; echo
(use uri-generic)
(write (uri-path (uri-reference "http://example.com/super/happy/fun/time")))
(newline)

$ chicken-install -r uri-generic > /dev/null
$ csc -unit uri-generic -uses matchable,defstruct -cJ uri-generic/uri-generic.scm -o uri-generic.o
$ csc -uses uri-generic -c program.scm -o program.o
$ csc -static program.o uri-generic.o matchable.o defstruct.o -o program
$ ./program
(/ "super" "happy" "fun" "time")

We now have a static binary containing all of the required extensions.

Note that, when it comes time to link our program, an object for every extension that’s used must be included in the resulting binary. This is tedious, but because they’re standard ELF objects, they can be bundled into archives, making them easier to manage in bulk.

$ ar rc uri-generic.a uri-generic.o matchable.o defstruct.o
$ rm *.o
$ csc -uses uri-generic -static program.scm uri-generic.a
$ ./program
(/ "super" "happy" "fun" "time")

There you have it. It’s a bit of work, but the same can be done for most extensions, and the ability to produce a self-contained program that makes use of the many eggs in CHICKEN’s coop is nice when needed.


  1. The setup and meta files in particular are used by CHICKEN’s package manager.↩︎

  2. In fact, the -unit and -uses flags are equivalent to inserting those declarations manually. Again from the manual:

    -unit NAME
        Compile this file as a library unit.
        Equivalent to -prelude "(declare (unit NAME))"
    -uses NAME
        Use definitions from the library unit NAME.
        This is equivalent to -prelude "(declare (uses NAME))".
    ↩︎
  3. Indeed, because CHICKEN’s module system is entirely syntactic, this file can be discarded once our program has been compiled. Import libraries are described in more detail here.↩︎

  4. A closer look at matchable and defstruct will show that they’re both syntax-only extensions, so it’s technically unnecessary to compile them into objects at all. Because macros are included in a module’s import library, it’s enough to produce matchable.import.scm and defstruct.import.scm and have those files available (i.e. present in the current directory) when compiling program.scm. This makes them bad examples in particular, but this article gives a general approach that will work with other extensions, too.↩︎

2013-01-18 Editing Scheme with Vim

For other kooks like me who refuse to use Emacs.

2018-02-15 Update

Much of the following information is out of date as of Vim 8.1, which incorporates my vim-scheme plugin and thus includes many of the changes described here without any extra configuration.

Indentation

Vim’s built-in Lisp indentation (“set lisp”) is hardcoded to shift inner forms by two spaces. I much prefer the indentation style used by the various emacsen, where identifiers not in lispwords are vertically aligned; this patch against Vim 7.3 emulates this style.

Alternatively, you can use my schematic-format utility as a source formatter. To configure it as Vim’s = operator for Scheme files, use the following command:

au FileType scheme setl equalprg=schematic-format

Lispwords

If you choose not to use an 'equalprg', getting lispwords right can ease a lot of manual-indentation pain. The most important change to make is…

au FileType scheme setl lispwords-=if

… Which vertically aligns the arms of if expressions.

Syntax

Vim colors parentheses as Delimiters by default, which is too bright for my taste in most colorschemes. Additionally, I like to have a visual indication of which parentheses are parts of quoted forms, as opposed to normal code. This patch colors “normal” parentheses as Comments (which are light grey in my colorscheme), while parentheses in quote and quasiquote forms remain colored as Delimiters (red, with inner unquotes returning parentheses to the lighter Comment color).

I also maintain reasonably complete syntax files for R7RS Scheme and CHICKEN’s extensions to the language. To use them, either install my vim-scheme plugin with your plugin manager of choice or place the following files in the corresponding directories under ~/.vim/:

REPL

I’ve written about simple REPL integration here. I still use a slight variation on that approach.

Plugins

Surround

If you use vim-surround, the following line adds a binding to the s key that surrounds forms in a function application, so that, for example, yssscons wraps the current line in (cons ...).

let g:surround_115 = "(\1function: \1 \r)"

Smart Input

lexima is the best autoclose plugin I’ve found so far. It’s based on the solid vim-smartinput, but provides the added benefit of dot-repeatable insertions.

It also works well for Scheme, with minor customization. The following lines in ~/.vimrc prevent it from autoclosing quote and quasiquote characters:

call lexima#add_rule({ 'char': "'",  'input': "'", 'filetype': ['lisp', 'scheme'] })
call lexima#add_rule({ 'char': "`",  'input': "`", 'filetype': ['lisp', 'scheme'] })

CHICKEN

Documentation

Setting keywordprg gives you access to chicken-doc’s documentation for a given identifier when K is pressed over it.

setl keywordprg=chicken-doc

Completion

Vim

The following script dumps function names from chicken-doc into files named by node under ~/.vim/completion/scheme.

#!/bin/sh -e

dir="$HOME/.vim/completion/scheme"

first() { cut -d' ' -f1; }

mkdir -p "$dir"

for n in $(chicken-doc -c chicken | first)
do
  chicken-doc -c chicken "$n" | first | tee "$dir/chicken-$n"
done

for n in $(chicken-doc -c | first)
do
  [ "$n" = "chicken" ] || chicken-doc -c "$n" | first | tee "$dir/$n"
done

These files can be sourced to add completion for CHICKEN identifiers by adding the following to ~/.vim/ftplugin/scheme.vim:

setl complete+=d,k~/.vim/completion/scheme/**

Obviously, the same could be done for any other language, given a way to generate its wordfile(s).

csi

The same wordfiles can be used for tab completion in csi with rlwrap.

cat ~/.vim/completion/scheme/* > ~/.csiwords

rlwrap -f "$HOME/.csiwords" csi

2012-03-17 Heroku buildpack for CHICKEN Scheme

Last week I put together a Buildpack for deploying CHICKEN Scheme apps on Heroku’s Cedar stack.

It comes with CHICKEN 4.7.0 and uses the egg packaging infrastructure to manage dependencies.

The code is available at Github; instructions and examples can be found in the README.

2011-11-15 On Cons and Icons

When discussing the merits of Lisp, one of the first things people tend to mention is macros. And it’s true, macros are a powerful feature, so it’s easy to stop there and leave happy. However, what’s really important about Lisp isn’t its macro expansion phase – many other languages provide something similar – but its simplicity and consistency. The saying is that Lisp’s code is data and its data is code1; a powerful macro system is a direct consequence of that coequality and just one of many examples of the power it affords. It’s telling that John McCarthy’s first question, when asked about potential similarities between Ruby and Lisp, wasn’t “does Ruby have macros?” or even “does Ruby have first-class functions?”, but rather “does Ruby use list structures as data?”, referring to the double-duty performed by lists in his list processing language.

Consider the following, from Darius Bacon’s A Hacker’s Introduction to Partial Evaluation.

(define (emit-square x) `(* ,x ,x))

(define (emit-power x n)
  (cond ((= n 0) 1)
        ((= n 1) x)
        ((odd? n) `(* ,x ,(emit-power x (- n 1))))
        (else (emit-square (emit-power x (/ n 2))))))

; (emit-power 'x 5) => (* x (* (* x x) (* x x)))

What we have here isn’t just a macro but a compiler, one that generates exponentiation expressions. And – because Lisp’s fundamental compound data type is precisely that of its syntax tree – it’s turtles Lisp all the way down. If “it is better to have 100 functions operate on one data structure than 10 functions on 10 data structures” and you’re going to design around just one, cons cells are a good choice.

While this technique of compilation by emitting a new syntax tree isn’t groundbreaking (the original C++ compiler emitted C, for example), the ease with which it can be done might be2. “Languages differ not so much in what they make possible, but in what they make easy”; Lisp makes self-reference easy, and because the referents, lists and symbols, are such versatile objects, it’s possible to encode a wide variety of ideas in a simple, common tongue.

A wonderful example of such an encoding is given in Shriram Krishnamurthi’s Automata via Macros, where he uses lists to describe a machine accepting the language c[ad]*r and a program to run it:

(define machine
  '((init (c more))
    (more (a more)
          (d more)
          (r end))
    (end)))

(define (run machine init-state stream)
  (define (walker state stream)
    (cond
      ((null? stream) #t)
      (else
       (let ((in (car stream))
             (transitions (cdr (assv state machine))))
         (let ((new-state (assv in transitions)))
           (if new-state
               (walker (first (cdr new-state)) (cdr stream))
               #f))))))
  (walker init-state stream))

; (run machine 'init '(c a d a d d r)) => #t
; (run machine 'init '(c a d a d d r r)) => #f

With Lisp one gets a flexible DSL language entirely for free, all at runtime and no macros required. Here, it’s a language for describing state machines, but similar techniques have been used to great effect for everything from defining regular expressions to building XML to querying SQL databases. Even when creating sublanguages, strong axioms remove the need for string-munging and ad-hoc parsers: one can simply (write (eval (read))).

It’s interesting to note that Lisp’s shared representation of code and data is somewhat of an historical accident. As originally conceived, the language would make use of S-expressions internally, but manually-prepared programs would instead use a notation similar to that of FORTRAN (referred to by McCarthy as “M-expressions”, for “meta-language”). Translation between the two grammars was planned but never implemented, however, as programmers took a liking to the simplicity of Lisp’s parenthetical syntax3.

It was a fortunate lapse. The flexibility of S-expressions have helped Lisp develop a culture of linguistic experimentation, one from which a powerful macro system was a natural but significant development; the ability to absorb and express a wide variety of paradigms has inspired Lisp’s description as a “language laboratory”. See for example Lisp’s switch statement, adapted from Steele & Gabriel’s The Evolution of Lisp, wherein Steele recalls using it to implement some ten interpreters a week:

(defmacro switch (value &rest body)
  (let* ((newbody (mapcar #'(lambda (clause)
                              `(,(gensym) ,@(cdr clause)))
                          body))
         (switcher (mapcar #'(lambda (clause newclause)
                               `(,(cadr clause) (go ,(car newclause))))
                           body newbody)))
    `(block switch
       (tagbody (case ,value ,@switcher)
                (break)
                ,@(apply #'nconc newbody)))))

(defmacro break ()
  '(return-from switch))

(switch n
  (case 0 (princ "none") (break))
  (case 1 (princ "one "))
  (case 2 (princ "too "))
  (case 3 (princ "many")))

In effect, to write code in a simply-homoiconic language is to do two things at once: to create a computer program and to create a series of data structures. That one can manipulate the other is the magic of it all. As a final illustration, here’s a Scheme program implementing a key-value data store that rewrites itself to include newly-inserted values (a literal interpretation of the phrase “self-modifying code”):

(define data '()) ; Initial data.

(let ((self (car (command-line)))
      (args (cdr (command-line))))
  (case (string->symbol (car args))
    ((get)
     (let ((pair (assoc (cadr args) data)))
       (when pair ; Print associated value.
         (display (cdr pair))
         (newline))))
    ((set)
     (let ((program ; Read own program.
            (with-input-from-file self
              (lambda () (read) (read)))))
       (with-output-to-file self
         (lambda ()
           (write ; Insert new value.
             `(define data
                '(,(cons (cadr args) (caddr args))
                  ,@data)))
           (write program)))))))

$ scheme data.scm get a
$ scheme data.scm set a 1
$ scheme data.scm set b 2
$ scheme data.scm get a
1
$ scheme data.scm get b
2

At this point, my Scheme bias is probably showing. If you have any examples of effective (or even just amusing) uses of homoiconicity in Scheme, Lisp or any other language, please send them my way.


  1. The term for this is homoiconicity, but the property itself isn’t terribly useful without Lisp’s iconic simplicity. If one felt pedantic, one could argue that, “well, programs are generally written as sequences of characters, so any language that can operate on strings is fundamentally homoiconic as well”. That’s technically true, but don’t stop there: strings can be encoded as lists of numbers, so any language that can operate on numerical expressions is the same. Then, you can Gödel-encode those expressions and claim that any Turing-complete language is homoiconic. This misses the point in classic fashion – the point is that Lisp’s simplicity makes the manipulations above not just possible but trivial.↩︎

  2. There are some modern languages, such as Io and REBOL, that do very interesting things involving introspection and self-modification. Lisp, however, predates each, and has certainly served as the foundation for such new ideas.↩︎

  3. There have actually been many attempts to remove the parentheses, most of which have floundered. Notable as fairly direct Lisp descendants without its S-expressive syntax are Logo and Dylan.↩︎