Dotted Pair Notation

A representation of lists used in LispLanguage and its derivatives, in which ConsCells are shown as a parenthesized pair of elements separated by a period, such that a cons cell whose car pointed to A and its cdr pointed to B would be shown as:

(A . B)

While one in which the car pointed to A and the cdr pointed to a second cons cell who car pointed to B and whose cdr is NIL, would be:

(A . (B . NIL))

This latter would usually be shortened to the ProperList

(A B)

for readability's sake.

Newbie question: I am wondering why it's not prefix:

     (. A B)

(One reason is that it's legal to use the dot to construct "improper lists" where cdr of the last cons is not NIL. For example: '(2 4 6 . 8))

If the dot were a function, then indeed it would be prefix in Lisp, but it's not a function, anymore than the '(' or ')' are functions.

It's an interesting point, though. One could easily have a dialect of Lisp where the '.' was in fact a function that ran at parse time (a macro), in which case it would be most natural for it to be prefix, as in your example.

So, if you like looking at it that way, you could consider it an accident of history; it dates to 1959, well before macros of any kind were added to Lisp.

On the other hand, there is no natural way in Lisp to make the parenthesis into prefix functions as well. You have to have some syntax as a starting point. (The issue of lexical dispatch is, I think, too far afield here.)

A similar question is why you can create a list at read time just by writing e.g.

   '(1 2 3 4 5)

Yet at run time you need to call a function:

   (list a b c d e)

Put yourself in BeginnersMind. If one wonders why "." isn't prefix, then similarly one should wonder about this parse time/run time list issue. The answer is very simple, yet very deep, so I'm not actually asking a question. Even (or especially) for non-beginners, practicing BeginnersMind can be valuable. Expertise causes one to take far too much for granted.

You could write the read macro in the normal syntax and then change the read table.

Don't macro writers create lists at macroexpand time with `(,a ,b ,c ,d ,e)? That easily generalizes to run time via the macroexpand function.

you can create lists with the backquote during read time too. Actually you can use that notation during all times. (defun foo (a b c) `(,a ,b ,c)) is equally valid. It is basically just a different notation for something like (list a b c) .

Don't forget that the context is a newbie question of why "." isn't a prefix function in the normal syntax -- asking for simple understanding, not about what kinds of techniques could be used to do any of these things.

Actually, there is a much simpler explanation for why DottedPairNotation is not prefix: the dotted pair is a representation of the list, whereas the prefix notation is the use of the list itself as a representation of a function call. To put it another way, the dotted pair and the function call exist on different meta-levels of representation. When you write:

 (a . b)

you are representing a cons cell whose CAR refers to the symbol 'a, and whose CDR refers to the symbol 'b. In box notation,

  --- ---
 | * | * |->b
  --- ---
   |
  \ / 
   a

Whereas when you write

(factorial 3)

You are representing a list whose first cons cell's CAR points to the symbol 'factorial, and whose CDR points to a second cons cell; the second cons cell in turn points to the symbol 3 in it CAR and the null value in it's CDR:

   --- ---     --- ---
  | * | * |-> | * | * |-> nil
   --- ---     --- ---
    |           |
   \ /         \ /
 factorial      3

Indeed, the conventional list representation is simply SyntacticSugar for the fully DottedPairNotation list

 (factorial . (3 . nil))

So where does the EssExpression prefix notation come into all of this? Simply put, it doesn't. Tthough the list representation itself does make the conventional Lisp function notation particularly simple implement, and provides several notational advantages, the representation of functions as lists is a completely orthogonal issue to the representation of the lists themselves,. - JayOsako

Yes and no. There's no absolute reason why it couldn't be prefix:

  (. factorial (. 3 nil))

...to represent the list (factorial 3)

So although obviously what you said is correct (aside from some qualms I have about your comments about "levels", "meta-levels", and "representation"), I don't really see that it is relevant to the newbie question about why it's not prefix.

It's an accident of history, as with most notations.

You are correct, of course; I'll concede the point of argument. What I gave was a post hoc justification for why they are different, not an explanation for why they were not the same in the first place. Further, I would be interested in hearing your concerns with the 'representation' terminology, especially if it might correct any misunderstanding I have. - JayOsako

Well...whether the list notation and the dotted pair notation are on the same level or on different levels is not as clear cut as the syntactic-sugar view of dotted-pair implies. You pointed out that you can regard them as being different levels, but I think you can also regard them as the same level: they're both ascii representations, and both are translated into a CONS cell implementation. They are typically translated independently, in fact; lists are usually translated directly into CONSes, not translated first into dotted-pairs that are then translated into CONSes.

Mathematical treatments that deal with M-syntax as the abstract form, and ASCII S-expressions as the concrete form encoding the M-syntax forms, will regard the M-syntax as level 1 and the S-expression ASCII forms as level 2, so both dotted-pairs and lists are on the same level there.

And ultimately this gets into the question of which things are not representations; outside of Platonic realms of belief, the symbol grounding problem (as well as views of mathematics as theorem proving via Semi-Thue rule/string rewriting systems) implies that everything is a representation, and that the ultimate referrent is ineffable. Almost all real numbers are ineffable, but we get by quite well with merely computable numbers. We model the ineffable with effable representations/models, and there are an infinite number of possible models, and the number of levels of representation within each potential model varies. Which boils down to saying that whether things are on the same level or not is a pragmatic issue of choice of model, rather than of a mathematically derivable truth valid across all models.

This probably is not a very interesting comment compared with what you probably thought I had in mind, but now you know what I meant by "qualms". :-) Since it's wildly divergent from the page topic, I guess DeleteWhenCooked. -- dm

CategoryLisp EssExpressions CategoryLanguageFeature