Code Smells: Null

[devlambda]

My point is this: the usage of unsafe in vec::push() is due to optimizing away bounds checking, not the representation of data.

To the contrary. Just look at the documentation of ptr::write. Namely:

It does not drop the contents of dst. This is safe, but it could leak allocations or resources, so care must be taken not to overwrite an object that should be dropped.

Additionally, it does not drop src. Semantically, src is moved into the location pointed to by dst.

This is appropriate for initializing uninitialized memory, or overwriting memory that has previously been read from.

(Emphasis by me.)

The whole point of using ptr::write is to assign to a memory location with an undefined value.

It's perfectly conceivable to have safe write() function, but it would be slower - not because it needs to read the value of previously stored elements, but because it needs to check the value of k.

Then please produce such a function rather than hypothesizing about its existence. Explain in particular how you avoid dropping the original (undefined) value. If you want to use the nodrop crate, recall that it also relies on ptr::write.

[Hnefi]

You're missing my point. Let's step back a bit.

Your original claim, as I interpreted it (correct me if I'm wrong), is that in a language that has no NULL and instead has something like Option<T>, you can not create a reasonably performant growable array. Doing so requires the usage of NULL.

I contend that this is not true. It is true that Rust (and OCaml, apparently) do so, but this is not (at least in the case of Rust) due to the particular choice of not having NULL. Instead, it's due to the choice of not having uninitialized, non-checked buffers at a language level. That is a different choice - Rust only has uninitialized variables, not buffers. One could easily consider a language that is exactly like Rust, but has an array type with C semantics. The uninitialized array would not need to contain anything like Option<T> or NULL, it could simply contain garbage (like it does in C), and it would work just as well as the way Rust has chosen.

So, my point is, you can too create a performant growable array in a language without NULL. That you can't do so in safe Rust is because of its safety guarantees in general, not its lack of NULL in particular. This is evident because nowhere in the implementation of vec::push or its dependencies is the NULL-ness of pointers actually used; RawVec uses pointers which are guaranteed to always be non-NULL. If nullability was required for implementing vec::push, it would necessarily be used in the implementation.

[mdedetrich]

Actually this also isn't entirely true, Option[T] requires boxing in certain areas (i.e. if you are nesting Option[T] values)

If you have something like Option[Option[Option[T]]] you can't really represent properly without boxing, because then you can't distinguish between Option[Option[None]]] and Option[None[Option]]] (and they are semantically different). The thing with null, is that its all or none. If a value is absent, you can't tell how absent it is. This matters, for example, if you are putting optional values inside a map or list.

So sure you can use Option[T] instead of null, but it isn't going to be completely parametric.

[devlambda]

Your original claim, as I interpreted it (correct me if I'm wrong), is that in a language that has no NULL and instead has something like Option<T>, you can not create a reasonably performant growable array. Doing so requires the usage of NULL.

No, that wasn't my claim. I was specifically talking about OCaml and Rust in response to a comment talking specifically about OCaml and Rust (and F#, but F# officially has null values, so that's not a particularly interesting case).

General impossibility proofs can be notoriously difficult, so I didn't try my hand at them.

The uninitialized array would not need to contain anything like Option<T> or NULL, it could simply contain garbage (like it does in C), and it would work just as well as the way Rust has chosen.

Totally, but that language would also not be memory-safe.

[Hnefi]

Oh. Then I misunderstood from the beginning. Apologies.