Some of the comments on this interesting blog post http://sebastiansylvan.com/2013/05/25/language-design-deal-breakers make me think that people only familiar with languages that allow null pointer dereference do not fully appreciate that it is an artifact of language design. I want to go into some detail about it. I'll introduce a typical language with NULL dereference, show how to transform it to a language without, and then show how proper use of the new language really does completely eliminate the problem.
Start with a pointer language, like C++, but without pointer arithmetic. And let's assume garbage collection, to eliminate explicitly freeing memory. Really, the language is more like C# or Java or Go, but let's stick with C++ syntax. I'm going to write NULL (not 0 or nullptr or nihilateration) for the null pointer.
Here are a couple of declarations in this language.
T t1; // t1 is a value of type T
T* p1; // p1 is a pointer to a value of type T
T can be whatever: int, float, another pointer, a struct, etc. But for talking about NULL, the type doesn't matter, so we'll just stick with T.
There are 3 ways to create a pointer to a value of type T.
Most simply, you can take the address of a value of type T:
&t1 // is a pointer value pointing to t1
p1 = &t1; // stores that pointer value in the pointer variable
That's easy, but not really that common in C++; and it's forbidden in Java. It's probably more common in Go.
The second way to create a pointer is by allocating a new chunk of memory:
new T() // allocates enough memory for a T value, initializes the value and returns a pointer to the memory
p1 = new T(); // stores that pointer in the variable
The third and final way to create a pointer is just to write NULL (possibly with a cast), which creates a value of type "pointer to T" that doesn't really point to anything. So, kind of misleading.
NULL // the null pointer
p1 = NULL; // make the variable p1 not point to anything
Many languages implicitly set pointers that are not explicitly initialized to NULL. In C and C++, that is true in some contexts; in other contexts the pointer just contains random garbage. Let's assume that pointers not explicitly initialized are implicitly initialized to NULL. So these are the same:
T* p1;
T* p1 = NULL;
The first two ways of creating a pointer value make it actually point to something; only the third way does not. The only way to get a NULL value is to specify NULL (or imply it by not specifying anything).
Taking the address of a value in memory always succeeds; and the NULL value is just another literal. new() can fail, either to allocate memory or to properly initialize the new value; if it fails it will throw; but if it gets past that, it can always successfully return the pointer value. In C, malloc will return NULL if it fails, but you should always check for that and usually fail with an "out of memory" error.
Let me briefly mention that in C which allows pretty flexible pointer arithmetic, such arithmetic still cannot turn a non-NULL pointer into a NULL, at least not in a way that is well defined.
So, what can you do with a pointer once you have it? In the absence of pointer arithmetic, not too much. A pointer is a value, so one thing you can do is copy it around: you can store it in variables, pass it to functions, return it from functions.
T* p2 = p1; // copy the value of the pointer p1 into p2 so that both now point to whatever p1 pointed to before
T* p2 = f(p1);
The second thing you can do with pointers is compare them:
if (p1 == p2) { ... }
if (NULL != p1) { ... }
In the absence of pointer arithmetic, less than (p1 < p2) and its brethren are forbidden.
And the last thing you can do with pointers is dereference them:
T t1 = *p1; // read through p1
*p2 = t1; // write through p2
That's it, three operations on pointer values: copying, comparing and dereferencing.
This is a pretty typical language. C#, Java, Go, C and C++ all work basically this way.
In languages like this, whether a pointer is NULL doesn't matter when you're copying it. Copying and comparing can never fail. But dereferencing a NULL pointer causes a NULL pointer exception, which makes everyone involved very sad. So you avoid NULL dereferences by judiciously sprinkling your code with lots of comparisons against NULL.
But wait, there's a better way. Let's morph the language into a new and improved language. In this new language, you can declare pointers that cannot point to NULL:
T*! v1 = &t1; // exclamation point (!) means never NULL
T*! v2 = NULL; // BZZT! The compiler won't allow this.
T*! v3; // BZZT! This is also forbidden, because it implicitly initializes to NULL.
T*! v4 = new T(); // fine; if it doesn't throw, it returns a non-NULL value
But you can still declare a pointer which can hold a NULL or an actual pointer.
T*? n1 = &t1; // question mark (?) means sometimes NULL
T*? n2 = NULL;
T*? n3; // implicitly NULL
T*? n4 = n1;
So there are two types of pointers to T: never NULL (T*!) and sometimes NULL (T*?). The new language does not support the traditional (T*) pointers from the old language.
Neither of these types (T*! and T*?) alone supports all of the operations allowed to T* pointers. T*! as we saw already, forbids assigning NULL. T*? forbids dereference, which prevents NULL derereference. You can implicitly turn a T*! pointer into a T*? pointer, but not the other way:
T*! v1 = n1; // BZZT! Cannot assign nullable pointer to non-nullable one.
T*! v1 = (T*!) n1; // BZZT! Not even explicitly.
if (n1 == v1) { ...} // same as: if (n1 == (T*?) v1) { ... }
If T*? pointers don't allow dereference and cannot be turned into T*! pointers, what good are they? Well, there is a way to get the T*! pointer back out, but it involves new syntax, the perhaps/butifnot statement:
perhaps (T*! v1 = n1) { // can assign T*? to T*! only in a "perhaps" header
// here v1 is in scope and can be dereferenced
t1 = *v1;
} butifnot {
// here it is not because n1 is NULL
t1 = t2;
}
This is sort of like
if (NULL != p1) {
t1 = *p1;
} else {
t1 = t2;
}
except that you can't accidentally forget the NULL check. Note that inside the perhaps clause you still can't dereference n1; you can dererence v1, the non-NULL pointer that n1 held.
People who have never used a language like this may initially think that it doesn't really add much value. It forces you to do your NULL checks, but that seems more annoying than anything else . Sure, there are technically no NULL dereferences, but don't you end up in "butifnot" blocks all the time with nothing to do but throw an exception, which might as well be a NullDereferenceException?
The answer to that question is: no, you never really end up in a "butifnot" block with nothing to do. Think about how you would get to this point:
perhaps (T*! v1 = n1) {
... *v1 ...
} butifnot {
// What should I do? How did I get here?
}
Think in particular about where n1 came from. Maybe you're writing a function, and it's a parameter:
void f(T*? n1) {
// ...
perhaps (T*! v1 = n1) {
... *v1 ...
} butifnot {
// How did I get here?
}
// ...
}
How did you get there? You declared the wrong type for the function parameter. You started writing the function thinking it would be ok for the pointer to be NULL, but you've now realized that you were wrong. The correct way to proceed is not to throw a NullDereference exception, or any exception. The right thing to do is to fix the declaration of the parameter. You need the parameter not to be NULL, so just declare it as non-nullable:
void f(T*! v1) {
// ...
... *v1 ...
// ...
}
No problem, no NULL dereference, no perhaps statement, no NULL checks. Sure, someone is calling your function, but if they are passing it NULL, it's just going to throw anyway, so make them fix the problem the same way.
Another way you might have gotten there is that you got the n1 is as the result of a function call:
T*? n1 = g();
// ...
perhaps (T*! v1 = n1) {
... *v1 ...
} butifnot {
// How did I get here?
}
// ...
But you need to call g() and get a non-NULL pointer back. You have two options. The better one is fixing g() to return a non-NULL pointer, but that's not always feasible. But you can always wrap it:
T*! wg() {
T*? n = g();
perhaps (T*! v = n) {
return v;
} butifnot {
throw GFailed;
}
}
And then you call your wrapper:
T*! v1 = wg();
// ...
... *v1 ...
// ...
Sure, this still may throws an exception, but it's really not equivalent to a NULL dereference. First, it fails earlier, which is better. Second, it tells you that g() didn't do what you were expecting, which is likely to be far more useful than a NULL dereference error.
By the way, a language like this doesn't need traditional NULL checks:
T*! vl = &t1;
if (NULL == v1) { ... } // known false at compile time, just from the type of v1
T*? n1;
if (NULL != n1) { ... } // ok, but not as useful as a perhaps/butifnot statement
The other thing you don't understand when you're used to languages with only nullable pointers is how rarely you actually need them. Most of the time non-nullable pointers are what you want. Which really means that the case of the function g() returning a nullable pointer doesn't happen very often.
I will post sometime about sum types and matching, which is a great language feature that lets you write T*? and perhaps/butifnot yourself, along with many other useful things.
Showing posts with label Java. Show all posts
Showing posts with label Java. Show all posts
Tuesday, June 4, 2013
Tuesday, April 30, 2013
High-level ints
In this blog, I am going to be talking about various aspects of computer programming and programming languages and everything else worthwhile in this world.
The first few entries will be about how I think numeric types should be handled in high-level languages.
Low-level languages, like assembler and C, are all about what the machine can do well. High-level languages are supposed to abstract away the machine and allow the programmer to more easily focus on solving a problem.
Almost all programming languages have numeric types, to do math, because arithmetic is often useful. But somehow, many get the basic numeric types wrong.
I'm going to discuss some numeric types in mathematics: integers, rational numbers, and real numbers; and also how they can be represented on the computer; and how they actually are represented in many programming languages. I'll also talk about some extensions to these types and how they could be represented.
In this post, I'm going to talk about integers. Integers, as you recall, are numbers with no fractional part:
..., -3, -2, -1, 0, 1, 2, 3, ...
You have been learning the properties of integers since you started learning to count, and you're familiar with them. One useful property is that integers are closed under addition, multiplication and subtraction. Or maybe that's three properties. But, if you add, subtract or multiply two integers, you get another integer as a result. Another property is that they are unbounded on both sides; there is neither a largest or a smallest integer. And there are lots more useful properties that you know, and that you use all the time when doing math, even if you don't consciously think about them.
Here's a useful property of integers that you may never have thought about: integers are exactly representable in a computer, in a way that is useful in that it readily supports implementing arithmetic efficiently. In other words, they can reasonably be a type in a programming language.
Not surprising, then, that most languages have a type called "integer" or "int" or something similar. What's surprising is that this type doesn't actually represent the integers in most languages.
From what I can tell, the most popular languages that get "int" basically right are Python and Ruby. Some less popular languages, including Smalltalk also get "int" right. Smalltalk is notable in that it seems to get "int" more right than Python and Ruby, which I'll talk about in the next post.
If you're a programmer, there's a good chance that you've used one of the C-derived languages, which include C, C++, C#, Objective-C, Java, Go and D. These languages, and many others, all have an "int" type which can represent only a subset of the integers. And the particular subset is usually one that fits into 32 or 64 bits (or 16 bits for some older implementations). This means there is a largest integer ("intMax") and a smallest one ("intMin"). Which means it's actually pretty different from the integers we know and love. Integers are unbounded, so we can love them without limit.
C and assembly languages are the common low-level languages, although there are a few others. Some languages, like C++ try to support both low-level and high-level programming. But most languages, definitely C# and Java, are trying to be high-level languages, and abstract machine details away from the programmer to make programming easier. But they're failing on "int", which seems pretty fundamental.
If you're reading the definition of "int" in a high-level language, and you see the phrase "fits into 32 bits", that's a strong hint that your high-level language is not actually abstracting away from the machine; and therefore is not actually a high-level language. You've been hoodwinked, bamboozled. It is a low-level language in sheep's clothing.
The main problem with restricting "int" to some number of bits is that it can overflow (or underflow, which is similar, but I will largely ignore). There are a few different options for managing overflow:
- Wrapping (modular arithmetic). This is very popular. Here, intMax + 1 is intMin, which is pretty strange when you first see it. But, if you're a programmer, chances are you've eventually grown used to this behavior.
- Promoting to a larger type. If you always automatically promote to a larger integer type, you're effectively implementing integers; this is how Python does it. But if you promote to a different type, it can lead to problems I'll discuss later. For example, PHP promotes "int" to "float" when "int" overflows.
- Failing (throwing an exception). This is less common. Here, intMax + 1 is an error.
- Clamping. I can't find any examples of this at all. Here, intMax + 1 = intMax.
I said I'd ignore underflow, but it has the same options, and always seems to be handled the same way overflow is, although in principle you could design a very confusing language where overflow wrapped and underflow clamped.
Here's one explicit example of the problem with bounded ints. The numbers in the example assume a typical signed 32-bit int; but you could create a similar example with different numbers for any bounded int.
You write a program which is supposed to count the number of characters in a file. You test it carefully on a bunch of small files, where you can actually count the characters by hand, and it works perfectly. Now you run it on the file you actually care about, which happens to have 6,442,450,941 characters in it, which is a large file.
The answer you get depends on how the language handles overflow. With wrapping, you get the answer 2,147,483,645 which is a large number, and you believe it. But it's only about a third of the right answer. Your program was completely wrong, and you can't even tell. If this were an actually useful result, something would catch on fire.
If your language is a rare language that clamps, you get 2,147,483,647 instead, which isn't all that different.
If your language throws on overflow, you just get an error. At least you know you don't have the right answer, but it's still not useful. But if your language supports bounded types, this is the best kind, because at least you know when you don't get the right answer. We should rather bear those ills we have than fly to others we know not of.
If the language promotes to a floating-point type which is large enough to hold the correct answer, you get the correct answer. But, for some larger file, floating-point types look kind of like clamping types: There is some smallest number M such that M+1 = M. Unlike real clamping types, there's another number M' such that M'+2 = M' (and also M' + 1 = M), where M' > M. But eventually you get the wrong answer.
I should briefly mention here that there are a few languages which don't have integers, and only have floating point numbers. These suffer from this same issue. I count Perl among these languages, although it is in principle possible to use int in Perl.
There are also a few languages that don't have any numeric types, and aren't good choices for doing even simple math, such as counting. Languages which specifically target non-numeric programming are, of course, exempt from criticism that they have a poor numeric types.
Many languages (such as Java) have a type hidden away in a library somewhere with a name like "bigint" which actually can represent all integers. Simply having such a type is not sufficient to be a high-level language. The easiest to use integer type, and the type of integer literals needs to behave like integers, not like bounded ints with some bit size.
There's nothing wrong with a high-level language including low-level types. There are two options high-level languages have for including low-level types. One way, just throwing in the C types (int32, int64) is ok; it lets people use them where they want them. There's another option, though, which is much more powerful.
define int16 as i : int such that -32768 < i and i < 32767;
A language could permit arbitrary constraints on a type; and check those constraints. That gives bounded types that throw, which are the best bounded types And it can use those constraints for optimization.
This lets the programmer put appropriate bounds on the types, not arbitrary ones because of bit sizes. If I want a type that can only hold even numbers from -6 to 60, I just declare that type.
So, in summary, the rule for high-level languages is: Integers should be easy. The integral type which is easiest to use, because it has the shortest, simplest name, and because it is the type of integer literals should be unbounded (or at least act as if it is).
Python basically gets integers right; and Java basically gets them wrong (along with lots of other languages). So what difference does it make? First, there's a class of bugs which can happen in Java that cannot happen in Python. Second, there's one fewer bizarre feature that needs to be learned in Python than in Java. It takes seconds to completely explain integer literals and addition, subtraction and multiplication of integers in Python, because it's just integers, and the student knows it already. In Java, you're talking about bits and bounds.
In the next post, I'll talk about dividing integers, which Smalltalk still gets right, but Python gets wrong.
The first few entries will be about how I think numeric types should be handled in high-level languages.
Low-level languages, like assembler and C, are all about what the machine can do well. High-level languages are supposed to abstract away the machine and allow the programmer to more easily focus on solving a problem.
Almost all programming languages have numeric types, to do math, because arithmetic is often useful. But somehow, many get the basic numeric types wrong.
I'm going to discuss some numeric types in mathematics: integers, rational numbers, and real numbers; and also how they can be represented on the computer; and how they actually are represented in many programming languages. I'll also talk about some extensions to these types and how they could be represented.
In this post, I'm going to talk about integers. Integers, as you recall, are numbers with no fractional part:
..., -3, -2, -1, 0, 1, 2, 3, ...
You have been learning the properties of integers since you started learning to count, and you're familiar with them. One useful property is that integers are closed under addition, multiplication and subtraction. Or maybe that's three properties. But, if you add, subtract or multiply two integers, you get another integer as a result. Another property is that they are unbounded on both sides; there is neither a largest or a smallest integer. And there are lots more useful properties that you know, and that you use all the time when doing math, even if you don't consciously think about them.
Here's a useful property of integers that you may never have thought about: integers are exactly representable in a computer, in a way that is useful in that it readily supports implementing arithmetic efficiently. In other words, they can reasonably be a type in a programming language.
Not surprising, then, that most languages have a type called "integer" or "int" or something similar. What's surprising is that this type doesn't actually represent the integers in most languages.
From what I can tell, the most popular languages that get "int" basically right are Python and Ruby. Some less popular languages, including Smalltalk also get "int" right. Smalltalk is notable in that it seems to get "int" more right than Python and Ruby, which I'll talk about in the next post.
If you're a programmer, there's a good chance that you've used one of the C-derived languages, which include C, C++, C#, Objective-C, Java, Go and D. These languages, and many others, all have an "int" type which can represent only a subset of the integers. And the particular subset is usually one that fits into 32 or 64 bits (or 16 bits for some older implementations). This means there is a largest integer ("intMax") and a smallest one ("intMin"). Which means it's actually pretty different from the integers we know and love. Integers are unbounded, so we can love them without limit.
C and assembly languages are the common low-level languages, although there are a few others. Some languages, like C++ try to support both low-level and high-level programming. But most languages, definitely C# and Java, are trying to be high-level languages, and abstract machine details away from the programmer to make programming easier. But they're failing on "int", which seems pretty fundamental.
If you're reading the definition of "int" in a high-level language, and you see the phrase "fits into 32 bits", that's a strong hint that your high-level language is not actually abstracting away from the machine; and therefore is not actually a high-level language. You've been hoodwinked, bamboozled. It is a low-level language in sheep's clothing.
The main problem with restricting "int" to some number of bits is that it can overflow (or underflow, which is similar, but I will largely ignore). There are a few different options for managing overflow:
- Wrapping (modular arithmetic). This is very popular. Here, intMax + 1 is intMin, which is pretty strange when you first see it. But, if you're a programmer, chances are you've eventually grown used to this behavior.
- Promoting to a larger type. If you always automatically promote to a larger integer type, you're effectively implementing integers; this is how Python does it. But if you promote to a different type, it can lead to problems I'll discuss later. For example, PHP promotes "int" to "float" when "int" overflows.
- Failing (throwing an exception). This is less common. Here, intMax + 1 is an error.
- Clamping. I can't find any examples of this at all. Here, intMax + 1 = intMax.
I said I'd ignore underflow, but it has the same options, and always seems to be handled the same way overflow is, although in principle you could design a very confusing language where overflow wrapped and underflow clamped.
Here's one explicit example of the problem with bounded ints. The numbers in the example assume a typical signed 32-bit int; but you could create a similar example with different numbers for any bounded int.
You write a program which is supposed to count the number of characters in a file. You test it carefully on a bunch of small files, where you can actually count the characters by hand, and it works perfectly. Now you run it on the file you actually care about, which happens to have 6,442,450,941 characters in it, which is a large file.
The answer you get depends on how the language handles overflow. With wrapping, you get the answer 2,147,483,645 which is a large number, and you believe it. But it's only about a third of the right answer. Your program was completely wrong, and you can't even tell. If this were an actually useful result, something would catch on fire.
If your language is a rare language that clamps, you get 2,147,483,647 instead, which isn't all that different.
If your language throws on overflow, you just get an error. At least you know you don't have the right answer, but it's still not useful. But if your language supports bounded types, this is the best kind, because at least you know when you don't get the right answer. We should rather bear those ills we have than fly to others we know not of.
If the language promotes to a floating-point type which is large enough to hold the correct answer, you get the correct answer. But, for some larger file, floating-point types look kind of like clamping types: There is some smallest number M such that M+1 = M. Unlike real clamping types, there's another number M' such that M'+2 = M' (and also M' + 1 = M), where M' > M. But eventually you get the wrong answer.
I should briefly mention here that there are a few languages which don't have integers, and only have floating point numbers. These suffer from this same issue. I count Perl among these languages, although it is in principle possible to use int in Perl.
There are also a few languages that don't have any numeric types, and aren't good choices for doing even simple math, such as counting. Languages which specifically target non-numeric programming are, of course, exempt from criticism that they have a poor numeric types.
Many languages (such as Java) have a type hidden away in a library somewhere with a name like "bigint" which actually can represent all integers. Simply having such a type is not sufficient to be a high-level language. The easiest to use integer type, and the type of integer literals needs to behave like integers, not like bounded ints with some bit size.
There's nothing wrong with a high-level language including low-level types. There are two options high-level languages have for including low-level types. One way, just throwing in the C types (int32, int64) is ok; it lets people use them where they want them. There's another option, though, which is much more powerful.
define int16 as i : int such that -32768 < i and i < 32767;
A language could permit arbitrary constraints on a type; and check those constraints. That gives bounded types that throw, which are the best bounded types And it can use those constraints for optimization.
This lets the programmer put appropriate bounds on the types, not arbitrary ones because of bit sizes. If I want a type that can only hold even numbers from -6 to 60, I just declare that type.
So, in summary, the rule for high-level languages is: Integers should be easy. The integral type which is easiest to use, because it has the shortest, simplest name, and because it is the type of integer literals should be unbounded (or at least act as if it is).
Python basically gets integers right; and Java basically gets them wrong (along with lots of other languages). So what difference does it make? First, there's a class of bugs which can happen in Java that cannot happen in Python. Second, there's one fewer bizarre feature that needs to be learned in Python than in Java. It takes seconds to completely explain integer literals and addition, subtraction and multiplication of integers in Python, because it's just integers, and the student knows it already. In Java, you're talking about bits and bounds.
In the next post, I'll talk about dividing integers, which Smalltalk still gets right, but Python gets wrong.
Subscribe to:
Posts (Atom)