Page 1 of 1

Are ALL S-Expressions really ordered pairs?

Posted: Sat Jan 30, 2010 2:43 pm
by yougene
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?

Re: Are ALL S-Expressions really ordered pairs?

Posted: Sat Jan 30, 2010 3:12 pm
by yougene
mmm, maybe (+ 1 2) is syntactic sugar for (+ (1(2))?

Re: Are ALL S-Expressions really ordered pairs?

Posted: Sat Jan 30, 2010 3:31 pm
by ramarren
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)))

Re: Are ALL S-Expressions really ordered pairs?

Posted: Sun Jan 31, 2010 5:21 am
by gugamilare
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

Image

In other words, Lisp lists are linked lists.

Re: Are ALL S-Expressions really ordered pairs?

Posted: Sun Jan 31, 2010 11:29 am
by yougene
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.

Re: Are ALL S-Expressions really ordered pairs?

Posted: Sun Jan 31, 2010 2:01 pm
by Paul Donnelly
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.

Re: Are ALL S-Expressions really ordered pairs?

Posted: Sun Jan 31, 2010 2:28 pm
by yougene
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.

Re: Are ALL S-Expressions really ordered pairs?

Posted: Mon Feb 01, 2010 3:29 pm
by nuntius
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.