Re: Why cons *pairs*?

Tom Lord wrote:
I think you are correct. It seems that what "list" meant
to people at that time and place was, specifically, the familiar
linked list. This seems to come from A. Newell, C. Shaw,
and H. Simon's theoretical and practical work on IPL(-*).

I don't know anything about the history of the term "list", but the idea of representing n-tuples using nested ordered pairs is well-known in mathematics, and I suspect it predates computers. It seems reasonably likely that McCarthy would have been aware of it.

So, Pr. McCarthy's statement that "The first problem was
how to do list structure in the IBM 704," probably means
"how to do linked list structure."

I'm not so sure. I'd say the latter is the answer to the former, i.e. that "linked lists" was the representation chosen for list structure. There are also some good reasons to choose that representation -- more below.

So, instead of wondering if cons pairs are an echo of the
704 architecture, it is safer to wonder if they aren't
simply an echo of IPL 2.

I doubt whether many mathematicians were aware of IPL.

So, why not do away with cons pairs, and go with shared sub-vectors?

(Also note that I'm not just asking about how to implement
things, although that is relevant. In Scheme, cons pairs are
enshrined as a disjoint type -- they can not be mistaken for
vectors of length 2. My question isn't so much "shouldn't
we stop writing programs that use ordered pairs?" as it is
"shouldn't our language not enshrine ordered pairs as a
special case, disjoint type?")

There's no particular reason for ordered pairs to be a special case, but what's wrong with them being a disjoint type?

The importance of lists in statically-typed functional languages like ML and Haskell is relevant here. As in Scheme, the reason lists are so important in those languages is that they support recursive processing and inductive reasoning, including inductive proof. That all depends heavily on operations equivalent to car, cdr, and cons.

If you're going to construct such lists out of something, as opposed to providing lists as a built-in abstraction, then constructing them out of an ordered pair type, which supports (operations equivalent to) car, cdr, and cons, makes a lot of sense. There's no historical accident, or concession to the machine, here.

That's a somewhat separate question from whether cons pairs should be replaced by 2-vectors, though. The reason the latter question even arises in Scheme is because both pairs and vectors in Scheme are mutable, and untyped. In mathematics and in statically-typed functional languages, such properties are used to distinguish different kinds of structures. Scheme blurs those distinctions. If the goal is to "model something true and essential", as stated earlier in the thread, then if anything, support for the expression of such distinctions should be improved, rather than abolished.

Anton
.

Relevant Pages

  • Counting combinations of ordered pairs of items without repetition
    ... Assume we have lists of ordered pairs of items, ... choosing a single pair from each list such that no single item is ...
    (sci.math)
  • Re: Ultimate debunking of Cantors Theory
    ... A list and a set are rather different beasts. ... A function is simply a set of ordered pairs. ... The above lists typical representation as a set would be ...
    (sci.math)
  • Re: Ultimate debunking of Cantors Theory
    ... A list and a set are rather different beasts. ... A function is simply a set of ordered pairs. ... The above lists typical representation as a set would be ...
    (sci.math)
  • HashList/MRU for Forth dictionaries
    ... handling Forth dictionaries. ... from one of 16 lists that he would then do a linear search on. ... but the HashList/MRU scheme fares much better than ... measure is to turn it off and see how it affects search performance. ...
    (comp.lang.forth)
  • brad does the neener neener gambit
    ... a faculty member of the College System in Minnesota. ... He made up some lies that he had some reason ... And it was ALWAYS with the strong support of hundreds of other list members. ... ever got any support from other members of lists. ...
    (sci.psychology.psychotherapy)