53

Eric Lippert made a very interesting point in his discussion of why C# uses a null rather than a Maybe<T> type:

Consistency of the type system is important; can we always know that a non-nullable reference is never under any circumstances observed to be invalid? What about in the constructor of an object with a non-nullable field of reference type? What about in the finalizer of such an object, where the object is finalized because the code that was supposed to fill in the reference threw an exception? A type system that lies to you about its guarantees is dangerous.

That was a bit of an eye-opener. The concepts involved interest me, and I've done some playing around with compilers and type systems, but I never thought about that scenario. How do languages that have a Maybe type instead of a null handle edge cases such as initialization and error recovery, in which a supposedly guaranteed non-null reference is not, in fact, in a valid state?

6
  • I guess if the Maybe is part of the language it might be that it is internally implemented via a null pointer and it's just syntactic sugar. But I don't think any language actually does it like this.
    – panzi
    May 3, 2014 at 23:01
  • 1
    @panzi: Ceylon uses flow-sensitive typing to distinguish between Type? (maybe) and Type (not null)
    – Lukas Eder
    May 4, 2014 at 5:44
  • 1
    @RobertHarvey Isn't there a "nice question" button in Stack Exchange already?
    – user253751
    May 4, 2014 at 8:47
  • 2
    @panzi That is a nice and valid optimization, but it doesn't help with this problem: When something isn't a Maybe T, it must not be None and hence you can't initialize its storage to the null pointer.
    – user7043
    May 4, 2014 at 14:24
  • @immibis: I already pushed it. We get precious few good questions here; I thought this one deserved a comment. May 4, 2014 at 20:45

6 Answers 6

45

That quote points to a problem that occurs if the declaration and assignment of identifiers (here: instance members) are separate from each other. As a quick pseudocode sketch:

class Broken {
    val foo: Foo  // where Foo and Bar are non-nullable reference types
    val bar: Bar

    Broken() {
        foo = new Foo()
        throw new Exception()
        // this code is never reached, so "bar" is not assigned
        bar = new Bar()
    }

    ~Broken() {
        foo.cleanup()
        bar.cleanup()
    }
}

The scenario is now that during construction of an instance, an error will be thrown, so construction will be aborted before the instance has been fully constructed. This language offers a destructor method which will run before the memory is deallocated, e.g. to manually free non-memory resources. It must also be run on partially constructed objects, because manually managed resources might already have been allocated before construction was aborted.

With nulls, the destructor could test whether a variable had been assigned like if (foo != null) foo.cleanup(). Without nulls, the object is now in an undefined state – what is the value of bar?

However, this problem exists due to the combination of three aspects:

  • The absence of default values like null or guaranteed initialization for the member variables.
  • The difference between declaration and assignment. Forcing variables to be assigned immediately (e.g. with a let statement as seen in functional languages) is an easy was to force guaranteed initialization – but restricts the language in other ways.
  • The specific flavor of destructors as a method that gets called by the language runtime.

It is easy to choose another design that does not exhibit these problems, for example by always combining declaration with assignment and having the language offer multiple finalizer blocks instead of a single finalization method:

// the body of the class *is* the constructor
class Working() {
    val foo: Foo = new Foo()
    FINALIZE { foo.cleanup() }  // block is registered to run when object is destroyed

    throw new Exception()

    // the below code is never reached, so
    //  1. the "bar" variable never enters the scope
    //  2. the second finalizer block is never registered.
    val bar: Bar = new Bar()
    FINALIZE { bar.cleanup() }  // block is registered to run when object is destroyed
}

So there is not an issue with the absence of null, but with the combination a set of other features with an absence of null.

The interesting question is now why C# chose one design but not the other. Here, the context of the quote lists many other arguments for a null in the C# language, which can be mostly summarized as “familiarity and compatibility” – and those are good reasons.

1
  • There is also another reason why the finalizer has to deal with nulls: the order of finalization is not guaranteed, because of the possibility of reference cycles. But I guess your FINALIZE design also solves that: if foo has been already finalized, its FINALIZE section simply won't run.
    – svick
    May 13, 2014 at 19:03
