Are ALL S-Expressions really ordered pairs?

http://www-formal.stanford.edu/jmc/recursive/node3.html

An S-expression is then simply an ordered pair, the terms of which may be atomic symbols or simpler S-expressions.

But it seems like functions are able to take as many parameters as they like. Is this a convention that never carried over into implementation or am I missing something?

mmm, maybe (+ 1 2) is syntactic sugar for (+ (1(2))?

Those ordered pairs are called cons cells, and the syntax for them in Common Lisp is

(first . second)

and a list is just a series of cons cells, with the second element of the final one being NIL, so the syntax is:

(first second third) == (first . (second . (third . nil)))

One example taken from Practical Common Lisp (a very good book available on-line). The list

(1 2 3)

Is represented internally this way



In other words, Lisp lists are linked lists.

I've been using that book as well, thanks for the input.

Yeah, I think I get it now.
Seems like lisp forms are structurally isomorphic to the abstract syntax tree which is structurally isomorphic to the S-Expression notation which is structurally isomorphic to the linked-list/tree data structure. I still don't know what a lisp form actually is, but I think I get the big picture.

yougene wrote:I still don't know what a lisp form actually is, but I think I get the big picture.

It's any object meant to be evalutated. Lists, symbols, strings, whatever. You can think of it as any object making up valid Lisp code.

Are functions also considered objects?

Am I to think of these objects as instances of the syntax tree? I'm not sure how this part of the construct works.

A function is an object; (defun foo (x) (+ 1 x)) is a form defining a function stored under the symbol named FOO. Subforms are defun, foo, (x), (+ 1 x). The last two have subforms x, +, ...

Both (symbol-function 'foo) and #'foo are forms extracting the actual function from its name.