From: ······@sdg.dra.com
Subject: Dotted S-expressions
Date: 
Message-ID: <1991Sep10.134516.16@sdg.dra.com>
Could anyone tell me the simplification for the following S-expression?

	((a . b) . (c . d))

And in general what is the rule for simplifying dotted expressions?
I am new to Lisp and find this very confusing any help would be greatly
appreciated.

Thanks,
Chris

From: Joe Konstan
Subject: Re: Dotted S-expressions
Date: 
Message-ID: <43192@ucbvax.BERKELEY.EDU>
In article <···················@sdg.dra.com>, ······@sdg.dra.com writes:
> Could anyone tell me the simplification for the following S-expression?
> 
> 	((a . b) . (c . d))
> 
> And in general what is the rule for simplifying dotted expressions?
> I am new to Lisp and find this very confusing any help would be greatly
> appreciated.

You certainly aren't alone.  Most people new to lisp experience trouble with
dotted s-expressions (or dotted lists or pairs as they are sometimes called)
because few textbooks provide a decent treatment of the topic.  Here is a
simple explanation:

When we write a list, we write "(" followed by the first element, the second
element, etc., folowing the CDR of the list until we hit nil.  Then we put in
a ")" (this applies to sublists as well).  An alternate representation is to
write "(" then the car, then "." the whole list represented by the cdr and the
")"  for instance:

	(a b c) is also (a . (b . (c . nil)))

	((a) b) is also ((a . nil) . (b . nil))

Similarly, you can remove extra dots by following two simple rules:

	( <anything> . nil ) becomes ( <anything> )
	( <anything1> . (<anything2>)) becomes (<anything1> <anything2>)

in the above, <anything> can be one or more symbols, lists, numbers, etc.

For your example:

	((a . b) . (c . d))

we only apply the second rule to give:

	((a . b) c . d)

Why are there remaining dots?  Any dots that remain represent CDR's that are 
not lists, dotted pairs, or nil.  Thus, this structure was built using:

	(cons (cons 'a 'b) (cons 'c 'd))

since there are two conses where the cdr is an atom, the simplified version
has two dots remaining.

I hope this is useful.  Please let me know if there is anything I can clarify
further (or watch and wait, I'm sure others will reply as well).

Joe Konstan
·······@cs.berkeley.edu
From: Jay Nelson
Subject: Re: Dotted S-expressions (long -- includes homework)
Date: 
Message-ID: <28CE707A.1C7C@deneva.sdd.trw.com>
Whenever things are hopelessly confusing, resort to "cons" diagrams.
A cons cell is a structure of two things: a car and a cdr.  Lists
are represented as cons cells.  So here is the cons diagram for the
simple list '(a b):

	+---+---+    +---+---+
	|   |   |    |   |   |
	| | | ------>| | | ------||
	| | |   |    | | |   |
	+-|-+---+    +-|-+---+
          |            |
          V            V

          A            B

The first box is a cons cell where the car is 'a and the cdr is the
list '(b).  The second box is a cons cell where the car is 'b and the
cdr is NIL (it's hard to draw a ground symbol in ASCII).

Now consider '(a . b) - the car is 'a and cdr is 'b.  So we have:

	+---+---+
	|   |   |
	| | | | |
	| | | | |
	+-|-+-|-+
          |   |
          V   V

          A   B

In your original expression you wanted to know what '((a . b).(c . d))
looks like.  First we make the elements as dotted cons cells:

	+---+---+	+---+---+
	|   |   |	|   |   |
	| | | | |	| | | | |
	| | | | |	| | | | |
	+-|-+-|-+	+-|-+-|-+
          |   |           |   |
          V   V           V   V

          A   B           C   D

And then we dot them in a new cons cell (notice that the down arrows
point to the ENTIRE cons cell below them):

		+---+---+
		|   |   |
		| | | | |
		| | | | |
		+-|-+-|-+
	          /   \
	         /     \
                /       \
               /         \
              /           \
             /             \
            V               V
	+---+---+	+---+---+
	|   |   |	|   |   |
	| | | | |	| | | | |
	| | | | |	| | | | |
	+-|-+-|-+	+-|-+-|-+
          |   |           |   |
          V   V           V   V

          A   B           C   D

Starting from the top level cons cell, the car is '(a . b) and the cdr
is '(c . d).  For that to work, we could have simplified the expression
as '((a.b) c . d), because the cdr of this list is also '(c.d).

The transformation algorithm from cons diagrams to simplified LISP
expression is:

  1) If the cell you are looking at is an atom, write the atom.
       Return to the caller.
  2) If the cell you are looking at is a cons cell, write a "("
       and then go to Step 2a.
     a) Look at the car.  Go to step 1.  After returning, Step 2a is
          complete. Continue with step 2b.
     b) Look at the cdr:
         - If the cdr points to an atom, write ". " then the atom.
             Step 2 is complete.  Continue with Step 3.
         - If the cdr points to NIL, do nothing. Step 2 is complete.
             Continue with Step 3.
         - If the cdr points to a cons cell, goto step 2a.
            (i.e., you are performing step 2 but do NOT write
                   the preceding "(")  After returning, Step 2
             is complete.  Continue with Step 3.
  3) Write a ")" and return to the caller.