15

The same ways you guarantee any other data is in a valid state.

One can structure semantics and control flow such that you can't have a variable/field of some type without fully creating a value for it. Instead of creating an object and letting a constructor assign "initial" values to its fields, you can only create an object by specifying values for all its fields at once. Instead of declaring a variable and then assigning an initial value, you can only introduce a variable with an initialization.

For example, in Rust you create an object of struct type via Point { x: 1, y: 2 } instead of writing a constructor that does self.x = 1; self.y = 2;. Of course, this may clash with the style of language you have in mind.

Another, complementary approach is using liveness analysis to prevent access to storage before its initialization. This allows declaring a variable without immediately initializing it, as long as it's provably assigned to before the first read. It can also catch some failure-related cases like

Object o;
try {
    call_can_throw();
    o = new Object();
} catch {}
use(o);

Technically, you could also define an arbitrary default initialization for objects, e.g. zero all numeric fields, create empty arrays for array fields, etc. but this is rather arbitrary, less efficient than other options, and can mask bugs.

8

Here's how Haskell does it: (not exactly a counter to Lippert's statements since Haskell is not an Object-Oriented language).

WARNING: long winded-answer from a serious Haskell fan-person ahead.

TL;DR

This example illustrates exactly how different Haskell is from C#. Instead of delegating the logistics of structure construction to a constructor, it must be handled in the surrounding code. There is no way for a null (Or Nothing in Haskell) value value to crop up where we are expecting a non-null value because null values can only occur within special wrapper types called Maybe which are not interchangeable with/directly convertible to regular, non-nullable types. In order to use an value made nullable by wrapping it in a Maybe, we must first extract the value using pattern matching, which forces us to divert control flow into a branch where we know for certain that we have a non-null value.

Therefore:

can we always know that a non-nullable reference is never under any circumstances observed to be invalid?

Yes. Int and Maybe Int are two completely separate types. Finding Nothing in a plain Int would be comparable to finding the string "fish" in an Int32.

What about in the constructor of an object with a non-nullable field of reference type?

Not an issue: value constructors in Haskell can't do anything but take the values they're given and put them together. All initialization logic takes place before the constructor is called.

What about in the finalizer of such an object, where the object is finalized because the code that was supposed to fill in the reference threw an exception?

There are no finalizers in Haskell, so I can't really address this. My first response still stands, however.

Full Answer:

Haskell has no null and uses the Maybe data type to represent nullables. Maybe is an algabraic data type defined like this:

data Maybe a = Just a | Nothing

For those of you unfamiliar with Haskell, read this as "A Maybe is either a Nothing or a Just a". Specifically:

  • Maybe is the type constructor: it can be thought of (incorrectly) as a generic class (where a is the type variable). The C# analogy is class Maybe<a>{}.
  • Just is a value constructor: it is a function that takes one argument of type a and returns a value of type Maybe a that contains the value. So the code x = Just 17 is analogous to int? x = 17;.
  • Nothing is another value constructor, but it takes no arguments and the Maybe returned has no value other than "Nothing". x = Nothing is analogous to int? x = null; (assuming we constrained our a in Haskell to be Int, which can be done by writing x = Nothing :: Maybe Int).

Now that the basics of the Maybe type are out of the way, how does Haskell avoid the issues discussed in the OP's question?

Well, Haskell is really different from most of the languages discussed so far, so I'll begin by explaining a few basic language principles.

First off, in Haskell, everything is immutable. Everything. Names refer to values, not to memory locations where values can be stored (this alone is an enormous source of bug elimination). Unlike in C#, where variable declaration and assignment are two separate operations, in Haskell values are created by defining their value (eg x = 15, y = "quux", z = Nothing), which can never change. Therefore, code like:

ReferenceType x;

Is not possible in Haskell. There are no problems with initializing values to null because everything must be explicitly initialized to a value in order for it to exist.

