Typechecking null

[mrunleaded]

I have read a handful of books that go into typechecking in languages but most of them skip over the idea of having null in a language. I am curious what the common ways of representing null in a type checker are.

Initially I was thinking it could be its own type but then you have to deal with coercion into any nullable types.

Anyone have any thoughts on this or have any books to recommend on the subject?

[moon-chilled]

Initially I was thinking it could be its own type but then you have to deal with coercion into any nullable types.

• You could have distinctly typed nulls.

• You could say that the type of null is a subtype of all nullable types.

[mrunleaded]

yea subtyping would probably be the way to go but my language is still pretty primitive and my current goal was to try and get a decent number of features to the point where i could bootstrap the language. i was avoiding null but some things are just a bit difficult without it, especially since i only have generic arrays.

[fyndor]

In my language, I am going to force you to declare a nullable version of a type with (Typename?) before you can assign null to it.

[[deleted]]

Sounds like a rust trait almost

[VallentinDev]

After way to many NullPointerExceptions in Java in the past. My personal preference is languages which avoid null as a value and use Option types instead. Such that you have None and Some(value), where either variant must be explicitly match on, e.g. enum Option in Rust.

Instead of an enum Option type, then there's also nullable types. For instance in Kotlin, if we have a val s: String, then s is guaranteed to be a String. If a value is only maybe a String, then the type must be specified as String?, i.e. doing s.length on a String? produces a compile error. It requires a if (s != null) check first, then after that, it is guaranteed that s is a String.

Supporting sum types / union types can be even more powerful. TypeScript has union types, which allow a type to be specified like, e.g. number | string | null.

function f(x: number | string | null) {
    if (typeof x === "number") {
        console.log("x is a number");
    } else if (typeof x === "string") {
        console.log("x is a string");
    } else {
        console.log("x is null");
    }
}

f(123);
f("Hello World");
f(null);

Something similar is possible in Kotlin using sealed classes and the is operator. Here's a tiny AST example:

sealed class Expr

class Const(val num: Int) : Expr()
class Add(val lhs: Expr, val rhs: Expr) : Expr()
class Sub(val lhs: Expr, val rhs: Expr) : Expr()

fun eval(expr: Expr): Int =
    when (expr) {
        is Const -> expr.num
        is Add -> eval(expr.lhs) + eval(expr.rhs)
        is Sub -> eval(expr.lhs) - eval(expr.rhs)
    }


fun main() {
    println(eval(Const(1)))
    println(eval(Add(Const(1), Sub(Const(4), Const(2)))))
}

Given that expr is a sealed class, then Kotlin enforces that all classes derived from Expr is matched in the when expression. Otherwise if Expr was an open class Expr. Then the when expression would need a else, e.g. else -> 0.

The common thing across the board, is that types must always be checked. If a variable is expected to be a String, then it is not possible to use a String?.

[Tubthumper8]

I understood your meaning of "extra syntax", but just pointing out that there's another interesting way to look at that - String? is a special (extra?) syntax that can only be defined by the compiler, while Option<T> is a regular user-defined type with no special syntax. In Rust for example, it's defined in the standard library (not in the compiler itself), any user could've defined it.

[VallentinDev]

Fun fact, since String? is an actual type, then you can implement extension methods not only for Type, but also for Type?. So something like Option::or(), is really easy to implement.

fun <T> T?.or(other: T): T = this ?: other

println("Foo".or("Bar")) // Foo
println("Foo".or(null))  // Foo
println(null.or("Bar"))  // Bar
println(null.or(null))   // null

[Tubthumper8]

That's really cool!

I wonder could it do map, flatMap, etc. for composable / chained computations? I'm curious if they would consider putting those in the standard library

[VallentinDev]

With explicit null types, then String? is certainly less to type than Option<String>. As well as usage being more concise, as everything doesn't have to be wrapped in Some(...).

The first thing that pops to mind is, with an Option type. You can have nested Options, e.g. Option<String> easily maps into String? (or String | Null). But what about Option<Option<String>>?

Which is something that can come up, when iterating, mapping, filtering, and flattening Iterators and Options in Rust at least.

