[Ecls-list] Re: HEADS UP!

[Juan Jose Garcia Ripoll]

On Wednesday 09 April 2003 00:45, Paul F. Dietz wrote:
> Be careful -- the general subtypep problem is NP hard, so you may
> have introduced scalability problems.  You should have a 'give up'
> counter that aborts subtypep after enough work is done (count the number
> of AND or OR type terms traversed, perhaps.)

The interesting thing about Baker's approach is that there is no scalability 
problem. Performing a SUBTYPEP takes O(2N^2) operations, where N is the 
number of elements in the type (and maybe pre-registered types). The routine 
first proceeds to register all types found in the type specifier, creating a 
binary tag for each of them. In a second row, the tree is traversed again, 
but this time the already created tags are LOGORed, LOGANDed, LOGNOTed, etc. 
An outcome of 0 means NIL (no type intersection).

The implementation I made simply stops at the first part (registering types), 
when either (SATISFIES) or a wrong type specifier is found. I figure I can 
improve it, so that it properly handles (SUBTYPEP '(MEMBER A B) '(SATISFIES 
SYMBOL)) and things like that -- it currently gives up, just like CMUCL.

Juanjo