[LISPWORKS][Common Lisp HyperSpec (TM)] [Previous][Up][Next]


Issue DOTTED-LIST-ARGUMENTS Writeup

Forum:		Public Review

Issue: DOTTED-LIST-ARGUMENTS

References: Loosemore's public review comment #10 (X3J13/92-1310)

Pitman's public review comments #37, #38, #39

(X3J13/92-2737, -2738, -2739)

Issue APPEND-DOTTED (retracted)

Issue APPEND-FIASCO (withdrawn)

Issue APPEND-ATOM (withdrawn)

Issue REMF-DESTRUCTION-UNSPECIFIED (passed)

Issue LAST-N (passed)

Category: CLARIFICATION, CHANGE

Edit history: 23 Dec 1992, Version 1 by Loosemore

04 Feb 1993, Version 2 by Loosemore (comments from Barmar)

Status: Proposal CLARIFY passed (6+3)-2 on letter ballot 93-302.

Problem description:

The next-to-last paragraph on page 14-2 (in draft 12.24) says that

functions that take list arguments should be prepared to signal an

error if they receive dotted list arguments, except as explicitly

stated otherwise. But many of the descriptions of the functions in

chapter 14 do not explicitly state otherwise, where they clearly ought

to. (In some cases, the "correct" behavior is implied by notes or

examples, which are not binding parts of the standard.) For example,

surely the committee did not intend to make primitive accessors such

as CAR and CDR fail on dotted lists!

Similarly, there are exceptions missing for the rule stated in the

last paragraph on page 14-2 (the consequences are undefined if

a circular list is passed).

For the functions which operate on trees, there is a further problem.

Some of the arguments are described as "objects", and others are

described as "lists", which I think is incorrect -- an atomic tree

argument should also be OK for functions such as SUBST and SUBLIS.

The dotted-list prohibition should clearly not apply to the tree

functions. But since tree functions recursively descend both the

car and cdr chains of a cons, there should be a prohibition against

circular tree structure in the arguments to these functions, not

just circular list structure.

Finally, there is confusion about whether atoms may be considered

degenerate dotted lists in some contexts.

Proposal (DOTTED-LIST-ARGUMENTS:CLARIFY):

(1) Add to page 14-2 a third paragraph:

Except as explicitly stated otherwise, for any standardized

function that is required to be a tree, the consequences are

undefined if that tree is circular.

(2) Clarify that association lists, property lists, and lists

that are treated as sequences must be proper lists.

(3) Change the glossary definitions of "dotted list" and "list" to

clarify that atoms are not considered dotted lists.

(4) Clarify the nature of list arguments to the functions in chapter

14, as follows:

CAR, CDR and friends: the argument "x" is permitted to be dotted

or circular.

Rationale: These are primitive accessors.

COPY-TREE: the argument "object" is a tree (not an object).

SUBLIS, NSUBLIS: the "tree" argument is a tree (not a list).

SUBST and friends: the "tree" argument is a tree (not a list).

TREE-EQUAL: the arguments "object1" and "object2" are trees

(not objects).

Rationale: This makes all the tree functions consistent.

COPY-LIST: the argument "list" may be dotted but not circular.

Rationale: This is what CLtL said.

LIST-LENGTH: the argument "list" may be circular but not dotted.

Rationale: It's supposed to detect and return NIL for

circular lists.

POP: the "place" argument is permitted to evaluate to a dotted or

circular list.

PUSH: the "place" argument may evaluate to any object (not just

a list).

Rationale: This follows from the equivalences given in the notes.

FIRST and friends: the argument "list" may be dotted or circular.

Rationale: These functions are commonly implemented as chains

of CAR and CDR operations.

NTH: the argument "list" may be dotted or circular. Note that

the references to the length of the argument list in the

description are incorrect, since this concept doesn't make

sense for dotted lists. The right thing to do is simply to

define (NTH n list) = (CAR (NTHCDR n list)).

Rationale: The notes for FIRST and friends say that

(FIFTH x) == (NTH 4 x). This also makes NTH and NTHCDR

consistent.

