Lambda the Ultimate

Much of that blinding speed you speak of comes from technologies like pipelining and out-of-sequence execution that make it very difficult to support precise synchronous exceptions in hardware; and without hardware support, no one is going to go near overflow detection.

The Ada specification demands that integer overflow be detected, but does not provide for bignums. The GNAT compiler turns this off by default; it must be restored by a compile-time switch. The AppletMetrics compiler, which output JVM bytecodes, decided to use the JVM's 64-bit instructions to do 32-bit arithmetic, precisely so it could reliably detect overflows.

I think the claim that integer overflows actually cause a serious number of problems in applications programming needs to be proved.

[[I think the claim that integer overflows actually cause a serious number of problems in applications programming needs to be proved.]]

In one interview, OpenBSD lead developer said that one security issue which was very hard for them to find and correct was integer overflow.

More anectodical: I remember reading 'Programming pearls' first edition, and in an article how many programmers got a sorting algorithm wrong, the author used a loop invariant to show that his version was correct but ... used
middle := (a + b)/2; in the code! which can leads to integer overflow.

Your comment rang a bell with me, so I did a search through the archives to find this. This is another example of overflow causing problems, this time in the Java library.

A couple of examples:
PHP
Sun XDR library

and, at a higher level, the Ariane 5 first launch failure.

Unless I missed something in math, integers don't wrap around.

In algebra, integers wrap. The finite abelian groups - integers modulo n.

In algebra, integers wrap.

I know that's the standard way to look at it, but I think there is a better viewpoint. The integers don't wrap; the modular operators do. In other words, 32 bit unsigned arithmetic as in C has 2^32 integers, an addition operator defined as (x+y)%2^32, etc. Modular plus isn't the same operator as just plain plus. The integers, however, are the same: the int32 7 is the same number as the bignum 7.

But those aren't integers. Don't forget that the elements of Z_n are not integers, they're congruence classes modulo n.

I don't see what point you are trying to make, and how it would affect what I propose. In any event, I don't agree. The elements of Z_n are the integers 0 .. n-1. That's how I was taught it in school and that's what a book I plucked off the shelf just now says as well. A three is a three is a three, whether in it is N, Z, or Z_2^32.

My understanding is that one uses Z/_nZ to denote the congruence classes modulo n.

But the issue as I understand it is how to think about the operators, and what algebraic properties they have and how we might derive proofs of properties of source code, and for that, I think my proposal is a good one. Do you have a specific concern?

They're equivalent. Yay! Now let's all go have tea.

I don't see what point you are trying to make, and how it would affect what I propose. In any event, I don't agree.

My comment wasn't a reply to your comment, it was a reply to the comment you were also replying to.

In school I was taught that the group Z_n was defined as the set of congruence classes of integers modulo n, with the operator + defined appropriately. This page seems to support that definition, however, I did find other pages that defined Z_n as you defined it. As Derek Elkins points out, the two groups (indeed even the appropriately defined Rings) are isomorphic, so really doesn't matter how you define Z_n. My point was that the Integers (specifically the ring of Integers) is not a finite cyclic group under +. Reading your reply to Marlene Miller's comment suggests that you agree with me (and I quote): "The integers don't wrap..."

I'm not sure I agree with you that the Int32 7 is the same as the Bignum 7, at least not from a pure mathematical sense, unless you qualify that with exactly what "the same as" means (i.e. how you define equality between the two different groups).

In the end, a common (the most common?) mental model of Int is the ring of Integers, but this is an incorrect model. We all know that Int isn't isomorphic to the ring of Integers, but when our minds are focused on other things (solving the problem at hand), many of us "default" to this incorrect model, without even realizing it.

My comment wasn't a reply to your comment

D'oh! My mistake.

I'm not sure I agree with you that the Int32 7 is the same as the Bignum 7, at least not from a pure mathematical sense, unless you qualify that with exactly what "the same as" means (i.e. how you define equality between the two different groups).

How about mathematical equality?

I tend to think that implementation issues have confused us programmers somewhat. I think even type theory has been so affected. As far as what the "right" mental model is, it seems to me that uint32 can be modeled as the ring of integers mod 2^32, and the signed 32 bit quantity is also a ring, albeit a not-often-identified one. That gets us + and * anyway.

