[M3devel] range analysis?

[Rodney M. Bates]

On 05/23/2011 01:45 PM, Tony Hosking wrote:
 >
 > On May 23, 2011, at 2:26 PM, Rodney M. Bates wrote:
 >
 >> This needs more thought.  On the one hand, 2.2.3 on array types allows
 >> the explicit element type in either kind of array type definition to
 >> be empty, unlike the way 2.2.4 on record types requires a field type
 >> to be nonempty.
 >
 > I note that an array type of empty elements is itself empty and cannot be instantiated.
 >

Yes.

 >> On the other hand, 2.2 has a general prohibition against declaring a
 >> variable of empty type, and it is all over the language spec that the
 >> elements of arrays are "variables".  The general definition of variable
 >> in 2.1 would apply to array elements.  Thre are numerous places that
 >> describe things that can be done with a variable that we all informally
 >> know can be done to an element, as it should be and we all have done
 >> many times.  Moreover, 2.2.3 says in the first paragraph that the
 >> elements are variables.
 >
 > So, it seems to me that we could simply disallow empty array elements and be within spec.

I agree.

 >
 >> So here, the compiler is too liberal, and the language would be clearer
 >> with an explicit rule against empty element types.
 >
 > Right.
 >
 >> I haven't spotted anywhere a parameter is specifically called a variable,
 >> and it is not required to have a nonempty type in the description of
 >> parameter declarations.  However, it certainly seems to me to fit
 >> the definition of variable, and as above, there are lots of things
 >> we know can be done with it that the language simply describes as
 >> doable to a variable.  Moreover, for every mode, there is a rule
 >> that at call time, the formal is "bound to" a variable, which pretty
 >> well makes it variable in any context where it can be used.  Even in
 >> a keyword binding, we are getting ready to bind it to a  variable
 >> very soon.
 >
 > Right.
 >
 >> So maybe we need to 1) say a formal parameter is a variable, and
 >
 > A formal parameter is not in itself a variable.  It's part of a type (the signature) not an implementation of that type.  But every formal parameter has a corresponding variable in the body of the procedure that implements a given signature.
 >
 >> 2) say the type in a parameter declaration must be nonempty.
 >
 > This seems overwrought.  I would stop simply at the variables (not the types) and let the binding of formal parameters to variables take care of the check as it currently does.
 >

My first thought was that this argument is no more or less applicable to
a procedure type containing a formal of empty type than to a record
type containing a field (which is currently defined as a variable)
of empty type.  Both are just types constructed from other type(s),
to be maybe instantiated later.  In the case of the record, we now
disallow the type to be constructed.  Your proposal would inconsistently
allow the procedure type to be constructed but complain when an
attempt is made to instantiate it (i.e., call it) later.

My second thought was that a procedure type with empty-typed formal
is not an empty type, because it contains the perfectly legitimate
value NIL, which of course, you can't call anyway, thus avoiding the
issue of instantiating the formal.  This is an essential difference
that would justify doing it differently for records and procedures.

My third thought is whereas you might consider such a procedure _type_
to have just one value, if you allow the signature in a procedure
_constant_ (i.e., an ordinary procedure declaration) to have an
empty-typed formal, you now have a value of this procedure type
other than NIL.  In fact, the number of such possible values is
unbounded.  Does such a procedure value make any more sense than a
value of a record with an empty-typed field?

Right now, the compiler allows the procedure type with empty-typed
formal, a variable of that type, and assignment of NIL to the variable.
But the compiler disallows the empty-typed formal in a procedure constant
(and calls the formal a "variable" in its error message.)  This seems
sensible enough to me, and I suggest we document the illegality of the
signature in a procedure constant.  We could only call the formal a
variable when in the signature of a procedure constant, not a procedure
type definition, otherwise the procedure type would be illegal too.

 >> The language definition is also full of an ambiguity in its use
 >> of "variable" that I have been bothered by in talking about programming
 >> languages in general for years.  One meaning is the meaning I have been
 >> talking about,  The other is the kind of variable that is declared by a
 >> VAR declaration (not a VAR parameter).  There are some uses in the
 >> language that I think need to have this latter meaning in order to be right.
 >
 > Can you enumerate?
 >

