Re: [Sbcl-help] string type uncertainty?

[Pascal B. <pj...@in...>]

Christophe Rhodes writes:
> Pascal Bourguignon <pj...@in...> writes:
>=20
> >> As an example: consider the type (SINGLE-FLOAT 0.0 1.0).  If you ask
> >> sbcl to create an array :ELEMENT-TYPE '(SINGLE-FLOAT 0.0 1.0), it wi=
ll
> >> give you back an array specialized to hold general SINGLE-FLOATs, th=
e
> >> layout of which looks something like this in memory:
> >>=20
> >>   [ header | length | element0 | element1 | element2 ]
> >>=20
> >> where the element<n>s are unboxed single floats (i.e. they don't hav=
e
> >> any header; they are just the bare IEEE single float in bits).  This
> >> is what is meant by a specialized array on some type.
> >
> > Yes, but  the type inference  engine should remember that  elements o=
f
> > this  array are  always  between 0.0  and  1.0, and  could apply  thi=
s
> > knowledge to (AREF (THE (ARRAY (SINGLE-FLOAT 0.0 1.0) PROBS) 0).
>=20
> I don't think that implementation strategy is as inexpensive as you
> seem to think it is.  Consider:
>   (defun foo (x)
>     (declare (type (simple-array (single-float 0.0 1.0) (*)) x))
>     (bar x)
>     (aref x 0))
>=20
> Is the "type inference engine" entitled to assume that the return
> value from FOO will be a single float in the range 0.0 to 1.0?  Well,
> maybe, by some lights, but BAR here is an arbitrary function that
> could modify the contents of X in an arbitrary way.  To provide
> reasonable diagnostics in the case of violation of this constraint, we
> have to execute _runtime_ checks in the presence of any modification
> inside BAR (and remember, we can change BAR's function binding at
> will, so we have to remember that we have to reinsert runtime checks
> on recompiling BAR).

I've not said anything about the cost of checking the assertions.  But
note that it's sbcl who started first to interpret the declarations as
assertions.

Yes, in foo, I'd expect the result to be between 0.0 and 1.0, and sbcl
promize to treat the declaration  as an assertion would imply to raise
an exception if any element of x is out of these bounds after (bar x).

I  let it  up  to  the compiler  to  decide if  it's  better to  check
systematically all the  elements of x after calling bar,  or if it can
prove that bar  does not invalidate this invariant  of x (for whatever
value bar may have at run time, if it can determine them).

It's similar to:

     (defun foofix (x)
         (declare (type (fixnum 0 10) x))
         (setq x (bar x))
         x)

There  too you'd  expect the  result  of foofix  to be  between 0  and
10. That  x be  a  scalar here,  or  an array  there  does not  change
anything.


> >> You might wish to consider what you would need to do to provide a
> >> specialization of array to hold objects of type (ARRAY BASE-CHAR).
> >
> > I  think that  since objects  of type  (ARRAY BASE-CHAR  *) may  be o=
f
> > different sizes,  an array  of such  objects needs to  be an  array o=
f
> > pointers to  them.  An  (ARRAY (ARRAY BASE-CHAR  10) *) could  put th=
e
> > BASE-CHAR inline:
> >
> >    [ header | length |t|e|n|c|h|a|r|a|c|t|t|e|n|c|h|a|r|a|c|t|...]
>=20
> No, you can't do this.  Arrays are objects which have identity; in
> other words, you can use EQL to ask whether two arrays are in fact the
> same object.  With the above implementation scheme, there would be no
> way of, say, storing the same array twice in one of these arrays of
> arrays.

I agree, I may have gone a little too far.  But I give more liberty to
the  compiler to  do whatever  it wants  as long  as it  preserves the
semantics.   (It  may  have   noticed  that  the  system  contains  no
references to  these 10-char  arrays, or it  may have  determined that
it's  more efficient  to make  them displaced  arrays given  the usage
pattern).

--=20
__Pascal_Bourguignon__                   http://www.informatimago.com/
----------------------------------------------------------------------
Do not adjust your mind, there is a fault in reality.