Considering that (1 2 3) is just sugar for (1 . (2 . (3 . nil))) modern lisp programmers find many practical uses for dotted lists.
In this case the implementation and interface are so intertwined that it seems difficult (impossible?) to change one without significantly changing the other. As absz pointed out, car, cdr, cons would have to be rethought and redesigned or simply replaced.
If you get rid of cons/car/cdr I don't think you really have lisp anymore. That's not to say non-lisps are dumb or useless, but when you set out to create a better lisp you should at least create a lisp.
I think that a sequence abstraction, à la Clojure[1,2], is a nice idea though.
Neh, what I meant was, you can have a thing that quacks like a list and never see the need for a dotted pair.
That can be hidden below the abstraction. See, case in point, lists/arrays in Ruby, which are more or less lists without the car and cdr part. Although, you do get a 'nil' if you access beyond the end of the array. ;-)
Ruby lists can quack? Bah, let me know when they can mate, that's when you know you have the same species: ie, can two Ruby more-or-less lists have shared structure, formed say by ruby-consing a different element onto the same list?
And ducks can nest. How about Ruby lists? I have always thought the language should have been called Trep, for Tree Processing language. Can I build a Ruby tree and then quickly flatten by juggling some Ruby ducktails?
As for "That can be hidden below the abstraction", OK, now you have a duck: moving smoothly on the surface and paddling like crazy beneath.
The whole comparison just seems (sorry on more levels than one) daffy.
Indeed, you are correct. Ruby[1] doesn't have "native" lists, it has native arrays. Observe:
irb(main):001:0> [].class
=> Array
There is no Ruby cons, nor Ruby car, nor Ruby cdr. There is y.unshift x or [x] + y for cons (though these cannot constructed "dotted Arrays"), arr[0] or arr.first for car, and arr[1..-1] for cdr, but they denote no structure-sharing. However, flattening would merely be arr.flatten—of course it doesn't work by cdr-juggling, but that's because there are no cdrs.
I'm not really sure what the grandparent post means: "lists without the car and cdr part"? That sounds to me like a very good definition of an... array![2]
Also, that set of duck puns/references was fantastic. Well done.
[1]: Which is a very nice language.
[2]: Well, without the O(1) access time, but I digress.
I can take no credit -- they just popped out of my keyboard. There must be some poorly understood connection between algorithms, data structures, and waterfowl.
Actually, they (the infamous "they") did a study, and apparently, ducks are the funniest animal. Take that with as large a grain of salt as you think is appropriate :)
I use them to build trees, two-sided lists, when I need to encapsulate a value (e.g. to dinsinguish between nil-the-boolean and nil-the-empty-list). For all those things, opaque lists or hashes could be used, too.
But the main use of dotted lists is for recursively-built and recursively-explored lists :
(def foo (a b)
(if a
(cons (car b) (foo (cdr b))
nil)
and relatives appear in so much of my code... I don't think I would like to see dotted pairs go away. And if you don't like them, you can always use (list ...), (l 0), (l 1), (last l), rev, ... and not care about actual implementation.
I know, I know, I just asked this question b/c I saw someone else's post about dotted pair containing lists (old timers would say "s-expressions") not working properly in some cases in arc, and I having noodled around implementing lisp in ruby recently, and having stubbed my toe on implementing cons after having chosen arrays as the underlying implementation of lists, I thought I'd throw this out there and see what people had to say.
One use of dotted lists is the degenerate case of a dotted pair: (cons 'a 'b). Slightly nicer for representing a pair than a complete list (though less so with the lst.n syntax). But it seems to me like they're important to have because of what a list is. A list has a car and a cdr: (car (cons x y)) -> x, and (cdr (cons x y)) -> y. If you remove dotted lists, you break that valuable identity. Would (cons 'x 'y) be an error, or implicitly create the list '(x y)? Either way, there's inconsistency that will come back to bite you.
I see that; it just seems like they don't have a huge amount of practical utility. I mean, they're nice to have, but when I was programming in CL, one rarely if ever saw them in production code.
But I think you're right -- they have that "feeling the bits between your toes" character.
They're not necessary in order to have a list abstraction, but they are the minimal thing you could build lists out of.
The whole point of the axiomatic approach is that you don't program in the axioms themselves. But you still do want to have the things you do program in built out of the smallest set of axioms.
Evaluation of (cons x '()) yields (x), but (cons x nil) yields (x nil) because nil is treated as a boolean value when evaluated instead of as an empty list. The cons of two atoms in newLISP does not yield a dotted pair, but rather a two-element list. The predicate atom? is true for nil, but false for the empty list. The empty list in newLISP is only an empty list and not equal to nil.
A list in newLISP is a LISP cell of type list. It acts like a container for the linked list of elements making up the list cell's contents. There is no dotted pair in newLISP because the cdr (tail) part of a LISP cell always points to another LISP cell and never to a basic data type, such as a number or a symbol. Only the car (head) part may contain a basic data type.
This is why Arc is better than newLISP. The only reason I can think of for this is that newLISP is trying to protect newbies from the actual structure of lists by telling them that cons adds an element to the beginning of a list, car gets the first element of a list, and cdr gets the rest of the list.
Arc doesn't try to protect people from these kinds of things. It's not like we can't handle the real meaning of cons.
Here's an implementation of lists which work mostly as arrays, until you actually use scdr. This seamlessly handles dotted lists and is optimized for proper lists.
