Are ALL S-Expressions really ordered pairs?

Discussion of Common Lisp
Post Reply
yougene
Posts: 23
Joined: Thu Jan 21, 2010 1:23 pm

Are ALL S-Expressions really ordered pairs?

Post by yougene » Sat Jan 30, 2010 2:43 pm

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?

Post by yougene » Sat Jan 30, 2010 3:12 pm

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

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

Re: Are ALL S-Expressions really ordered pairs?

Post by ramarren » Sat Jan 30, 2010 3:31 pm

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)))

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

Re: Are ALL S-Expressions really ordered pairs?

Post by gugamilare » Sun Jan 31, 2010 5:21 am

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.

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

Re: Are ALL S-Expressions really ordered pairs?

Post by yougene » Sun Jan 31, 2010 11:29 am

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.

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

Re: Are ALL S-Expressions really ordered pairs?

Post by Paul Donnelly » Sun Jan 31, 2010 2:01 pm

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.

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

Re: Are ALL S-Expressions really ordered pairs?

Post by yougene » Sun Jan 31, 2010 2:28 pm

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.

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

Re: Are ALL S-Expressions really ordered pairs?

Post by nuntius » Mon Feb 01, 2010 3:29 pm

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.

Post Reply