Some interesting papers that have affected my viewpoint:

Should Your Specification Language Be Typed? (Lamport, Paulso)

Cleaning up the Tower: Numbers in Scheme (Egner)

(on edit: fix, format links)

You can say that a three is a three is a three, but it doesn't have a lot of meaning unless we know what you mean by a three. A string is a string is a string, but I'm not likely to have much success tying up my package using a sequence of bytes. A three that is an element of an algebraic group Z₄ is not a three that is a cardinal of a finite collection. Sure they use the same name, but saying they are referring to the same thing is rather disingenuous.

A three that is an element of an algebraic group Z4 is not a three that is a cardinal of a finite collection. Sure they use the same name, but saying they are referring to the same thing is rather disingenuous.

I disagree. Every three you find in every context is the same three. The 3 in Z₄ and the 3 in Z₅ and the 3 in Z, as well as the 3 in N, Q R and C, is the same 3. If you add one to it, you get 4.

The thing that does change between all those contexts is what "add" means. The "+" in "3+4" means the same in Z, Q, etc., but the "+" in the context of Z₄ means add then modulo 4.

It is the operators that change with context, not the operands.

Once one adopts this view, the situation with regards to things like overflow are much clearer. If you add using + modulo 2^32, you get different results than if you use a floating point (approximate) add, or a bignum add. And that makes perfect sense, if you consider them different operators.

It is the operators that change with context, not the operands.

One of the deep lessons of algebra (at least as far as this amateur can see) is that operators and operands can't really be independently defined. It may make sense to a point to adopt the "point of view" of operators and distinguish the operands, and it may make sense to a point to adopt the "point of view" of the operands. As Dogen said in a different (but "structurally related," and more on that later) context: "When one side is illuminated, the other side is dark."

Of course on the other hand it does make sense to say that 3, 3, and 3 are all the "same" 3. They certainly have a structural relationship, whether they're 3 in Z, 3 in R, or 3 in Z₃₂. On the other hand, it also does make sense to say that +, + and + are all the "same" +. They certainly have a structural relationship, whether they're + in Z, + in R or + in Z₃₂. When one side is illuminated, the other side is dark.

The + in Z is a subset of the plus in R, so I can see calling them the same. But the + in Z_n is disjoint from the + in R, so I have a hard time saying they're the same.

Over the last sixty years, the hardware guys have labored mightily to give us an ever-increasing bounty of cycles

Perhaps the hardware guys are focusing on some wrong problems, from an application development perspective. Very few applications need integers that go up to exactly 2^31, or 2^63, etc. That's just a hack: as an engineering compromise, the hardware designers are providing fixed-width bit fields, leaving programming languages and/or programmers to work around any issues that creates.

In that sense, one important use for the extra cycles being provided by the hardware is to allow us to more easily work around limitations that haven't been addressed in hardware.

If you're working in an area where you don't want to do that for some reason, then obviously you don't. That's a big reason that the hardware designers avoid addressing these issues: doing it in hardware would add complexity for something that isn't a universal requirement. But for most applications, any effort spent dealing with an integer bit-width limit is wasted.

So the economics of program inefficiency (e.g. on a 6000-CPU cluster) have to be balanced against the economics of the development time wasted working around hardware limitations that are exposed by programming languages.

So the economics of program inefficiency (e.g. on a 6000-CPU cluster) have to be balanced against the economics of the development time wasted working around hardware limitations that are exposed by programming languages.

Not by the hardware designers. The important part of that sentence is the last four words.

I mostly agree, which is why I included those four words and also wrote "doing it in hardware would add complexity for something that isn't a universal requirement."

OTOH, the computing hardware industry has a lot of constraints — like the mult-billion dollar cost of fabs — and this tends to result in computing hardware occupying a very narrow and conservative local maximum, which is highly self-reinforcing. If hardware were easier to create, we might see some quite different CPU features arising and being used. Perhaps this hypothesis will be tested by the rise of FPGAs.

but have largely been slower (and older) versions of their dedicated-silicon counterparts, in terms of architecture. Including things like fixed-width registers. Even the world of DSPs, which long did things differently than general-purpose CPUs, are more and more resembling their general-purpose cousins.