Yeah, but not this minute.

 >> So we need a different or qualified term for this narrower meaning.
 >>
 >> On 05/23/2011 11:54 AM, Tony Hosking wrote:
 >>>
 >>> On May 23, 2011, at 12:45 PM, Rodney M. Bates wrote:
 >>>
 >>>> On 05/23/2011 09:31 AM, Tony Hosking wrote:
 >>>>> An empty subrange gives a warning in the compiler.
 >>>>
 >>>> By my experiments, empty subrange, empty enumeration, and arrays
 >>>> thereof don't warn.
 >>>
 >>> Sorry yes, you're right.  But usage to declare any variable does.
 >>>
 >>>>
 >>>>> But, the semantics is that it is empty, and has no values of the type.
 >>>>> You cannot allocate (NEW) an empty type.
 >>>>> You cannot declare a field of empty type.
 >>>>
 >>>> It seems odd that we have this rule for fields, but no corresponding
 >>>> prohibition against arrays with empty element types.  By experiments,
 >>>> cm3 allows this, for both fixed and open arrays, but treats such array
 >>>> types as empty types, something the language also does not say.
 >>>>
 >>>> At the least, the language and the compiler should agree with each other.
 >>>> Maybe records/objects and arrays should be treated consistently here?
 >>>
 >>> Yes, I suppose so.
 >>>
 >>>>> Nor can you declare a variable of empty type.
 >>>>
 >>>> Again, oddly, there is no such prohibition in the language against
 >>>> declaring a formal parameter of empty type.  Cm3 prohibits it,
 >>>> and calls it a 'variable' in the error message.
 >>>
 >>> You're right, though it's not the parameter that errors but the variable associated with the parameter.
 >>>
 >>>> Again, language and compiler should agree.
 >>>
 >>> Can you point me to the relevant entries in the language spec?
 >>>
 >>>>
 >>>> The language also prohibits applying FIRST and LAST to the empty
 >>>> enumeration, but they are OK applied to an empty subrange.
 >>>> This makes sense, because they return values of the base type
 >>>> of the argument type, and such values exist for an empty subrange
 >>>> but not the empty enumeration, whose base type is only itself.
 >>>>
 >>>>>
 >>>>> On May 23, 2011, at 8:41 AM, Hendrik Boom wrote:
 >>>>>
 >>>>>> On Sun, May 22, 2011 at 11:18:02PM +0000, Jay K wrote:
 >>>>>>>
 >>>>>>> Well, I can build the whole tree and see how many times it helps.
 >>>>>>> I think this is a pretty standard optimization technique.
 >>>>>>> Though it'd work better with compiler-derived additional information.
 >>>>>>>
 >>>>>>> I initially happened upon this idea developing test cases.
 >>>>>>>
 >>>>>>>> The code assumes the minimum of a type is less than or equal to its maximum.
 >>>>>>>
 >>>>>>> I'll change it not have that problem -- to just fall back to usual pessimistic code for such types, I guess.
 >>>>>>
 >>>>>> What *is* the semantics of a range whose minimum is greater than its
 >>>>>> maximum?  There plainly can't be any values in this range.  How is a
 >>>>>> variable of this tyoe initialized?  Not to some arbitrary value of the
 >>>>>> type, because there aren't any.  I can see this type being useful to
 >>>>>> admit convenient generalizations -- for example, an array with n
 >>>>>> elements can still exist if n happens to be zero, but it seems to me
 >>>>>> that any code involving a value of the range for subscripts for this
 >>>>>> array must be simple unexecutable.
 >>>>>>
 >>>>>> Or is there some latitude available in the principle that a value of a
 >>>>>> variable must always be of the correct type?
 >>>>>>
 >>>>>> -- hendrik
 >>>>>
 >>>>>
 >>>
 >>>
 >