Scheme language standardization process
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