Re: Types in CL

[NGALL@G.BBN.COM]

    Date:     Thu, 17 Dec 87 10:48:05 PST
    From:     Jeff Barnett <jbarnett@nrtc.northrop.com>
    
    ...
    PROBLEM I.  Assume that the following have been evaluated
	    (DEFTYPE T1 '(ARRAY T2 1))
	    (DEFTYPE T2 '(NOT T1))
    Let A be a one-dimensional array of size 1 such that (EQ A (AREF A 0)).
    What should the value of (TYPEP A 'T1) be?
    ...
Yes, a problem. CLtL should specify that the result of a call to TYPEP
that causes an identical subcall (i.e., it loops) is undefined.  Here
is a related (but perhaps better motivated example):

(DEFTYPE TREE (LEAF-TYPE) `(OR ,LEAF-TYPE (VECTOR TREE 2)))
(SETF CIRC-TREE '#(NIL NIL))
(FILL CIRC-TREE CIRC-TREE)
(TYPEP CIRC-TREE '(TREE INTEGER)) => {undefined}

This same problem affects CLtL's definitions of LIST, TRUE-LIST, and
DOTTED-LIST on pg. 28: A circular list is a LIST that is not a TRUE-LIST or
a DOTTED-LIST...

    PROBLEM II.  Assume that the following return non-NIL
	    (SUBTYPEP 'T1 'T2)
	    (SUBTYPEP 'T2 'T3)
    The question is what are the subtypes of the type specifier
	    (FUNCTION (T2) T2)
    I think that the answer is
	    (FUNCTION (T3) T1)
    because the type-specific contract of an F in type (FUNCTION (T2) T2) is
    to (1) accept as arguments objects in T2 and (2) return objects in T2.
    Therefore, an F that accepts objects in T3 (which includes all of T2)
    and returns objects in T1 (all of which are in T2) satisfies that
    contract.  An F in (FUNCTION (T1) T3) does not because (1) it does not
    promise to handle an object in T2-T1 and (2) may return an object in
    T3-T2.  Therefore,
	    (SUBTYPEP '(FUNCTION (T3) T1) '(FUNCTION (T2) T2))
    ...
The type specifier (FUNCTION ...) is not acceptable to TYPEP (pg. 47),
therefore it is not acceptable to SUBTYPEP (pg. 72).

-- Nick