BATTLE OF THE LISPS: Common Lisp vs. Scheme

The title of this post is misleading, there’s no battle or no decision about which lisp is “better”. I just wanted something provocative. What this post does do is compare the two lisps.

Both Scheme and Common Lisp (CL) are “lisps”, a family of languages which emphasize a few points (essentially the idea I explained in this blog post). Arguably, both Scheme and CL are renditions of the number of lisps that preceded them.  The original “Lisp” was invented in 1958, and ideas from that original lisp caused the language to branch out in many places. So, in a sense, Scheme and CL are both attempts to “unify” the lisps.

Scheme’s Idea

The way Scheme unified compared to the way CL differs vastly. Scheme’s idea of unification is exemplified by one of the first statements in the Scheme standard itself:

Programming languages should be designed not by piling feature on top of feature, but by removing the weaknesses and restrictions that make additional features appear necessary.

Essentially, Scheme was an attempt to take the core idea of Lisp, and derive a bare but practical “minimum” which could be reasonably extended as needed. This was highly successful, and the Scheme standard ended up being just over 50 or so pages (and anyone who has seen a language standard before would be staggered by such a low number). Due to the succinctness of the definition of the language, it is an incredible medium for studying programming languages and computer science in general (it is the language used in the famous book Structure and Interpretation of Computer Programs, or SICP).

The use of Scheme extends beyond simple educational or theoretical value. It is a practical language. The standard includes many examples of practical use. Since Scheme is a lisp, it can be extended to the users’ needs via macros and such. So, while being incredibly simple and small, it does not preclude it from being useful or practical.

CL’s Idea

CL took an entirely different approach. Instead of making a language as a result of picking out fundamentals of earlier languages and ideas, it, in a sense, took many of the previous popular lisps (notably MacLisp, not related to Apple’s Macintosh), and took the good, tested, and popular features from them. A central goal in the design of CL was to make a language that was highly compatible (in terms of features and how things worked) with other lisps. If four out of five lisps had a certain way of doing hash tables, then CL would likely have this feature as well.

As a result, CL ended up being a very large language with the genes of previous lisps highly woven in. The language standard is 1153 pages of printed text (though just about every function described has examples and whatnot). Some people see CL as having an incredible amount of cruft and baggage, others see the extra features (that could otherwise be there with libraries) as means of keeping code consistent and portable.

As one might guess, CL is not a great language for using as a model for studying. But if one is programming to get things done, then it of course is great and practical.

Comparisons

Symbols and Case

Scheme has very few symbols defined that are accessible to the user initially. Most symbols are either numerical functions (max, min, gcd, etc.) or string functions — aside from the core language symbols (lambda, define, etc.). CL on the other hand, has a great handful. It includes functions for most common things: list functions, numerical functions, string functions, hash table function, and macros out the wazoo. The default CL runtime is quite large (however, the standard does specify that a conforming CL implementation may only include a subset of CL in total). As a result, Scheme tends to be much more lightweight in this respect, but is also seen as being a hindrance to practical programming.

Usually, in Scheme, symbols are case sensitive (this is not necessarily true, but it is usually the case). CL, on the other hand, is notoriously case insensitive—iconic because you’re reminded it is every time you talk to the REPL:

