Frank Heckenbach wrote:
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
Your definition is clearer if you use some parentheses.
asl(a, b) := a * (2 pow b)
and I strongly favor making these syntactical extensions functions (so they can be easily replaced in purely standard systems) and naming them asl, asr when they consider the sign. That allows clear distinction from lsl, lsr which insert 0 bits at one end or the other, and can be defined to never create an overflow by using modular arithmetic as in C unsigned.
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
This is why the arithmetic and logical shift operations should be firmly separated. The logicals will be defined in terms of modulo arithmetic, just as C does.
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.
Again, define them as functions, and let the function parameters include the size in terms of binary bit count:
FUNCTION ror(in : T, places, bits : int) : T;
and compile time checking ensures that places and bits are compatible with T. Constants can be checked at compile time, so runtime checks only appear for variables there. It could be defined in terms of modulo arithmetic on an unsigned value range 0..2**bits-1.
When all these things are standard functions defined at level 0, they do not interfere with any older code, yet are available. When used in newer code that code remains portable for the effort of defining those functions. No syntactical compiler effort is needed.
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.
But when they are needed they often need to be efficient. That's why building them into the run-time library can pay off. Incidentally, in PascalP I had two extension warning levels. One warned about syntactic extensions (such as defining byte values by special numeric operations) and another about use of non-standard standard procedures. These gave instant knowledge about portability problems.