Fuzion Choice Type

Motivation

In many situations, data can have one of several forms. Imagine we want to define the data type for a binary tree that stores 32-bit integer values in its leafs. Such a tree can be either the empty tree,

empty is

or it can be a single leaf containing a 32-bit integer value,

i32

or it could be a reference to a node with a left and a right sub-tree.

Node(l, r Tree) ref is

For the definition of a Tree, fuzion provides choice types:

Tree : choice empty i32 Node is

Options

Often, data of a specific type can either be present or absent. For example, a function that looks up data the corresponds to a person of a given name, could return this data if a person with that name was found, or return nothing otherwise.

In many languages, returning nothing is indicated by a special value such as null. However, this results in countless programming errors since it is not explicit that a given value is optional.

Languages like Rust use an Option enum that provides a choice between Some(v) and None. Fuzion provides a similar choice type, but avoids the need to additionally wrap a value as done in Some(v):

option(T type) : choice T nil is

Switch statement syntax

In Rust, unwrapping an enum into its actual values is done with the match expression as follows:

fn size(tree: Tree) -> i32 {
    match tree {
        Empty     => 0,
        Leaf(i)   => i,
        Node(l,r) => sum(l) + sum(r),
    }
}

In Fuzion, the different values a choice type could take are feature types already, there is no need to unwrap them. A decision to make is whether new identifiers should be introduced for the specific types, e.g., with new identifiers l and n

sum(t Tree) i32 =>
  match t
    empty Empty => 0
    l i32 => l
    n Node => (sum n.l) + (sum n.r)

or without new identifiers, but with a re-interpretation of t's static type to match the actual case

sum(t Tree) i32 =>
  match t
    empty Empty => 0
    i32 => t
    Node => (sum t.l) + (sum t.r)

Using an extension of the undeservedly disliked ternary ? | operator, we can achieve a very concise syntax

sum(t Tree) i32 =>
  t ? empty Empty => 0
    | i32 => t
    | Node => (sum t.l) + (sum t.r)

Using , instead of :, the syntax would be closer to that of a match expression

sum(t Tree) i32 =>
  t ? empty Empty => 0,
      i32 => t,
      Node => (sum t.l) + (sum t.r)

Feature declarations in a choice declaration

For operations that work on a choice value, it might make sense to declare corresponding features directly locally within the choice declaration, such as

Tree : choice empty i32 Node is
  size i32 =>
    Tree.this ? empty  => 0
              | i32    => 1
              | n Node => n.l.size + n.r.size

Choice as a specific feature

One way to think about a choice is as of a generic class with an open list of generic parameters T1, t2, etc. and, conceptually, one field for each generic type, i.e.,

choice T1, T2, ... is
  private value1 T1
  private value2 T2
  [..]

together with some logic that ensures that exactly one of the fields value1, value2, etc. is set and accessible. Another way to look at this is like a union type in C, but equipped with type safety that ensures that only the valid value can be accessed.

Then, the definition of a concrete choice becomes a feature that inherits from choice:

Tree : choice empty i32 Node is
  size i32 =>
    Tree.this ? empty  => 0
              | i32    => 1
              | n Node => n.l.size + n.r.size

Note that Tree.this refers to the value of the feature surrounding size, the value of Tree. This would even allow choices to be extensible, e.g. to define an US traffic light

red is
yellow is
green is

traffic_light : choice red yellow green is

European traffic lights typically show red and yellow together before they turn green, so we need an additional state, which can be done as follows

red_and_yellow is

european_traffic_light : choice traffic_light red_and_yellow is

Using the specific feature choice with generic parameters, the Option choice defined above would look as follows:

option(T type): choice T none is
  is_present bool =>
    option.this ? T    => true
                | None => false

or, using a new operator "choice ? type" that is true iff the given choice value at runtime is the given type (which is a bit like Java's instanceof operation).

option(T type): choice T none is
  is_present bool =>
    option.this ? T

Algebraic data types

As we have seen in the section Fuzion Features, features can be used to declare product types. To implement algebraic data types, the choice types provides the missing composite data type.