Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Select

Select lets us create a graph node with multiple possible output paths that will choose one path for each value based on a set of conditions. Kind of like,

                     ┌─────────────────────> if foo > 0 => ...
                     │
                     │
ref(foo) ──> select ─┼─────────────────────> if foo < 0 => ...
                     │
                     │
                     └─────────────────────> otherwise => ...

is written as

select foo {
  n if n > 0 => ...,
  n if n < 0 => ...,
  n => ...
}

select takes an expression as an argument and then evaluates one or more “arms”. Each arm consists of an optional type predicate, a destructuring pattern, and an optional guard clause. If the type predicate matches, the pattern matches, and the guard evaluates to true then the arm is “selected”. Only one arm may be selected at a time, the arms are evaluated in lexical order, and first arm to be selected is chosen as the one and only selected arm.

The code on the right side of the selected arm is the only code that is evaluated by select, all other code is “asleep”, it will not be evaluated until it is selected (and if it has netidx subscriptions or published values they will be unsubscribed and unpublished until it is selected again). Sleep is a pause: when the arm is selected again it resumes where it stood. Its counters, onces and queues keep their state, a call it made is not made again, and the only events it sees are the ones that fired while it slept, each once, at its current value. The first time an arm is selected is its birth: its constants fire then, and only then.

Like every other expression, a select updates whenever any of its inputs update: a new value of the argument, a new value read by a guard, or a new value produced by the selected arm’s body all cause the select to produce its current value — even if the same arm stays selected and the value is unchanged. If you want updates only when the value actually changes, wrap the argument (or the whole select) in uniq.

Matching Types

Consider we want to select from a value of type [Array<i64>, i64, null],

let x: [Array<i64>, i64, null] = null;
x <- sys::time::timer(duration:1.s, false) ~ [1, 2, 3, 4, 5];
x <- sys::time::timer(duration:2.s, false) ~ 7;
select x {
  Array<i64> as a => array::fold(a, 0, |s, x| s + x),
  i64 as n => n,
  null as _ => 42
}

This program will print 42, 15, 7 and then wait. The compiler will check that you have handled all the possible cases. If we remove the null case from this select we will get a compile error.

$ graphix test.gx
Error: in file test.gx

