Construction by Destruction

We’ve now seen the chan expression in action, using the obtained channel to return early in its process. But that only scratches the surface!

The channel obtained is actually a lot more than a return handle. It’s a dual, a direct access to the consumer of the whole chan expression. It can be interacted with sequentially, constructing a value step-by-step.

The title of this section, “construction by destruction”, is very apt! What we’re about to learn here is exactly analogous to the famous trick in mathematics: a proof by contradiction. And, it’s just as powerful.

Duality in theory

Every type in Par has a dual — the opposite role in communication.

There is a type operator, dual <type>, which transforms a type to its dual. Here’s how it’s defined structurally:

dual either {
  .left A,
  .right B,
}

choice {
  .left => dual A,
  .right => dual B,
}

dual choice {
  .left => A,
  .right => B,
}

either {
  .left dual A,
  .right dual B,
}

Don’t get scared by the F<...> in self-referential types and generics. It’s just a way to formalize that after flipping from recursive to iterative (and similarly in the other cases), we proceed to dualize the body.

Looking at the table, here’s what we can see:

• Units are dual to continuations.
• Functions are dual to pairs.
• Eithers are dual to choices.
• Recursives are dual to iteratives.
• Foralls are dual to existentials.
• The duality always goes both ways!

The last point is important. It’s a fact, in general, that dual dual A is equal to A.

Duality in action

Here’s a familiar definition:

type List<a> = recursive either {
  .end!,
  .item(a) self,
}

So, what’s its dual? Applying the above rules, we get:

iterative choice {
  .end => ?,
  .item(a) => self,
}

While a List<a> provides items, until it reaches the end, its dual requires you to give items (via the .item branch), or signal the end. Whoever is consuming a list, this dual type provides a good way to communicate with them.

Notice the ? in the .end branch. That’s a continuation. There is no expression syntax for this type, but finally, we’re going to learn how to handle it in processes!

Now, let’s remember that in the chan expression, the channel obtained inside its process has the dual type of the overall result of the expression. Let’s use this to construct a list step-by-step.

def SmallList: List<Int> = chan yield {
  yield.item(1)
  yield.item(2)
  yield.item(3)
  yield.end
  yield!
}

// def SmallList = *(1, 2, 3)

This is just a usual handling of an iterative choice, except for the last line.

Selecting the .end branch turns the yield channel into a ?. When a channel has type ?, it means you’re done — nothing more is expected of you, and in fact, nothing more is allowed for you. You have to finish.

The only command available for ? is called break. It’s spelled !, that’s the last line:

  yield!  // break here

Like linking, it has to be the last command in a process. In fact, link and break are the only ways to end a process.

A real example: flattening a list of lists

Let’s now use this style to implement something meaningful. We’ll write a function that flattens a nested list:

dec Flatten : [type a] [List<List<a>>] List<a>

It’s a generic function, using the forall for polymorphism.

Here’s the full implementation, imperative-style:

def Flatten = [type a] [lists] chan yield {
  lists.begin/outer.case {
    .end! => {
      yield.end!
    }

    .item(list) => {
      list.begin/inner.case {
        .end! => {}
        .item(value) => {
          yield.item(value)
          list.loop/inner
        }
      }
      lists.loop/outer
    }
  }
}

It makes a bunch of concepts we’ve already covered come together.

• We loop through the outer list of lists using .begin/outer and .loop/outer.
• If it’s .end!, we finish: yield.end!.
• If it’s .item(list), we then begin looping through the inner list.
  • We don’t manually bind the remainder of the list, the communication simply continues on the original variable: lists.
  • The nested .begin/.loop shines here; no helper functions needed.
• In the inner loop:
  • If it’s .end!, we’re done with that list — we continue the outer loop.
  • If it’s .item(value), we yield it to the consumer with yield.item(value), then loop again. Re-binding of the rest of the list is not needed here, either.

And so we see, duality combined with the chan expressions gives us a lot of expressivity. Constructing lists generator-style is just one of the use-cases. Whenever it feels more appropriate to become a value instead of constructing it out of parts, chan and duality come to the task!