Secondarily, Haskell is not an object-oriented language: it is a purely functional language, so there are no objects in the strict sense of the word. Instead, there are simply functions (value constructors) that take their arguments and return an amalgamated structure.

Next, there is absolutely no imperative style code. By this, I mean that most languages follow a pattern something like this:

do thing 1
add thing 2 to thing 3
do thing 4
if thing 5:
    do thing 6
return thing 7

Program behavior is expressed as a series of instructions. In Object-Oriented languages, class and function declarations also play a huge role in program flow, but is essence, the "meat" of a program's execution takes the form of a series of instructions to be executed.

In Haskell, this is not possible. Instead, program flow is dictated entirely by chaining functions. Even the imperative-looking do-notation is just syntactic sugar for passing anonymous functions to the >>= operator. All functions take the form of:

<optional explicit type signature>
functionName arg1 arg2 ... argn = body-expression

Where body-expression can be anything that evaluates to a value. Obviously there are more syntax features available but the main point is the complete absence of sequences of statements.

Lastly, and probably most importantly, Haskell's type system is incredibly strict. If I had to summarize the central design philosophy of Haskell's type system, I would say: "Make as many things as possible go wrong at compile time so as little as possible goes wrong at runtime." There are no implicit conversions whatsoever (want to promote an Int to a Double? Use the fromIntegral function). The only to possibly have an invalid value occur at runtime is to use Prelude.undefined (which apparently just has to be there and is impossible to remove).

With all of this in mind, let's look at amon's "broken" example and try to re-express this code in Haskell. First, the data declaration (using record syntax for named fields):

data NotSoBroken = NotSoBroken {foo :: Foo, bar :: Bar } 

(foo and bar are really accessor functions to anonymous fields here instead of actual fields, but we can ignore this detail).

The NotSoBroken value constructor is incapable of taking any action other than taking a Foo and a Bar (which are not nullable) and making a NotSoBroken out of them. There is no place to put imperative code or even manually assign the fields. All initialization logic must take place elsewhere, most likely in a dedicated factory function.

In the example, the construction of Broken always fails. There is no way to break the NotSoBroken value constructor in a similar fashion (there is simply nowhere to write the code), but we can create a factory function that is similarly defective.

makeNotSoBroken :: Foo -> Bar -> Maybe NotSoBroken
makeNotSoBroken foo bar = Nothing

(the first line is a type signature declaration: makeNotSoBroken takes a Foo and a Bar as arguments and produces a Maybe NotSoBroken).

The return type must be Maybe NotSoBroken and not simply NotSoBroken because we told it to evaluate to Nothing, which is a value constructor for Maybe. The types simply wouldn't line up if we wrote anything different.

Aside from being absolutely pointless, this function doesn't even fulfill its real purpose, as we'll we see when we try to use it. Let's create a function called useNotSoBroken which expects a NotSoBroken as an argument:

useNotSoBroken :: NotSoBroken -> Whatever

(useNotSoBroken accepts a NotSoBroken as an argument and produces a Whatever).

And use it like so:

useNotSoBroken (makeNotSoBroken)

In most language, this sort of behavior might cause a null pointer exception. In Haskell, the types don't match up: makeNotSoBroken returns a Maybe NotSoBroken, but useNotSoBroken expects a NotSoBroken. These types are not interchangeable, and the code fails to compile.

To get around this, we can use a case statement to branch based on the structure of the Maybe value (using a feature called pattern matching):

case makeNotSoBroken of
    Nothing  -> --handle situation here
    (Just x) -> useNotSoBroken x

Obviously this snippet needs to placed inside some context to actually compile, but it demonstrates the basics of how Haskell handles nullables. Here is a step-by-step explanation of the above code:

  • First, makeNotSoBroken is evaluated, which is guaranteed to produce a value of type Maybe NotSoBroken.
  • The case statement inspects the structure of this value.
  • If the value is Nothing, the "handle situation here" code is evaluated.
  • If the value instead matches against a Just value, the other branch is executed. Note how the matching clause simultaneously identifies the value as a Just construction and binds its internal NotSoBroken field to a name (in this case, x). x can then be used like the normal NotSoBroken value that is.

