Are ALL S-Expressions really ordered pairs?

Discussion of Common Lisp

Are ALL S-Expressions really ordered pairs?

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

Postby yougene » Sat Jan 30, 2010 3:12 pm

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?

Postby 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)))
Ramarren
 
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland

Re: Are ALL S-Expressions really ordered pairs?

Postby 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.
gugamilare
 
Posts: 406
Joined: Sat Mar 07, 2009 6:17 pm
Location: Brazil

Re: Are ALL S-Expressions really ordered pairs?

Postby 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.
yougene
 
Posts: 23
Joined: Thu Jan 21, 2010 1:23 pm

Re: Are ALL S-Expressions really ordered pairs?

Postby 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.
Paul Donnelly
 
Posts: 148
Joined: Wed Jul 30, 2008 11:26 pm

Re: Are ALL S-Expressions really ordered pairs?

Postby 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.
yougene
 
Posts: 23
Joined: Thu Jan 21, 2010 1:23 pm

Re: Are ALL S-Expressions really ordered pairs?

Postby 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.
User avatar
nuntius
 
Posts: 498
Joined: Sat Aug 09, 2008 10:44 am
Location: Burlington, MA


Return to Common Lisp

Who is online

Users browsing this forum: No registered users and 4 guests