[Gcl-devel] Re: Calling for top ten ANSI issues ...

[Christophe Rhodes]

"Paul F. Dietz" <address@hidden> writes:

> Camm Maguire wrote:
>
>> OK, I've put in code (not yet committed) in subtypep to coerce symbols
>> to the class they may name if possible, and resolve the subtype
>> relationship according to the class precedence list, i.e. just as
>> subtypep handles class object arguments at present.
>> A few type/class questions:
>> 1) I'm assuming from what I read that the above logic is valid.
>> 2) I'm assuming that there is no analogous logic I can use to process
>>         subtypep relationships between instances of classes
>> 3) Our subtypep function really needs help.  Its mostly a list of
>>         one-off relationships at present.  Do you know of a more
>>         elegant algorithm, likely recursive, to handle non-class type
>>         relationships in subtypep in a more robust fashion?
>
> Getting SUBTYPEP to work well was a lot of work for the SBCL/CMUCL
> developers (the test cases showed up lots of problems there.)

Yes.  More below.

> Baker has an algorithm from the early 1990s that does well, *except*
> on CONS types (where it can take exponential time; the compound CONS
> type was added to the Common Lisp standard shortly after Baker wrote
> this paper.)  ECL uses this algorithm.

I'm not sure, but I think Baker's algorithm _might_ have some problems
with the KEYWORD and ATOM types.  I want to reread his paper at some
point when I have time.

> The exponential cases all have and/or/not in them somewhere,
> though, so it's ok to give up when you see those.  This is an area
> where standards compliance allows the implementation to get away with
> doing very little.  There are many tests in the test suite on subtypep
> that can be passed by either successfully computing the subtypep relationship
> or by failing (returning NIL NIL).

Baker makes the point, quite strongly followed in SBCL, that the
SUBTYPEP is actually mostly an implementation-assisting function, in
that it allows the compiler to reason about the code it's compiling;
it happens to be exposed to the user.  Given this, in SBCL I took the
philosophy that returning NIL, NIL was almost as bad as being wrong,
so we have an "ambitious" SUBTYPEP.  If the SUBTYPEP function is
completely divorced from the internal machinery, then an adjusted
Baker algorithm, giving up quickly in the difficult case, is probably
fine.

Cheers,

Christophe
-- 
http://www-jcsu.jesus.cam.ac.uk/~csr21/       +44 1223 510 299/+44 7729 383 757
(set-pprint-dispatch 'number (lambda (s o) (declare (special b)) (format s b)))
(defvar b "~&Just another Lisp hacker~%")    (pprint #36rJesusCollegeCambridge)