Dotted List

[underablackrainbow]

Hello to every one. I've a question for everyone : why dotted list? why they exists?
Can anyone give me a piece of code using a dotted list that cannot be translated without the dot?

I'm currently developing a new Lisp-dialect (actually using dotted lists) and the existance of an atom on the CDR make me some extra checks. I don't know....but I'm considering the idea that "dot" were used when the amount of available memory was very very very small.

Thank you all.

[Ramarren]

why dotted list? why they exists?

For historical reasons related to implementation strategies of early lisps the are no actual lists as a data type in many languages in the Lisp family. The primary building block is a cons, that is, a pair. Lists exist only as a conventional arrangements of pairs. Dotted lists are a syntax for an arrangement of pairs slightly different than a proper list.

Can anyone give me a piece of code using a dotted list that cannot be translated without the dot?

Before attempting to develop a programming language dialect I would recommend learning enough computer science theory to understand the concept of Turin equivalence. And it is not as if this was some kind of Turing tarpit, those are marginally different data structures, and the "dot" is purely syntactic anyway. That said, there is nothing fundamental about using conses as a core data structure.

[underablackrainbow]

Oh, It's not a problem of studying...Really, the interpreter have an evolution of more than 10 years but I've never released it. Actually it use conses in the common way, dotted lists and so on.

It's a little bit difficult to me to explain what I mean, since english is not my mother language. I try. Keep patience.

After Common Lisp, Scheme, Clojure, I've examined newLisp. I don't like it, but this one don't uses the dotted syntax. Why? To simplify the interpreter? Ok ... so if I can't use the "dot" there isn't a "cons" function that really make a proper list. Seem that

(rest (cons 'a b')) return '(b)

so

(cons 'a 'b) is equal to (list 'a 'b)

Deleting the "dot" sintax from the reader, there is no way to make a pair where there's an atom in CDR. Will be sure that CDR will always point to a list. Then, for consistency I cannot print a dotted pair, and I cannot give to the user a function that make it one. At the end of the circle, it's only a rule. The instrument don't give me the possibility to represent a dotted pair but permit me only to make proper lists.

Then I can use proper lists for association lists, tree and other structures based on conses, with the only differences that use extra space to allocate an extra cons cell.

I'm not considering to change internal representations of Conses at the moment. I'm only asking to me (and you ) if today there is a reason to implement new Lisp dialects that use this sintax instead of representing everything with proper lists.

Probably I'm missing the extra code to extract an element from this structures that produce inefficency.

[nuntius]

If you want a CONS structure, then you will need a dotted list notation (or something else that denotes a CONS with a non-list CDR).

Conses are nice; they can be used to build lists, trees, etc. but I'm not sure they're necessary. You could probably build a nice lisp on finger trees (used by Haskell) or the structure used in Clojure (forget which tree). Without CONS as the basis of your list structure, you probably have no need for a dotted notation (or another notation may be natural).

[underablackrainbow]

Yesssssss!!! Is what I mean. Good. Anyway, I don't remove this sintax.

[sylwester]

There is not in any LISP implementation, any case you cannot use proper lists in place of dotted pair. A proper list is of course made with pairs so both will be made out of the same stuff.
There is no problem implementing a LISP dialect without dotted lists. Make sure CONS will fail if second argument is not a list. During design of my own interpreter I also thought of not supporting it but the current design version has it.

Why use them when you don't need lists:
Space effiececy: the list (a b) == ( a . ( b . NIL)) uses TWO conses while (a . b) uses ONE.
Simpler access: (cdr pair) versus (car(cdr list)) (allthough many implementations don't alias cadr to do this it has to follow a pointer twice instead of once)