So, pattern matching provides a powerful facility for enforcing type safety, since the structure of the object is inseparably tied to the branching of control.

I hope this was a comprehensible explanation. If it doesn't make sense, jump into Learn You A Haskell For Great Good!, one of the best online language tutorials I've ever read. Hopefully you will see the same beauty in this language that I do.

1
  • 1
    TL;DR should be on the top :)
    – andrew.fox
    Jan 8, 2016 at 20:21
1

A long read

With constraints, I've found that applications have to make some concession regarding the building of data.

The constraints that are expected to apply when data is in some defined stationary configuration, are not the constraints that are expected to apply whilst the data is moving from one stationary configuration to another - when the data is being built or rebuilt.

This principle operates at more than one level. A non-nullable variable must inevitably pass through a stage where the memory is allocated but the intended value is not yet set.

A record with multiple fields, and with the constraint that all fields must be set, must inevitably pass through a stage where only some fields are set - and it must allow this state to exist temporarily whilst being built.

A database that requires multiple related records to be present together, must nevertheless allow some records to be missing for a moment during building, as one record is already added but the next has not yet been.

The principle also applies in multiple contexts. It applies not just in code for the programmer, but often to the front-end application as the user sees it.

User interfaces have to allow partial or temporarily invalid information to be entered. Clearly, a textbox requiring 10 characters minimum, must allow the user to start off with 1 character, then 2, then 3, etc, otherwise he would never reach 10 or more.

And if one field is validated based on another, then it must be possible for the slave field to be invalid for a moment during building, when the master field is altered in a way that imposes new constraints on the slave, but the slave field has not yet been altered to comply.

In fact, pestering the user forcefully about validation errors when they are clearly still in the process of building the record, is a known awkwardness and oversight by UI designers.

Any kind of system that allow constraints to be declared, generally has implied checkpoints when these constraints are actually checked and must be met. So the declaration of a constraint isn't the declaration of a rule that applies from the beginning to the end of time - it is the definition of a checking operation that takes place at a defined time.

With non-nullable variables, I suspect some people have followed a line of thinking that "we sometimes leave variables in our program in a half-built condition by mistake, therefore we should eliminate the build stage".

There's some echo here in the line of thinking about concurrent access to mutable data, and how the grand solution was supposed to be to make the whole program immutable and side-effect-free - and therefore inert and useless.

Actually non-nullable variables are only useful in a program when you have reached a stage where the build is over. So there will often be two stages in a program. The first where nullable variables are used, to allow the programmer to build the data. And the second where the building is complete and the non-nullable constraints are then checked and enforced.

The successful transition between the two is achieved by the programmer ensuring that upon arriving at the second stage, which occurs at a time of the programmer's own choosing, all variables that are in principle nullable, are in fact not null.

What you can see from this is that non-nullable variables do not exist to allow the programmer to be completely free of the concern of dealing with nulls. He must still deal with them properly during any stage where he is building data.

Non-nullable variables exist to allow him to check that the building stage of his program has worked correctly, and that if execution has passed that stage, then he need not worry about the possibility of nulls in his variables from then on (rather than the current state of affairs, where erroneous nulls can reach areas far away from the area where the error originated).

In languages that have non-null variables, the implication must be that the build stage for the specific non-null variable, is complete at the end of the declaration of the variable - the non-null check occurs immediately after the declaration, and the scope of the build stage is reduced to the minimum possible. Therefore, the declaration and assignment must be one composite operation in the language. And there must be a pre-built value ready to assign.

But note, the very concept of there being a build stage where nulls are acceptable, has not completely disappeared. Instead, there is merely an extreme locality of that build stage, and an extreme imminency of when the non-null check occurs.

0

I think your quote is a straw man argument.

