From: Juan Jose Garcia Ripoll <worm@ar...>  20030408 15:19:47

Hi, I have almost finished the new implementation of SUBTYPEP, and intend to=20 commit it to the CVS repository tomorrow afternoon. This implies severe=20 changes on the system, and, even though the new implementation solves man= y=20 errors (There will be now only about 700 failures in the GCL testsuite),= =20 there might pieces of ECL which still rely on old quirks. So, I have tagged the CVS, as it is (with several fixes to the LOG*=20 operations), as STABLE. Therefore, ++++++++ +++ Please notify before tomorrow afternoon any problem to build ECL! ++++++++ Weak hearts should stay with this release until otherwise stated. As a side note, the new implementation is based on Henry Baker's paper=20 (http://home.pipeline.com/~hbaker1/). However, I did not use separate tag= s=20 for different type classes (arrays, intervals, classes, etc), but rather = keep=20 them together. Furthermore, handling of intervals is a bit more clever: the basic elemen= t is=20 the interval (REAL a *) (Where "A" may be *, an integer, or a list with o= ne=20 integer), and all other intervals are based on this: INTEGER =3D> (AND INTEGER (REAL * *)) (RATIO 2 3) =3D> (AND RATIO (REAL 2 *) (NOT (REAL (3) *))) (INTEGER 0 2) (AND INTEGER (REAL 0 *) (NOT (REAL 3 *))) etc. When facing a (SATISFIES whatever) or an unknown symbol, the algorithm si= mply=20 gives up. There are NO OTHER situations in which the routine does not giv= e a=20 definitive answer. I will probably add a flag, so that the system may sig= nal=20 a correctable error when unknown type specifiers are found. The best thing about having reimplemented SUBTYPEP is that now it is poss= ible=20 to do types intersections and type inference accurately, and the compiler= =20 will soon benefit from that! Best regards Juanjo 
From: Paul F. Dietz <dietz@dl...>  20030408 22:44:15

Juan Jose Garcia Ripoll wrote: > When facing a (SATISFIES whatever) or an unknown symbol, the algorithm simply > gives up. There are NO OTHER situations in which the routine does not give a > definitive answer. I will probably add a flag, so that the system may signal > a correctable error when unknown type specifiers are found. 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.) Paul 
From: Juan Jose Garcia Ripoll <worm@ar...>  20030409 08:39:27

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 numbe= r > of AND or OR type terms traversed, perhaps.) The interesting thing about Baker's approach is that there is no scalabil= ity=20 problem. Performing a SUBTYPEP takes O(2N^2) operations, where N is the=20 number of elements in the type (and maybe preregistered types). The rout= ine=20 first proceeds to register all types found in the type specifier, creatin= g a=20 binary tag for each of them. In a second row, the tree is traversed again= ,=20 but this time the already created tags are LOGORed, LOGANDed, LOGNOTed, e= tc.=20 An outcome of 0 means NIL (no type intersection). The implementation I made simply stops at the first part (registering typ= es),=20 when either (SATISFIES) or a wrong type specifier is found. I figure I ca= n=20 improve it, so that it properly handles (SUBTYPEP '(MEMBER A B) '(SATISFI= ES=20 SYMBOL)) and things like that  it currently gives up, just like CMUCL. Juanjo 
From: Paul F. Dietz <dietz@dl...>  20030409 22:43:43

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 preregistered 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) ))) With n BITs, this specifies all proper lists of length n whose elements are 0 or 1. It's not hard to reduce the tautology problem on disjunctive normal form boolean formulas to a subtypep query on cons types. DNF tautology is coNP complete. Paul 
From: Paul F. Dietz <dietz@dl...>  20030409 02:34:09

Juan Jose Garcia Ripoll wrote: > +++ Please notify before tomorrow afternoon any problem to build ECL! I have a successful build (under RedHat 7.3, gcc '2.96'.) Paul 