CBFalconer wrote:
Adriaan van Os wrote:
... snip ...
We also have shl and shr and I suggest adding rol and ror (rotate left and rotate right).
If you are going to do that you should have a complete spectrum:
asl asr arithmetic shift. (asl = lsl but overflows) lsl lsr logical shift (unsigned) rol ror rotation. (length dependant)
I think the difference between "arithmetic" and "logical" shifts is only whether they operate on signed and unsigned types. This distinction is needed on the assembler level (compiler output), but not on the laguage level I think.
The trouble is that many of these require a binary representation of integer operands, and Pascal in general does not require that.
So we should provide abstract definitions, just like I did for `and' etc.
Also Pascal does not have the equivalent of a C unsigned type.
We should define them on values, not on types. I.e., the result of a positive value shifted by n should be the same whether it's stored in a signed or unsigned type -- barring overflows, which would appear as runtime errors, just as can happen with any other operations.
How do you interpret them on a decimal machine, a 1's complement machine, a sign-magnitude machine?
Again, they'd have to be implemented in such a way as to produce the same results. This might require (internally) different cases for positive and negative numbers on such machines, but so be it. (Just like we have to do for `mod', e.g.)
Also with differing values for maxint (which need not be a binary power of 2 in Pascal).
Conceptually, compute the result in arbitrary precision, compare this against MaxInt and if greater, it's a runtime error. Actual implementations can usually do it easier, but in case of doubt, one can always check if one gets the same result as the conceptual definition.
You can define the arithmetic shifts in terms of multiply/divide.
Yes, with `pow' standing for integer powers as defined in EP (if you don't like that, you can insert the usual recursive definition of powers, of course), I think we can define:
a shl b := a * 2 pow b
Right shifts are a bit more tricky because they're like division rounding towards negative infinity unlike `div' which round towards 0. So we could write:
a shr b := a div 2 pow b if a >= 0 (a - 2 pow b + 1) div 2 pow b if a < 0
One potential problem with shl is that it can easily produce overflows. Currently it's not a practical problem, as GPC doesn't do overflow checks, but when it does, we'll have to consider this case. We could define `shl' to "ignore overflows", but this would again make the semantics type-size-dependent. Of course, a programmer will be able to turn off overflow checking locally with compiler directives, as a last resort. One could also mask the result using `and'. A good implementation can optimize away the `and' (as GPC seems to do with the following program on i386 with optimizations). Furthermore, even a completely different integer-representation would then yield the same results, if `and' is defined as I wrote before.
program Foo;
var a, b: Cardinal attribute (Size = 32);
begin a := (b shl 4) and 16#ffffffff end.
Rotates are problematic since they indeed depend on the type size. I see no way to define them independently. I've had a discussion with Mirsad Todorovad about these, and we came to the conclusion that it's probably more trouble than it helps. E.g., if a is a constant and we use the term `a ror 4', suddenly the type of the constant becomes very important (not just for whether there's an overflow, but it would change the result completely) which is contrary to Pascal's rules.
OTOH, rotates don't seem to be needed very often (at least an order of magnitude less than shifts); in fact the only place I could need them in my code is in MD5. So it's probably not worth spending too much effort here.
One way out of the dilemma would be to define specifically "sized" rotates, e.g. `a ror32 b' would mean the values of a rotated by b bits on a 32 bit type. This then could be defined implementation-independent again (though we might have to think about signed and unsigned types, possibly making two versions; I haven't thought this through ATM), and again any integer implementation could be used to implement this on.
Such semantics are indeed what's usually wanted -- e.g., MD5 needs a 32 bit rotation. If the type used to store the values for some reason happened to be 64 bit on any machine (though this shouldn't happen with GPC since we use `attribute Size'), we don't want 64 bit rotation as that would produce wrong results. Instead, we want to do 32 bit rotation on the "lower 32 bits" (and get a runtime error if any of the "higher 32 bits" are set, i.e. if the value is too large). A `rol32' operation would (conceptually) do just that.
But again, rotates aren't very important to me, so I won't spend my time implementing them either way; but I wouldn't object if someone else does. ;-)
Frank