Modern languages today (including C#), guarantee you that the constructor either fully completes or it does not.

If there is an exception in the constructor and the object is left partially uninitialized, having null or Maybe::none for uninitialized state makes no real difference in the destructor code.

You will just have to deal with it either way. When there is external resources to manage, you must manage those explicitly any way. Languages and libraries can help, but you will have to put some thought into this.

Btw: In C#, null value is pretty much equivalent to Maybe::none. You can assign null only to variables and object members that on a type level are declared as nullable:

String? nullableString = getOptionalString();
Nullable<String> maybe = nullableString; // This is equivalent

This is in no way different than the following snippet:

Maybe<String> optionalString = getOptionalString();

So in conclusion, I do not see how nullability is in any way opposite to Maybe types. I would even suggest that C# has sneaked in it's own Maybe type and called it Nullable<T>.

With extension methods, it is even easy to get the clean-up of the Nullable to follow the monadic pattern:

Resource? resource = initializationThatMayFail();
...
resource.ifExists( Resource r -> r.cleanup() );
15
  • 2
    what does it mean, "constructor either fully completes or it does not"? In Java for example, initialization of (non-final) field in constructor is not protected from data race - does that qualify as fully-completes or not?
    – gnat
    May 8, 2014 at 9:02
  • 1
    Sorry for the eight year late reply, just saw this now -- C# makes absolutely no guarantee that a constructor runs to completion. A constructor's thread can be aborted! But it is far, far worse than that! A partially constructed object where the constructor was aborted is still an object, and therefore eligible for finalization, so finalizers must be robust to finalizing an object that was only partially initialized. BUT WAIT IT GETS WORSE. Jul 27, 2022 at 2:45
  • 1
    It is also possible for a constructor to be aborted, for the constructor to continue running code, AND for the finalizer to start running on another thread WHILE the constructor is still running! There are a great many horrifying ways in which an object may be observed to be in a partially constructed state and it can be quite tricky to make the code robust to all possible situations. Jul 27, 2022 at 2:46
  • 1
    All that said, your more general point that Maybe T and Nullable<T> are morally the same thing is correct. And that Nullable<T> is essentially a monad. It's unfortunately that getting nullability in the type system was originally restricted to value types. Jul 27, 2022 at 2:48
  • 2
    Thanks @EricLippert, you are informative as ever. I can not imagine the kind of contortions one has to do to end up in situations you describe but it seems rather horrid place to be :) I surely hope I never get to debug such race conditions in production… Jul 28, 2022 at 5:50
-3

C++ does it by having access to the initializer that occurs before the constructor body. C# runs the default initializer before the constructor body, it roughly assigns 0 to everything, floats become 0.0, bools become false, references become null, etc. In C++ you can make it run a different initializer to ensure a non-null reference type is never null.

class Foo { Foo(int i) { throw new Exception("Never finishes"); }
class Bar { Bar(string s) { } }

class Broken
{
    val foo: Foo  // where Foo and Bar are non-nullable reference types
    val bar: Bar

    Broken() :
        foo = new Foo(123),// roughly causes a "goto destroy_foo;"
        bar = new Bar("never executes") { }

    // This destructory-function never runs because the constructor never completed
    ~Broken() 
    // This is made-up syntax:
    // : 
    // destroy_bar:
    // bar.~Bar();
    // destroy_foo:
    // foo.~Foo();
    {
    }
}
3
  • 2
    the question was about languages with Maybe types
    – gnat
    May 3, 2014 at 21:02
  • 3
    references become null” – the whole premise of the question is that we don't have null, and the only way to indicate the absence of a value is to use a Maybe type (also known as Option), which AFAIK C++ does not have in the standard library. The absence of nulls allows us to guarantee that a field will always be valid as a property of the type system. This is a stronger guarantee than manually making sure that no code path exists where a variable might still be null.
    – amon
    May 3, 2014 at 21:43
  • While c++ doesn't natively have Maybe types explicitly, things like std::shared_ptr<T> are close enough that I think it's still relevant that c++ handles the case where initialization of variables can happen "out of scope" of the constructor, and is in fact required for reference types (&), since they cannot be null.
    – FryGuy
    May 3, 2014 at 23:14

Not the answer you're looking for? Browse other questions tagged or ask your own question.