Comparison of Scheme and Common Lisp

Standards

Common Lisp is defined by ANSI Common Lisp (X3J13). This standard has been translated to the web as the Common Lisp HyperSpec. An earlier draft of the language was defined in Common Lisp the Language, editions 1 and 2 (CLtL1 and CLtL2); these are superseded by ANSI.

Scheme is defined by the Revisedn Report on the Algorithmic Language Scheme (RnRS). The latest is R7RS. R6RS is still in active use. R5RS is the classic definition of Scheme. R6RS and R7RS are compatible with R5RS, but R5RS is rarely used as-is anymore; in particular, it lacks a library system, making it hard to write modular programs. R4RS is still the basis of very small, niche Scheme implementations. R3RS and earlier are no longer used. R2RS "The Revised Revised Report on Scheme (AI Memo No. 848)"), R1RS "The Revised Report on Scheme (AI Memo No. 452) , R0RS "Scheme: An Interpreter for Extended Lambda Calculus (AI Memo No. 349)". The IEEE Standard for the Scheme Programming Language (1178-1990) is almost the same as R4RS. DSSSL (Document Style Semantics and Specification Language (ISO/IEC 10179:1996)) is R4RS with some extensions.

Scheme has the SRFI process which has been running continuously since 1998.

Naming conventions

Scheme and CL both use so-called lisp-case or kebab-case: identifiers are written all in the same case (almost always lowercase), with dashes (not underscores) between words: multi-word-identifier.

Predicates

A predicate is a fuction that tests something and returns a boolean value indicating whether the test passed or failed. The word predicate comes from logic. The names of Scheme predicates conventionally end in question mark: list?, string?. The names of CL predicates conventionally end with the letter p (which stands for "predicate"). Multi-word predicates end with -p.

<
listp
proper-list-p
string-lessp
<
list?
proper-list?
string<?

Constants, global and dynamic variables

Common Lisp programmers like to put stars around the names of global variables: standard-input. (Actually stars are used for all special variables, aka dynamic variables, not just global ones.)

Scheme global variables are not dynamic; they are static.

Scheme does not really have dynamic variables at all. Dynamic variables are emulated using parameter objects, or parameters for short. The parameterize syntax can temporarily change the value of a parameter. In Common Lisp, a dynamic variable is temporarily rebound using ordinary let.

Continuations, exception handling, unwind-protect

Common Lisp does not have standard user-visible continuations. Scheme does.

Scheme has dynamic-wind which can be used to temporarily set the value.

You may see talk of "fluid let". That is not really used nowadays.

Lisp-1 vs lisp-2

Common Lisp has separate namespaces for variables and functions. (Since functions are first-class objects, it’s still possible to store a function object in a variable, but the binding is different.)

Data types

Pairs and lists

Pairs and lists have the same syntax and semantics in both languages:

()
(1)
(1 2)
(1 2 3)

Dotted pairs work the same:

(1 . 2)
(1 2 . 3)
(1 2 3 . ())

The empty list

In Scheme, the empty list () must be quoted when used as a literal: '(). In Common Lisp the empty list is a self-evaluating object and the quote is optional.

In Common Lisp, the empty list () is the same as the symbol nil which is also self-evaluating. All of the following are true:

