[Gcl-devel] Re: subtypep tests

[Paul F. Dietz]

Camm Maguire wrote:
> Greetings!  I need a more powerful subtypep for the compiler, and it
> appears I have one basically implemented.  I'd like to make use of the
> second value to indicate whether the first type is in the complement
> of the second type -- i.e. nil t means the types are disjoint (so that
> the corresponding typep can return a constant nil), and I'd
> like to return nil nil in cases of overlap even when I know the answer
> for sure.  I think this should comply with the standard.  Please
> correct me if wrong.  If this is the case, there are a number of tests
> which insist on nil t and won't accept nil nil (like many others do),
> e.g. (subtypep '(integer 0 10) '(integer 0 (10))).  Is this
> intentional? 

If SUBTYPEP returns nil t, that means the first type is not a subtype
of the second.  It does not mean they are disjoint.

The returning of true in the second position is required in the
case you mention:

  "subtypep never returns a second value of nil when both type-1 and
   type-2 involve only the names in Figure 4-2, or names of types
   defined by defstruct, define-condition, or defclass, or derived
   types that expand into only those names."

where 'involves' is defined by:

  "(A type specifier `involves' such a symbol if, after being type
   expanded, it contains that symbol in a position that would call
   for its meaning as a type specifier to be used.)"

The second value tells us whether SUBTYPEP has 'given up' in trying
to determine if type-1 is a subtype of type-2, and the standard
restricts when it is allowed to give up.

You asked earlier if Baker's algorithm were still considered
state of the art.  Baker's paper on that algorithm came out just
before the CONS compound type constructor was added to Common Lisp.
With this, Baker's algorithm can take exponential time.

        Paul