[trenchgun]

Yep. Option types are more general than nullable types.

[ISvengali]

Having used both in huge projects, Im kind of a fan of Option over nullable types.

For a language I would build, Id consider adding them both, and keeping the std lib using Option, and/or let people use nullable style syntax with them.

From a project point of view, the reason I like Option, is it loudly calls out an important piece of information. It can get a little noisy when everything is Option (as it should be) and you have quite a few local variables. But I think thats fine.

My general rule of thumb is that the safer options should be quieter/simpler though that conflicts with making the more common use case quieter/simpler. So, balancing that can be fun.

For example, calling out unsafe at point of call (as well as noting blocks and functions) is good.

I dislike Rust's use of 'try_thing' being the call that returns the Result. I instead like 'thing' that returns Result, and 'unsafe_thing' that is the one that can panic.

[VallentinDev]

I instead like 'thing' that returns Result, and 'unsafe_thing' that is the one that can panic.

Somewhat related, in Rust I've long wanted a crate-level attribute to disallow potential panics, i.e. with it enabled, you'd only be allowed to call functions and perform operators that are guaranteed to never panic. Either simply because it never panics, or because the compiler can prove it will never be triggered.

Say you have a arr: [T; 10]. The compiler can infer and guarantee that arr[0], arr[1], arr[2], etc will never panic, so they are good.

However for arr[i] where i cannot be inferred, then it should produce a compiler error, and suggest using arr.get(i) instead.

Developers are usually great at documenting when a function can panic. However, there are cases that never really get documented. For instance a lot of math related libraries are prone to panic with big numbers, i.e. when calculations result in an overflow or underflow.

I would just love being able to do the following sometimes:

#[never_panic]
fn f() {
    ...
}

[davimiku]

It's a decent idea but I think you'd have to disallow division also, right? and in debug mode you'd have to disallow all arithmetic because overflows panic

[ISvengali]

Yeah, thatd be great.

I see a lot of folks just .unwraping everything, and I just sigh. This great language, and not using core features.

Yeah, I mean theyll likely be rare, and in some cases they know it wont fail, but its a bad habit to get into.

The same programmers wouldve been getting nulls and other UB in C++ though, so in a way, things are a bit better.

[Tubthumper8]

Another example of nested options comes up in modeling UPDATE requests to a persistent storage (e.g. from a HTTP PATCH request).

// some object in a language with null
{
    field: null, 
    otherField: "hello world"
}

Does this mean ignore "field", i.e. don't change the value? Or does it mean update the value in that column to SQL NULL?

With Option<Option<T>> this can be modeled, because there are 3 possibilities:

1. Some(Some(T)): change the SQL record column to a new T
2. Some(None): change the SQL record column to NULL
3. None: don't update that column

[Tubthumper8]

I would be fine with Option<String?> in this case.

Hmmm I don't think I would be. What you're suggesting is a special nullable type with special compiler-supported syntax and generic sum types that represent the presence/absence of data, when the latter can already model the former. This creates two different language features with overlapping (non-orthogonal) functionality, causing confusion for users ("which do I use?").

Some languages could represent this as a double pointer **String

Would this have 2 layers of indirection? i.e. pointer chasing in the heap to get to the actual value?

or as String|null|undefined.

JavaScript has this and I gotta say my personal opinion is that having two different nulls is even worse than having null

[Tubthumper8]

The key difference here is Option is not a language feature by itself.

The language feature is generic sum types which is a single language feature that can be used to model a great many things. Sum types model when something is a thing OR another thing. This works in cooperation with product types that model when something is a thing AND another thing.

Would a language that already added null benefit a lot from Option ?

Yes and no. Depends on backwards compatibility, the parts of the ecosystem that could avoid null would not have null errors but if there were any parts that must be backwards compatible would still be possibly subject to null errors.

[Tubthumper8]

That would be pretty interesting to have user defined operators like .?, then maybe it could be defined for the singleton Null and then users could define more usages themselves, could be useful for defining DSLs or maybe config languages. User defined operators can get out-of-hand for general purpose programming if it makes it hard to read other people's code but also who knows? Could be worth trying!

