Re: [Scheme-reports] Query - Pairs and Lists

[Per Bothner <per@x>]

On 03/04/2012 08:43 AM, Ray Dillinger wrote:
> Passing a structure which is not a list to a procedure that
> is specified to work on lists gives a non-specified result.
>
> Implentations may signal an error, but the cost of doing so
> (especially in the case where there is no error) would be
> high.
>
> So high, in fact, that *guaranteeing* a signaled error would
> invalidate the programmer's model of the time complexity
> of the code.

You could have a bit or separate typecode for non-list cons
cells - for example LIST_PAIR vs NON_LIST_PAIR.  Cons creates
a LIST_PAIR if the cdr is '() or a LIST_PAIR, and creates a
NON_LIST_PAIR otherwise.  set-cdr! checks the new cdr if it
is a NON_LIST_PAIR *or* if the set-cdr! would create a cycle.

In that case checking for a pure list is O(1).  Only set-cdr!
becomes order-of-magnitude slower, but it's not a function
we want to encourage use of anyway.

Note that NON_LIST_PAIR is conservative: You might create
a non-list, and then a future set-cdr! might change it back
to a true list.  One might accept that as OK (i.e. false
raise of an exception), or just use NON_LIST_PAIR as an indicator
that a slow scan is needed.  For simplicity I' be tempted to
say that once a pair is a NON_LIST_PAIR it is forever tainted.

But I'm not sure this is all worth it, though it would be
nice to have list? be an inexpensive type-check.  In that case
I'd be tempted to go further: Have two kinds of cons operator:
cons creates a LIST_PAIR *and* makes the cdr immutable;
impure-cons creates a NON_LIST_PAIR with a mutable cdr.  Still,
that's a big departure from tradition.
-- 
	--Per Bothner
per@x   http://per.bothner.com/

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