[M3devel] the meaning of -FIRST(INTEGER)?

Sun Jan 24 10:23:29 CET 2010

I still don't understand what is broken here...

On 23 Jan 2010, at 14:30, Jay K wrote:

> Once I fix Lex.m3, should we continue to allow -FIRST(INTEGER) or not?
> As well, should we go the extra bit and disallow it even if it doesn't overflow?
>   ie: on one's complement?
>  
>  
> I already disallow it in some code -- depending on which code gets
> hit in the backend. But this disallowing is new.
>  
>  - Jay
> 
>  
> From: jay.krell at cornell.edu
> To: hosking at cs.purdue.edu
> CC: rodney_bates at lcwb.coop; m3devel at elegosoft.com
> Subject: RE: [M3devel] the meaning of -FIRST(INTEGER)?
> Date: Sat, 23 Jan 2010 05:00:34 +0000
> 
> Sorry, not literals.
>  
> How do I write correct portable code to test if a Word is greater than -FIRST(INTEGER)?
>  
> How do I express -FIRST(INTEGER)? Without incurring signed overflow
> while evaluating the constant expression?
>  
> For a one's complement system, nothing wrong with -FIRST(INTEGER).
>   It equals LAST(INTEGER).
>  
> But for a two's complement system, evaluating -FIRST(INTEGER)
>  incurs overflow.
>  
> Maybe:
>  Word.Add(-(FIRST(INTEGER) + 1)), 1)
>  
> ?
>  
> Probably. I'll try that.
>  
> You know, C has the same dilemna and similar solution.
> not a great idea to write
> unsigned u = (unsigned)-INT_MIN;
>  
> nor
>  
> unsigned u = -(unsigned)INT_MIN;
>  
> though the second is maybe ok.
> The first incurs signed overflow in C as well.
> Which isn't defined. The first also gets a warning
> with some compilers: "negating unsigned is still unsigned".
>  
> An idiom is
> unsigned u = ((unsigned)-(INT_MIN + 1)) + 1;
>  
> derivation:
> INT_MIN + 1 yields a negative number that can be safely negated.
> Which yields a positive number one less than the desired value.
>  
>  
>  - Jay
> 
> Subject: Re: [M3devel] the meaning of -FIRST(INTEGER)?
> From: hosking at cs.purdue.edu
> Date: Fri, 22 Jan 2010 18:52:05 -0500
> CC: rodney_bates at lcwb.coop; m3devel at elegosoft.com
> To: jay.krell at cornell.edu
> 
> There's no language hole!  Unsigned literals and unsigned constant expressions can easily be handled.
> 
> Literals:
> 
> If no explicit base is present, the value of the literal must be at most LAST(INTEGER). If an explicit base is present, the value of the literal must be less than2^Word.Size, and its interpretation uses the convention of the Word interface. For example, on a sixteen-bit two's complement machine, 16_FFFF and -1represent the same value.
> 
> Constant expressions:
> 
> CONST x = Word.Plus(16_FFFF, 1)
> 
> 
> On 22 Jan 2010, at 17:51, Jay K wrote:
> 
> I think there is a language hole here.
> The language should perhaps allow for
> unsigned literals and unsigned constant
> expressions.
> 
> 
> Something I don't quite have my head around as well,
> maybe a language/library hole, is how to do
> e.g. the below, without assuming two's complement
> representation of signed integers.
> 
> 
> Can we maybe add Word.AbsoluteValueOfInteger?
> The implementation would, roughly:
>   IF i < 0 THEN 
>     i := -i;
>   END;
>   RETURN i;
>   END;
> 
> with the extra qualification that overflow is silent
> 
> 
>  > But surely, we could agree that compile time
>  > arithmetic should do the same thing as runtime would, for a given
>  > implementation.
> 
> Uh huh. This is why you need *different types* (or interfaces)
> for the variety of integer overflow behavior and not a runtime
> setting. Otherwise the compiler can't know what the
> runtime behavior is.
> 
> 
> As well, using static typing instead of a runtime setting,
> allows for efficiency. Imagine, say, if x86 does require
> extra code to check for overflow.
> Well, if using "integer-with-silent-overflow", that
> would be omitted. If using "integer-with-overflow"
> the code would be included.
> 
> 
> I introduce the error. It used to be silent.
> I changed it to a warning, for the
> very specific case of negating FIRST(INTEGER).
> Any other overflow here, which is probably not
> possible, will still error.
> 
>  - Jay
> 
> 
> > Date: Fri, 22 Jan 2010 19:56:37 +0000
> > From: rodney_bates at lcwb.coop
> > To: m3devel at elegosoft.com
> > Subject: Re: [M3devel] the meaning of -FIRST(INTEGER)?
> > 
> > >
> > > So..I have m3back using Target.Int a bunch.
> > >
> > > And converting back and forth some between Target.Int and
> > >
> > > INTEGER and doing match with Target.Int.
> > >
> > > And various operations can fail.
> > >
> > >
> > >
> > >
> > >
> > > And my current diff results in:
> > >
> > >
> > >
> > >
> > >
> > > new source -> compiling Lex.m3
> > > "..\src\fmtlex\Lex.m3", line 227: doneg: Negate overflowed
> > > "..\src\fmtlex\Lex.m3", line 343: doneg: Negate overflowed
> > > 2 errors encountered
> > > new source -> compiling Scan.i3
> > >
> > >
> > >
> > >
> > >
> > > which is nice to see, it means my code is actually running.
> > >
> > >
> > >
> > >
> > >
> > > So I look at the code in question:
> > >
> > >
> > >
> > >
> > >
> > > PROCEDURE ReadNumber(rd: Rd.T; defaultBase: [2..16]; signed: BOOLEAN):
> > > Word.T
> > > VAR c: CHAR; sign: [0..1]; res: Word.T; BEGIN
> > > ...
> > >
> > > IF signed AND
> > > ((sign = 0 AND Word.GT(res, LAST(INTEGER))) OR
> > > (sign = 1 AND Word.GT(res, -FIRST(INTEGER)))) THEN
> > > RAISE FloatMode.Trap(FloatMode.Flag.IntOverflow)
> > > ....
> > >
> > >
> > >
> > >
> > >
> > > -FIRST(INTEGER).
> > >
> > >
> > >
> > >
> > >
> > > What is that supposed to do?
> > >
> > >
> > >
> > >
> > >
> > > I mean, I kind of know, I'm slightly playing stupid, partly not.
> > >
> > > Does the compiler know what is an INTEGER vs. what is a "Word"?
> > ---------------------------------------------------------Word.T?
> > 
> > No, they are the same type.
> > 
> > > Or it is just obligated to assume everything is a Word?
> > 
> > It is obligated to do the builtin operators (unary - being one
> > of these) using signed interpretation of the value and functions
> > in Word using unsigned interpretation.
> > 
> > The signed operators don't assume anything about the machine
> > representation. The functions in Word do assume two-s complement
> > binary, in order to be defined. This is a low-level facility.
> > 
> > > To do the negation at compile time and ignore the overflow?
> > 
> > This may be poorly specified. The code sample you cite clearly assumes
> > this is what it does. The compile errors indicate the assumption
> > has become wrong.
> > 
> > > Does the language need work here?
> > 
> > Overflow detection wars! But surely, we could agree that compile time
> > arithmetic should do the same thing as runtime would, for a given
> > implementation.
> > 
> > > I mean, like, -FIRST(INTEGER), that is a problematic expression, isn't it?
> > 
> > Yes, it's a statically unconditional overflow, and the language doesn't
> > specify what happens.
> > 
> > As long as we are assuming two-s complement binary, I would just remove
> > the - in front of FIRST(INTEGER). If the compiler does not consider it
> > and overflow error and wraps around, in this particular case, the - is
> > an identity operation on the bits. Maybe the writer intended the -
> > to hint to a human reader that unsigned interpretation is about to be
> > applied to this value.
> > 
> > >
> > >
> > >
> > >
> > > - Jay
> > >
> > >
> > >
> > 
> > 
> 
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://m3lists.elegosoft.com/pipermail/m3devel/attachments/20100124/1c654099/attachment-0002.html>