Not surprising, really. Most embedded CPU cores for FPGAs correspond to existing CPU architectures or instruction sets--so the core can take advantage of the oodles of tooling and infrastructure available for that instruction set (compilers, linkers, debuggers, operating systems to some extent). The sort of application that calls for deviating from this--high performance computing, generally--does not gravitate towards natively supporting high-level languages. (If anything, high-performance CPU cores and high-performance architectures like VLIW, make the programmer or tool-writer's job harder, not easier).

The way that modern CPU architectures benefit HL programming techniques is by being fast enough to make them practical; not by directly mapping them into silicon.

The way that modern CPU architectures benefit HL programming techniques is by being fast enough to make them practical; not by directly mapping them into silicon.

That's a description of the status quo, but I was suggesting that reduced barriers to entry for experimenting with computing hardware approaches could change that, over time.

...you're bringing Lisp Machine back? ;-)

to have a machine which actually has a CAR and CDR as registers. :)

The Lisp machine, the transputer, the Java chip, the Crusoe... those were mostly[*] ultimately failures as commercial ventures, but interesting and instructive, or even influential, from a research perspective. Being able to perform experiments like that, and get the results into the hands of people outside the research team, without having to first raise major commercial-scale funding, is likely to result in inventions and innovations that would otherwise be overlooked.

Who knows what approaches haven't been explored properly, due to an economically-driven focus on applying Moore's Law to the designs that already existed? In programming languages, many LtUers would agree that the first few generations of PL design have left something to be desired; are we so sure that isn't true of hardware, too?

[*] Edit: I originally wrote "all", but didn't realize that the Java chip is still alive & kicking in various forms. I should have known that, because I actually own a Java-powered Crypto iButton.

No, the math is not complicated, but it's "one more thing" to check, and they pile up.

The hardware guys are not unreasonable, nor are we. Things like time to market, maintainability, flexibility, etc. matters so I don't feel bad about wasting clock cycles if otherwise the app wouldn't be running at all and I wouldn't be buying more CPUs.

What I could use in a situation like this is a type system that infers whether my numbers must be represented by bignums or machine integers. I think we'll get there.

What I could use in a situation like this is a type system that infers whether my numbers must be represented by bignums or machine integers. I think we'll get there.

I think it's possible right now. It's a problem of tracking more than just type information through the branches of the program. The difficulty comes from constraints: if limits cannot be determined at runtime, any outside influence (reading from a file or stdin, etc) suddenly makes your input unbound.

You clearly can not avoid a check, but you can propagate this runtime information at compile-time.

check :: Integer -> (Int -> a) -> (Integer -> a) -> a
check i intk integerk | isInIntBounds i = intk (convertToInt i)
                      | otherwise = integerk i

You'd really want to push this check into a parseInteger routine or some such, though trivial cases are likely to be optimized away (the wrapping and unwrapping to Integer, I mean). In Haskell, the duplication in code that this may suggest can easily be handled (in almost all cases).

P.S. The continuation based approach can easily be removed by replacing (A -> a) -> (B -> a) -> a with the equivalent, Either A B.

[W]ho thinks that Real [i.e. float] should mean real?

Me. (Of course, nobody ever listens to me.)

Failing that, I am of the opinion that the use of floats ought to come with a licensing requirement: anyone going anywhere near them really should have numerical methods training, precisely because

...which is more onerous, verifying non-overflow or backwards error analysis?

Anyway, while it may be true that "demonstrating the absence of overflow is usually a no-brainer" (and I'm certainly happy with N-bit ints; they're my buddies), it does require additional work and additional application code; and that extra work is usually missing. Further, while it may be true that for more applications enforced overflow checking would be a loss, compared to those where it is a win, I would be willing to bet that both categories are swamped by a third: applications where overflow checking (or the demonstration that it is not needed) is missing and the win/loss has never been evaluated. How many PRNG's are there compared to, say, webby shopping carts or GUI calculators, or any other program where "i+j" occurs and no one has ever figured out what happens when i is 2^N-1?