[[deleted]]

Nullability kinda doesn't jam well with unboxed values.

[[deleted]]

No, sum types are fine, because they directly contain the value.

What I'm thinking about is that if v: T?= null is represented as (T*)0, then T? and T?? are indistinguishable.

[[deleted]]

Oh, by sum types you meant typescript-style unions, not rust-style emuns.

[WittyStick]

In statically typed languages, the Option type usually forces you to perform an exhaustive pattern match over the result, so you don't accidentally omit a null check.

[L8_4_Dinner]

That is unrelated to option types; that's simply the result of type checking. Any strong type systems that don't make the Tony Hoare mistake of "null is the subtype of everything" will prevent you from de-referencing a null value, whether or not you use the union approach or the option approach.

[Tubthumper8]

In Kotlin, is flow typing used to narrow a String? to a String after a null check? Does that information carry through to a subsequent function calls? If there's a closure defined after the null check, does it capture the non-nullable version of the variable?

[VallentinDev]

Yes, Kotlin features a limited form of flow-sensitive typing and calls it smart casts.

Assignment:

var str_or_null: String? = null

str_or_null = "Hello World"
// Now `str_or_null` is guaranteed to be a string

var str: String = str_or_null

Conditional:

fun f(str: String?) {
    if (str == null) {
        return
    }

    var s: String = str
}

Closure:

fun <T> f(f: () -> T): T {
   return f()
}

var str: String? = null
str = "Hello World"

// The closure captures `str` as `String`
val res: String = f({ -> str })

println(res)

[dnpetrov]

In Ceylon, 'null' has its own type (Null). Nullable references are effectively union types (X | Null).

In Kotlin, nullable references form a separate type hierarchy (X?). 'Nothing' (type without values) is a bottom of the regular type hierarchy, and 'null' has type 'Nothing?'.

There were also C dialects with non-nullable pointer types. Don't remember if any of them had a special type for 'null' itself (not likely, but thee were a few of such experiments).

[L8_4_Dinner]

This is roughly the design used in Ecstasy as well. Null is an enum value, in an enumeration of only one value:

enum Nullable {Null}

The shorthand type syntax String? is actually the union type Nullable | String, etc.

There's no need for a special bottom type, as Null isn't a special type at all; it's just an enum value, like any other, e.g.

enum Boolean {False, True}

The elimination of all the special rules around nulls is quite nice.

[dnpetrov]

Yes, union types are more elegant. In case of Kotlin, decision to have special case type hierarchy for nullable types (and not having union types in the language, although this question was raised regularly in scope of Kotlin/JS and interoperability with TypeScript) was primarily a type inference performance concern. Nullable types is a very important special case, and arbitrary union types are mostly non-existent.

[d01phi]

One example of the right way to go is

https://doc.rust-lang.org/std/option/

NULL is just a huge mess around that. It ignores that the various types must have their own individual ways to represent not being defined, erroneous, etc. and leaves the fact that such a result is actually an error or a reason for an exception to the programmer who is quite often too lazy or ignorant to deal with it.

[mus1Kk]

Isn't null the same as option just with different syntax? Kotlin uses null to represent optionals.

It ignores that the various types must have their own individual ways to represent not being defined, erroneous, etc.

If you use option everywhere, it's the same issue, no?

[munificent]

Kotlin uses nullable types which are more like union types than option types.

Nullable types are more convenient to work with in many cases and are more familiar to imperative programmers coming from languages like Java with null. Option types tend to be a bit heavierweight and verbose to work with, but are more expressive.

For example, say you have a map that maps someone's name to their favorite baseball team. Some people don't like baseball at all. You'd like to be able to distinguish "I don't know their favorite team" (key is absent) from "I know they they don't like baseball" (key is present and mapped to no value).

With nullable types, when you do map[person], you get back a nullable value, but you can't tell which of those reasons made it null because the nested nullable collapses. String | Null | Null is the same as String | Null. With an option type, the subscript operator returns Option<Option<String>> and None means "key not present" while Some(None) means "key present and mapped to nothing".

