[Ecls-list] Re: HEADS UP!
Juan Jose Garcia Ripoll
worm at arrakis.es
Thu Apr 10 07:35:08 UTC 2003
Last night may connection to SourceForge's CVS was down and I could not
upload the patches until this morning.
On Thursday 10 April 2003 00:44, Paul F. Dietz wrote:
> Juan Jose Garcia Ripoll wrote:
> > 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).
> Baker worked on his algorithm just before the CONS type specifier was
> added. With (CONS ... ...) types, a type specifier of size N can
> specify a type with exponentially many (in N) elements. For example:
> (CONS BIT (CONS BIT (CONS ... (CONS BIT NULL) )))
I am aware of this problem. In the current implementation I have
intentionally removed compound CONS types from SUBTYPEP and added them to
TYPEP. The SUBTYPEP routine silently gives up. It is nothing terribly bad
because ECL has never been able to handle CONS types.
As for the future, I think I know how to extend Baker's algorithm for CONS
types -- the basic idea would be to use lists of tags, deferring the OR
operations to the very end. However, my fear is that this would bloat ECL :-/
I'll keep thinking on that.
More information about the ecl-devel