type-of

[Robert W. Kerns <RWK@YUKON.SCRC.Symbolics.COM>]

I'm considering writing a paper on the type system and the role of
SUBTYPEP.  (I've been working on an extension of the type system for the
last year or so).  Your question really relates to one of the core
issues of this topic.

I can think of a lot of analogies for TYPE-OF and SUBTYPEP,
and maybe I'll develop one of them for the paper, but they
all boil down to SELECTION of an object, and matching the
object with something which ACCEPTS objects.  The exact
token which passes between the object and the acceptor of
objects doesn't matter, so long as the information is there!
Viewed in the abstract, it should be clear that the more
information this token has, the more flexibility the acceptor
has in deciding whether this object is suitable.

The tokens, of course, are the type specifiers.  The
acceptor can be TYPE-CASE, CHECK-TYPE, or any function
which handles only a certain range of types.  And SUBTYPEP/TYPEP
is what answers the question "is this object suitable."
Given this model, there is no such thing as "too specific"
an answer from TYPE-OF.  On the contrary, the concern should
be with "not specific enough".

To address your specific points:

    Date: Mon, 17 Nov 86 18:06:12+0900
    From: Masayuki Ida <z30083%ccut.u-tokyo.junet%utokyo-relay.csnet@RELAY.CS.NET>

    Is it absolutely impossible to define TYPE-OF more specific than 
    the current CLtL ?
    I have been seen many problems derived from the underspecification of TYPE-OF.
    As one of the users of PCL since Feb. on several different CommonLisp 
    implementation, I felt PCL might get more portability if TYPE-OF can be more defined.
TYPE-OF's >>lack<< of restriction is essential for
portability.  It is SUBTYPEP which needs to be more
carefully defined.

    I had sent a mail to several key persons about the possiblity of new definition of TYPE-OF,
    but thier answers were pesimistic to do so.
    The main reason of them is 
    'it is impossible or very hard to determine "the most-specific type"
    among lots of CL implementations.'
It is wrong and impossible to define "the most-specific type".
What you want to specify is the "least-specific type".  I.e.
we should specify that it must return a type *at least as specific as* X.
X is then the LEAST-SPECIFIC type which TYPE-OF may return; it may,
however, return something a good deal more specific.  And it should,
if at all possible.

For example, TYPE-OF of a number must return one of INTEGER, COMPLEX, FLOAT,
RATIO, or one of their subtypes (if any), or some other subtype of NUMBER.
However, it is not good enough for it to return NUMBER.

However, it does not make sense to specify that TYPE-OF return one
of FIXNUM or BIGNUM, rather than INTEGER; a system which implemented
all numbers as "BIGNA" would be correct, if inefficient.

And a system might reasonably have two kinds of BIGNUM's, NEGATIVE-BIGNUM and
POSITIVE-BIGNUM.  If you specify that TYPE-OF return just BIGNUM,
you prevent any program from distinguishing between them, when it
may be the program's advantage to make the distinction.

By over-specifying TYPE-OF, you can eliminate any implementation
flexibility or extensibility.

Along with this flexibility in what TYPE-OF returns goes a requirement
that SUBTYPEP know the answer when comparing the result of TYPE-OF and
whatever "least-specific type" that is specified.  For example, if
TYPE-OF returns POWER-OF-TWO-POSITIVE-BIGNUM, SUBTYPEP must return
the values T T when asked if this is a subtype of BIGNUM, of INTEGER,
and of NUMBER.

SUBTYPEP is the only predicate provided for comparing types;
it goes without saying that any code that uses something else
like EQUAL will not be portable.  Any type you get back from
TYPE-OF you must interpret with SUBTYPEP.

Here is an example of completely-portable code which depends on
TYPE-OF returning the MOST specific type.

