Joachim Breitner's Homepage

The Motoko programming language has a built-in data type for optional values, named ?t with values null and ?v (for v : t); this is the equivalent of Haskell’s Maybe, Ocaml’s option or Rust’s Option. In this post, I explain how Motoko represents such optional values (almost) without allocation.

I neither claim nor expect that any of this is novel; I just hope it’s interesting.

Uniform representation

The Motoko programming language, designed by Andreas Rossberg and implemented by a pretty cool team at DFINITY is a high-level language with strict semantics and a strong, structural, equi-recursive type system that compiles down to WebAssembly.

Because the type system supports polymorphism, it represents all values uniformly. Simplified for the purpose of this blog post, they are always pointers into a heap object where the first word of the heap object, the heap tag, contains information about the value:

┌─────┬───┄
│ tag │ …
└─────┴───┄

The tag is something like array, int64, blob, variant, record, …, and it has two purposes:

• The garbage collector uses it to understand what kind of object it is looking at, so that it can move it around and follow pointers therein. Variable size objects such as arrays include the object size in a subsequent word of the heap object.

• Some types have values that may have different shapes on the heap. For example, the ropes used in our text representation can either be a plain blob, or a concatenation node of two blobs. For these types, the tag of the heap object is inspected.

The optional type, naively

The optional type (?t) is another example of such a type: Its values can either be null, or ?v for some value v of type t, and the primitive operations on this type are the two introduction forms, an analysis function, and a projection for non-null values:

null : () -> ?t
some : t -> ?t
is_some : ?t -> bool
project : ?t -> t     // must only be used if is_some holds

It is natural to use the heap tag to distinguish the two kind of values:

• The null value is a simple one-word heap object with just a tag that says that this is null:

  ┌──────┐
  │ null │
  └──────┘

• The other values are represented by a two-word object: The tag some, indicating that it is a ?v, and then the payload, which is the pointer that represents the value v:

  ┌──────┬─────────┐
  │ some │ payload │
  └──────┴─────────┘

With this, the four operations can be implemented as follows:

def null():
  ptr <- alloc(1)
  ptr[0] = NULL_TAG
  return ptr

def some(v):
  ptr <- alloc(2)
  ptr[0] = SOME_TAG
  ptr[1] = v
  return ptr

def is_some(p):
  return p[0] == SOME_TAG

def project(p):
  return p[1]

The problem with this implementation is that null() and some(v) both allocate memory. This is bad if they are used very often, and very liberally, and this is the case in Motoko: For example the iterators used for the for (x in e) construct have type

type Iter<T> = { next : () -> ?T }

and would unavoidably allocate a few words on each iteration. Can we avoid this?

Static values

It is quite simple to avoid this for for null: Just statically create a single null value and use it every time:

static_null = [NULL_TAG]

def null():
  return static_null

This way, at least null() doesn’t allocate. But we gain more: Now every null value is represented by the same pointer, and since the pointer points to static memory, it does not change even with a moving garbage collector, so we can speed up is_some:

def is_some(p):
  return p != static_null

This is not a very surprising change so far, and most compilers out there can and will do at least the static allocation of such singleton constructors.

For example, in Haskell, there is only a single empty list ([]) and a single Nothing value in your program, as you can see in my videos exploring the Haskell heap.

But can we get rid of the allocation in some(v) too?

Unwrapped optional values

If we don’t want to allocate in some(v), what can we do? How about simply

def some(v):
  return v

That does not allocate! But it is also broken. At type ??Int, the values null, ?null and ??null are distinct values, but here this breaks.

Or, more formally, the following laws should hold for our four primitive operations:

1. is_some(null()) = false
2. ∀v. is_some(some(v)) = true
3. ∀p. project(some(p)) = p

But with the new definition of some, we’d get is_some(some(null())) = false. Not good!

But note that we only have a problem if we are wrapping a value that is null or some(v). So maybe take the shortcut only then, and write the following:

def some(v):
  if v == static_null || v[0] == SOME_TAG:
    ptr <- alloc(2)
    ptr[0] = SOME_TAG
    ptr[1] = v
    return ptr
  else:
    return v

The definition of is_some can stay as it is: It is still the case that all null values are represented by static_null. But the some values are now no longer all of the same shape, so we have to change project():

def project(p):
  if p[0] == SOME_TAG:
    return p[1]
  else:
    return p

Now things fall into place: A value ?v can, in many cases, be represented the same way as v, and no allocation is needed. Only when v is null or ?null or ??null or ???null etc. we need to use the some heap object, and thus have to allocate.

In fact, it doesn’t cost much to avoid allocation even for ?null:

static_some_null = [SOME_TAG, static_null]
def some(v):
  if v == static_null:
    return static_some_null
  else if v[0] == SOME_TAG:
    ptr <- alloc(2)
    ptr[0] = SOME_TAG
    ptr[1] = v
    return ptr
  else:
    return v

So unless one nests the ? type two levels deep, there is no allocation whatsoever, and the only cost is a bit more branching in some and project.

That wasn’t hard, but quite rewarding, as one can now use idioms like the iterator shown above with greater ease.

Examples

The following tables shows the representation of various values before and after. Here […] is a pointed-to dynamically allocated heap object, {…} a statically allocated heap object, N = NULL_TAG and S = SOME_TAG.

type	value	before	after
Null	null	{N}	{N}
?Int	null	{N}	{N}
?Int	?23	[S,23]	23
??Int	null	{N}	{N}
??Int	?null	[S,{N}]	{S,{N}}
??Int	??23	[S,[S,23]]	23
???Int	null	{N}	{N}
???Int	?null	[S,{N}]	{S,{N}}
???Int	??null	[S,[S,{N}]]	[S,{S,{N}}]
???Int	???23	[S,[S,[S,23]]]	23

Concluding remarks

• If you know what parametric polymorphism is, and wonder how this encoding can work in a language that has that, note that this representation is on the low-level of the untyped run-time value representation: We don’t need to know the type of v in some(v), merely its heap representation.

• The uniform representation in Motoko is a bit more involved: The pointers are tagged (by subtracting 1) and some scalar values are represented directly in place (shifted left by 1 bit). But this is luckily orthogonal to what I showed here.

• Could Haskell do this for its Maybe type? Not so easily:

  • The Maybe type is not built-in, but rather a standard library-defined algebraic data type. But the compiler could feasibly detect that this is option-like?

  • Haskell is lazy, so at runtime, the type Maybe could be Nothing, or Just v, or, and this is crucial, a yet to be evaluated expression, also called a thunk. And one definitely needs to distinguish between a thunk t :: Maybe a that may evaluate to Nothing, and a value Just t :: Maybe a that definitely is Just, but contains a value, which may be a thunk.

  Something like this may work for a strict Maybe type or unlifted sums like (# (# #) | a #), but may clash with other ticks in GHC, such as pointer tagging.

• As I said above, I don’t expect this to be novel, and I am happy to add references to prior art here.

• Given that a heap object with tag SOME_TAG now always encodes a tower ?ⁿnull for n>0, one could try to optimize that even more by just storing the n:

  ┌──────┬─────┐
  │ some │  n  │
  └──────┴─────┘

  But that seems unadvisable: It is only a win if you have deep towers, which is probably rare. Worse, now the project function would have to return such a heap object with n decremented, so now projection might have to allocate, which goes against the cost model expected by the programmer.

• If you rather want to see code than blog posts, feel free to check out Motoko PR #2115.

• Does this kind of stuff excite you? Motoko is open source, so your contributions may be welcome!