As for your paycheck's application, I am not terribly warm, either. No one is suggesting that bignums or overflow exceptions should be the only option, just the default. If trimming cycles in your app is worth millions, you should already be spending more effort on it than it would take to avoid the default. But there is waste, and then there is waste, and for most situations programmer time (or not living with potentially bad results) is more valuable than cycles.

[W]ho thinks that Real [i.e. float] should mean real?
Me. (Of course, nobody ever listens to me.)
There is the catch that to do that properly you would need to use intuitionistic logic, and generally people want the result of x=y to be a boolean value. Not that I'm against it, I just think you'll have trouble convincing all those people who can't even use floats correctly...

[W]ho thinks that Real [i.e. float] should mean real?

Me. (Of course, nobody ever listens to me.)

How would you represent such a real? Representing rationals exactly is pretty easy; but arithmetic numbers get tricky, and transcendental numbers are worse. It seems like you'd need some sort of symbolic representation, as in tools like Mathematica.

There's lots of plausible representations. For example, continued fractions represented as infinite lists, lazily producing new terms on demand, have been used since before the term "lazy evaluation" was coined. (See HAKMEM item 101 and Continued Fraction Arithmetic, both by Gosper from the early 1970s.)

For many applications, the gross approximation provided by floating-point is appropriate, including most scientific and engineering applications.

One good lesson for PLT design is this: When a PLT adds features which encompass or implements things from some other problem domain--experts in that domain should be consulted. Designing a good numeric tower requires mathematical expertise beyond the discrete maths taught as part of CS curricula--doing a good job requires in-depth knowledge of statistics and numerical analysis techniques. Engineers, meteorologists, accountants, physicists, "pure" mathematicians, statisticians, and cryptographers all are users of math--and all have differing needs which frequently are not well-met by the stock types (32- or 64-bit ints and IEEE-754 floats) provided by modern computing hardware (and PLs which map closely to such HW, including C, C++, and Java). It's often up to us in the PLT community to provide appropriate mathematical abstractions to meet their diverse requirements--and frequently we fall short of the goal. The success of things like Mathematica and Mablab (not to mention retrograde PLs like Fortran and even COBOL), is one indicator that there is work to do.

(Edited to insert "differing" above...)

The other solution would be to just call your floating point numbers Floats, and don't implement any Reals.

assuming the implementation of signed its (2s complement, 1s compliment, sign-magnitude) is known. Most hardware these days is 2's complement, which is nicely behaved, other than the issue of the maximal negative (which most systems treat as an ordinary number; though some treat as an "integer Nan").

When you have problems is when the behavior of overflow is undefined.

Right, I realize that 2s complement arithmetic is no less mathematical than modular arithmetic, but modular arithmetic has a (relatively) straightforward statically typed encoding in a Hindley-Milner based type system. Is there something similar for 2s complement based arithmetic?

It would be great if you said a little more about this - I've done a little reading, spidering out from the link you posted, but it's still not clear to me why we oughtn't to think of it as 'wrapping'.

Start with the rationals. We can construct the reals by a process of 'completion'. The idea is that we can construct sequences of rationals that get closer and closer to each other, eg. 3,31/10,314/100,3141/1000,... . Although we can construct sequences where the gap between successive elements gets arbitrarily small, in general such sequences don't have rational limits. So we throw in all the limits we need and extend the rationals to the reals.

But there was a choice in this process. We chose a notion of 'closeness' based on the distance between successive elements. But there are other notions of closeness. One such notion is the p-adic valuation which we can apply to integers. We measure the closeness of two integers by the reciprocal of the largest power of p that divides the difference. Let's pick p=2. According to this notion, 1 and 1025 are close, but 2 and 65538 are closer and so on. Writing in binary in the conventional way with the 1's column on the right, differences between digits towards the left become less and less significant in this valuation, the opposite of what happens with the usual measure of closeness. Turns out we can form the completion, known as the 2-adic integers. These are either finite binary strings or binary strings that extend out to infinity towards the left. They form a perfectly well behaved ring (and for p prime, can be extended to a field).

What I find interesting is that n-bit words are essentially just approximations to p-adic integers. What's cool about this is that the p-adics share many properties with the reals and you can use theorems from analysis to solve problems with integers. For example you can do calculus and even sometimes use Newton's method to solve equations involving integers. In many ways they're much better behaved than the reals and lots of arguments you'd intuitively like to use with the reals, but aren't rigorous, work fine with the p-adics.

