Are ALL S-Expressions really ordered pairs?

Discussion of Common Lisp

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?
yougene

Posts: 23
Joined: Thu Jan 21, 2010 1:23 pm

Re: Are ALL S-Expressions really ordered pairs?

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

Posts: 23
Joined: Thu Jan 21, 2010 1:23 pm

Re: Are ALL S-Expressions really ordered pairs?

Those ordered pairs are called cons cells, and the syntax for them in Common Lisp is
Code: Select all
`(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:
Code: Select all
`(first second third) == (first . (second . (third . nil)))`
Ramarren

Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland

Re: Are ALL S-Expressions really ordered pairs?

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

Code: Select all
`(1 2 3)`

Is represented internally this way

In other words, Lisp lists are linked lists.
gugamilare

Posts: 406
Joined: Sat Mar 07, 2009 6:17 pm
Location: Brazil

Re: Are ALL S-Expressions really ordered pairs?

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

Posts: 23
Joined: Thu Jan 21, 2010 1:23 pm

Re: Are ALL S-Expressions really ordered pairs?

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.
Paul Donnelly

Posts: 148
Joined: Wed Jul 30, 2008 11:26 pm

Re: Are ALL S-Expressions really ordered pairs?

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

Posts: 23
Joined: Thu Jan 21, 2010 1:23 pm

Re: Are ALL S-Expressions really ordered pairs?

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.

nuntius

Posts: 532
Joined: Sat Aug 09, 2008 10:44 am
Location: Newton, MA