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

Sat Jan 23 20:30:33 CET 2010

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/20100123/8d175afb/attachment-0002.html>