Null reference and end of list

Rust as I know, avoid null references. Why? Inventor of null say that null causes problems. What are these problems, what instead of null. How do linked lists for example?
Creating list in c-like pseudocode

node_t *head=null;
for (int i=0; i<10; i++)
{
  node_t *node = new();
  node->next = head;
  head = node;
}

and iteration over list:

p = head;
while (p)
  p = p->next;

Second: if heap object can have one owner in Rust, this means, iteration over list, frees objects?

I'd say that the main of them is implicitness. You must always keep in mind that anything can suddenly arrive as null.

Nullable types - in case of Rust this will be Option.

Check this, if you're sure that this kind of structure worth the trouble.

Not necessarily - iterator may borrow the objects, not taking them out of the list. Think of this as temporary locking access to the particular address in memory.

3 Likes

The inventor of the null reference was Tony Hoare. I would not argue with him if he says it was a mistake. I think he explains well enough here:

To my simple mind the case is clear. The null reference has much in common with the error return values you found in languages like C.

In both cases the issue is that the thing you are holding has two types. On the one hand it is primarily a thing that you want and are thinking about, a reference to another node or a returned value. On the other hand it is sometimes an error or special marker.

One has to continually write code to check those special cases. The compiler has no idea what is going on, it cannot help you, so it's up to you to get it right every time.

It's like holding a puppy in your hand that suddenly turns into a hand grenade!

Rust introduces the Option to do what you want with null. But as it is an actual type the compiler can help you handle it correctly.

Much can be said of the linked list. It's a great example in C programming books. As your code snippet above shows. Turns out that that is pretty much all it is good for :slight_smile:

2 Likes

Rust's solution for the nil/null is the Option type. It not only solves the problem of nil/null, it solves it with a type correct solution.

In Rust Option<NodePointer> optimizes to code identical to an actual nullable pointer, so the compiled program works the same and has the same performance. The difference is only in language semantics which force you to check if the Option is Some(node) or None.

It may seem Option similar to a nullable pointer, but the crucial difference is you can't just use Option<Node> where Node is required. The program treats them as different types, and always makes you check for None if the value is optional. OTOH it doesn't require you to check for None/null where it knows it's a regular type, not an optional one. In C whether something can be null or not is an unwritten assumption you need to keep in mind. In Rust that is part of the program that the compiler checks for you.

Lack of null fixes a type-system bug that other languages have:

  1. You have a type node_t which has a next field.
  2. You're given a pointer to the type node_t.
  3. Given that 1 and 2 is true, can you access the next field? You don't know! Type information is unreliable and it's sometimes a lie. You ask for node_t with a next field, but you may get a pointer to a different type of object that doesn't have the next field and node->next will crash! null is a case which breaks type systems. In Rust if you have node_t you have 100% guarantee it's always node_t and it always has fields it says it has.
5 Likes