How Integers Should Work (In Systems Programming Languages)
blog.regehr.org
blog.regehr.org
What's needed is a dependent type system (like that of ATS or Ada) that allows the range of allowable values for an integer to be decalred. A halfway-smart compiler can then statically check (using e.g. abstract interpretation) that the intermediate results of arithmetic performed on such integers does not exceed the system integer size, and that the results do not exceed the declared size of the result variable.
(In fact, if the programmer places runtime checks at the right places, such range declarations aren't even necessary as they can be inferred by the compiler.)
Such a system would statically guarantee that no overflow will occur. This means no spurious hard-to-track-down NaN results at runtime.
Thus, your pointer would have a type that provides evidence that it points to at least 100 bytes. This would make pointer arithmetic adding 100 bytes possible. Something like:
addPtr :: Address (size : Nat) -> (x : Fin size) -> Address (size - x) addPtr :: Address (presize : Nat, size : Nat) -> (x : Fin size) -> Address ( presize + x, size - x)
size = number of 'slots' available after the current value.
That would allow for later subtraction, too.
I did not mean to write an actual implementation, just to make a small point.
In an actual implementation, I'd probably want the type to convey information about the content stored at the address, too.
addPtr : Address (size : Nat) -> (x : Fin size) -> Address (size - x)
"addPtr" is a value of the following type:
"Address (size : Nat)" is the "Address" type applied to one Natural number parameter named "size" (indicating the allocation size the value of that Address points at).
(x : Fin size) means it takes an "x" of type "Fin size". The "Fin param" type is a type that can hold a natural number 0..param-1. The resulting Address has a smaller size it points at.
I'm not sure I like allowing invalid intermediate results. It means that there are many expressions whose correctness is dependent on a compiler, and more specifically a compilation target. It's not hard to come up with an example of an expression that is valid, but only calculable on specific architectures.
If none of the examples that Arseniy came up with satisfy you, think of something absurd like (x << 20000) >> 19999. As it stands, no computer architecture I know of could calculate the proper result. But with a clever compiler you can derive an equivalent program that will execute correctly. If you have the clever compiler and allow invalid intermediate results, your program will execute correctly. If you have the same constraints and a slightly dumber compiler, then you will trap.
There are probably examples that are flat out impossible to execute without trapping on particular architectures, but fine on others. As a result, architecture and compiler details will start bubbling up and affecting program correctness. The ways in which this will happen will be far more perfidious (if less common) than the current architecture details program writers often must consider such as word length.
> Of course there are specialized domains like DSP that want
> saturation and crypto codes that want wraparound; there’s
> nothing wrong with having special datatypes to support
> those semantics.
More to the point, I think you'd want to standardise on the optimisations a compliant compiler can/must implement. Algebraic rearrangements might be the way to do it, but I'm not 100% sure even they're possible. For the example given:
result = result * 10 + cursor - '0';
That has two problems.
1. Once you start formalizing optimizations that must occur, you run the risk that some optimizations will be impossible or have horrible performance on some compilation targets. For example saying something like "an expression made up of only 32-bit addition operations must successfully evaluate if the result fits in a 32-bit integer" might be really painful to implement on an embedded system with only a few 32-bit registers.
2. Even if the correctness of an expression can be determined statically and reliably by the language standard, if the correctness of an expression depends on optimizations performed, then someone reading a program needs to know all of those optimizations. For example, it is often quite a laborious task to tell whether a C expression will evaluate correctly, because C has occasionally bizarre rules for the promotion of the types of operands. Fortunately there are some decently reliable heuristics that apply, that let you assume that an unsigned char added to an unsigned long will probably promote the unsigned char to a long and do the addition. Now imagine instead of understanding C's type system, you had to understand the algebraic reductions available to your compiler. The volume of arcana required to determine whether an expression will be correctly optimized or not would be absurd. And heaven forbid you tried to modify the expression. You might add a simple constant somewhere that breaks an optimization and suddenly the expression fails to evaluate when x is 2^31 - 1 or something.
When you consider these things, hopefully you will see why it is so much more preferable to just enforce that all intermediate results must be valid, and have the program writer do the algebraic reductions necessary to make (x << 20000) >> 19999 evaluate with no invalid intermediate values.
The only explicit "invalid" value I know of is available for floating point numbers. NULL in C is usually* not an invalid address, even if user-space programmers often seem to think so. Rather there are no pages mapped at that address and the kernel hands this page fault to user-space in some way. There is plenty of hardware where physical memory starts at 0x0. Lots of fun can be had debugging such a thing.
* IIRC there was a CPU architecture that interpreted "9" as an invalid address, but I can't remember what it was..?
In any case, processor vendors aren't about to change the way they do integer math so this discussion, while quite interesting, is completely academic.
> In any case, processor vendors aren't about to change the way they do integer math so this discussion, while quite interesting, is completely academic.
I thought so too initially, but really every processor already has a status register that shows you when overflow happened (otherwise big integer algorithms would be hard) which is all you really need for this proposal. But it does require a bunch of tests around and integer arithmetic which makes it unlikely to be a good candidate for a C language addition (a language whose main impetus is speed).
In general, maybe so. But in systems programming? What could that possibly mean that is not a bug? There are answers to that, but since the answers are going to be <1% corner cases it doesn't justify defaulting to the dangerous case while requiring one to jump through hoops to get the safe case. If you desperately need "INT_MAX + 10 - 20", ask for it.
But I don't care for iNaN. I'd rather get the exception at the point the problem was created.
I'm also not sure what I think about the idea that intermediate results should be able to be wider than the integer type being computed with. I'd rather be able to introduce temporaries for subexpressions without changing the meaning of the program -- this is basic referential transparency.
That said, I'm not completely convinced by the argument that it's too dangerous for a language to support arbitrary precision by default. Special types or operators can be used in contexts, like interrupt handlers, where allocation is undesirable. We have an existence proof that this is workable: the Lisp Machine operating system.
In fact, integers that we have in current CPUs are product of let's say at least 50 years of engineering and they are optimum, even if somebody declares them "the root of a lot of serious bugs in C/C++ applications." I've got the news for him: a lot of other and older languages have the same behavior because that's the local optimum for a hardware implementation and it will remain so even once we have decimal fp numbers of the same speed as integers (even if we ignore that actually we won't). Before two's complement there were other integer variants implemented in hardware and they turned out to be less functional as two's complement representation.
Then gives the example that if this code
result = result * 10 + cursor - '0';
result * 10 + (cursor - '0')
(result * 10 + cursor) - '0'
Then he ends with the loop that wouldn't work with floating point NaNs (and therefore wouldn't fit in NaNs for integers too):
for (x = INT_MIN; x != iNaN; x++)
I'd say everything he wrote is not even wrong.
They go so far as to point out that high-level languages shouldn't have these limitations (sure, agreed), but then is baffled that something like C/C++ does (and should).
C maps more-or-less directly onto assembly, which in turn maps more-or-less directly onto command bit vectors for an ALU. There is no magic decision in the industry to use twos-complement, wrapping arithmetic, or fixed-size integers (which map onto machine words).
This person needs to spend some quality time with low-level architectural stuff and gain a better understanding of why things are the way they are.
(not that the points are bad, necessarily, for a DSL or something--but stay out of our systems languages!)
EDIT: Okay, author is clearly somewhat knowledgeable about the field, but still... these are interesting ideas that don't really make sense for low-level stuff. It's not a matter of allocating enough memory (for bignums or whatever)--it's how the mapping occurs to the actual hardware instructions and datatypes.
There's not any issues at the hardware level. Integer arithmetic is simplistic mostly because languages that run on current CPU's have simplistic integer semantics. It's not because more complicated semantics would be impossible to implement at the hardware level.
Take a look at some of the complex integer instructions that SSE supports with single-cycle latency.
The author doesn't ignore that this would require a change at the hardware level - he says "Processor architectures will have to add a family of integer math instructions that properly propagate NaN values..." - and he is right that the change would not be a costly one.
This doesn't preclude the use of twos complement, and twos complement isn't enforced (or mentioned) in C's standard. It doesn't need to be expensive, either - as said in the article, "These should be simple ALU hacks." I don't see any reason why these operations on processors would be slower than the ones we have already. I wouldn't be surprised if they used a few more transistors, but on the scale of today's processors it won't cost anything at all compared to all of the silicon required for instruction pipelining, branch prediction and out-of-order execution.
> a lot of other and older languages have the same behavior
This isn't true either. If you'd take the time to read the other posts on the site (and probably the LLVM guide to undefined behaviour[1]) you'll find that the C and C++ standards place quite different restrictions on the behaviour of integers than, say, Java (which is by comparison rather strict).
The loop that you say "would never end"? It would end. When `x` overflows it'll be set to `iNaN`, and the loop will exit.
Your "order of operations" complaint? He's talking about simple, unobvious errors with a real-life example. He then proposes semantics for a new language that would solve this problem. What's your complaint here?
On the whole I thought John came up with a bunch of ideas, most of them good, almost all of them better than the status quo. I thought your post was the exactly the sort of knee-jerk response I've come to expect from Reddit.
[1]: http://blog.llvm.org/2011/05/what-every-c-programmer-should-...
I see you don't have experience with NaN semantics:
http://en.wikipedia.org/wiki/NaN
"A comparison with a NaN always returns an unordered result even when comparing with itself."
If you say "but iNaNs would be different" you already missed the point.
He could have said "`!(x is iNaN)`", or "`!isINAN(x)`" instead of "`x != iNaN`", but he didn't. Maybe he should have, I'm sure he didn't give it much thought.
Nowhere does he say that the semantics of his `iNaN` are exactly analogous to the those of existing floating-point NaNs, though. Implying that he did so that you have one more nit to pick damages the tone of conversation.
Since current semantics is used everywhere today, using semantics that you imply for some new cases and keeping the current for existing would immensely add to confusion and it would be wrong. It's not nit to pick, it obviously shows that author (and you too) is not acquainted with something that should be a common knowledge in the profession since at least 1985, http://en.wikipedia.org/wiki/IEEE_754-1985
And that was exactly my point since my first post.
You are complaining about a single line of code that demonstrates a concept that cannot possibly be executed and there isn't any actual effort to make this line into something that can be executed. You are arguing that it is a bad idea for a reason that is completely orthogonal to the spirit of the post. So sure, implicit in that loop is the idea that iNaN would be treated subtly different than existing NaNs, but you are just responding to the text of an example that is written to be as simple and clear as possible to readers rather than the actual content of his message, which is nit picking at best.
2) Arguing to keep a local optimum seems silly to me. Why not reach for the global optimum?
3) He's not arguing for a change in the order of evaluation, he's identifying a situation that would work with integers that operate linearly and showing that it doesn't work when integers behave non-linearly (ie: around INT_MAX and INT_MIN).
Choosing "overflow" or "underflow" to mean "I fucked up" is totally arbitrary. Variables usually indicate values that have a domain - a range of valid numbers. Saying "I don't want to think about what that it is, but oh if X hits 2 billion and change then warn me when some math fails" is no better than having it not fail at all. In most cases there's already a problem.
So, simply, writing "OS quality" code means explicitly checking inputs to ensure they are in the permissible range. Once you know what the range is, you know if your code needs to go up to 64bit math to handle them.
UPDATE: Some explanation for the downvote would be appreciated.
The C compiler in that machine was written in Lisp. :)
"catching security holes" is the compiler version of "think of the children".
18446744073709551616Oh. My. God.
[I'm kidding, of course. I learned a lot from teachers who had obvious axes to grind . . . just not the lessons they wanted me to come away with. Finals were an interesting exercise in remembering to cough up the party line, and even the TAs were snickering in some sessions.]