(eq nil ())
(eq nil '())
(eq nil 'nil)

Scheme has no nil. () is the only way to write an empty list. The predicate null? tests only for ().

Booleans and predicates

In Common Lisp, the symbol nil doubles as the boolean value false. The symbol t represents the boolean value true. Like nil, t is self-evaluating.

(not t)     => nil
(not nil)   => t
(null nil)  => t
(listp nil) => t
(listp t)   => nil

In Scheme, boolean true and false are written using sharpsign syntax as #t and #f. These are unique objects that do not represent any other data type.

(not #t)   => #f
(not #f)   => #t
(null? #f) => #f
(list? #f) => #f
(list? #t) => #f

Nil punning and truthiness

Common Lisp code often takes advantage of the aliasing of nil as nothing, false, and empty list, for various purposes. Scheme code mostly uses #f as the "nothing" value, but does not conflate the empty list and nothing into the same value like CL does.

In particular, Scheme conditionals like (if …​) and (and …​) and (or …​) check for #f versus non-#f.

Equality

Equality predicates work much the same. Scheme has no equivalent to equalp.

CL Scheme

eq

eq?

eql

eqv?

equal

equal?

equalp

N/A

Numbers

The number tower is approximately the same: integers (fixnums and bignums), ratios, real and complex numbers.

Scheme distinguishes between exact and inexact numbers. Integers and ratios are exact; real numbers are inexact. In principle, Scheme supports inexact integers (with missing digits) and exact reals, but these features are practically never implemented. In SRFIs, the specification often says "exact integer" instead of just "integer".

Streams aka ports

Common Lisp talks about "streams". Scheme talks about "ports". These are the same thing.

(When schemers talk about streams, they tend to mean lazy sequences from functional programming. SRFI 41 is the most popular definition of such streams, and RnRS has delay/force which can be used to define such streams.)

R6RS provides custom ports similar to the Gray Streams extension for CL.

Vectors and arrays

Scheme has a standard vector datatype but no standard array datatype. SRFIs provide multidimensional arrays, which are disjoint from Scheme’s standard vector datatype.

Common Lisp has standard arrays, and a vector is a special case of an array.

Common Lisp has growing vectors ("adjustable arrays"). Standard Scheme vectors do not grow; the size is fixed on creation. SRFI provides a growing vector.

Strings and characters

In Common Lisp, a string is a special case of a vector. Scheme strings and vectors are completely different datatypes. Both Scheme and Common Lisp provide standard string ports/streams which are a useful alternative to growing strings.

Recursion and tail calls

Scheme is possibly the most recursive programming language ever. Recursion is the default style for expressing almost any algorithm that is not abstracted into higher-order functions. Pervasive use of recursion is the main source of Scheme’s simplicity, versatility, and economy of expression.

The Common Lisp standard ships with many loops: do, dotimes, dolist, with-hash-table-iterator, and last but not least, the infamous loop macro.

The Scheme standard ships only the do loop, and even that is considered by many to be questionable style. The standard ships the higher-order functions for-each, vector-for-each, and string-for-each for iteration. These take a lambda and call it for each step of the iteration, which is the preferred way apart from recursion to loop in Scheme. Though it’s possible to write the same kinds of loop macros that CL users use, schemers tend to avoid it, preferring higher-order functions.

Standard Common Lisp does not mandate proper tail calls; it’s an optional optimization. Standard Scheme does.

It’s well known that proper tail calls turn recursive self-calls into jumps. However, they also do the following things that are little known outside Scheme:

  • Non-tail recursion is not optimized, only tail recursion is.

  • Tail calls from any function to any other function are optimized. Not just recursive self-calls.

  • In fact, tail calls don’t intrinsically have anything to do with recursion. The deciding factor is whether or not a function is being exited, not which function is going to be entered (the same one or a different one). When a function call is the last thing that (any given conditional branch of) a function will do, we say that the call is being made in tail position, and should therefore be turned into a tail call.

  • Tail call optimization incidentally turns mutual recursion between two procedures into a co-routine.

  • Since continuations are callable in Scheme, you can tail-call a continuation.

  • A tail call to call-with-current-continuation will yield a continuation that jumps to the procedure provided by the caller.

  • You can tail-call a promise, and thereby force it.

  • Tail-call optimization does not need to be done by a compiler. Even the simplest tree-walking interpreter can do it with very little extra complexity. All that’s needed is for eval to keep track of whether or not the expression being evaluated is in tail position.

References:

Debunking the "Expensive Procedure Call" Myth or, Procedure Call Implementations Considered Harmful or, Lambda: The Ultimate GOTO. [Guy Steele 1977]

A typical recursive function is written in CL thus:

(labels ((factorial (n)
           (if (<= n 1) 1 (* n (factorial (- n 1))))))
  (factorial 50))

In Scheme:

(letrec ((factorial (lambda (n)
                      (if (<= n 1) 1 (* n (factorial (- n 1)))))))
  (factorial 50))

This is usually shortened to a special case of the let form:

(let factorial ((n 50))
  (if (<= n 1) 1 (* n (factorial (- n 1)))))

The above is ubiquitous in recursive Scheme code, and recursion is ubiquitous in Scheme, so commit this to memory.

Multi-purpose let and define

Scheme’s let and define are multi-purpose.

Basic let works like Common Lisp:

(let ((a "abc")
      (b 123))
  ...)

Scheme also supports named let which is a bit perplexing to Common Lispers since it actually defines a function, not a variable. But additionally defines variables to be used as argmuents to that function. But unlike normal function definitions, also gives initial values to the function arguments. And then calls that function with those arguments.

Wonky named let

Higher-order functions

The basic flow of Scheme programming is to use recursion for everything, and when the recursion gets hard to read, package part of it into a higher-order function.

Libraries and packages

R5RS and earlier Scheme standards did not contain any kind of standard module system. As a result, many Scheme implementations built their own, which is not a boon to portable code.

R6RS and R7RS both specify a library system in the standard. These systems are broadly compatible, but use slightly different syntax.

Contributing

doc.scheme.org is a community subdomain of scheme.org.