Lisp: list vs S-expression

Question

I'm studying Lisp now. I encountered 2 terms "list" and "S-expression". I just can't distinguish between them. Are they just synonyms in Lisp?

Answer 1

First, not all S-expressions represent lists; an expression such as foobar, representing a bare atom, is also considered an S-expression. As is the "cons cell" syntax, (car . cons), used when the "cons" part is not itself another list (or nil). The more familiar list expression, such as (a b c d), is just syntactic sugar for a chain of nested cons cells; that example expands to (a . (b . (c . (d . nil)))).

Second, the term "S-expression" refers to the syntax - (items like this (possibly nested)). Such an S-expression is the representation in Lisp source code of a list, but it's not technically a list itself. This distinction is the same as that between a sequence of decimal digits and their numeric value, or between a sequence of characters within quotation marks and the resulting string.

That is perhaps an overly technical distinction; programmers routinely refer to literal representations of values as though they were the values themselves. But with Lisp and lists, things get a little trickier because everything in a Lisp program is technically a list.

For example, consider this expression:

(+ 1 2)

The above is a straightforward S-expression which represents a flat list, consisting of the atoms +, 1, and 2.

However, within a Lisp program, such a list will be interpreted as a call to the + function with 1 and 2 as arguments. (Do note that is the list, not the S-expression, that is so interpreted; the evaluator is handed lists that have been pre-parsed by the reader, not source code text.)

So while the above S-expression represents a list, it would only rarely be referred to as a "list" in the context of a Lisp program. Unless discussing macros, or the inner workings of the reader, or engaged in a metasyntactic discussion because of some other code-generation or parsing context, a typical Lisp programmer would instead treat the above as a numeric expression.

On the other hand, any of the following S-expressions likely would be referred to as "lists", because evaluating them as Lisp code would produce the list represented by the above literal S-expression as a runtime value:

'(+ 1 2)
(quote (+ 1 2))
(list '+ 1 2)

Of course, the equivalence of code and data is one of the cool things about Lisp, so the distinction is fluid. But my point is that while all of the above are S-expressions and lists, only some would be referred to as "lists" in casual Lisp-speak.

Answer 2

S-expressions are a notation for data.

Historically an s-expression (short for symbolic expression) is described as:

• symbols like FOO and BAR
• cons cells with s-expressions as its first and second element : ( expression-1 . expression-2 )
• the list termination symbol NIL
• and a convention to write lists: ( A . ( B . NIL ) ) is simpler written as the list (A B)

Note also that historically program text was written differently. An example for the function ASSOC.

assoc[x;y] =
   eq[caar[y];x] -> cadar[y];
   T -> assoc[x;cdr[y]]

Historically there existed also a mapping from these m-expressions (short for meta expressions) to s-expressions. Today most Lisp program code is written using s-expressions.

This is described here: McCarthy, Recursive Functions of Symbolic Expressions

In a Lisp programming language like Common Lisp nowadays s-expressions have more syntax and can encode more data types:

• Symbols: symbol123, |This is a symbol with spaces|
• Numbers: 123, 1.0, 1/3, ...
• Strings: "This is a string"
• Characters: #\a, #\space
• Vectors: #(a b c)
• Conses and lists: ( a . b ), (a b c)
• Comments: ; this is a comment, #| this is a comment |#

and more.

Lists

A list is a data structure. It consists of cons cells and a list end marker. Lists have in Lisp a notation as lists in s-expressions. You could use some other notations for lists, but in Lisp one has settled on the s-expression syntax to write them.

Side note: programs and forms

In a programming language like Common Lisp, the expressions of the programming language are not text, but data! This is different from many other programming languages. Expressions in the programming language Common Lisp are called Lisp forms.

For example a function call is Lisp data, where the call is a list with a function symbol as its first element and the next elements are its arguments.

We can write that as (sin 3.0). But it really is data. Data we can also construct.

The function to evaluate Lisp forms is called EVAL and it takes Lisp data, not program text or strings of program text. Thus you can construct programs using Lisp functions which return Lisp data: (EVAL (LIST 'SIN 3.0)) evaluates to 0.14112.

Since Lisp forms have a data representation, they are usually written using the external data representation of Lisp - which is what? - s-expressions!

It is s-expressions. Lisp forms as Lisp data are written externally as s-expression.

Answer 3

You should first understand main Lisp feature - program can be manipulated as data. Unlike other languages (like C or Java), where you write program by using special syntax ({, }, class, define, etc.), in Lisp you write code as (nested) lists (btw, this allows to express abstract syntactic trees directly). Once again: you write programs that look just like language's data structures.

When you talk about it as data, you call it "list", but when you talk about program code, you should better use term "s-expression". Thus, technically they are similar, but used in different contexts. The only real place where these terms are mixed is meta-programming (normally with macros).

Also note that s-expression may also consist of the only atom (like numbers, strings, etc.).

Answer 4

A simple definition for an S-expression is

(define S-expression?
    (λ (object)
        (or (atom? object) (list? object))))

;; Where atom? is:

(define atom?
  (λ (object) 
    (and (not (pair? object)) (not (null? object)))))

;; And list? is:

(define list? (λ (object)
  (let loop ((l1 object) (l2 object))
    (if (pair? l1)
        (let ((l1 (cdr l1)))
          (cond ((eq? l1 l2) #f)
                ((pair? l1) (loop (cdr l1) (cdr l2)))
                (else (null? l1))))
        (null? l1)))))

Answer 5

Both are written in similar way: (blah blah blah), may be nested. with one difference - lists are prefixed with apostrophe.

On evaluation:

• S-expression returns some result (may be an atom or list or nil or whatever)
• Lists return Lists

If we need, we can convert lists to s-exp and vice versa.

• (eval '(blah blah blah)) => list is treated as an s-exp and a result is returned.
• (quote (blah blah blah)) => sexp is converted to list and the list is returned without evaluating

IAS:

• If a List is treated as data it is called List, if it is treated as code it is called s-exp.