[Ecls-list] Re: HEADS UP!

[Juan Jose Garcia Ripoll]

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.

Juanjo