Anyway, under this view, bits that fall off the left end of your words when they 'wrap' are exactly analogous to bits that fall off the right in, say, a floating point calculation. The latter is typically not treated as an error condition, and so from this point of view, neither should bits falling off the left of a finite width word. It's no longer wrapping because in the p-adic valuation, the bit falling off the end is 'small'. This is different from what you get in the usual point of view because in that case the bit falling off the end corresponds to wrapping around from the largest possible representable integer to the smallest possible integer. As you might expect, the usual ordering of the integers is no longer quite so natural with the p-adics, another reason why the notion of wrapping no longer makes sense.

Suppose x and y are p-adics and approx() is the n-bit approximation function that trncates to just the last n bits. One nice property is that approx(x)+approx(y)=approx(x+y) and approx(x)*approx(y)=approx(x*y). This is totally different to the reals. So in a sense the 2-adics encapsulate n-bit binary computers for all n simultaneously, and they do so in a nice way.

I don't consider having to insert 'branch on overflow' nearly everywhere on the generated binary an 'efficient' implementation killing your code density.

What would be an efficient implementation is an interrupt like implementation where the overflow would trigger an interrupt giving the address of the offending intruction, this should allow an easy generation of a corresponding software interrupt.

That said it would work only for native types: 8,16,32,64bit operation, but few HLL defines integer range as a native type (Ada at least) ..

...generating such interrupts can be a minor pain to CPU vendors.

On the other hand, they seem to handle integer-divide-by-zero properly, some handle a few other "nasty" cases in integer math as well (-0x80000000 * -1).

Trapping on arithmetic overflow is no serious problem for the determined processor architect. MIPS does it (with, as far as I can see, no additional penalty) and besides, all load/store instructions need to handle precise exceptions anyway, so every modern out-of-order implementation already has the mechanism in place.

No, the problem is rather that the demand of such features, as perceived by CPU vendors, is not big enough to be significant at all. They point to MIPS (trapping arithmetic) and SPARC (tagged arithmetic) and argue that such features did not give these architectures any serious advantages even for the kind of languages the CPU vendors do not care about (ie, anything other than C or Fortran).

Now, for overflowing fixnums into bignums, traps are probably too expensive (at least that is what most Lisp implementors seem to think, even where this is possible). But for detecting overflow as an error, it would certainly be handy.

Note that if you implemented fixnum->bignum conversion by trap, if there is no overflow it's nice, but after one overflow trap, what do you do?

You'd have to duplicate (at least) the code generated to go to a slow path.. So it's not the trap who is too expensive, but the handling of the trap which is not so simple in this case.

You'd have to duplicate (at least) the code generated to go to a slow path.. So it's not the trap who is too expensive, but the handling of the trap which is not so simple in this case.

Both, actually. You are right, it's messier to arrange the code for quick execution after a trap, but basically it's just a different way to jump - it can be done in various ways.

A taken conditional branch is always faster than a trap (partly for microarchitectural reasons, but mostly because it usually implies a trip into the kernel and back, involving dozens or even thousands of instructions).

Fast user-mode traps would improve matters a lot - everyone have wanted them for decades but somehow they never materialise. Not only for fast arithmetic traps, but for all sorts of things where this sort of hardware/software cooperation would be handy: garbage collection, emulation/virtualisation, transactional memory, etc.

As mentioned in my post, yes, the are negative cache effects. Then again, most modern languages now do array bounds checking, and array access is very common too.

Smarter compilers could remove or hoist most of the overflow checks, just as array bounds check removal is done now (it could even use parts of the ABC-removal code, namely integer range analysis). It would require more interprocedural analysis though, loop variables tend to be localized, while in general integers get passed around and stored a lot.

Kind of a chicken-and-egg problem, I suppose: it isn't optimized because no one uses it, and no one uses it because it isn't optimized.

Handling overflow gracefully instead of just throwing an exception (which is still much better than what we currently have) is trickier, since it implies structural changes in integer storage. Regarding trap paths, there are a finite number of operation/register/memory combinations, so I speculate that the trap code size would be bounded, still.