> '(hello how are you today?)
(HELLO HOW ARE YOU TODAY?)
> (defun make-lols (n)
    (if (> n 10)
        '(why so many lols?)
        (make-list n :initial-element 'lol)))
PRINT-LOLS
> (make-lols 5)
'(LOL LOL LOL LOL LOL)
> (make-lols 10000)
(WHY SO MANY LOLS?)

Everything is in caps because that is the default case. Back in the day, lisp (or LISP) was even typed out in all caps.

Many programmers seem to see case sensitivity is an important feature for them. I am divided on it. When I program, it seems case is usually very unimportant to me. But in mathematics, I would never, ever have $n$ be equivalent to $N$ just because they both represent the letter “enn”.

Names

CL is often regarded as “old” and “obsolete” simply because of the names of some procedures. With Scheme this isn’t the case. In Scheme, most procedures have a very natural name. Consider these approximate equivalences in Scheme and CL:

Scheme	Common Lisp	Meaning
map	mapcar	Apply a function to every element of a list.
define	defun, defparameter, defvar	Define a function (or value).
begin	progn	Execute a block of “statements” (à la Pascal).
newline	terpri	Print a newline.
set-car!	rplaca	Destructively set the car of a pair.
pair?	consp	Determine if a value is a pair.
string->number	parse-integer	Convert a string literal like "123" to a number (integer).

The “informality” and brevity of CL’s choice of many names seems to be a turn-off to many. As it turns out, however, the names of many CL functions are the way they are for a reason. If something is a definitional form, it will almost always begin with def (defun, defmacro, defparameter, defconstant, …). If something is destructive or non-consing, it will likely begin with the letter n (nconc, nreverse, nsubst, …). In contrast, Scheme uses ! to denote destructive operations (set!, reverse!, concatenate!, …).

On a similar note, CL tends to end a function with p if it is a predicate of some sort (characterp, evenp, …) whereas Scheme uses a ? to denote such (char?, even?, …).

Functions and Values

Both languages allow for first class functions. However, in Scheme, functions are “truly” first class in that they have no special treatment. A parameter to a function may also be a function, may be listed, may be called, etc. In CL however, things are different. While function parameters may themselves be functions, they must be used in a different way.

In CL, every symbol may have a function definition, and “value” definition. So one symbol may actually represent several different data. Consider this example

(defun lisp (list)
  (list (list list list)
        (list list list)))

Ridiculous, yes, but it is perfectly legal. However, in this example, list has two distinct meanings. In one case, where it is the head of a list, it means the traditional meaning: make a list out of the arguments. When it’s not in the head position, it represents the argument to the function lisp. So we have

> (lisp #'cons)
((#<FUNCTION CONS> #<FUNCTION CONS>) (#<FUNCTION CONS> #<FUNCTION CONS>))
> (lisp 5)
((5 5) (5 5))

In Scheme, if we define an analogous function:

(define (lisp list)
  (list (list list list)
        (list list list)))

it too will not error. However,

> (lisp 5)
ERROR: 5 is not a procedure.
> (lisp list)
((#<procedure list> #<procedure list>) (#<procedure list> #<procedure list>))
> (lisp cons)
((#<procedure cons> . #<procedure cons>) #<procedure cons> . #<procedure cons>)

Notice that the last example returned a list of pairs instead of a list of lists. With CL, we will always get a list of lists. How can we do the equivalent thing Scheme does in CL?

(defun lisp (list)
  (funcall list (funcall list list list)
                (funcall list list list)))

So now we have, for example,

> (lisp #'cons)
((#<FUNCTION CONS> . #<FUNCTION CONS>) #<FUNCTION CONS> . #<FUNCTION CONS>)

This decision to have functions and “values” in separate namespaces was intentional in CL. There are efficiency considerations to be made which compiler writers would understand. In Scheme’s example, you couldn’t inline the “list” function, since you’re assuming full generality. To do the equivalent in Scheme of what CL does, you must do this:

(define (lisp l)
  (list (list l l)
        (list l l)))

to make names unique. It is impossible in Scheme to name the argument list and use the regular list function as well (some pre-CL languages saw this as a downside, since you are often sending a list as an argument, and so one might as well let the argument name be list).

The use of funcall sort of “patches” CL to allow arbitrary functions to be called in non-function position (which Scheme doesn’t need). More generally, CL has “duals” to most Scheme procedures/macros. CL has flet for a function-let; a sharp-quote as a dual to quote; etc.

CL is often called a “Lisp-2″ because it has two primary namespaces for values to exist. Scheme is called a “Lisp-1″ because all values co-exist in a single namespace. In reality, we might actually say CL is a “Lisp-$n$”, because we actually can have more namespaces, such as for dynamic variables.

Macros

Lisp is a language designed to be extended in syntax and semantics, and lisps always provide a way to do this.

I’m not going to break down precisely what macros are and how they work, nor will I give a very detailed tutorial about how things work in either language, but I will point out the main differences.

In CL, macros are very “raw”. You can define a lisp macro to do essentially arbitrary processing of lisp code using the lisp evaluator before it reaches the lisp evaluator for final evaluation (hehe). Macros are quite straightforward. Let’s define the good ol’ C pre-increment operator.

(defmacro preinc (x)
  `(prog1
     ,x
     (setq ,x (+ 1 ,x))))

[To my CL-knowledgeable readers, please note that I do know about incf and my avoiding use of it.]

This macro allows one to do (defparameter x 5) (preinc x), which will return 5, and increment the value of x to 6. We can do the same thing in Scheme in this way:

(define-syntax preinc
  (syntax-rules ()
    ((_ x) (set! x (+ 1 x)))))

which isn’t quite as straightforward to the untrained eye. Scheme’s define-syntax is more directed at syntactic source code transformations. CL’s defmacro is directed at arbitrary transformations and computations. Scheme’s macro facility also provides hygeine, we won’t run into issues of variable capture if we use things like lambda or let; variables are appropriately renamed, whereas CL is unhygienic and is susceptible to variable capture unless explicitly dealt with.

There have been holy wars about which macro system is better and it really is an opinion unless you attach some definitions of what makes something “better”. Scheme’s system is rather simple once you get it, and is quite flexible, and suitable for most macro needs (most language constructs in Scheme are actually just a Scheme macro, like cond and let). Common Lisp however is very simple and really puts the burden on the programmer to write safe macros. However, where there’s unsafety, there’s also interesting hacks and uses. One might argue that CL’s macro system is better since one can just use it to define Scheme’s macro system, though this argument is usually moot if Scheme’s macro system is better in the first place, then there’s no point to having a more primitive system in a language designed to be practical. Most CLers don’t seem to think Scheme’s is better, however.

Libraries and Portability

Both languages have a formal standard. However, in general, you can expect CL code to be “more portable” than Scheme code. Why?

The issue is this. When a language standard is small, one will tend to have to re-invent the wheel over and over to get things practical. As such, Schemer Bob might write his own hash table implementation, and Schemer Alice might write her own. More likely than not, both of these implementations will be highly incompatible.

So why not have standard libraries? Scheme does have these, sort of. There are documents called “Scheme Requests for Implementation” or SRFIs which are intended to solve this problem. An SRFI is intended for implementors to include with their implementation. For example, SRFI-1 is essentially a list library, adding many common procedures for lists (reverse, fold, etc.). SRFI-13 is a string library.

Surely this solves that portability issue? Unfortunately not. The most implemented and accepted Scheme standard is $\textrm{R}^5\textrm{RS}$, which defines no way to define libraries or import libraries. So libraries are made on an ad hoc basis. Most Schemes either provide their own library facility, or just have a simple “load file” function. With each Scheme having their own way to load files or libraries, most user written libraries are incompatible. Schemer Bob using Implementation X probably can’t share code with Scheme Alice using implementation Y unless Bob simply sends the raw Scheme code. If Bob’s code uses libraries, then Alice needs to modify it (assuming a library exists for her implementation!), or just rewrite it on her own.

This problem was definitely recognized by the Scheme community, and was “solved” in $\textrm{R}^6\textrm{RS}$. However, $\textrm{R}^6\textrm{RS}$ seems to have been a flop (sort of like Vista (which also was the sixth rendition of Windows, coincidence?!)). Currently, two Scheme committees “Scheme Working Groups 1 & 2″ seek to make a more acceptable standard. Unfortunately, they are splitting the Scheme language into two languages: one “small” Scheme for academic use, and one “large” Scheme for practical and production use. Bad move in my opinion.

So how does this all compare with CL? Well, CL aimed to definitely be practical from the start. It includes native ways to package code, and there is a more-or-less standard way to package libraries, called “Another System Definition Facility”, or ASDF. More recently, the use of libraries has been made excruciatingly simple, thanks to Zach Beane, with his great system Quicklisp.

So in general, libraries and such are pretty portable in CL and easy to share.

Implementations

Everyone and their dog has their own Scheme implementation.

I don’t know nor remember where I heard that, but it is basically true. I am barely exaggerating when I say there are thousands of Scheme implementations (okay, I am really exaggerating, but there are a lot). The language is so simple and easy that, once grokked, it’s simple to implement.

Is this a good thing? Well, the more available implementations implies that there’s more choice. Choice of what exactly? Ideally, an implementation should be different from another in terms of execution speed, compiler speed, portability, size, etc. However, in the Scheme world, many, many implementations also differ in all sorts of features. Some compiler/interpreter writers try to solve shortcomings in Scheme and add their own features (like library support, as discussed), making Scheme implementations highly incompatible. This isn’t terrible, per se, if the extra features are optional (and they usually are). But implementations also have another issue: a lot of them don’t even stick to the standard strictly, and a lot of them don’t care to implement the trickier parts of Scheme well enough (e.g., continuations).

So what we end up with is a steaming pile of Schemes which don’t play well with one another, and are usually inefficient because only one person is working on his or her own compiler. There are some good exceptions. I highly recommend two Schemes: Chicken Scheme for your compiling and interpreting needs (also has a great library system and code repository system), and Chibi Scheme, a standards-strict tiny Scheme suitable for embedding in C applications. There are other good Schemes, but those are what I like most.

Common Lisp is a little different. One person is usually not enough to get a full, conforming implementation. The language is pretty big and confusing in many areas. As a result, we have far, far fewer implementations of CL. We still do have a good variety of both free and commercial CL implementations.

The CL implementations are generally known to be standards conforming and usually produce good code. My two favorites are SBCL for general work and very efficient compilation, and CLISP as a very portable system (as it uses its own bytecodes and VM). A nice thing about extensions to the CL language is that they can be delimited in their own namespace (using CL’s packages). In SBCL for example, extensions are in the SB-EXT package.

Conclusion

That concludes a variety of ways to compare the languages. There’s much more to be said, but those are the main good points I think. Remember, I am not claiming either is better than the other. In this post, it might sound like I implied Scheme is better, but I didn’t at all talk about development environments (CL has SLIME, a wonderful environment to code in; Scheme has no ‘universal’ environment for coding in Scheme—you usually just use Emacs and a very basic mode to send data to the REPL).

I do encourage one thing however. If you are curious about lisp in general, you should probably learn Scheme, as it’s very easy to learn and play with. If you know Scheme and perhaps want to give a different style of developing things and thinking about things a go, then try CL. Some of those who are in love with software engineering and all that BS would probably like CL because of the native stuff it provides, like packages and OO. However, as I hinted, many Schemes do include this stuff. Previously mentioned Chicken Scheme has OO facilities, foreign function facilities, packages, etc.

So take it all as you will, digest it, let me know what you think, and click the subscribe button!!