Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
    
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 at 23:01
1  
@panzi: Ceylon uses flow-sensitive typing to distinguish between Type? (maybe) and Type (not null) –  Lukas Eder May 4 at 5:44
1  
@RobertHarvey Isn't there a "nice question" button in Stack Exchange already? –  immibis May 4 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. –  delnan May 4 at 14:24
    
@immibis: I already pushed it. We get precious few good questions here; I thought this one deserved a comment. –  Robert Harvey May 4 at 20:45

5 Answers 5

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.

share|improve this answer
    
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 at 19:03

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.

share|improve this answer

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

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

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).

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 multiple, ordered 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, 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 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.

TL;DR

This example illustrates exactly how different Haskell is from C#. Instead of delegating the logistics of structure construction to the value constructor, it must be handled in the surrounding code. There is no way for a Nothing value to crop up where we are expecting a NotSoBroken because Nothing has type of Maybe NotSoBroken, which is not interchangeable with NotSoBroken. In order to use the NotSoBroken values that are wrapped inside of our nullable type (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 Just (non-null) value.

Therefore:

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

Yes. This would be comparable to finding a String in an Int: the types simply wouldn't match up.

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

Not an issue: the value constructor can't do anything but take the values it's given and put them together.

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.

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.

share|improve this answer

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() );
share|improve this answer
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 at 9:02
    
@gnat: what do you mean by "In Java for example, initialization of (non-final) field in constructor is not protected from data race". Unless you do something spectacularly complex involving multiple threads, the chances of race conditions inside a constructor are (or should be) near impossible. You can not access a field of an unconstructed object except from within the object constructor. And if the construction fails, you do not have a reference to the object. –  Roland Tepp May 8 at 9:08
    
The big difference between null as implicit member of every type and Maybe<T> is that will with Maybe<T>, you can also have just T, which doesn't have any default value. –  svick May 13 at 19:09
    
When creating arrays, it will frequently not be possible to determine useful values to for all elements without having to read some, nor will it be possible to statically verify that no element is read without a useful value has been computed for it. The best one can do is initialize array elements in such fashion that they can be recognized as unusable. –  supercat yesterday
    
@svick: In C# (which was the language in question by the OP), null is not an implicit member of every type. For null to be lebal value, you need to define the type to be nullable explicitly, which makes a T? (syntax sugar for Nullable<T>) essentially equivalent to Maybe<T>. –  Roland Tepp yesterday

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();
    {
    }
}
share|improve this answer
2  
the question was about languages with Maybe types –  gnat May 3 at 21:02
2  
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 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 at 23:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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