ENDP: the argument "list" may be dotted or circular.

Rationale: This function only cares whether the argument is

NIL/a cons/something else.

NCONC: the last "list" argument may be any object. The remaining

"lists" may be dotted but not circular.

Rationale: This follows from the equivalence in the description

(from issue REMF-DESTRUCTION-UNSPECIFIED).

NRECONC: the argument "list1" must be a proper list.

The argument "list2" can be any object (not just a list).

(The example showing "list1" as a dotted list is incorrect.)

Rationale: This follows from the equivalence in the side effects

section, which was added by issue REMF-DESTRUCTION-UNSPECIFIED.

(NREVERSE is a sequence function.)

APPEND: the last "list" argument may be any object.

The remaining "lists" must be proper lists.

Rationale: Allowing any object as the last argument came from

CLtL. The inconsistency of the remaining arguments compared to

NCONC was a deliberate decision by X3J13 (issues APPEND-DOTTED, etc).

REVAPPEND: the argument "list1" must be a proper list.

The argument "list2" can be any object (not just a list).

(The example showing "list1" as a dotted list is incorrect.)

Rationale: This follows from the equivalence in the notes section.

(REVERSE is a sequence function.)

BUTLAST, NBUTLAST: the argument "list" may be dotted but not

circular. (The functions should complement LAST by counting

conses, not elements.)

Rationale: An obvious identity is

(BUTLAST list n) == (LDIFF list (LAST list n))

The intent of issue LAST-N was clearly to make LAST and BUTLAST

complementary.

LAST: the argument "list" may be dotted but not circular.

Rationale: This follows from the definition in the notes section.

LDIFF, TAILP: the "list" argument may be dotted. The "sublist"

argument may be any object (not just a list). Both arguments may

be circular lists only if (TAILP sub-list list) is true.

Rationale: This is already stated for TAILP and the two functions

are clearly related.

NTHCDR: the "list" argument may be dotted or circular.

Rationale: The examples show use on a dotted list, and the

function will clearly still terminate if passed a circular list.

REST: the "list" argument is permitted to be dotted or circular.

Rationale: compatibility with CDR and FIRST.

MEMBER and friends: the "list" argument must be a proper list.

INTERSECTION, NINTERSECTION: the "list-1" and "list-2" arguments

must be proper lists.

ADJOIN: the "list" argument must be a proper list.

PUSHNEW: the "place" argument must evaluate to a proper list.

SET-DIFFERENCE, NSET-DIFFERENCE: the "list-1" and "list-2"

arguments must be proper lists.

SET-EXCLUSIVE-OR, NSET-EXCLUSIVE-OR: the "list-1" and "list-2"

arguments must be proper lists.

SUBSETP: the "list1" and "list2" arguments must be proper lists.

UNION, NUNION: the "list1" and "list2" arguments must be proper lists.

Rationale: This makes all the functions that operate on lists as

sets consistent.

MAPC and friends: the "list" arguments must be proper lists.

Rationale: The description makes clear that the lists are treated

as sequences.

Current practice:

Loosemore thinks the only item that is likely to cause compatibility

problems is explicitly requiring BUTLAST to work on dotted lists:

currently at least CMU CL and AKCL signal an error, but it works

in Lucid.

Cost to implementors:

This proposal should probably make it easier for implementors to do

the right thing. Given the previous addition of the requirement that

implementations "should be prepared to signal" errors about dotted lists

and tighter restrictions about signalling TYPE-ERRORs for incorrect

arguments, all implementors probably need to reexamine the definitions

of these functions for conformance anyway.

Cost to users:

There may be a few currently working programs that will stop working.

Aesthetics:

This whole problem is messy to deal with.

Editorial impact:

Substantial, but it needs to be done to correct obvious errors.

Discussion:

Loosemore notes that there are a few more functions which could

reasonably be defined to work on atoms as degenerate dotted lists

(notably, TAILP and LDIFF) but that current practice is to signal

an error, so the proposal does not include these.


[Starting Points][Contents][Index][Symbols][Glossary][Issues]
Copyright 1996-2005, LispWorks Ltd. All rights reserved.