Caused by:
    0: at: line: 4, column: 1 in file test.gx, in: select x { Array<i64> as a => array::f..
    1: missing match cases: no arm covers null

The compiler subtracts what each arm matches from the argument’s type, and names what is left when the arms run out: here null, which no arm covers. This goes both ways, a match case that could never match is also an error.

let x: [Array<i64>, i64, null] = null;
x <- sys::time::timer(duration:1.s, false) ~ [1, 2, 3, 4, 5];
x <- sys::time::timer(duration:2.s, false) ~ 7;
select x {
  Array<i64> as a => array::fold(a, 0, |s, x| s + x),
  i64 as n => n,
  f64 as n => cast<i64>(n)?,
  null as _ => 42
}

Here we’ve added an f64 match case, but the argument type can never contain an f64 so we will get a compile error.

$ graphix test.gx
Error: in file test.gx

Caused by:
    0: at: line: 4, column: 1 in file test.gx, in: select x { Array<i64> as a => array::f..
    1: at: line: 7, column: 3 in file test.gx
    2: pattern f64 will never match null, unused match cases

The diagnostic message gives you an insight into the compiler’s thinking. What it is saying is that, by the time it’s gotten to looking at the f64 pattern, the only type left in the argument that hasn’t already been matched is null, and since f64 doesn’t unify with null it is sure this pattern can never match.

Guarded patterns can always not match because of the guard, so they do not subtract from the argument type set. You are required to match without a guard at some point. No analysis is done to determine if your guard covers the entire range of a type.

let x: [Array<i64>, i64, null] = null;
x <- sys::time::timer(duration:1.s, false) ~ [1, 2, 3, 4, 5];
x <- sys::time::timer(duration:2.s, false) ~ 7;
select x {
  Array<i64> as a => array::fold(a, 0, |s, x| s + x),
  i64 as n if n > 10 => n,
  null as _ => 42
}

This will fail with a missing match case because the i64 pattern is guarded and no unguarded pattern exists that matches i64.

$ graphix test.gx
Error: in file test.gx

Caused by:
    0: at: line: 4, column: 1 in file test.gx, in: select x { Array<i64> as a => array::f..
    1: missing match cases: no arm covers i64

This is the same error you would get if you omitted the i64 match case entirely.

Matching Structure

The type predicate is optional in a pattern, and the more commonly used pattern is structural. Graphix supports several kinds of structural matching,

  • array slices
  • tuples
  • structs
  • variants
  • literals, ignore
  • or alternatives

NB: In most contexts you can match the entire value as well as parts of it’s structure by adding a v@ pattern before the pattern. You will see this in many of the examples.

The captured v has the type of what the arm matched in the value being selected, not the type the pattern happens to spell out. A partial struct pattern leaves the other fields readable, and a _ slot keeps its real type:

type Pair = { left: i64, right: i64 };
let p: Pair = { left: 1, right: 2 };
select p { whole@ { left, .. } => left + whole.right }

Over a union, v is the member the arm matched; in an or-pattern, where every alternative captures the same name, it is the union of what they match.

Slice Patterns

Suppose we want to classify arrays that have at least two elements vs arrays that don’t, and we want to return a variant with a triple of the first two elements and the rest of the array or `Short with the whole array.

let a = [1, 2, 3, 4];
a <- [1];
a <- [5, 6];
select a {
  [x, y, tl..] => `Ok((x, y, tl)),
  a => `Short(a)
}

This program will print,

$ graphix test.gx
`Ok((1, 2, [3, 4]))
`Short([1])
`Ok((5, 6, []))

The following kinds of slice patterns are supported,

  • whole slice, with binds, or literals, e.g. [1, x, 2, y] matches a 4 element array and binds it’s 2nd and 4th element to x and y respectively.

  • head pattern, like the above program, e.g. [(x, y), ..] matches the first pair in an array of pairs and ignores the rest of the array, binding the pair elements to x and y. You can also name the remainder, as we saw, e.g. [(x, y), tl..] does the same thing, but binds the rest of the array to tl

  • tail pattern, just like the head pattern, but for the end of the array. e.g. [hd.., {foo, bar}] matches the last element of an array of structs with fields foo and bar, binding hd to the array minus the last element, and foo to field foo and bar to field bar.

Structure patterns (all of the different types) can be nested to any depth.

Slice patterns count toward exhaustiveness by LENGTH: a set of unguarded slice arms whose element patterns are all binds or _ covers the array when their lengths cover every possible length — which needs a head or tail (rest) pattern for the unbounded lengths, plus an exact-length arm for each length below the rest pattern’s minimum. So this select is exhaustive with no wildcard arm:

select a {
  [] => `Empty,
  [x, tl..] => `Cons(x, tl)
}

An arm carrying a guard, or an element pattern that can refute (a literal, a variant, a nested slice), only matches SOME arrays of its length, so it claims no coverage — the error says so when that is why a select falls short. Note also that a slice arm covers only arrays of its own inferred (or written) element type: if the scrutinee is a union of differently-typed arrays, each array member needs the whole length ladder to check out against every slice arm’s type.

Dead-arm checking is length-precise in the same way: an arm whose every matchable length is already matched by earlier covering slice arms can never run and is refused — [init.., y] after [x, tl..] is dead (both match every non-empty array), and a _ behind a complete ladder like the one above is dead exactly as it would be behind a full variant set. Order exact-length arms above the rest arm that subsumes them.

List Patterns

Lists (see Fundamental Types) have their own slice-like patterns, written with the list literal’s delimiters. [<>] matches the empty list, [<a, b>] matches a list of exactly two elements, and [<h, rest..>] matches any non-empty list, binding h to the first element and rest to everything after it. Binding the rest is O(1) and copies nothing — the bound tail is the matched list’s tail, memory shared — which is what makes a recursive walk over a list linear:

let rec sum = |l: List<i64>, acc: i64| -> i64 select l {
  [<>] => acc,
  [<x, rest..>] => sum(rest, acc + x)
};
sum([<1, 2, 3, 4>], 0)

$ graphix test.gx
10

There is no suffix form: [<init.., x>] is refused. Reaching the last element of a singly linked list means walking the whole spine, so the pattern that would hide an O(n) walk does not exist — convert to an array if you need to work from the back. (Arrays keep both forms because their slices are zero-copy views, so [x, rest..] and [init.., x] are both O(1) there.)

Exhaustiveness and dead-arm checking work by length exactly as for slice patterns: [<>] plus [<h, rest..>] covers every list, an exact-length arm above a rest arm claims its length, and a guard or a refutable element pattern claims no coverage.

Tuple Patterns

Tuple patterns allow you to match tuples. Compared to slice patterns they are fairly simple. You must specify every field of the tuple, you can choose to bind it, or ignore it with _. e.g.

("I", "am", "a", "happy", "tuple", w, _, "patterns")

Struct Patterns

Struct patterns, like tuple patterns, are pretty simple.

  • { x, y } if you like the field names then there is no need to change them
  • { x: x_coord, y: y_coord } but if you need to use a different name you can
  • { x, .. } you don’t have to write every field

Consider

let a = {x: 54, y: 23};
a <- {x: 21, y: 88};
a <- {x: 5, y: 42};
a <- {x: 23, y: 32};
select a {
  {x, y: _} if (x < 10) || (x > 50) => `VWall,
  {y, x: _} if (y < 10) || (y > 40)  => `HWall,
  {x, y} => `Ok(x, y)
}

does some 2d bounds checking, and will output

$ graphix test.gx
`VWall
`HWall
`VWall
`Ok(23, 32)

You can replace y: _ with .. — a partial pattern names only the fields it needs, and the type checker completes the rest from the scrutinee’s type:

let a = {x: 54, y: 23};
a <- {x: 21, y: 88};
a <- {x: 5, y: 42};
a <- {x: 23, y: 32};
select a {
  {x, ..} if (x < 10) || (x > 50) => `VWall,
  {y, ..} if (y < 10) || (y > 40)  => `HWall,
  {x, y} => `Ok(x, y)
}

$ graphix test.gx
`VWall
`HWall
`VWall
`Ok(23, 32)

This works at any nesting depth — a partial pattern inside a variant payload (`Event({id, ..})) completes against that payload’s type. The one case that still needs help is when SEVERAL struct members that reach the arm carry all the named fields (a member an earlier arm already matched does not count): the pattern is ambiguous, and the compiler asks you to annotate the member you mean:

S as {x, ..} if (x < 10) || (x > 50) => `VWall

Any type in scope (or an inline structural type, {x: i64, y: i64} as {x, ..}) works as the annotation.

Variant Patterns

Variant patterns match variants. Consider,

let v: [`Bare, `Arg(i64), `MoreArg(string, i64)] = `Bare;
v <- `Arg(42);
v <- `MoreArg("hello world", 42);
select v {
  `Bare => "it's bare, no argument",
  `Arg(i) => "it has an arg [i]",
  x@ `MoreArg(s, n) => "it's big [x] with args \"[s]\" and [n]"
}

produces

$ graphix test.gx
"it's bare, no argument"
"it has an arg 42"
"it's big `MoreArg(\"hello world\", 42) with args \"hello world\" and 42"

Variant patterns enforce the same kinds of match case checking as all the other pattern types

let v: [`Bare, `Arg(i64), `MoreArg(string, i64)] = `Bare;
v <- `Arg(42);
v <- `MoreArg("hello world", 42);
select v {
  `Bare => "it's bare, no argument",
  `Arg(i) => "it has an arg [i]",
  x@ `MoreArg(s, n) => "it's big [x] with args \"[s]\" and [n]",
  `Wrong => "this won't compile"
}

yields

$ graphix test.gx
Error: in file test.gx

Caused by:
    0: at: line: 4, column: 1 in file test.gx, in: select v { `Bare => "it's bare, no arg..
    1: at: line: 8, column: 3 in file test.gx
    2: unreachable arm: the earlier arms already cover the whole scrutinee, unused match cases

Literals, Ignore

You can match literals as well as bind variables, as you may have noticed, and the special pattern _ means match anything and don’t bind it to a variable.

Or Patterns

An arm can match several alternative patterns, separated by |. Alternatives are tried left to right, and the first one that matches structurally selects the arm and delivers its bindings.

select (0, 5) {
    (0, y) | (y, 0) => y,
    _ => -1
}

$ graphix or.gx
5

The rules are the orthodox ones:

  • Same binds. Every alternative must bind exactly the same names, and a name’s type is the union of its types in the alternatives: `A(n) | `B(n) over [`A(i64), `B(string)] binds n: [i64, string]. (0, y) | (y, 0) is fine over (i64, i64); 1 | x is refused (the second alternative binds x, the first binds nothing).
  • One guard per arm. A guard written after the alternation covers the whole arm: (0, y) | (y, 0) if y > 3 => y.
  • No dead alternatives. An alternative that can never match — a duplicate of an earlier one, anything after an alternative that matches everything, or one whose type can’t match what’s left of the scrutinee — is an error, just like a dead arm.

Alternatives nest anywhere a sub-pattern can appear: `A(1 | 2) matches `A carrying 1 or 2. Coverage counts each alternative separately, so an arm’s alternatives can complete a set of variants or a slice length ladder — [] | [_, ..] covers every array length with no wildcard.

Top-level or-patterns belong to select arms only: let bindings and lambda parameters refuse them (a lambda’s argument list is itself delimited by |, and those positions are irrefutable anyway — an or-pattern there could never be useful).

There is no x@ (p1 | p2) — patterns have no grouping parentheses. A capture is per-alternative, and the same-binds rule keeps it symmetric: t@ D(_) | t@ E(_) => f(t).

Arms That Never Fire

never() is a value that never arrives. It is the natural body of an arm that has nothing to say: the arm is selected, the select produces nothing, and nothing downstream updates until the scrutinee moves on. It takes any number of arguments, all of which stay live and are consumed, so never(x) keeps x running without producing it.

The type of a bare never() is bottom, which every type absorbs: a select whose other arms are all string is itself a string, however deeply the never() arms nest.

let admins = select load {
  `Roster => list_admins(target),
  _ => never()
};

A let whose initializer is a bare never() takes its type from whatever writes it, so let res = never(); res <- s types res as s does. Where nothing fixes the type — a field, an argument, a binding nothing writes — spell it: never<T>() types as T.

let pick = never<[`Servers, `Clusters]>();

A struct literal with a never<i64>() field is a struct that never materializes, since a struct fires once every field has arrived; that is the right behaviour for a placeholder something else must write.

Select and Connect

Using select and connect together is one way to iterate in Graphix. Consider,

let a = [1, 2, 3, 4, 5];
let len = 0;
select a {
  [x, tl..] => {
    len <- len + 1;
    a <- tl
  },
  _ => len
}

produces

$ graphix test.gx
5

This is not normally how we would get the length of an array in Graphix, or even how we would do something with every element of an array (see array::map and array::fold), however it illustrates the power of select and connect together.

Writing From an Arm

A connect inside an arm is an ordinary node of that arm: it fires when its right-hand side fires. Sample the event when the write should run on every delivery into the arm. A constant right-hand side fires when the constant does, at the arm’s first entry and never again, so the check warns of it; the same goes for a call with an effect whose arguments are all constants, and a seq with no trigger.

select k.code {
  kk@ `Up => sel <- kk ~ (sel - 1),
  kk@ `Down => sel <- kk ~ (sel + 1),
  kk@ `Enter => screen <- kk ~ `Pick,
  _ => never()
}

e ~! v is the strict sample: v at each fire of e, and bottom with no bank when v is bottom. ~ still banks.