[Ecls-list] Re: HEADS UP!
Juan Jose Garcia Ripoll
worm at arrakis.es
Wed Apr 9 01:40:08 UTC 2003
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.
More information about the ecl-devel