listlisps-expression

Lisp: list vs S-expression


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


Solution

  • 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.