(defun store-in-array-if-fits (object array &rest indicies)
  (let ((object-type (type-of object))
        (array-type (array-element-type array)))
    (if (subtypep object-type array-type)
	;; If the object fits, store it
	(setf (apply #'aref array indicies) object)
      ;; Doesn't fit, so store 0 instead.
      (setf (apply #'aref array indicies) 0))))

SUBTYPEP does explicitly the comparison that TYPEP does
implicitly when given an object and a type.  For example,
when you write (TYPEP FOO 'BIGNUM) you don't have to worry
about whether the BIGNUM type is split into POWER-OF-TWO-BIGNUM
and NON-POWER-OF-TWO-BIGNUM's.  Yet, a programmer writing
lower-level code can use the same primitive to distinguish
the two cases.  For example:

(defun count-bits (integer)
  (type-case integer
     (fixnum (count-fixnum-bits integer))
     ;; Easy BIGNUM case
     (positive-power-of-two-bignum 1)
     ;; All other BIGNUM's
     (bignum (count-general-bignum-bits integer))))

This is the reason for the "most-specific" requirement in 2.15.

If I implement the type (ARRAY POSITIVE-POWER-OF-TWO-BIGNUM)
efficiently (by just storing the exponent), my first example continues
to work, so long as TYPE-OF returns the most-specific type.
If it instead just returned BIGNUM, as you propose, there
would be no way to write code which would decide whether this
particluar type of number will fit in this particular type
of array.

    I know there are many implementation designs and we cannot standardize it.
    But, on the langauage specification level not on the hardware level,
    we can define "the most specific type" of object according to 2.15 of CLtL.
    Or 2.15 of CLtL should be updated to copy with TYPE-OF.

    I had wrote a hierarchy chart based on 2.15.
    which is attached on the japanese edition of CLtL.

    Here is a brief sketch of it.
The english version of CLtL would be clearer if it
included something like this.

    T>{pathname,stream,hash-table,readtable,package,random-state,
       sequence,symbol,array,character,number}
   
       sequence>{list,vector}
	 list>{cons,null}
       symbol>{null}
       array>{vector,simple-array}
	 vector>{string,bit-vector}
	 simple-array>{simple-string,simple-bit-array,simple-vector}
	 string>{simple-string}
	 bit-vector>{simple-bit-vector}
       charcter>{string-char}
	 string-char>{standard-char}
       number>{rational,float,complex}
	 rational>{integer,ratio}
	 integer>{fixnum,bignum}
	 float>{short-float,single-float,double-float,long-float}

       where 'a>b' means 'a is the direct super of b, or b is just connected
       to a as a direct subtype'

       I tried to define 'terminal types'
       terminal-types={pathname,stream,hash-table,readtable,package,
	 random-state,cons,null,simple-string,
	 simple-bit-vector,simple-vector,standard-char,fixnum,bignum,
	 ratio,short-float,single-float,double-float,long-float,complex}
       terminal-types are types which do not appear on the left of the above '>'.
       (keyword type was not appeared in 2.15, so keyword is not included here.)

       Roughly, I imagine the value of TYPE-OF should be,
	 the symbol (not the list) of the most specific type among
	 terminal-types or higher types which are listed above or nil.
	 (do not permit the lower hardware dependent types)
** REQUIRE ** the lower hardware dependent types.

	 'nil' is for undefined object, say unreadable objects.

No, not NIL.  T would be a better choice here than NIL!

First, there are several kinds of unreadable objects
which already have types, such as COMPILED-FUNCTION.
Second, NIL is defined to be the *empty* type, that is *no*
objects are of type NIL.  There is nothing wrong with having
an UNDEFINED type, however.  NIL will be a subtype of
UNDEFINED, of course, and UNDEFINED will be a subtype of T.

     I am writing an educational CommonLoops interpreter (the first version was
    represented at the conf. of JSSST and IPSJ).
    in it, I have a strong desire to get the firm definition of TYPE-OF.
More important is a firm definition of SUBTYPEP!
SUBTYPEP is the key to using the result of TYPE-OF.

     I also have a suggestion from friends that
	 'there is a CLASS-OF in PCL'.
    but CLASS-OF also need the detailed definition
    on the built-in-classes.
      If CLASS-OF is the right things to discuss,
    I have no problem to shift the discussion  to CLASS-OF.
CLASS-OF is not the issue here.

	 Masayuki Ida

	 PS: there is no Ethernet-like link between US and Japan.
	 (though there is a firm link between us)
	 So, my response will be not timely. Sorry.