Null dereference is not something that you need

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.

RIFL Examples

In the last post, I introduced a pattern I call RIFL, or "Resource Is Function-Local".  The goal is to control access to a resource in such a way that there is a guarantee that it is released exactly once.  The idea is that the resource never exists in the wild.  It is created within a function, and can only be used when passed into another function which is a parameter of the first.  That's a little confusing, but let me jump into some examples which should make it clearer.

First, here is a RIFL wrapper around writing files in Go.  Note that a function declaration in Go is something like "funcName(argName argType) returnType".

package rifl
import "os"

type File struct{ file *os.File }

func WithFile(fileName string, useFile func(file File) error) error {
    file, err := os.Create(fileName) // create or truncate, open for writing
    if err != nil {
        return err
    }
    defer file.Close() // see note below
    return useFile(File{file})
}

func (file File) WriteString(s string) (int, error) {
    return file.file.WriteString(s)
}

I think this example is fairly readable for those who don't know Go.  The only thing that really needs explaining is the "defer" statement.  "defer" basically means: put the rest of the function in a "try" block, and put this in the "finally" clause.  That is, it contains a function call which is not executed until the rest of the function is completed; but is guaranteed to execute, even if there is exception (which Go calls a "panic").

And this is how the rifl package might be used, with poor error handling:

package main
import "rifl"

func main() {
    rifl.WithFile("out.txt", func(file rifl.File) error {
        file.WriteString("Hello\n")
        file.WriteString("Goodbye\n")
        return nil
    })
}

Go is a really good language in many ways, but if you're used to C++'s destructors, you'll miss them mightily.  RIFL can help you feel a bit better.

Note that in the main package, there are no references to os.File, only to rifl.File; we're not using the raw resource, just the RIFL wrapper.  I only implemented WriteString, but I could have implemented the entire interface, or (in principle) improved it.  Or made it worse.  Also, unlike my abstract example in the previous post, the Obtain function (os.Create) and the Use function (WriteString) both take arguments and return multiple values.  So it's a bit noiser.

I deliberately made the useFile argument the last argument to WithFile, because it tends to run on over many lines.

The most important point, of course, is that, in the WithFile function, we guarantee that the file will be closed, by using "defer".  It doesn't matter how many goats are sacrificed while running "useFile"; the file will get closed.

Also, the os.File object "file" is hidden from users.  In Go, identifiers with an initial uppercase letter (File, WithFile, WriteString) are exported; others (file) are not.  This means the caller has no way to call Close().  But that's fine, since WithFile handles that.

Now for something completely different.  Here's a RIFL wrapper for a database transaction in Perl, annotated (comments after # signs) so that those who don't know Perl can (I hope) follow it:

package XAct; # class
use Moose;

has '_dbh' => (is => 'ro'); # private data

sub Atomically { # RIFL function
    my ($dbh, $func) = @_;
    my @results;
    $dbh->begin_work; # start transaction
    eval { # try
    my $wrap = XAct->new(_dbh => $dbh);
    @results = $func->($wrap); # in transaction
    $dbh->commit;
    };
    if ($@) { # catch
    $dbh->rollback;
    die $@; # rethrow
    }
    return @results;
}

sub prepare { # pass-through Use
    my ($self, @args) = @_;
    return $self->_dbh->prepare(@args);
}

1; # end package

The RIFL function Atomically guarantees that the transaction is in effect when the passed-in function, $func is called; and that it is cleaned up afterwards.  A transaction, unlike a typical resource, can be Released either by a Commit or by a Rollback.  Atomically guarantees that if $func does not throw, the transaction is committed; and if it does throw, the transaction is rolled back.  So, this is an additional complexity easily handled by RIFL.

As before, the transaction object (which is really the the database handle) is wrapped to prevent direct access to the commit or rollback.

Note that the database handle itself is a resource, which could also be managed by a RIFL function, but that is not included in this example.

Here is an example function using Atomically:

sub InsertSomeNames {
    my ($dbh, %map) = @_;
    my $sql = 'INSERT INTO SomeNames(Id, Name) VALUES(?,?)';
    XAct::Atomically($dbh, sub {
    my ($xact)=@_; # get resource
    my $sth = $xact->prepare($sql); # use directly
    while (my ($id, $name) = each(%map)) {
        $sth->bind_param(1, $id);
        $sth->bind_param(2, $name);
        $sth->execute; # use indirectly
        }
    });
};

Here the transaction is being passed to the inner function as $xact, which is being used to insert many values into the database.  If any of those inserts fail, all of them will be rolled back; they will only be committed if they all succeed.

The point of this post is that the RIFL pattern is pretty easy to implement and pretty easy to use in many languages.  It relies only on good anonymous functions (lambda functions), used when calling the RIFL function.  Of course, you also have to be able to reasonably manage the resource so that it is guaranteed to be freed at the end of the RIFL function; but it seems like that's a fundamental prerequisite to being able to manage resources in any way in the language.

In the next post, I'll compare RIFL with RAII and show some C++ examples.