On Wed, Apr 10, 2002 at 02:17:45PM +0100, Christophe Rhodes wrote:
> Here's another slightly dodgy type system patch that could probably do
> with review.
> I thought that I would attack the remaining major type system bug (bug
> 91, described in BUGS as
As I said last week, I wouldn't have any detailed response to this
'til this week.
> (subtypep '(or (integer -1 1)
> '(or (rational -1 7)
> (integer -1 1))) => NIL, T
> This I felt was especially bad, as we weren't just expressing
> uncertainty, we were returning a wrong result.
> As you can gather from this, there were (again) some nasty surprises
> along the path; effort and tinkering were required both to get it to
> compile, and then to get it to be able to compile itself. It has now
> done both, and I'm reasonably happy with it. Thoughts?
I'm pretty happy with the patch. It's rather nice that the type system
no longer confidently gives a wrong answer. I'm not 100% sure that no
other problem will be exposed by the changes but the certainty of
fixing a wrong answer makes up for a fair amount of anxiety about
Messing With Things Better Left Alone.
> RCS file: /cvsroot/sbcl/sbcl/src/code/typedefs.lisp,v
> retrieving revision 1.15
> diff -u -r1.15 typedefs.lisp
> --- src/code/typedefs.lisp 8 Apr 2002 22:00:39 -0000 1.15
> +++ src/code/typedefs.lisp 10 Apr 2002 13:11:17 -0000
> @@ -107,6 +107,8 @@
> (multiple-value-bind (subtypep2 win2) (csubtypep type2 type1)
> (cond (subtypep1 type1)
> (subtypep2 type2)
> + ;; FIXME: I don't understand this clause. Can someone
> + ;; please explain? - CSR, 2002-04-09
> ((and win1 win2) *empty-type*)
> (t nil)))))
> (defun hierarchical-union2 (type1 type2)
It's old CMU CL code (though the CMU CL code called this
VANILLA-INTERSECTION instead of HIERARCHICAL-INTERSECTION). Isn't that
I thought about it for a while and maybe I understand it now. The
short version is:
For hierarchical types, which are the kinds of things which we should
be calling HIERARCHICAL-INTERSECTION2 on, then when TYPE1 is not
a subset of TYPE2 and TYPE2 is not a subset of TYPE1, then they don't
overlap at all.
So perhaps that code should look something like
(defun hierarchical-intersection2 (type1 type2)
(multiple-value-bind (subtypep1 win1) (csubtypep type1 type2)
(multiple-value-bind (subtypep2 win2) (csubtypep type2 type1)
(cond (subtypep1 type1)
((and win1 win2)
;; For hierarchical types (which are of course the only
;; kinds of things which we should be calling
;; HIERARCHICAL-INTERSECTION2 on!) then when TYPE1 is not
;; a subset of TYPE2 and TYPE2 is not a subset of TYPE1,
;; there is no overlap between TYPE1 and TYPE2 at all.
The hierarchicalness of the types passed to HIERARCHICAL-INTERSECTION2
is implicit. As in the comment above DELEGATE-COMPLEX-INTERSECTION2,
;;; These functions are used as method for types which need a complex
;;; subtypep method to handle some superclasses, but cover a subtree
;;; of the type graph (i.e. there is no simple way for any other type
;;; class to be a subtype.) There are always still complex ways,
Probably that comment should be rewritten as
;;; there is no simple way for any other type class to intersect
which is a stronger statement, and still true. Also it might be
reasonable to make hierarchicalness explicit in the representation of
types, with a CTYPE-HIERARCHICAL-P slot or some such thing.
(Incidentally, my CTYPE-MIGHT-CONTAIN-OTHER-TYPES? slot name should
probably be CTYPE-MIGHT-CONTAIN-OTHER-TYPES-P. (I've been doing too
much coding on another project with post-1977 naming conventions
recently.:-) I'll probably put this in the next patch I make.)
This hierarchicalness is a common (but not universal) property of
things in the Common Lisp type system. It is violated by e.g.
SIMPLE-ARRAY and (VECTOR T), which don't have a hierarchical
relationship with each other.
| +------------------+ |
| ARRAY | | |
| | SIMPLE-ARRAY | |
| | | |
| +------------+---------------+ | |
| | | | | |
| | | SIMPLE-VECTOR | | |
| | (VECTOR T) | | | |
| | +---------------+--+ |
| | | |
| +----------------------------+ |
And of course it's violated by the various interval types like
(INTEGER -10 10) and (INTEGER 0 20). But lots of Common Lisp types
are hierarchical: If HASH-TABLE isn't a subset of CONS, then it doesn't
overlap at all (and similarly NUMBER and ARRAY and STRUCTURE-OBJECT
and CLASS and CHARACTER, but not STREAM, since some STREAMs are
STRUCTURE-OBJECTs but Gray streams aren't).
William Harold Newman <william.newman@...>
Users like this are like a mongoose backed into a corner: with its back to
the wall and seeing certain death staring it in the face, it attacks
frantically, because doing something has to be better than doing nothing.
This is not well adapted to the type of problems computers produce.
PGP key fingerprint 85 CE 1C BA 79 8D 51 8C B9 25 FB EE E0 C3 E5 7C