Option and null in dynamic languages

Many dynamic languages have a value denoting absence: None in Python, undefined in Javascript, and nil in Lisp, Clojure, Ruby, and Lua. We can compare this to the null value of reference types in languages like C, Java, or Go. Or, we can compare it to the None value of option types in languages like ML, Haskell, Rust, or Swift. But these two comparisons have very different properties! Nullable references make it easy to write code with non-obvious bugs. Options fix this, by requiring you to check for None before using the value inside.

Which is nil in a dynamic language more akin to? Is nil more like nullable references, or like options? The answer depends on how APIs in your language use nil. In particular, it depends on whether they reliably distinguish success from failure — the essence of option types.

Let’s start with an example.

A simple function

Consider the following specification:

values_in(keys, dict) --> values

Returns a list containing, for each key in `keys', its
associated value in `dict', dropping keys not in `dict'.

Let's implement this in our favorite dynamic languages:

# Ruby
def values_in(keys, dict)
  # find associated values with .map and throw out nils
  # with .compact (nils indicate absent keys)
  keys.map {|k| dict[k]}.compact
end

// Javascript (objects as dicts, strings as keys)
let values_in = (keys, dict) =>
  keys.map(x => dict[x]).filter(x => x !== undefined);

;; Clojure
(defn values-in [keys dict]
  (filter (complement nil?) (map dict keys)))

# Python
def values_in(keys, dict):
    return [dict[x] for x in keys
            if dict.get(x) is not None]

You may notice that this code smells. Can you spot the bug? If dict maps a key in keys to nil/undefined/None, this value will be absent from the list returned by values_in! It will get discarded by compact in Ruby (or by the filter in Javascript and Clojure, or by the if clause in our Python list comprehension). Of course, we can fix this:

def values_in(keys, dict)
  # We filter out keys not in the dictionary first
  keys.select {|x| dict.has_key? x}.map {|x| dict[x]}
end

let values_in = (keys,dict) =>
  keys.filter(x => x in dict).map(x => dict[x]);

(defn values-in [keys dict]
  (map dict (filter #(contains? dict %) keys)))

def values_in(keys, dict):
    return [dict[x] for x in keys if x in dict]

The correct way is to filter out absent keys before we look them up in the dictionary. The tempting-but-wrong way is to look up all the keys and filter out failures (indicated by nil) afterward. But this conflates the absence of a key with the presence of a key which is mapped to nil. We have failed to distinguish success from failure!

Null- and option-like interfaces

But wait! In Python, dictionary lookup dict[key] doesn’t return None (Python’s nil) on failure: it raises a KeyError! Comparing the two Python solutions, the correct one is actually simpler; the wrong one has to carefully avoid an exception using dict.get(key), which returns None on failure.

Dictionary lookup is null-like in Ruby, Javascript, and Clojure, but is option-like in Python.1 Dictionary lookup in Ruby, Javascript, and Clojure does not reliably distinguish between success and failure (unless you know that nil can’t be a value in your dictionary). Python’s dict[key] returns on success, and throws an exception on failure.

(Interestingly, Lua takes a “none of the above” approach. In Lua, it’s impossible to have a dictionary that maps a key to nil: setting a key to nil removes it from the dictionary!)

Options and exceptions

I call Python’s dictionary lookup option-like, but it doesn’t involve anything that looks like an option type in Haskell, ML, Rust, or Swift. Why do I say they’re analogous?

Informally, by “option-like” I just mean “always distinguishes success from failure”. Options do this by having two forms: None, representing failure, and Just x, representing a successful result x. If I look up an absent key, I get None. If I look up a key mapped to v, I get Just v. Even if the key is mapped to None (the equivalent of a key mapped to nil in a dynamic language), I get Just None — which, critically, is not the same as None!

Exceptions accomplish the same goal differently, by altering control flow. Success returns to the function who called us; failure jumps to an enclosing catch. Instead of two forms, we have two continuations.

But there is a formal connection here, too. In a language with exceptions, we can view functions as giving either a successful result (if the function returns), or a value representing failure (if it threw an exception). This is akin to returning an option (more generally, a sum type). The Either monad and the MonadError typeclass in Haskell are manifestations of this connection.

Why care?

One might object: why would you ever store nil in a dictionary anyway? I have two retorts to this, one philosophical and one concrete.

Philosophically, I hate fragile abstractions. Barring typos and other trivialities, in my experience most bugs originate from using a leaky abstraction and not being aware of it. Sometimes it’s hard or impossible to build an abstraction that doesn’t leak (consider any language that lets you allocate memory without checking for OOM conditions); but dictionary lookup is not one of those cases.

Concretely, one case where it’s natural to map a value to nil is reflection. For example, if I’m representing a context mapping symbols to their values, nil is a perfectly reasonable thing to put in a dictionary. You may object that in that context, I should take care to write code that avoids conflating nil with absence. But if I wish to use a library function (some less trivial analog of values_in), I can only hope that its author was as careful as you advise me to be.

Languages and libraries are defined not by what they make possible (the Church-Turing thesis tells us that), but by what they make easy. If a language makes it easy to conflate nil and absence, to write code that does not reliably distinguish between success and failure, then bugs are sure to follow.

Footnotes

  1. Well, mostly. Python’s dict.get is null-like. And Ruby’s Hash#fetch is option-like in its one-argument form.

Appendices

A Does language affect how people write code?

I did a horrendously unscientific study by asking current and former Hacker Schoolers to implement values_in in whichever of {Ruby, Javascript, Clojure, Python} they knew. I hypothesized that most Python solutions would handle None correctly, and most {Ruby, Clojure, Javascript} solutions would not. (Some of you may notice a similarity to the infamous Sapir-Whorf hypothesis.) Most Python solutions were indeed correct. The {Ruby, Clojure, Javascript} solutions were split about evenly between correct and nil-dropping.

However, the sample size was tiny. So scientifically the answer is a resounding “maybe”. (If you really want to know, give me a research grant.)

B Adding options to Python

Suppose we wanted option-like behavior in a dynamic language without throwing exceptions. Is that possible? Yes, it is:

class Just(object):
    def __init__(self, value):
        self.value = value

# Our option-like lookup function
def lookup(dict, key):
    try: return Just(dict[key])
    except KeyError: return None

# How to use it
def values_in(keys, dict):
    return [x.value for k in keys
                    for x in [lookup(dict,k)]
                    if x]

This is more complex than the previously-given correct Python code. However, it does only one lookup per key, rather than two. And there are no standard library functions for working with our new Just type. By contrast, in Haskell we could say:

import Data.Maybe (mapMaybe)
import qualified Data.Map as Map
valuesIn keys dict = mapMaybe (\x -> Map.lookup x dict) keys

C Language comparison

Language dict[key] equivalent For absent key
Python dict[key] raises KeyError
dict.get(key) None
dict.get(key, default) default
Ruby dict[key] nil
dict.fetch(key) raises KeyError
dict.fetch(key, default) default
dict.fetch(key) {|x| block} block(key)
Clojure (get dict key) nil
(get dict key default) default
Javascript dict[key]
(for string keys)
undefined
Lua dict[key] nil
Racket (dict-ref dict key) throws exception
(dict-ref dict key default) default, unless it’s a function
(dict-ref dict key default) (default), if it’s a function
Common
Lisp
(gethash key dict) nil; nil (multiple return values)
(gethash key dict default) default; nil (multiple return values)