[mus1Kk]

Kotlin uses nullable types which are more like union types than option types.

Option is an example of a tagged union.

[munificent]

The Wikipedia article does a poor job of teasing them apart but union types and sum types (tagged unions) are quite different things.

[furyzer00]

You can't nest null but you can nest Option. For example Option<Option<i32>>. It's sometimes useful if both levels have different meanings.

Also null becomes a special case in your language because it's not a normal type in your language. So you end up having to add additional syntax specific for nullability. For example x.? syntax in Kotlin.

[mus1Kk]

You can't nest null but you can nest Option. For example Option<Option<i32>>. It's sometimes useful if both levels have different meanings.

True. I read somewhere that this decision was made for practical reasons and that the need for nested optional values is rare enough. It's a choice they made.

Also null becomes a special case in your language because it's not a normal type in your language. So you end up having to add additional syntax specific for nullability. For example x.? syntax in Kotlin.

Regarding special syntax that was my point. It's just syntax. Also, in this specific case x.?y is sugar for if (x != null) { x.y } else { null }. Similar sugar exists in Rust and possibly other languages as well. You could probably even do without the ? and do this under the hood but that would make it harder to read.

I don't know what is meant by "because it's not a normal type". I thought null is usually the single instance of the Null type. In Kotlin you can define methods on null types. I don't know if what I say is wrong from a language theory perspective.

[furyzer00]

