[Scheme-reports] Query - Pairs and Lists

[Stephen Leach <sfkleach@x>]

Hi all,

I have a small question on the phrasing of the section (6.4) Pairs and Lists. We have the clear definition that:

> [From 6.4] A chain of pairs not ending in the empty list is called an improper list. Note that an improper list is not a list. 

But this doesn't seem consistent with some of the actual uses of the phrase list in the function definitions. For example, list-tail is described as applying to a list rather than a proper list or improper list. However the example implementation is not constrained to work on a proper list. So the question arises, is that a feature you can rely on?

A similar question applies to list-ref and list-set! - can they reliably be applied to an improper list? It seems completely implausible to me that there would be such a constraint. However, I was quite surprised to find that Guile, for example, does signal an error for memq for an improper list - which seems to incur a considerable cost - but MIT/GNU Scheme does not. So different implementors have made inconsistent choices.

Strictly speaking the draft clear: one cannot reliably use list-tail, list-ref etc on an improper list as the result is unspecified. I just wanted to check that this was the intention as it strikes me as a strange thing not to determine.

In a slightly pedantic vein I have a further query. We have the definition of (list-copy LIST) which does support improper lists. However the phrasing is not in terms of improper versus proper lists. In passing I note that the closing parenthesis in the text is missing.

> [From 6.4] Returns a newly allocated copy of the given LIST. Only the pairs themselves are copied; the cars of the result are the same (in the sense of eqv? as the cars of LIST. If the last pair of LIST has a cdr which is not the empty list, the last pair of the result does, too. An argument which is not a list is returned unchanged.

Since the type of the formal parameter LIST is implied by the use of the name "LIST", but a chain of pairs not ending in the empty list is not a list. Therefore the suggestion that "If the last pair of LIST has a cdr which is not the empty list" is a contradiction.

I suggest that it would be neater to describe it in terms of a chain-of-pairs and the terminus of the chain.

> [From 6.4]  (list-copy CHAIN) procedure 
> 
> Returns a newly allocated copy of the given chain-of-pairs. Only the pairs themselves are copied; the cars of the result are the same (as in eqv?) as the cars of CHAIN. The terminus of the copy is the same (as in eqv?) as the terminus of CHAIN.

The same kind of issue applies to append. 

> Returns a LIST consisting of the elements of the first list followed by the elements of the other LISTs.

Having implied all the arguments are lists, it then promptly contradicts itself with: "The resulting list is always newly allocated, except that it shares structure with the last list argument. The last argument may actually be any object"

My first niggle is that this implies there is a last argument and hence there is at least one argument, contradicting the signature. My second niggle is that this states the result is newly allocated but this is not true in the case of 1 or 0 arguments. 

I would have thought that the relevant definition should be more like this:

> (append)
> (append LIST... CHAIN )
> 
> The first form of append returns the empty list. The second form returns a chain whose elements are the elements of the LISTs and the final CHAIN in order. The result will share the entire chain-of-pairs of the final CHAIN. All the other pairs of the result will be newly allocated.



Steve
_______________________________________________
Scheme-reports mailing list
Scheme-reports@x
http://lists.scheme-reports.org/cgi-bin/mailman/listinfo/scheme-reports