or something like that . ;-) At least it works on the example above.
Somebody else can find the errors and post corrections.

As an exercise, implement structures which have "CAR" and "CDR" slots
and write the algorithm as a lisp function which prints out the
simplified representation of a connected set of structures.  Have fun!








-- 
Jay Nelson  (TRW)  ···@wilbur.coyote.trw.com
From: Harley Davis
Subject: Re: Dotted S-expressions (long -- includes homework)
Date: 
Message-ID: <DAVIS.91Sep12134628@passy.ilog.fr>
In article <·············@deneva.sdd.trw.com> ···@nyssa.coyote.trw.com (Jay Nelson) writes:

   Whenever things are hopelessly confusing, resort to "cons" diagrams.

Whenever list structure gets hopelessly confusing, it's usually time
to consider using a more structured data type.  Modern Lisps have
structures, hash tables, etc. which provide much better interfaces for
typical programming abstractions.  I rarely use lists which are not
flat, and this saves endless time in debugging and maintenance, since
code which, using lisps, would be littered with CADRs, CDARs, CDDARs,
and other similar horrors, instead uses trivially defined accessor
functions.  Memory requirements and access speed are usually better
with structured objects as well.

-- Harley
--
------------------------------------------------------------------------------
nom: Harley Davis			ILOG S.A.
net: ·····@ilog.fr			2 Avenue Gallie'ni, BP 85
tel: (33 1) 46 63 66 66			94253 Gentilly Cedex, France
From: Jay Nelson
Subject: Re: Dotted S-expressions (long -- includes homework)
Date: 
Message-ID: <28CFA202.4260@deneva.sdd.trw.com>
Harley Davis makes a good point: use a data structure that is well
suited to the problem rather than making complicated list structures.
The only time I use dotted cons cells is when I making a quick and
dirty solution using association lists.
-- 
Jay Nelson  (TRW)  ···@wilbur.coyote.trw.com
From: Jeff Dalton
Subject: Re: Dotted S-expressions (long -- includes homework)
Date: 
Message-ID: <5299@skye.ed.ac.uk>
In article <···················@passy.ilog.fr> ·····@passy.ilog.fr (Harley Davis) writes:
>
>In article <·············@deneva.sdd.trw.com> ···@nyssa.coyote.trw.com (Jay Nelson) writes:
>
>   Whenever things are hopelessly confusing, resort to "cons" diagrams.
>
>Whenever list structure gets hopelessly confusing, it's usually time
>to consider using a more structured data type.  [...]  I rarely use
>lists which are not flat, [...]

Not true, Harley: you write Lisp code.  Even dotted lists may
appear in code (eg in a backquote).

It's generally a good idea, IMHO, to have some understanding of
non-flat list structure, and even of dotted pairs.  Lists and binary
trees are useful data structures that it's worth knowing about.
Unfortunately, most Lisp texts put the cons and tree diagrams in
the section of destructive operations and then try to discourage
you from wnting to know about them.  But I've seen a number of
people who are learning Lisp completely misunderstand even flat
lists until they saw some "box and arrow" diagrams.

Instead of drawing cons diagrams, however, why not have a program do
it?  There's code that does so in the book _Common Lisp: A Gentle
Introduction to Symbolic Computation_ by David S. Touretzky, The
Benjamin/Cummings Publishing Co., 1990.  The code used to be available
for ftp to those who have purchased the book.  Anyway, here's what the
"generic" version produces for the list that started this discussion:

   > (sdraw '((a . b) . (c . d)))

   [*|*]------->[*|*]--->D
    |            |
    v            v
   [*|*]--->B    C
    |
    v
    A

Another notation that's (1) concise and hence easy to type and (2)
uses dots in an appropriate way goes like this:

   .-- cdr
   |
   car

Note that if you rotate the diagram clockwise 45 degrees you 
get something that even looks like a binary tree.  Anyway,
the list ((a . b) . (c . d)) would be:

   .--------.--D
   |        |
   .-- B    C
   |
   A

I first saw this in _The New UCI Lisp Manual_, by James R. Meehan
(with contributions from various others).

-- jeff