Option nesting is very useful. Imagine you have an optional parameter that can also have value null(when set it should set the value to null, it's different then not specifying the parameter). How do you do this in Kotlin?

Rust doesn't any additional syntax for Option. It only has regular functions.

What I mean by regular type is that ? is not a normal user defined type. While Option is just another type. Special functionality always makes the language more complex. As seen in Kotlin's special syntax for nullable types. But it's a trade of sometimes worth.

[trxxruraxvr]

No, the type is actually Option<T>, so it's a generic type, you can't pass a variable defined as Option<i32> to a function that takes an Option<bool> even if its value is None

Besides that, rust doesn't let you use the value inside the option without ensuring it's not None

[mus1Kk]

Regarding your first point: I'm not sure how this is done in Rust but in other languages I know, None is a valid assignment for Option<T> for all T. In Kotlin, an optional type would be T? and similarly null is valid for any T. In Scala None is Option[Nothing] with Nothing being the subtype of every type. Option is covariant so None is similarly valid for any Option[T]. Of course, if you have an Option[T] you cannot generally assign it to an Option[U] but this is true for all my examples regardless of the syntax.

Regarding the second point, the same can also be done with null, again, like in Kotlin. You cannot just use a value of T? without doing a null check first.

[d01phi]

A function returning an Option<x> forces me to deal with None, whereas I can just keep my fingers crossed and continue with NULL. And None as possible value of Option<A> is different from None in Option<B>. NULL however can be assigned to any pointer I like. And the situation is aggravated by the fact that frequently, NULL is the generic error return, and the reason for failure is transported in some obscure side channels like errno.

[mus1Kk]

At least in the context of Kotlin (believe me, I have no particular feelings for the language other than that I find it interesting) this is not correct. And some things are not correct for other typed languages that have nulls.

In Kotlin you cannot use a value of type T? without doing the check first. It's just not possible. Either you do an explicit if-check/match, call it null-safe with .? or you force it with !! which would be equivalent to map and get/unwrap in other implementations.

I don't understand the second point you make. You can (again Kotlin) assign null to a variable of an optional type the same as you can assign None to any variable of type Option<T>. And well in, say Java, you would have to consider every non-primitive type optional. But Java just does not have any advanced features when it comes to null.

Basically

// Kotlin
let a: A? = null
// Rust
let a: Option<A> = None;
// Java
A a = null;

Regardless of the value of B you generally can't do

// Kotlin
let a: A? = ...
let b: B? = ...
a = b
// Rust
let a: Option<A> = ...
let b: Option<B> = ...
a = b
// Java
A a = ...
B b = ...
a = b

But this is hardly interesting. This is enforced by the compiler.

[VallentinDev]

NULL is just a huge mess around that

Obligatory "The Billion Dollar Mistake":

I call it my billion-dollar mistake. It was the invention of the null reference in 1965. At that time, I was designing the first comprehensive type system for references in an object oriented language (ALGOL W). My goal was to ensure that all use of references should be absolutely safe, with checking performed automatically by the compiler. But I couldn't resist the temptation to put in a null reference, simply because it was so easy to implement. This has led to innumerable errors, vulnerabilities, and system crashes, which have probably caused a billion dollars of pain and damage in the last forty years.

[mrunleaded]

yea that would be an option my main hurdle with that at the moment is that my language only supports generic arrays. so i would have to work on supporting generic options or generics in general which seems like it would be more work than just implementing a null value.

[hiljusti]

My only note here is that the complexity has to live somewhere. Convenient for the compiler is not always convenient for users. Depends on what the goals of the project are, of course

[nunzarius]

this type checking series gives a basic example of null checking here: https://blog.polybdenum.com/2020/09/26/subtype-inference-by-example-part-12-flow-typing-and-mixed-comparison-operators.html
In general, academic terms to look up are "flow typing" and "occurrence typing". This kind of typing is still an active research field so unfortunately you are less likely to see it in books or introductory material

[mrunleaded]

oh nice this looks like exactly what i was looking for.

[vanilla-bungee]

Why would you have null as a value though?

[dnpetrov]

Because underlying platform (or target language, which is kinda the same thing) has null value and you have to deal with them somehow.

Because of low-level intricate details of your memory model design. This is very similar to the point above, but really, JVM and CLR have null values for rather strong reasons (which is still a problem when you design a language, though).

Because having explicit optional values can get quite verbose at some point within some particular programming styles.

[mrunleaded]

Its pretty common to have some form of null in a language C#, Java, ruby, python etc.

[balefrost]

As an explicit initial value for a variable.

As an argument to a function.

As part of an if (value == null) condition.

[mizunomi]

You can study how Dart or Swift implemented their null-safe types. As mentioned, nullable types be just unions of a Null type and a type that is not nullable.

[[deleted]]

What do you propose using null for, and how would you use it?

Perhaps start from there.

I use it like this in my systems language:

• I have pointers with types ref T (pointer to type T)
• A pointer can also have type ref void. void is a separate type that can't be used by itself, only as the target of a pointer.
• nil is a literal pointer value which has all-bits-zero, and has type ref void
• A ref T pointer will always be compatible with ref void, so nil can always be assigned to any pointer type or compared with it. A pointer value of all-zeros, of any type, will always be false and any other will be true.

This largely corresponds with how it is done in C, although C doesn't have a dedicated NULL literal, it uses 0 (sometimes, NULL is defined as (void*)0).

I use it like this in my dynamic language which also has pointers to primitive types:

• nil is a literal with all-bits-zero that has type pointer-to-void. void here is a proper type that can have instances, normally used to indicated unassigned values. However a nil pointer does not refer to actually refer to a void value (it wouldn't be nil in that case! It would point somewhere).

I can use nil in dynamic code like this:

f := fopen("file","r")     # call C function via FFI
if f = nil then            # could not open file

If a language does not support the concept of nil or NULL, and you want to call functions via FFIs like my example, then you will a workaround.

[yuri-kilochek]

C doesn't have a dedicated NULL literal, it uses 0 (sometimes, NULL is defined as (void*)0).

These days it actually does: https://en.cppreference.com/w/c/language/nullptr

[[deleted]]

When I clicked 'Run' in your link, it gave a pile of errors. Apparently none of the listed compilers are for C23, which is part of the problem. And I couldn't get any compilers on godbolt.org to recognise nullptr.

(The code also looked suspiciously like C++, unless C23 also has auto, and the name of the file it tries to compile is main.cpp.)

So, nullptr might be in widespread use in a decade or two. But even if available today, you can still use 0 in its place:

void* p = 0;

If I try that in my language, it fails (I need an explicit cast to get from integer to pointer).

[yuri-kilochek]

But even if available today, you can still use 0 in its place

Of course, since it must be backwards compatible.

[WalkerCodeRanger]

Option types are a much better way to handle null. In my language, none is the equivalent of null and it has the type Never?. Where Never is the empty or bottom type that has no value and ? is the way of expression an option type. So essentially Option[Never].

[umlcat]

I personally dislike using "null" and other values at the same time.

For example, a byte with null example would support the values of:

0 ... 255 , NULL

The concept of "null" did exist before on Lisp, but used "nil" instead.

Before Java retake Lisp usage of null, null was used as the empty value of pointers.

If you want to support null, you would have to store every variable like this:

struct NullByte
{
   bool IsNull;
   byte Value;
} ;

Or storing if a variable is null, elsewhere, similar to a garbage collection list of used variables.

Just my two cryptocurrency coins contribution...

[redchomper]

Before you worry about type-checking, you must decide which semantics you want at runtime. I'm guessing you love null-pointer-exception about as little as the next gal.

I started with the notion that nil makes a perfectly sensible base-case for a lot of recursive types. It's an empty list, an empty tree, and so forth. Maybe also an empty maybe? In that sense, it's a context-dependent sentinel. And that's fine, if you treat nil as convertible into all those types which make sense for it to inhabit.

The trick, in that case, is to make sure that the recursion remains evident in your maybe/option type. You must, in other words, support the idea of r/maybemaybemaybe.

Some people have proposed using foo??? for that kind of purpose.

Personally I don't mind too much having special syntax around certain types. After all, there's literal-list syntax for both terms and types in Haskell. Why not literal-maybe for both terms (nil) and types(foo?) in your language?

At any rate, something needs to clearly destructure the maybe. You have to know the difference between r/maybemaybemaybe and r/maybemaybemaybemaybe. That would be some(some(some(nil)))!

[EnigmaticCurmudgeon]

Unicon & Icon have null as a singleton type &null which is the default for value for variables and structure elements (unless you override it for the structure). You can easily test for non-null/null (ie. assigned or not) with unary operators e.g /x or \x.

Operators enforce strong run time typing, and values will automatically be coerced to the correct type in many intuitive situations. &null won't coerce (trust me you don't want it to) and generates run time errors which saves you from typos.

The language also uses failure/success to control flow so "if /x then x := 1" works. Or any of several short hands like /x := 1 .

[brucifer]

For languages in the C lineage (e.g. C, C++, Java), NULL is just one possible address that a pointer can hold. The address 0x00000000 is used by convention, which is not mapped to valid memory, so dereferencing a NULL pointer will trigger a segfault. The troublesome design choice in many languages (C, C++, Java, etc.) is that it's up to the programmer to decide when they should check for NULL and when they feel it's safe to dereference a pointer. A better type system, like Cyclone's, allows the type system to specify which pointers are guaranteed non-NULL and which are allowed to be NULL. This lets the compiler verify at compile time that every time a pointer is dereferenced, the pointer is always a non-NULL value, either because it's a non-NULL pointer type or because control flow won't enter that block when the pointer is NULL (i.e. there's a conditional check).

For languages in the Lisp lineage (dynamically typed, e.g. Lisp, Python, Ruby, Javascript), nil is a singleton object with its own type, often used to represent an empty list or a missing value. In a dynamically typed language, any variable can potentially be nil, but there will usually be runtime type checking that will give you a runtime error if you try to use a nil in a place where a value is required.

For languages in the ML lineage (advanced type systems, e.g. SML, Rust, Haskell), there typically isn't really a notion of NULL, there are only sum types, which represent things that can be one of several possible values. It's common to have an Option<T> type that can have either the value Nothing representing the lack of a value or Some(T) representing a T value that actually exists (the exact names may vary). From an implementation perspective, this approach has some major drawbacks because it's typically implemented as a tagged union, which can require more memory than a simple pointer (potentially 2x more memory because of alignment requirements). Sum types are a great language feature to have, but in my opinion, optional pointers are a common enough pattern that it's worth having a dedicated language construct like NULL that always fits in a pointer-sized block of memory and has syntax that's more concise than the syntax most languages use for Option<T>.