Re: [Gcl-devel] Re: subtypep tests

[Camm Maguire]

Greetings, and thanks for your reply!

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

> 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.
> 

Sigh.  I knew the intended meaning, I just thought I could give up
more easily and make use of the second value.  Personally, I don't see
any use of the second value being T in practical application the way
its defined.

> 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.
> 

OK, so is there something better?  Or a modification for cons?

GCL's compiler makes heavy use of type-and (and soon type-or, which is
now used in gcl_coolectfn.o to some extent), which I noticed Baker
also thought handy.  The idea of orthogonalizing the type space into a
cartesian product, performing boolean sigma algebra ops on it, and
checking for (type-null `(and ,x (not ,y))) to me gives a semblance of
logic to what is otherwise quite a mishmash.  I have noticed that my
implementation is slower, but I haven't paid attention to this yet.  

In sum, I don't need to waste time reinventing the wheel, but I need a
thorough type-and and type-or, the implementation of which should at
least also give me the first return value of subtypep.  What is then
the 'state of the art'?  Perhaps some solid lgpl-compatible
implementation already exists?

Take care,

>       Paul
> 
> 
> 
> 
> _______________________________________________
> Gcl-devel mailing list
> address@hidden
> http://lists.gnu.org/mailman/listinfo/gcl-devel
> 
> 
> 

-- 
Camm Maguire                                            address@hidden
==========================================================================
"The earth is but one country, and mankind its citizens."  --  Baha'u'llah